Индекс вне диапазона ошибок при поиске B-гладких чисел с логарифмами - PullRequest
Новая
       53

Индекс вне диапазона ошибок при поиске B-гладких чисел с логарифмами

1 голос
/ 13 января 2020

Итак, я пытался реализовать квадратичное c сито, и я сделал шаг 1, который (в коде): 

f = 44
b = ceil(sqrt(n))
factorBase = [i for i in genPrimes(f) if jacobi(n, i) == 1]
t = [modInverse(n, p) for p in factorBase]
sol1 = [(t[i] - b) % factorBase[i] for i in range(len(t))]
sol2 = [(-t[i] - b) % factorBase[i] for i in range(len(t))]
l = [ln(p) for p in factorBase]
size = 60

Здесь genPrimes () - это Сито Эратосфена, Якоби проверяет, если n является квадратичным c остаток mod i, а modInverse является алгоритмом Тонелли-Шенкса.

Следующий шаг в квадратичном c сите следующий: 

Initialize a sieve array to 0's. For each odd prime p in the factor
base, add l[p] to the locations sol1[p] + ip and soln[p] + ip of the sieve array, for
i = 0, 1, 2,... For the prime p = 2, sieve only with sol1.

Или как описано здесь: 

Then I have to add values from ?? to sieving array to positions ???1[?]+?∗factor_base[j] and 
???1[?]+?∗ factor_base[j], where 0≤?≤ size and 0≤?≤|factor_base|. And for prime ?=2 add ?? only to 
positions with sol1.

Теперь скажите, что это были мои списки: 

sieveArray = [0 for i in range(60)]
factorBase = [2,3,7,17,23,29,37,41]
sol1  = [0,0,2,13,11,26,10,28]
sol2 = [0,1,5,14,8,10,17,26]
l = [0.69,1.1,1.95,2.83,3.14,3.37,3.61,3.71] # logs of factorbase rounded to 2 decimals

Я должен, следуя вышеизложенному, получить этот новый список: 

sieveArray = [1.79,1.1,2.64,1.1,1.79,1.95,1.79,1.1,3.83,3.05,8.77,3.14,3.74,3.93,3.52,1.1,3.74,3.61,1.79,3.0
5,0.69,1.1,1.79,1.95,1.79,1.1,9.72,1.1,5.5,0.0,6.57,7.07,0.69,3.05,4.93,0.0,1.79,3.05,0.69,4.47
,3.74,0.0,1.79,1.1,2.64,1.1,1.79,8.39,4.62,1.1,0.69,3.05,1.79,0.0,10.49,4.47,0.69,4.24,3.74,0.0]

Однако всякий раз, когда я попытаться запрограммировать, я испортил ужасно и индексировать вне диапазона ошибок. Вот мой ошибочный код: 

for j in factorBase:
    if j != 2:
        for i in range(0, size):
            try: 
                sieveArray[sol1[j] + (i * factorBase[j])] += l[j]
                sieveArray[sol2[j] + (i * factorBase[j])] += l[j]
            except:
                continue
#Didn't implement case for 2 since I didn't know what I was doing.

Может кто-нибудь объяснить мне, что я делаю неправильно и как я могу получить ожидаемые результаты. Также Если вы хотите получить фактическое объяснение того, что это шаг, от go до https://pdfs.semanticscholar.org/5c52/8a975c1405bd35c65993abf5a4edb667c1db.pdf стр. 6 (алгоритм qs), шаг 2 или https://math.stackexchange.com/questions/183183/quadratic-sieve-algorithm?rq=1. Ошибка при отсутствии операторов try-кроме: 

sieveArray[sol1[j] + (i * factorBase[j])] += j
    IndexError: list index out of range

Примечание. Ошибка отсутствия индекса вне диапазона из-за попытки исключения, но код по-прежнему не работает должным образом.

...