Przeskocz do treści

Delta mi!

Mała Delta

Pierwiastkowanie pod kreską

Karol Gryszka

o artykule ...

  • Publikacja w Delcie: luty 2018
  • Publikacja elektroniczna: 1 lutego 2018
  • Autor: Karol Gryszka
    Afiliacja: doktorant, Instytut Matematyki, Uniwersytet Jagielloński
  • Wersja do druku [application/pdf]: (65 KB)

Każdy z nas obcował z działaniami pisemnymi na liczbach naturalnych - dodawaniem, odejmowaniem, mnożeniem i dzieleniem. Z pisemnym potęgowaniem można się rozprawić, wielokrotnie stosując pisemne mnożenie. Dzieląc dwie liczby całkowite, możemy otrzymać pełne rozwinięcie dziesiętne (okresowe lub skończone) albo uzyskać dowolną dokładność wyniku. Tak, działania pisemne są sprytne. A co z pierwiastkowaniem? Czy istnieje metoda na pisemne wyznaczanie kolejnych cyfr rozwinięcia dziesiętnego liczby  --- |√ 17? Odpowiedź brzmi: tak.

Opis algorytmu

Algorytm zaprezentujemy na konkretnych przykładach.

obrazek

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ą a1 ), której kwadrat nie przekracza wartości liczbowej tego segmentu ( a1 to pierwsza cyfra wyniku). Od wartości liczbowej segmentu odejmujemy |a21.
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 R1. W przykładzie 1. wynikiem odejmowania 1 −1 jest 0, nie wpisujemy go, stąd w trzeciej linii działania pisemnego pojawia się samo 4.
(4)
Szukamy takiej największej liczby naturalnej a2, że |a2⋅(20a1 +a2) ⩽ R1 (u nas a2⋅(20 ⋅1+ a2)⩽ 4, stąd |a2 = 0 ). Liczba |a2 jest kolejną cyfrą wyniku pierwiastkowania.
(5)
Od R1 odejmujemy liczbę a2 ⋅(20⋅a1 +a2) (w przykładzie jest 4 − 0 ). Wynik odejmowania wraz z dopisanymi dwoma cyframi kolejnego bloku to |R 2 (w przykładzie R = 485 2 ).
(6)
Przyjmijmy, że Ri = Ri− 1 −ai(20 ⋅a1a2...ai−1 +ai) z dopisanymi po prawej stronie dwiema cyframi odpowiedniego segmentu. Przez ai oznaczamy i-tą cyfrę (patrząc od lewej) wyniku pierwiastkowania. W kolejnych krokach szukamy takiej największej liczby a j, że |a j⋅(20 ⋅a1a2 ...a j− 1 + a j) ⩽ R j−1.
(7)
Powtarzamy krok 6 do czasu, gdy jakieś Rj wyniesie 0 i wszystkie "niewykorzystane" bloki są zerowe, wynik jest wtedy dokładny (do bieżącego wyniku a1a2 ...aj 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 n. Szukamy takiej liczby b2, że |(10b1 +b2)2 ⩽ n oraz |10b1 + b2 jest największą możliwą liczbą. Można, oczywiście, zgadywać, czego nie polecamy, zamiast tego dokonajmy prostego przekształcenia:

(10b1 + b2)2 = 100b2 +20b1b2 + b2= b2⋅100 + b2(2⋅b1⋅10 +b2). 1 2 1

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 (10b1 +b2)2 ⩽ n 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ć √ -- √ --- |35, 24 105. 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ć:

pict

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.

obrazek

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  √ -- |5 2, ale nawet sam po wyznaczeniu drugiej cyfry po przecinku miał już dosyć obliczeń  -- |( 5√ 2≈ 1,14). 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...