Tym razem, po długiej przerwie, kolejny algorytm 'trial division' na rozkład liczby N na czynniki. Jak moje najnowsze podejścia, znów jest prosty dla bardzo dużych wartości, zaś daje w kość dla małych dzielników.
Przedstawiam liczbę N w postaci iloczynu dwu wartości p, q i reszty r:
N = p*q + r,
gdzie p>q są liczbami nieparzystymi, r jest liczbą nieujemną, zmniejszaną by nie przekraczała podwojonego q.
Podstawowym przekształceniem jest
(p+k)*(q-k) = pq + k(q-p) - k^2 (1) ,
albo w używanej postaci szczególnej
(p+2)*(q-2) = pq - 2(p-q) - 4 (2) .
Inicjacja następuje dla nieparzystych p = q < sqrt(N) lub p < sqrt N < q = p+2 gdy sqrt N jest parzyste. Liczba
r = N - pq
jest parzysta.
W kolejnych iteracjach wykorzystujemy stary iloczyn pq by dostać nowe r następująco:
p = p+2;
q = q-2;
s = r + 2(p-q) + 4;
r = s (mod 2q); // s można zapamiętać by mniej liczyć
p = p+ floor( s/ 2q );
jeśli r =0, dzielnikami są p i q.
niezmienniki: p, q nieparzyste, z r zabierana parzysta wielokrotność q, która jest dodawana do p.
W ten sposób p rośnie wykładniczo, zwłaszcza dla małych q, q maleje liniowo. Zmiany są bardzo małe, zwłaszcza dla q mniejszych niż pierwiastek sześcienny z 2N. Z kolei dla q mniejszych efekt wykładniczy modyfikuje p bardzo silnie.
W praktyce przeważająca krotność przypadków przypada na małe zmiany.
Do tego stopnia zmiany są małe, że dla dużych q możemy korzystać ze cech podzielności dla q i korzystając z (1) przeskakiwać nie po kolejnych nieparzystych, ale wybierać te, które nie mają dzielników 3, 5. Podobna zakusa istnieje też dla p, ale tylko dla tak dużych wartości, by p/q <2.
Przykład: fragment
sqrt 8934053 jest bliskie 2988
p = 2989, q = 2987, r = 5910
różnica 2(p-q)+4 = 8, zatem
p = 2991, q = 2985, r = 5918
jeszcze dwa razy i mamy
p = 2997, q = 2979, r = 5990 = 2*2979+32,
za duże r, dochodzi do głosu dzielenie r/ 2q , zatem uzyskujemy zwiększenie p:
p = 2999, q = 2979, r = 32
przy kolejnym zmniejszaniu q przenoszenia do p występują coraz częściej, aż od
p = 4169+2, q = 2141, r = 2*2141+3942
stają się powszechne
dochodzimy w pobliże dzielnika,
p = 8189+14 = 8203, q = 1089, r = 14*1089+986
p = 8205+14 = 8219, q = 1087, r = 14*1087
p = 8221+12 = 8233, q = 1085, r = 12*1085+1248
poczynając od wartości
p = 33971+258, q = 261, r = 258*261+284
lepiej zmienić algorytm. Tu już q jest stosunkowo bardzo małe względem p.
11 listopada 2016
27 czerwca 2016
Czy istnieje logarytmiczny sposób rozkładu liczb
Czy istnieje sposób rozkładu liczb, w którym kolejne obliczenia wyznaczają kolejne cyfry dzielników?
Wydaje się to niemożliwe dzięki przeniesieniom.
Lecz testuję pewien sposób dzielenia, który w dziesiątkowym działa w znikomej krotności przypadków, i on jest w stanie to ominąć.
Według jednego z pomysłów należałoby zbadać wykładniczą liczność przypadków dopasowania cyfr. Badane dzielenie wyłuskuje prostą zależność między cyframi dzielników, które ogranicza tę liczność. Dodatkowy test wyznacza konkretne cyfry, zwłaszcza kiedy w trakcie przebiegu zostanie złamana symetria.
Występuje nieoznaczoność, gdyż teoretycznie dostaję 2 wartości dla liczb pierwszych, co najmniej 4 dla złożonych. Są one symetryczne, i ta symetria nie pozwala przewidywać dokładnie. Jednak większość przypadków po złamaniu symetrii jestem w stanie wyznaczać jednoznacznie. Łamanie symetrii następuje tuż po pierwszym wystąpieniu pary różnych cyfr.
Dla wygody rachuję w binarnym. Wtedy dzielenie zwraca wielomian postaci np.
a+b+[0]^*+[1]^* = 1
z dwoma niewiadomymi. Zapis [0]^* oznacza, że dodawane jest kilka zer, ale nie muszą wystąpić. Po uproszczeniu mamy a+b=1 lub a+b=0, gdzie a i b są cyframi binarnymi, dopisywanymi do kandydatów na dzielniki.
Drugi z testów jest związany z parzystością różnicy liczby rozkładanej i iloczynu cząstkowego znajdowanych kandydatów na dzielniki.
Wydaje się to niemożliwe dzięki przeniesieniom.
Lecz testuję pewien sposób dzielenia, który w dziesiątkowym działa w znikomej krotności przypadków, i on jest w stanie to ominąć.
Według jednego z pomysłów należałoby zbadać wykładniczą liczność przypadków dopasowania cyfr. Badane dzielenie wyłuskuje prostą zależność między cyframi dzielników, które ogranicza tę liczność. Dodatkowy test wyznacza konkretne cyfry, zwłaszcza kiedy w trakcie przebiegu zostanie złamana symetria.
Występuje nieoznaczoność, gdyż teoretycznie dostaję 2 wartości dla liczb pierwszych, co najmniej 4 dla złożonych. Są one symetryczne, i ta symetria nie pozwala przewidywać dokładnie. Jednak większość przypadków po złamaniu symetrii jestem w stanie wyznaczać jednoznacznie. Łamanie symetrii następuje tuż po pierwszym wystąpieniu pary różnych cyfr.
Dla wygody rachuję w binarnym. Wtedy dzielenie zwraca wielomian postaci np.
a+b+[0]^*+[1]^* = 1
z dwoma niewiadomymi. Zapis [0]^* oznacza, że dodawane jest kilka zer, ale nie muszą wystąpić. Po uproszczeniu mamy a+b=1 lub a+b=0, gdzie a i b są cyframi binarnymi, dopisywanymi do kandydatów na dzielniki.
Drugi z testów jest związany z parzystością różnicy liczby rozkładanej i iloczynu cząstkowego znajdowanych kandydatów na dzielniki.
29 maja 2016
Zmniejszenie krotności przypadków dla bardzo dużych liczb, poprawka
Wspomniany w styczniu sposób zmniejszania krotności nie jest tak dobry, jak początkowo uważałem.
Przetestowałem kilka sposobów dla postaci
N = ap^2 + bp +c
1) trzymam jak najwięcej w a, dopasowuję skok k by c-bk > p
mamy pierwiastek sześcienny przypadków, a początkowo błyskawicznie maleje, po przekroczeniu p > root[3] N wartość a zmniejsza się o 1 na każde obliczenie.
Jednak istnieje duże ryzyko chybienia dzielników. Podczas testu wykryłem dzielnik tylko dlatego, że go znałem, i w odpowiednim miejscu zastosowałem cechę podzielności. Było bardzo blisko.
2) Jak największe b, a=1
Nie różni się licznością przypadków od 'trial division' przez kolejne liczby nieparzyste.
3) c jest kwadratem dużych wartości, bez nawrotów przy zmniejszaniu a (by zastosować (sqrt a *p+c)^2 +/- bp )
Szybkie zmniejszanie a i c, ale wartość w c za szybko stała się na tyle mała, że sposób przekształcił się w standardowe konwersje o 2.
Myślałem, że jest możliwość sprawdzania równocześnie małych i dużych dzielników, ale do tego trzeba nawrotów, tzn. przenoszenia wartości z a do c i obliczanie kolejny raz dużych kwadratów.
Wnioski. Dla dzielników mniejszych niż pierwiastek sześcienny root[3] {6N} i tak się stosuje konwersje o 2. Dla dzielników większych, a jest na tyle małe, że b zaczyna dominować nad zmianami c. Duże b pociąga znów konwersję o 2.
Zmiany c przy ustalonych a, b i wolno rosnącym p to funkcja kwadratowa z wierzchołkiem w środku przedziału, zatem trudno jest dopasować skoki poza zboczem rosnącym.
Zatem nie uda się zmniejszyć liczności przypadków sprawdzanych do pierwiastka sześciennego.
Przetestowałem kilka sposobów dla postaci
N = ap^2 + bp +c
1) trzymam jak najwięcej w a, dopasowuję skok k by c-bk > p
mamy pierwiastek sześcienny przypadków, a początkowo błyskawicznie maleje, po przekroczeniu p > root[3] N wartość a zmniejsza się o 1 na każde obliczenie.
Jednak istnieje duże ryzyko chybienia dzielników. Podczas testu wykryłem dzielnik tylko dlatego, że go znałem, i w odpowiednim miejscu zastosowałem cechę podzielności. Było bardzo blisko.
2) Jak największe b, a=1
Nie różni się licznością przypadków od 'trial division' przez kolejne liczby nieparzyste.
3) c jest kwadratem dużych wartości, bez nawrotów przy zmniejszaniu a (by zastosować (sqrt a *p+c)^2 +/- bp )
Szybkie zmniejszanie a i c, ale wartość w c za szybko stała się na tyle mała, że sposób przekształcił się w standardowe konwersje o 2.
Myślałem, że jest możliwość sprawdzania równocześnie małych i dużych dzielników, ale do tego trzeba nawrotów, tzn. przenoszenia wartości z a do c i obliczanie kolejny raz dużych kwadratów.
Wnioski. Dla dzielników mniejszych niż pierwiastek sześcienny root[3] {6N} i tak się stosuje konwersje o 2. Dla dzielników większych, a jest na tyle małe, że b zaczyna dominować nad zmianami c. Duże b pociąga znów konwersję o 2.
Zmiany c przy ustalonych a, b i wolno rosnącym p to funkcja kwadratowa z wierzchołkiem w środku przedziału, zatem trudno jest dopasować skoki poza zboczem rosnącym.
Zatem nie uda się zmniejszyć liczności przypadków sprawdzanych do pierwiastka sześciennego.
25 stycznia 2016
Zmniejszenie krotności przypadków rozkładu dla bardzo dużych liczb
Ten pomysł nie jest najlepszy obliczeniowo, ale w pobliżu pierwiastka z liczby rzadko natrafia się na dzielniki. Znalazłem sposób zmniejszenia krotności przypadków, szacuję, że nawet do pierwiastka sześciennego z rozkładanej liczby. Ale koszt jest duży.
Stosując konwersję odwrotną dla liczby N=(a*p+b)*p+c, gdy p^2<N<(p+1)^2, a=1, b jest zerem lub jedynką, normalnie przenosiłem nadmiar z c do b.
Można tego zaniechać. Wtedy współczynniki dla kolejnych iteracji p-k są funkcjami rosnącymi, a właściwie szeregami
c[0] = N-(p+b)*p;
c[k+1] = b[k]+1 + c[k];
b[0] = 0 | 1; (zależy od liczby N)
b[k+1] = 2*k+b[0];
Dosyć szybko c[k]>p-k. Z dzielnikiem mamy do czynienia wtedy, gdy p-k dzieli c[k]. Wyrazy ciągu c[k] można łatwo wyznaczyć, interesują nas tylko te, kiedy c[k] ma resztę bliską p-k.
Najciekawszy efekt jest wtedy, gdy zapisujemy c[k] w systemie o podstawie p-k.
Mamy wtedy przekształcenia kroku iteracji k:
dec p;
konwersja c[k] na system o podstawie 1 mniejszą;
c[k] + b[k]_p; (b[k]_p oznacza liczbę b[k] w systemie o podstawie p)
sprawdzenie, czy cyfra jedności c[k] jest zerem.
Korzystając z monotoniczności c[k] można wyznaczyć sumę ciągu (b[i]+1) tak, by wyznaczyć kolejną wartość przy występującym skoku cyfry jedności c[k], oraz wyznaczyć c[k], p.
W pewnym momencie c[k] zaczyna być liczbą trzycyfrową. Wtedy lepiej zmienić algorytm. Gdyż kontynuacja spowoduje, że c[k] będzie się rozrastać do wielkości rzędu liczby N.
Przykładowo dla N=8934053 mamy jak niżej. Zapis [1,2]_7 oznacza liczbę zapisaną siódemkowo 1*7+2
b[0] = 1, c[0] = 2921, p = 2988
b[7] = 15, c[7] = 2977; p = 2981
b[8] = 17, c[8] = 2993 = [1,13]_2980; p = 2980
b[9] = 19, c[9] = 3011 = [1,32]_2979; p = 2979
następne można pominąć aż do b[53], gdyż jest skok cyfry jedności c[k]_p
b[54] = 109; c[54] = 5891 = [2,23]_2934; p = 2934
b[1901] = 3803; c[1901] = 3618623 = [3,68,0]_1087; p=1087 dzielnik
b[2981] = 5963; c[2981] = 8892263; p=7
Stosując konwersję odwrotną dla liczby N=(a*p+b)*p+c, gdy p^2<N<(p+1)^2, a=1, b jest zerem lub jedynką, normalnie przenosiłem nadmiar z c do b.
Można tego zaniechać. Wtedy współczynniki dla kolejnych iteracji p-k są funkcjami rosnącymi, a właściwie szeregami
c[0] = N-(p+b)*p;
c[k+1] = b[k]+1 + c[k];
b[0] = 0 | 1; (zależy od liczby N)
b[k+1] = 2*k+b[0];
Dosyć szybko c[k]>p-k. Z dzielnikiem mamy do czynienia wtedy, gdy p-k dzieli c[k]. Wyrazy ciągu c[k] można łatwo wyznaczyć, interesują nas tylko te, kiedy c[k] ma resztę bliską p-k.
Najciekawszy efekt jest wtedy, gdy zapisujemy c[k] w systemie o podstawie p-k.
Mamy wtedy przekształcenia kroku iteracji k:
dec p;
konwersja c[k] na system o podstawie 1 mniejszą;
c[k] + b[k]_p; (b[k]_p oznacza liczbę b[k] w systemie o podstawie p)
sprawdzenie, czy cyfra jedności c[k] jest zerem.
Korzystając z monotoniczności c[k] można wyznaczyć sumę ciągu (b[i]+1) tak, by wyznaczyć kolejną wartość przy występującym skoku cyfry jedności c[k], oraz wyznaczyć c[k], p.
W pewnym momencie c[k] zaczyna być liczbą trzycyfrową. Wtedy lepiej zmienić algorytm. Gdyż kontynuacja spowoduje, że c[k] będzie się rozrastać do wielkości rzędu liczby N.
Przykładowo dla N=8934053 mamy jak niżej. Zapis [1,2]_7 oznacza liczbę zapisaną siódemkowo 1*7+2
b[0] = 1, c[0] = 2921, p = 2988
b[7] = 15, c[7] = 2977; p = 2981
b[8] = 17, c[8] = 2993 = [1,13]_2980; p = 2980
b[9] = 19, c[9] = 3011 = [1,32]_2979; p = 2979
następne można pominąć aż do b[53], gdyż jest skok cyfry jedności c[k]_p
b[54] = 109; c[54] = 5891 = [2,23]_2934; p = 2934
b[1901] = 3803; c[1901] = 3618623 = [3,68,0]_1087; p=1087 dzielnik
b[2981] = 5963; c[2981] = 8892263; p=7
05 stycznia 2016
Podnoszenie do kwadratu lub mnożenie
Podobny sposób, który był użyty do znajdowania pierwiastka kwadratowego w ostatnim poście, może też być użyty do podnoszenia liczby do kwadratu.
Są jednak pewne komplikacje - albo pracuje się na dużych liczbach, albo odcina się reszty, które są wyznaczonymi już cyframi wyniku.
Podczas badania odcinania reszt, wpadłem na pewną metodę. Każdy z czynników mnożenia zawiera 'schemat' dojścia konwersjami do potęgi 10, drugi czynnik podążając za tym schematem modyfikuje się w bardzo specyficzny sposób. Kiedy pierwszy stanie się już potęgą 10, drugi staje się wartością iloczynu.
Najciekawsze jest to, że krotność konwersji jest nie większa niż podwojona liczność cyfr liczby, z której pobieramy schemat.
Rozpracowałem już mnożenie, ale zanim je opublikuję, chcę je skonsultować z naukowcami. Powód jest prosty, szacując złożoność, uzyskuję że jest ona logarytmiczna. Zaś mnożenie nie powinno być mniej pracochłonne niż dodawanie czy odejmowanie. Tym bardziej, że przy mnożeniu korzystam z kilku dzieleń.
Są jednak pewne komplikacje - albo pracuje się na dużych liczbach, albo odcina się reszty, które są wyznaczonymi już cyframi wyniku.
Podczas badania odcinania reszt, wpadłem na pewną metodę. Każdy z czynników mnożenia zawiera 'schemat' dojścia konwersjami do potęgi 10, drugi czynnik podążając za tym schematem modyfikuje się w bardzo specyficzny sposób. Kiedy pierwszy stanie się już potęgą 10, drugi staje się wartością iloczynu.
Najciekawsze jest to, że krotność konwersji jest nie większa niż podwojona liczność cyfr liczby, z której pobieramy schemat.
Rozpracowałem już mnożenie, ale zanim je opublikuję, chcę je skonsultować z naukowcami. Powód jest prosty, szacując złożoność, uzyskuję że jest ona logarytmiczna. Zaś mnożenie nie powinno być mniej pracochłonne niż dodawanie czy odejmowanie. Tym bardziej, że przy mnożeniu korzystam z kilku dzieleń.
Subskrybuj:
Posty (Atom)