Mam porównać swój algorytm faktoryzacji liczb ze standardowym. Liczby, które zadaję są za małe.
Zatem należy poznać bibliotekę rachunków na dużych liczbach - gmp.
Nie byłbym sobą, gdybym wpierw nie przejrzał dokumentacji i zastanowił się nad algorytmami.
Oczywiście dla dodawania i odejmowania algorytmy nie są wspomniane. Są liniowe, jak to opisuje Knuth w Sztuce programowania rozdział 4.3.1.
Większość algorytmów używanych przez gmp jest też podana przez Knutha. Najprostszy ma złożoność O(NM), gdzie N i M są licznościami cyfr czynników. Lepsze mają złożoność związaną z licznością cyfr N wzorem O(N 2^(sqrt(2 lg N)) log N) .
Lecz Knuth nie zauważył jeszcze jednego podejścia, związanego z podawaną wielokrotnie przez niego równoważną postacią liczby.
Liczba binarna a_n a_{n-1}... a_0 może być przedstawiona następująco:
A = (...(a_n*2+a_{n-1})*2+...)*2 + a_0
Oznaczmy A_i nawias zawierający jako najmniej znaczącą cyfrę a_i.
Obliczając dwie takie liczby A oraz B uzyskujemy iloczyn
A*B = (A_1*2 + a_0) * (B_1*2 + b_0 ) = ((A_1*B_1)*2 + A_1*b_0 + a_0*B_1)*2 + a_0*b_0
Ponieważ mnożenie przez 2 jest równoważne przesunięciu, mamy 3 mnożenia przez cyfry 0, 1; do wyniku dodajemy 3 sumy cząstkowe oraz mamy wywołanie rekurencyjne dla liczb mających mniej cyfr.
Złożoność tego algorytmu to 3 mnożenia, 3 dodawania oraz 3 przesunięcia na każdą iterację, za każdym razem wyznaczamy 2 cyfry. Do wyznaczonych cyfr najmniej znaczących już nie musimy wracać. Iteracji jest tyle, by któraś z liczb A_i, B_i stała się jednocyfrowa.
Ponieważ w przypadku binarnym mnożenia mozemy zastąpić dodawaniami liczb o długości co najwyżej max(N,M), cała złożoność nie przekracza złożoności sum coraz krótszych liczb. Jest zatem co najwyzej kwadratowa dla wiekszej z nich. Dokladniej porownujac, uzyskuje zlozonosc taka sama jak u Knutha O(NM), lecz na coraz mniejszych cyfrach.
