Udało mi się zbudować kolejny kod faktoryzacji, w którym lokalizuję i sprawdzam przeniesienia występujące podczas konwersji na coraz większe podstawy. Dla małych wartości ma narzut obliczeniowy, który jednak jest kompensowany dla liczb kilkunastocyfrowych. Liczba, którą innym przeglądem zupełnym rozkładałem (i zatrzymywałem po kilkunastu godzinach gdy podstawa systemów przekroczyła milion), tą wersją uległa rozłożeniu na czynniki w 2h 13 minut.
Program nie ma już pętli wykonującej się (sqrt N) /2 razy, przeskakuje część iteracji, gdy wiadomo, że nie ma przeniesienia podczas konwersji, a zatem nie ma kandydata na dzielnik. Ile razy wykona się pętla? Nie wiem. Są obszary, kiedy w sekundy obrabia setki tysięcy podstaw w sekundę (liczba 16-cyfrowa), a są inne, w którym przeniesienia podczas konwersji są co kolejną podstawę.
Kiedy zażyczyłem sobie, żeby program starał się jednak zwiększać podstawę o co najmniej 2, mógł przeskoczyć dzielnik, ale kiedy dołączyłem warunek parzystości podstawy, ta sama liczba co wspomniana już została rozłożona na czynniki w godzinę 8 minut... Prawie 50 procent szybciej.
Podaję kod 'jak powstał', w którym conversion1(n,p) polega na przedstawieniu liczby w systemie o podstawie p, zaś dalej(...,p,k) to konwersja na system p+k bez wykonania przeniesień ([a,b,c] => [a, b-2k*a, c-k*b+k*k*a]), by je lokalizować w tym przedziale. Na podstawie tych postaci przekształconej liczby dobieramy skok k. Można go jeszcze usprawnić...
def factorize(n):
divisors = []
while 0==n%2:
divisors.append(2)
n/=2
p=p1=3
a1,b1,c1 = conversion1(n,3)
k=2
a=0 #,b1,c1,p1 = conversion(a,b,c,p,k)
while a1!=a:
a,b,c,p = a1,b1,c1,p1
if 0==c:
if 0==n%p1:
divisors.append(p1)
n/=p1
a1,b1,c1 = conversion1(n,p1)
continue
c = n%p1
b = ((n-c)/p)%p
a = (n-b*p*a)/(p*p)
p1 = p+k
a1,b1,c1 = conversion1(n,p1)
#print "[",a,",",b,",",c,"]_",p," ",
print "[",a1,",",b1,",",c1,"]_",p1
print "dalej teraz a maleje do 1"
print "[",a1,",",b1,",",c1,"]_",p1," druga czesc"
if b1<a1:
a1-=1
b1+=p1
while 0<a1: #szukanie binarne k
k3 = b1/a1/2
k1,k2 = 0,k3
a3,b3,c3,p3 = a1,b1,c1,p1
a,b,c,p = a1,b1,c1,p1
while k1<k2-1:
k = k1+(k2-k1)/2
a,b,c,p = dalej(a1,b1,c1,p1,k)
p3 = p1+k
a3,b3,c3 = conversion1(n,p3)
#print "[",a,",",b,",",c,"]_",p," ",k1,k,k2," ",
#print "[",a3,",",b3,",",c3,"]_",p3," "
if b3>a3 and 0<c:
k1=k
else:
k2=k
print "[",a1,",",b1,",",c1,"]_",p1," ",
print "[",a,",",b,",",c,"]_",p," ",k1,k,k2," ",
print "[",a3,",",b3,",",c3,"]_",p3," "
if b3<a3:
a1,b1,c1,p1 = a3-1,b3+p3,c3,p3
else:
if 2>k and 1==p1%2:
k=2
p1 = p1+k
a1,b1,c1 = conversion1(n,p1)
print "po [",a1,",",b1,",",c1,"]_",p1
if 0==c1:
while 0==n%p1:
divisors.append(p1)
n/=p1
a1,b1,c1 = conversion1(n,p1)
if 1<n:
divisors.append(n)
return divisors
