Opis algorytmu

Algorytm zaprezentujemy na konkretnych przykładach.

Ideę algorytmu pierwiastkowania można opisać następująco (odwoływać się będziemy do przykładu 1):

(1)

Dzielimy liczbę na dwucyfrowe segmenty, począwszy od prawej strony - na przykładzie zaznaczone pionowymi liniami.

(2)

Dla pierwszego z lewej segmentu (może być jednocyfrowy) szukamy największej liczby naturalnej (oznaczmy ją ), której kwadrat nie przekracza wartości liczbowej tego segmentu ( to pierwsza cyfra wyniku). Od wartości liczbowej segmentu odejmujemy
W powyższych przykładach kolejne cyfry wyniku pierwiastkowania zostały wpisane w kwadraty.

(3)

Do wyniku odejmowania dopisujemy z prawej strony cyfry kolejnego segmentu - analogicznie jak w dzieleniu pisemnym - tę liczbę oznaczmy przez W przykładzie 1. wynikiem odejmowania jest 0, nie wpisujemy go, stąd w trzeciej linii działania pisemnego pojawia się samo 4.

(4)

Szukamy takiej największej liczby naturalnej że (u nas stąd ). Liczba jest kolejną cyfrą wyniku pierwiastkowania.

(5)

Od odejmujemy liczbę (w przykładzie jest ). Wynik odejmowania wraz z dopisanymi dwoma cyframi kolejnego bloku to (w przykładzie ).

(6)

Przyjmijmy, że z dopisanymi po prawej stronie dwiema cyframi odpowiedniego segmentu. Przez oznaczamy -tą cyfrę (patrząc od lewej) wyniku pierwiastkowania. W kolejnych krokach szukamy takiej największej liczby że

(7)

Powtarzamy krok 6 do czasu, gdy jakieś wyniesie 0 i wszystkie "niewykorzystane" bloki są zerowe, wynik jest wtedy dokładny (do bieżącego wyniku należy dopisać jeszcze tyle zer, ile bloków zostało),

albo

kończymy algorytm w dowolnym innym momencie (wynik jest wtedy przybliżony). Jeśli na tym etapie pozostały niewykorzystane bloki, za każdy taki blok należy dopisać cyfrę 0 do wyniku,

albo

procedurę możemy kontynuować ad infinitum: jeśli wyczerpaliśmy wszystkie segmenty, a wynik odejmowania nie zeruje się, możemy dopisać nowy blok złożony z dwóch zer, a kolejne cyfry wyniku pierwiastkowania dopisywać po przecinku (analogicznie do dzielenia pisemnego).

Dlaczego to działa?

Spróbujemy krótko uzasadnić, dlaczego taki algorytm działa. Spójrzmy na problem następująco: dana jest pewna liczba Szukamy takiej liczby że oraz jest największą możliwą liczbą. Można, oczywiście, zgadywać, czego nie polecamy, zamiast tego dokonajmy prostego przekształcenia:

Gdy wrócimy do algorytmu, przekonamy się, że w oparciu o właśnie takie jak wyżej przekształcenie i jednoczesne zachowanie warunku maksymalizacji wyrażenia spełniającego szukaliśmy liczb, które wpisywaliśmy w kwadraty.

Pierwiastki innych stopni

Pokazaliśmy, jak poradzić sobie z obliczaniem pierwiastka kwadratowego z dowolnej liczby całkowitej (nawet jeżeli ta wartość jest liczbą niewymierną). Ale przecież stopień pierwiastka może być inny! Możemy, na przykład, chcieć obliczyć I cóż wtedy?

Autor niniejszego artykułu nie poddał się! Pierwszym spostrzeżeniem była redukcja problemu do pierwiastków, których stopień jest liczbą pierwszą. Kolejne spostrzeżenie to analogiczne przekształcenie wzoru na odpowiednią potęgę sumy dwóch liczb. Możemy mianowicie zastosować:

i tak dalej... Powyższe wzory pozwoliły skonstruować odpowiednie algorytmy. Niestety, nie są to już tak proste i szybkie procedury (zwłaszcza, gdy wymóg ręcznego wykonywania obliczeń nadal pozostaje w mocy). Złożoność obliczeniowa wzrasta, natomiast część, w której "zgadywana" jest liczba (kolejne cyfry), staje się tym trudniejsza, im wyższy jest stopień pierwiastka.

Przejdźmy od teorii do praktyki. Algorytm obliczania pierwiastków stopnia trzeciego prezentujemy na poniższym przykładzie. Zaczynamy od podzielenia pierwiastkowanej liczby na trzycyfrowe segmenty.

Zachęcamy do prześledzenia powyższego przykładu - Czytelnik powinien zauważyć podobieństwo do poprzedniego algorytmu oraz ideę stojącą za obliczeniami.

Autor skonstruował również odpowiedni schemat w celu wyznaczenia liczby ale nawet sam po wyznaczeniu drugiej cyfry po przecinku miał już dosyć obliczeń Nie ma jednak powodu do rozpaczy - otrzymany wynik jest lepszy od wyników, które można uzyskać prostym kalkulatorem. Te ostatnie bowiem potrafią zwykle obliczać jedynie pierwiastki kwadratowe...