W połowie listopada podałem, jak z liczby n zrobić płat F(b,d)=c o niezmienniku
n = d^2+bd+c = d(b+d)+c
Okazało się, że zarówno dzielniki, jak i ich wielokrotności tworzą łatwo wykrywalne cięcia przy stałych d, z których łatwo znajdziemy dzielniki. Im mniejszy dzielnik, tym tych specyficznych cięć jest więcej, regularnie rozłożonych. Oznacza to, że możemy ograniczyć się tylko do badania liczb bliskich pierwiastowi kwadratowego z liczby rozkładanej.
Algorytm wygląda zatem następująco:
szukamy pierwiastka liczby sqrt n; jego wyraz wolny równy 0 wyznacza rozkład z pierwiastka;
obliczamy wartość modulo mała liczba stop z wyrażenia d(b+d)+c; możemy też teraz zwiększyć stop;
obliczamy największy wspólny dzielnik wyrazu wolnego c oraz podstawy d, co sprawdza przynależność do tego specyficznego cięcia;
przejście na sąsiednie cięcie płata F:
d--;
b+=2;
c+=b-1;
czasem tak uzyskana wartość c jest większa niż podstawa d, zmniejszamy ją w pętli o operacjach przypominających przeniesienie między cyframi liczby w systemie pozycyjnym
{ b++; c-=d; }
jeśli uzyskamy 0=c, poznamy dzielnik.
Kryterium stopu jest
stop > d
po spełnieniu którego wiemy, że liczba jest pierwsza.
Dochodzi kilka drobnych, lecz istotnych szczegółów. Możemy przyspieszyć wzrost wartości stop do kolejnych liczb niepodzielnych przez 3, 5, 7 (oczywiście większych niż 7, by ewentualny tak mały dzielnik nam nie umknął). Oznacza to, że stop staje się minimum z badanych wartości, co możemy uwzględnić w liczeniu największej wspólnej wielokrotności. Nachylenie tej krzywej dyskretnej stop(d) jest między 2d a 10d. Od dużych wartości jest ograniczone przez d, Zmniejsza to obszar poszukiwań pierwiastka.
Jeżeli iloraz dzielników liczby n=p*q, czyli p/q>1, napotkamy po drodze więcej niż jedno cięcie wskazujące dzielnik. Zatrzymujemy się na pierwszym. Na ogół wtedy znaleziony wspólny dzielnik jest iloczynem małej wartosci i dzielnika n. Może być parzysty, dlatego nie możemy wykluczyć parzystych wartości d. Potrzebne będzie wtedy jeszcze jedno liczenie znalezionego wspólnego dzielnika z liczbą rozkładaną n.
Kod zwiększania wartości stop jest następujący:
if( nie_podzielne(...) ) // test: stop | d(b+d)+c
else while(1) {
stop+=2;
if( 7<stop && (!(stop%3) || !(stop%5) || !(stop%7)) ) continue;
else break;
};
Kod obliczania dzielnika podam w kolejnym poście. Jest zbyt specyficzny i pozwoli zerknąć na nowe możliwości obliczania funkcji rekursywnych.
Brak komentarzy:
Prześlij komentarz