Rozkład liczby n na czynniki za pomocą prostego dzielenia polega na kolejnym wstawianiu do ilorazu n/b kolejnych, najlepiej pierwszych, ewentualnie nieparzystych, liczb b. Reszta równa 0 oznacza, że b jest dzielnikiem.
Dla dużych liczb n b też jest duże, chociaż mniejsze niż pierwiastek z n. Wtedy dzielenie jest uciążliwe.
Istnieje sposób, by zmniejszyć argumenty dzielenia, by nie dzielić n/b, lecz jakieś c/b, gdzie c<n. A nawet dwa sposoby.
Pierwszy korzysta z przedstawienia liczby n jako 'liczby dwycyfrowej' jakiegoś systemu liczenia o dużej podstawie, oraz konwersje pozwalają na znajdowanie reszt - niestety, metoda wymaga liczenia ilorazów dla kolejnych liczb naturalnych przy zmniejszaniu dzielnej.
Metoda, którą opiszę dalej, pozwala przeskakiwać liczby parzyste. Zatem tworzymy ilorazy c/b, gdzie c jest nieparzyste, mniejsze od n.
Zapiszmy liczbę n w postaci wyrażenia:
n = a*b + c (1)
będziemy przekształcać wartości a, b, oraz c w taki sposób, by podczas przekształceń a tworzyło ciąg nierosnący, b było ciągiem rosnącym po wartościach nieparzystych, zaś c tworzyło ciąg przedziałami monotoniczny.
Algorytm jest rozgałęziony, a jego ogólny schemat wygląda następująco:
inicjacja: a = floor(n/3), b=3, c=n%3.
pętla dopóki a>b
czy b dzieli c (warunek 0 = c%b)? jeśli tak, b jest dzielnikiem, wyjście;
b = b+2;
rozgałęzienie, jeśli c<2a
c = c + (a%b)*(b-2);
a = b*floor(a/b) - 2*floor(a/b);
w przeciwnym razie (c>2a)
c = c-2a;
koniec pętli
Pierwsza część rozgałęzienia jest całkowito-liczbową operacją a*(b-2)/b, która zwiększa c oraz zmniejsza a. Mamy tu dodatkowo jedno dzielenie oraz mnożenie, co komplikuje algorytm. Można je przekształcić, by dzielić przez b oraz odjąć podwojony iloraz od a.
Z kolei druga część rozgałęzienia jest zwykłym odejmowaniem.
W początkowej fazie algorytmu przeważa pierwsza część, z dodatkowymi działaniami. Wykonują się jednak one na małych wartościach, dużo mniejszych niż pierwiastek z n. Pod koniec algorytmu najgorszym kawałkiem jest mnożenie (a%b)*(b-2), którego wartość może być stosunkowo blisko n. Zwiększa ona c do bardzo dużych wartości, umożliwiając stosowanie drugiej, prostszej odnogi.
Już po sprawdzeniu około 20% przypadków na możliwe wartości b do głosu dochodzi druga część rozgałęzienia, zaś przy 30% praktycznie dominuje.
Cały czas należy sprawdzać podzielność c przez b. Chociaż c (zwłaszcza przy dominacji drugiej odnogi) szybko maleje nawet do wartości bliskich b.
Fragment przykładu numerycznego, liczba 8 934 053 = 1087 * 8219.
inicjacja: a*b+c = 2 978 017 * 3 + 2
b = 3+2 = 5;
pierwsza odnoga: 2 978 017 - 2 = 2 978 015, bo 2 978 017 % 5 = 2,
c = 2 + 2*3 = 8
zmniejszanie a: 2 978 015 * 3 / 5 = 2 978 015 - 2*(595 603) = 1 786 809
nieco dalej:
a = 122 049; b = 73; c = 24 476;
sprawdzamy c%b = 21, nie jest zerem; pierwsza odnoga
b=75; reszta a%b = 24
c = 24 476 + 24*(75-2) = 26 228;
a = (122 049 - 24) - 2*(122 049 - 24)/75 = 118 771
jeszcze dalej:
a = 69 125; b = 127; c = 155 178;
sprawdzamy c%b = 111, druga odnoga
b = 129;
c = 155 178 - 2 * 69 125 = 16 928;
możemy znów sprawdzać c%b = 16 928 % 129
dla b>400 co parę przekształceń mamy kilka iteracji odnogą drugą, zaś blisko końca algorytmu mamy
a = 8685; b = 1027; c = 14 558;
sprawdzamy c%b = 180; pierwsza odnoga
b = 1029;
c = c + 453*1027 = 479 789;
a = (a-453) - 2*(a-453)/1029 = 8232-16 = 8216;
Teraz przez 29 iteracji powtarza się odejmowanie w drugiej odnodze, zanim znów zastosujemy pierwszą.
Zakończenie algorytmu
a*b+c = 8216 * 1087 + 3261, oraz 3261 = 3*1087.
Algorytm nie jest zbyt dobry. Może być nawet gorszy niż zwykłe dzielenia. Może być traktowany jako ciekawostka.
Brak komentarzy:
Prześlij komentarz