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.
Brak komentarzy:
Prześlij komentarz