10 grudnia 2015

Pierwiastkowanie złożoności logarytmicznej

Ostatni algorytm konwersji wskazał możliwość uzyskania pierwiastka kwadratowego stosunkowo małym kosztem. Jako pierwszy znalazłem sposób dla licz zapisanych w postaci binarnej. Istnieje też sposób w systemie dziesiętnym, który jest nieco bardziej rozbudowany.

Liczbę będącą kwadratem p^2 zapiszemy jako czwórkę [1,0,0,p], w której pierwsze pozycje to cyfry rozwinięcia w systemie o podstawie p, czyli
N = 1*p^2 + 0*p+0 .
Oto wszystkie używane manipulacje:
1) [1, a+2, b+a+1, p] = [1, a, b, p+1]
2) [1, a, 2*p+c, p ] = [1, a+2, c, p]
3) [100, 10*a, b, p] = [1, a, b, 10*p] . 
Pierwsza to konwersja na system o 1 większy.

Bierzemy liczbę N i odcinamy grupy po 2 cyfry. Następnie wyznaczamy  przybliżoną wartość pierwiastka. Mając ją, mnożymy wszystkie wartości przez 100 i stosujemy konwersję 3). Uzyskujemy w ten sposób przybliżenie pierwiastka uciętej liczby z niedomiarem, który poprawiamy za pomocą 1) lub 2). Powtórzą się one nie więcej niż 9 razy.
Staramy się doprowadzać do tego, by wszystkie wyrazy były nieujemne, oraz na pozycji drugiej była wartość 0 lub 1 ([1, 0|1, b, p]. Bardzo rzadko pojawia się przypadek, kiedy uzyskamy [1, 2, 0, p] - o 1 mniej niż kwadrat. Zamieniamy go na niepoprawne w systemie [1, 1, p, p]. Uzyskamy w ten sposób dokładną kolejną cyfrę pierwiastka.
Zatem złożoność to logarytm z liczby znajdowanych cyfr plus stały narzut.

Jeśli kto chce znaleźć właściwą wartość pierwiastka i nadmiar, wartość pierwiastka jest przybliżana przez p, zaś nadmiar z [1, a, b, p] jest liczony jako a*p+b większy od p^2.

Przykład: 8 93 40 53
kwadrat z 8 to [1, 2, 0, 2]=[1,1,2,2] (2^2+2*2) - jest to ten wyjątkowy przypadek z drugą wartością większą niż 1.
Mnożymy przez 100 i dodajemy kolejne 2 cyfry uzyskując 893
[100, 100*1/10, 100*2+93, 2] = [1, 10, 293, 20]  z 3)
konwersje 1) i poprawki 2) przybliżają p do pierwiastka:
[1, 10, 293, 20] = [1, 8, 284, 21] = [1, 10, 242, 21] = ...
= [1,1, 23, 29] jest kolejnym przybliżeniem do pierwiastka z przyciętej wartości.
Dokładamy kolejne cyfry 40 uzyskując po konwersji 3):
[1, 10, 2340, 290] = ... = [1, 1, 238, 298]
Ostatnie cyfry 53 i mamy
[1, 10, 23853, 2980] = ... = [1, 1, 2921, 2988]
pierwiastkiem całkowitym jest 2988 z resztą 1*2988+2921.
Możemy kontynuować dokładając '00', uzyskamy w ten sposób kolejne cyfry części ułamkowej z niedomiarem.