Проблема внедрения колес в решето Эратосфена

Я немного борюсь с дальнейшей оптимизацией моей основной вычислительной функции.

Пока что я остановился на решете Эратосфена.

Я нашел на https://primesieve.org/ подсказку для дальнейшей оптимизации с реализацией колес и ссылкой к этой статье: ftp://ftp.cs.wisc.edu/ паб/techreports/1991/TR1028.pdf

Я пытался перевести этот псевдокод на python, но он не работает должным образом. У меня такое ощущение, что итерации на шаге B неверны. При вычислении prime_sieve_fast(100, 3) 91 не удаляется. Это логично, поскольку текущие переменные никогда не достигают 7*13 или 13*7. Что я сделал не так?

def prime_sieve(n):
    prime_list=[0,0]
    for i in range(2,n+1):
        prime_list.append(1)
    for p in range(2,int(n**(1/2))+1):
        for j in range(p**2,n+1,p):
            prime_list[j]=0
    primenumbers=[]
    for i in range(n):
        if prime_list[i+1]==1:
            primenumbers.append(i+1)
    return prime_list,primenumbers    

def prime_sieve_faster(n,n_wheel):
    primes=prime_sieve(100)[1][:n_wheel+1]
    w=wheel(n_wheel,primes[:-1])
    M=len(w)
    prime_list=[1]*(n+1)
    for r in range(M):
        if w[r%M]==0:
            b=0
        else:
            b=1
        for i in range(r,n+1,M):
            prime_list[i]=b
    for i in range(n_wheel):
        prime_list[primes[i]]=1
    prime_list[1]=0
    for p in range(primes[n_wheel],int(n**(1/2))+1):
        print(p)
        step=w[p%M]
        if step==0:
            prime_list[p]=0
        else:
            for f in range(p,p+M+1,step):
                for x in range(p*f,n+1,M*p):
                    prime_list[x]=0
                    print(p,f,x,M*p)
    primenumbers=[]
    for i in range(n):
        if prime_list[i+1]==1:
            primenumbers.append(i+1)
    return prime_list,primenumbers


def wheel(k,primes):
    M=1
    for prime in primes:
        M*=prime
    W=[1]*M
    for prime in primes:
        for x in range(0,M,prime):
            W[x]=0
    W[M-1]=2
    prev=M-1
    for x in range (M-2,0,-1):
        if W[x]!=0:
            W[x]=prev-x
            prev=x
    return W

person FordPrefect    schedule 29.10.2018    source источник
comment
Пожалуйста, проверьте свои отступы в сообщении и при необходимости исправьте, это трудно прочитать и не будет работать как есть.   -  person G. Anderson    schedule 29.10.2018
comment
Сорри, поправил. Это был мой первый пост здесь, и блоки кода на самом деле не подходят для копирования и вставки, как мне пришлось выяснить. Редактировать: по-видимому, в коде есть ненужные функции print(), которые я поместил туда для анализа. Если цифры становятся большими, их следует прокомментировать.   -  person FordPrefect    schedule 29.10.2018
comment
Функция normal_sieve в этом коде была лучшим фильтром Я мог бы придумать. Он не использует колеса, но вы можете взглянуть.   -  person mikeLundquist    schedule 29.10.2018
comment
Я посмотрю на это. Однако я действительно хочу понять, почему моя реализация кода в этой статье не работает. Я наткнулся на этот материал, борясь с проблемой Эйлера проекта 501, я уже понял, что мне нужно найти хорошую реализацию pi (x), а не подсчитывать множество простых чисел, находя их. Но так как я потратил так много времени на понимание различных простых сит и на их реализацию, я действительно хочу знать, что здесь не так. Руль работает исправно. Также первая половина Prime_sieve_fast работает правильно.   -  person FordPrefect    schedule 29.10.2018
comment
Список только с единицами для спиц настроен правильно, только последующее просеивание не работает должным образом из-за неправильной реализации границ или из-за того, что я пропускаю какое-то неупомянутое ограничение в документе.   -  person FordPrefect    schedule 29.10.2018
comment
Я использую колеса здесь, но это неопределенное сито. посмотрите, поможет ли это как-то....   -  person Will Ness    schedule 29.10.2018
comment
Спасибо за ссылку. Но я думаю, что вы используете совсем другую попытку, чем в статье. Так что дело не столько в том, чтобы получить алгоритм самого быстрого генератора простых чисел на питоне. Я больше хочу понять, где я не правильно понял инструкции из этой бумаги. Меня это очень беспокоит. Кстати: @user4757074 из любопытства я попробовал ваш код. Но первая функция не работает, потому что индекс во внутреннем ядре становится больше, чем длина массива. Из второго я попробовал идею использования битового массива, но на самом деле это занимает в два раза больше времени, чем у меня.   -  person FordPrefect    schedule 29.10.2018
comment
Я хочу сказать, что вы должны начать с упрощения кода. Например, выполнение for i in range(2,n+1):prime_list.append(1) приводит к тому же результату, что и prime_list += range(2,n+1). Вы можете использовать линтер PEP8, чтобы многое сделать за вас. normal_sieve было самым простым и быстрым решетом, которое я смог найти. В реальном коде C вы будете использовать битовый массив. Но опять же, битовый массив не имеет значения. Дело в УПРОЩЕНИИ. И да, не смотрите на sieve в этом коде, просто на normal_sieve.   -  person mikeLundquist    schedule 30.10.2018
comment
я думаю, вы имеете в виду prime_list=[0,0]+[1]*(n-1). То, что вы написали, не совпадает. На самом деле это на небольшой процент быстрее. Но я предполагаю, что улучшения правильной интеграции колеса на порядки быстрее.   -  person FordPrefect    schedule 30.10.2018
comment
ускорение колеса составляет PROD( p/(p-1) ) по всем p с в wheel. с wheel = {3,5,7,11} это 2,4x, а с 13 это 2,6x. Итак, не даже на один порядок. Простое число 2 дает 2x ускорение само по себе, поэтому технически это примерно 5x ускорение в целом, но так легко пропускать четные числа, что я бы сказал, что это не так. считать. И эти ускорения являются теоретическими — использование пространства возрастает настолько, что работа с механикой колес быстро перевешивает ожидаемые выгоды. Я получил ускорение 2,2x с 3,5,7 и остался доволен. :)   -  person Will Ness    schedule 30.10.2018