Metody obliczania pierwiastków kwadratowych - Methods of computing square roots

Metody obliczania pierwiastków kwadratowych to algorytmy analizy numerycznej do znajdowania głównego lub nieujemnego pierwiastka kwadratowego (zwykle oznaczanego jako √ S , ² √ S , lub S ^1/2 ) liczby rzeczywistej. Arytmetycznie oznacza dane S, procedurę znajdowania liczby, która po pomnożeniu przez siebie daje S; algebraicznie oznacza procedurę znajdowania nieujemnego pierwiastka równania x ² - S = 0; geometrycznie oznacza dane pole kwadratu, procedurę konstruowania boku kwadratu.

Każda liczba rzeczywista ma dwa pierwiastki kwadratowe. Główny pierwiastek kwadratowy większości liczb jest liczbą niewymierną z nieskończonym rozwinięciem dziesiętnym. W rezultacie rozszerzenie dziesiętne takiego pierwiastka kwadratowego można obliczyć tylko do pewnego przybliżenia o skończonej precyzji. Jednak nawet jeśli wyciągamy pierwiastek kwadratowy z idealnej liczby całkowitej kwadratowej, tak aby wynik miał dokładną skończoną reprezentację, procedura użyta do jej obliczenia może zwrócić tylko serię coraz dokładniejszych przybliżeń.

Ułamka reprezentację liczb rzeczywistych może być stosowany zamiast jego przecinku lub ekspansji binarnej i reprezentacja ta ma tę właściwość, że jako pierwiastek kwadratowy z dowolnej liczby racjonalnego (który nie jest już kwadratem) ma okresową, powtarzając ekspansji, podobne do jak liczby wymierne mają powtarzające się rozwinięcia w systemie notacji dziesiętnej.

Najpowszechniejsze metody analityczne są iteracyjne i składają się z dwóch etapów: znalezienia odpowiedniej wartości początkowej, a następnie iteracyjnego udoskonalenia aż do spełnienia pewnego kryterium zakończenia. Wartość początkowa może być dowolną liczbą, ale im bliższy wynikowi końcowemu, tym mniej iteracji będzie wymaganych. Najbardziej znaną taką metodą, najbardziej odpowiednią do obliczeń programowych, jest metoda Newtona, która opiera się na własności pochodnej w rachunku różniczkowym. Kilka metod, takich jak syntetyczne dzielenie papieru i ołówka i rozszerzanie szeregów, nie wymaga wartości początkowej. W niektórych aplikacjach wymagany jest pierwiastek kwadratowy liczby całkowitej , który jest pierwiastkiem kwadratowym zaokrąglonym lub obciętym do najbliższej liczby całkowitej (w tym przypadku można zastosować zmodyfikowaną procedurę).

Zastosowana metoda zależy od tego, do czego ma być użyty wynik (tj. jak dokładny musi być), ile wysiłku jest się w stanie włożyć w procedurę i jakie narzędzia są pod ręką. Metody te można z grubsza sklasyfikować jako odpowiednie do obliczeń umysłowych, te zwykle wymagające co najmniej papieru i ołówka oraz te, które są implementowane jako programy do wykonania na cyfrowym komputerze elektronicznym lub innym urządzeniu obliczeniowym. Algorytmy mogą uwzględniać zbieżność (ile iteracji jest wymaganych do uzyskania określonej precyzji), złożoność obliczeniową poszczególnych operacji (np. dzielenie) lub iteracji oraz propagację błędów (dokładność końcowego wyniku).

Procedury znajdowania pierwiastka kwadratowego (szczególnie pierwiastka kwadratowego z 2) znane są co najmniej od okresu starożytnego Babilonu w XVII wieku p.n.e. Metoda Herona z Egiptu w I wieku była pierwszym możliwym do ustalenia algorytmem obliczania pierwiastka kwadratowego. Nowoczesne metody analityczne zaczęto rozwijać po wprowadzeniu do zachodniej Europy systemu liczb arabskich we wczesnym renesansie. Obecnie prawie wszystkie urządzenia obliczeniowe mają szybką i dokładną funkcję pierwiastka kwadratowego, albo jako konstrukcję języka programowania, wewnętrzną funkcję kompilatora lub funkcję biblioteki, albo jako operator sprzętowy, w oparciu o jedną z opisanych procedur.

Wstępne oszacowanie

Wiele iteracyjnych algorytmów pierwiastka kwadratowego wymaga początkowej wartości inicjatora . Ziarno musi być niezerową liczbą dodatnią; powinien wynosić od 1 do , liczby, której pierwiastek kwadratowy jest pożądany, ponieważ pierwiastek kwadratowy musi znajdować się w tym zakresie. Jeśli ziarno znajduje się daleko od korzenia, algorytm będzie wymagał więcej iteracji. Jeśli inicjuje się z x ₀ = 1 (lub S ), to w przybliżeniu iteracje zostaną zmarnowane, po prostu uzyskując rząd wielkości pierwiastka. Dlatego warto mieć przybliżone oszacowanie, które może mieć ograniczoną dokładność, ale jest łatwe do obliczenia. Ogólnie rzecz biorąc, im lepsze oszacowanie początkowe, tym szybsza konwergencja. W metodzie Newtona (zwanej również metodą babilońską lub metodą czapli) ziarno nieco większe niż korzeń zbiegnie się nieco szybciej niż ziarno nieco mniejsze niż korzeń. ${\displaystyle S}$${\displaystyle {\tfrac{1}{2}}\vert \log_{2}S\vert}$

Ogólnie rzecz biorąc, oszacowanie odbywa się zgodnie z arbitralnym przedziałem, o którym wiadomo, że zawiera pierwiastek (np. [x ₀ , S/x ₀ ]). Oszacowanie to specyficzna wartość przybliżona funkcyjnej, f (x) = √ x w przedziale. Uzyskanie lepszego oszacowania wymaga albo uzyskania ciaśniejszych granic przedziału, albo znalezienia lepszego przybliżenia funkcjonalnego do f(x). To ostatnie zwykle oznacza użycie wielomianu wyższego rzędu w aproksymacji, chociaż nie wszystkie aproksymacje są wielomianowe. Powszechnie stosowane metody szacowania to skalarne, liniowe, hiperboliczne i logarytmiczne. Podstawa dziesiętna jest zwykle używana do szacowania w myślach lub przy użyciu papieru i ołówka. Baza binarna jest bardziej odpowiednia do oszacowań komputerowych. Przy szacowaniu wykładnik i mantysa są zwykle traktowane oddzielnie, ponieważ liczba byłaby wyrażona w notacji naukowej.

Szacunki dziesiętne

Zazwyczaj liczba jest wyrażana w notacji naukowej jako gdzie i n jest liczbą całkowitą, a zakres możliwych pierwiastków kwadratowych to gdzie . ${\displaystyle S}$${\ Displaystyle a \ razy 10 ^ {2n}}$${\displaystyle 1\leq a<100}$${\ Displaystyle {\ sqrt {a}} \ razy 10 ^ {n}}$${\displaystyle 1\leq {\sqrt {a}}<10}$

Szacunki skalarne

Metody skalarne dzielą zakres na przedziały, a oszacowanie w każdym przedziale jest reprezentowane przez pojedynczą liczbę skalarną. Jeśli zakres jest traktowany jako pojedynczy przedział, średnia arytmetyczna (5,5) lub średnia geometryczna ( ) razy są wiarygodnymi szacunkami. Błąd bezwzględny i względny dla nich będzie się różnić. Ogólnie rzecz biorąc, pojedynczy skalar będzie bardzo niedokładny. Lepsze oszacowania dzielą zakres na dwa lub więcej przedziałów, ale oszacowania skalarne mają z natury niską dokładność. ${\displaystyle {\sqrt {10}}\ok 3,16}$${\ Displaystyle 10 ^ {n}}$

Dla dwóch przedziałów, podzielonych geometrycznie, pierwiastek kwadratowy można oszacować jako ${\ Displaystyle {\ sqrt {S}} = {\ sqrt {a}} \ razy 10 ^ {n}}$

${\ Displaystyle {\ sqrt {S}} \ około {\ zacząć {przypadki} 2 \ cdot 10 ^ {n} i {\ tekst {jeśli}} a <10 \ \ 6 \ cdot 10 ^ {n} i { \text{if }}a\geq 10.\end{cases}}}$

To oszacowanie ma maksymalny błąd bezwzględny przy a = 100 i maksymalny błąd względny 100% przy a = 1. ${\ Displaystyle 4 \ cdot 10 ^ {n}}$

Na przykład dla faktorów jako , oszacowanie wynosi . , błąd bezwzględny 246 i błąd względny prawie 70%. ${\ Displaystyle S = 125348}$${\ Displaystyle 12.5348 \ razy 10 ^ {4}}$${\ Displaystyle {\ sqrt {S}} \ około 6 \ cdot 10 ^ {2} = 600}$${\displaystyle {\sqrt {125348}}=354,0}$

Szacunki liniowe

Lepszym oszacowaniem i stosowana standardowa metoda jest liniowe przybliżenie funkcji na małym łuku. Jeżeli, jak wyżej, potęgi podstawy są wyliczane z liczby, a przedział sprowadzany do [1100], jako aproksymację można zastosować sieczną obejmującą łuk lub styczną leżącą gdzieś wzdłuż łuku, ale co najmniej: kwadratowa linia regresji przecinająca łuk będzie dokładniejsza. ${\ Displaystyle y = x ^ {2}}$${\displaystyle S}$

Linia regresji najmniejszych kwadratów minimalizuje średnią różnicę między oszacowaniem a wartością funkcji. Jego równanie to . Zmiana kolejności, . Zaokrąglanie współczynników dla ułatwienia obliczeń, ${\ Displaystyle y = 8,7 x-10}$${\ Displaystyle x = 0,115y + 1,15}$

${\ Displaystyle {\ sqrt {S}} \ około (A/10 + 1,2) \ cdot 10 ^ {n}}$

Jest to najlepsze średnie oszacowanie, jakie można uzyskać za pomocą jednoelementowej aproksymacji liniowej funkcji y=x ² w przedziale [1100]. Ma maksymalny błąd bezwzględny 1,2 przy a=100 i maksymalny błąd względny 30% przy S=1 i 10.

Aby podzielić przez 10, odejmij jeden od wykładnika , lub przenośnie przesuń kropkę dziesiętną o jedną cyfrę w lewo. W przypadku tego sformułowania dowolna stała dodawania 1 plus mały przyrost da zadowalające oszacowanie, więc zapamiętanie dokładnej liczby nie jest uciążliwe. Aproksymacja (zaokrąglona lub nie) przy użyciu pojedynczej linii obejmującej zakres [1100] jest mniejsza niż jedna cyfra znacząca precyzji; względny błąd jest większy od 1/2 ² , to przewidziane są mniej niż 2 bity informacji. Dokładność jest poważnie ograniczona, ponieważ zakres wynosi dwa rzędy wielkości, dość duży dla tego rodzaju estymacji. ${\displaystyle a}$

Znacznie lepsze oszacowanie można uzyskać przez aproksymację liniową odcinkową: wiele segmentów linii, z których każdy aproksymuje pewien podłuk oryginału. Im więcej użytych odcinków linii, tym lepsze przybliżenie. Najpopularniejszym sposobem jest użycie linii stycznych; najważniejsze wybory to sposób podziału łuku i umiejscowienie punktów stycznych. Skutecznym sposobem na podzielenie łuku od y=1 do y=100 jest geometrycznie: dla dwóch przedziałów granice przedziałów są pierwiastkiem kwadratowym z granic pierwotnego przedziału, 1*100, czyli [1, ² √ 100 ] i [ ² √ 100 ,100]. Dla trzech przedziałów granicami są pierwiastki sześcienne liczby 100: [1, ³ √ 100 ], [ ³ √ 100 ,( ³ √ 100 ) ² ] i [( ³ √ 100 ) ² ,100] itd. Dla dwóch interwały, ² √ 100 = 10, bardzo wygodna liczba. Linie styczne są łatwe do wyprowadzenia i znajdują się w x = √ 1* √ 10 i x = √ 10* √ 10 . Ich równania to: y = 3,56x - 3,16 i y = 11,2x - 31,6. Odwracając, pierwiastki kwadratowe wynoszą: x = 0,28y + 0,89 i x = 0,089y + 2,8. Zatem dla S = a * 10 ²ⁿ :

${\ Displaystyle {\ sqrt {S}} \ około {\ zacząć {przypadki} (0,28a + 0,89) \ cdot 10 ^ {n} i {\ tekst {jeśli}} a <10 \ \ (0,089a + 2,8 )\cdot 10^{n}&{\text{if }}a\geq 10.\end{cases}}}$

Maksymalne błędy bezwzględne występują w najwyższych punktach przedziałów, przy a=10 i 100 i wynoszą odpowiednio 0,54 i 1,7. Maksymalne błędy względne znajdują się w punktach końcowych przedziałów, przy a=1, 10 i 100, i wynoszą 17% w obu przypadkach. 17% lub 0,17 jest większe niż 1/10, więc metoda daje dokładność mniejszą niż cyfra dziesiętna.

Szacunki hiperboliczne

W niektórych przypadkach oszacowania hiperboliczne mogą być skuteczne, ponieważ hiperbola jest również krzywą wypukłą i może leżeć wzdłuż łuku Y = x ² lepiej niż linia. Szacunki hiperboliczne są bardziej złożone obliczeniowo, ponieważ z konieczności wymagają dzielenia zmiennego. Prawie optymalne przybliżenie hiperboliczne do x ² w przedziale [1100] to y=190/(10-x)-20. Transponując pierwiastek kwadratowy to x = -190/(y+20)+10. Tak więc dla : ${\ Displaystyle S = a \ cdot 10 ^ {2n}}$

${\ Displaystyle {\ sqrt {S}} \ około \ lewo ({\ Frac {-190} {a + 20}} + 10 \ po prawej) \ cdot 10 ^ {n}}$

Dzielenie zmiennoprzecinkowe musi być dokładne tylko do jednej cyfry dziesiętnej, ponieważ ogólne oszacowanie jest tylko tak dokładne i można to zrobić mentalnie. Oszacowanie hiperboliczne jest średnio lepsze niż oszacowanie skalarne lub liniowe. Ma maksymalny błąd bezwzględny 1,58 przy 100 i maksymalny błąd względny 16,0% przy 10. W najgorszym przypadku przy a=10 oszacowanie wynosi 3,67. Jeśli jeden zaczyna się od 10 i od razu stosuje iteracje Newtona-Raphsona, wymagane będą dwie iteracje, dające 3,66, zanim dokładność oszacowania hiperbolicznego zostanie przekroczona. W bardziej typowym przypadku, takim jak 75, oszacowanie hiperboliczne wynosi 8,00, a do uzyskania dokładniejszego wyniku wymagane jest 5 iteracji Newtona-Raphsona, zaczynając od 75.

Szacunki arytmetyczne

Metoda analogiczna do aproksymacji liniowej kawałkami, ale używająca tylko arytmetyki zamiast równań algebraicznych, wykorzystuje tabliczki mnożenia w odwrotnej kolejności: pierwiastek kwadratowy z liczby od 1 do 100 wynosi od 1 do 10, więc jeśli wiemy, że 25 jest idealnym kwadratem (5 × 5), a 36 jest idealnym kwadratem (6 × 6), to pierwiastek kwadratowy z liczby większej lub równej 25, ale mniejszej niż 36, zaczyna się od 5. Podobnie dla liczb między innymi kwadratami. Ta metoda da poprawną pierwszą cyfrę, ale nie jest dokładna do jednej cyfry: na przykład pierwsza cyfra pierwiastka kwadratowego z 35 to 5, ale pierwiastek kwadratowy z 35 to prawie 6.

Lepszym sposobem jest podzielenie zakresu na interwały w połowie odległości między kwadratami. Tak więc dowolna liczba od 25 do połowy drogi do 36, czyli 30,5, oszacuj 5; dowolna liczba większa niż 30,5 do 36, oszacowanie 6. Procedura wymaga jedynie trochę arytmetyki, aby znaleźć liczbę graniczną w środku dwóch iloczynów z tabliczki mnożenia. Oto tabela referencyjna tych granic:

a	najbliższy plac	${\ Displaystyle k = {\ sqrt {a}}}$ szac.
1 do 2,5	1 (= 1 2 )	1
2,5 do 6,5	4 (= 2 2 )	2
6,5 do 12,5	9 (= 3 2 )	3
12,5 do 20,5	16 (= 4 2 )	4
20,5 do 30,5	25 (= 5 2 )	5
30,5 do 42,5	36 (= 6 2 )	6
42,5 do 56,5	49 (= 7 2 )	7
56,5 do 72,5	64 (= 8 2 )	8
72,5 do 90,5	81 (= 9 2 )	9
90,5 do 100	100 (= 10 2 )	10

Ostatnią operacją jest pomnożenie oszacowania k przez potęgę dziesiątki podzielone przez 2, więc dla , ${\ Displaystyle S = a \ cdot 10 ^ {2n}}$

${\ Displaystyle {\ sqrt {S}} \ około k \ cdot 10 ^ {n}}$

Metoda niejawnie daje jedną znaczącą cyfrę dokładności, ponieważ zaokrągla się do najlepszej pierwszej cyfry.

W większości przypadków metodę można rozszerzyć o 3 cyfry znaczące, interpolując między najbliższymi kwadratami ograniczającymi operand. Jeśli , to w przybliżeniu k plus ułamek, różnica między a i k ² podzielona przez różnicę między dwoma kwadratami: ${\ Displaystyle k ^ {2} \ leq a < (k + 1) ^ {2}}$${\displaystyle {\sqrt {a}}}$

${\ Displaystyle {\ sqrt {a}} \ ok. k + R}$ gdzie ${\ Displaystyle R = {\ Frac {(ak ^ {2})} {(k + 1) ^ {2}-k ^ {2}}}}$

Ostatnią operacją, jak wyżej, jest pomnożenie wyniku przez potęgę dziesiątki podzielone przez 2;

${\ Displaystyle {\ sqrt {S}} = {\ sqrt {a}} \ cdot 10 ^ {n} \ w przybliżeniu (k + R) \ cdot 10 ^ {n}}$

k to cyfra dziesiętna, a R to ułamek, który należy przekonwertować na dziesiętny. Zwykle ma tylko jedną cyfrę w liczniku i jedną lub dwie cyfry w mianowniku, więc konwersję na dziesiętną można wykonać mentalnie.

Przykład: znalezienie pierwiastka kwadratowego 75. 75 = 75 x 10 ^{2  · 0} , więc wynosi 75, a n wynosi 0. Z tabel mnożenie pierwiastek kwadratowy mantysie musi być 8 punkt coś ponieważ 8 x 8 64 ale 9 × 9 to 81, więc jest za duże, więc k to 8; coś jest dziesiętną reprezentacją R . Ułamek R to 75 - k ² = 11, licznik, a 81 - k ² = 17, mianownik. 11/17 to trochę mniej niż 12/18, czyli 2/3 lub 0,67, więc zgadnij 0,66 (można zgadnąć, błąd jest bardzo mały). Szacunek wynosi więc 8 + 0,66 = 8,66 . √ 75 do trzech cyfr znaczących to 8,66, więc szacunek jest dobry do 3 cyfr znaczących. Nie wszystkie takie szacunki przy użyciu tej metody będą tak dokładne, ale będą bliskie.

Szacunki binarne

Podczas pracy w systemie liczb binarnych (tak jak komputery wewnętrznie), wyrażając jako gdzie , pierwiastek kwadratowy można oszacować jako ${\displaystyle S}$${\ Displaystyle a \ razy 2 ^ {2n}}$${\displaystyle 0.1_{2}\leq a<10_{2}}$${\ Displaystyle {\ sqrt {S}} = {\ sqrt {a}} \ razy 2 ^ {n}}$

${\ Displaystyle {\ sqrt {S}} \ około (0,485 + 0,485 \ cdot a) \ cdot 2 ^ {n}}$

która jest linią regresji najmniejszych kwadratów do 3 współczynników cyfr znaczących. ma maksymalny błąd bezwzględny 0,0408 przy =2 i maksymalny błąd względny 3,0% przy =1. Wygodne obliczeniowo zaokrąglone oszacowanie (ponieważ współczynniki są potęgami 2) to: ${\displaystyle {\sqrt {a}}}$${\displaystyle a}$${\displaystyle a}$

${\ Displaystyle {\ sqrt {S}} \ około (0,5 + 0,5 \ cdot a) \ cdot 2 ^ {n}}$

który ma maksymalny błąd bezwzględny 0,086 przy 2 i maksymalny błąd względny 6,1% przy =0,5 i =2,0. ${\displaystyle a}$${\displaystyle a}$

Dla , przybliżenie binarne daje . , więc szacunek ma błąd bezwzględny 19 i błąd względny 5,3%. Błąd względny jest nieco mniejszy niż 1/2 ⁴ , więc oszacowanie jest dobre do ponad ⁴ bitów. ${\ Displaystyle S = 125348 = 1 \; 1110 \; 1001 \; 1010 \; 0100_ {2} = 1,1110 \; 1001 \; 1010 \; 0100_ {2} \ razy 2 ^ {16} \,}$${\ Displaystyle {\ sqrt {S}} \ około (0,5 + 0,5 \ cdot a) \ cdot 2 ^ {8} = 1,011 \; 0100 \; 1101 \; 0010_ {2} \ cdot 1 \; 0000 \; 0000_ {2}=1.456\cdot 256=372.8}$${\displaystyle {\sqrt {125348}}=354,0}$

Szacunek dla dobrych do 8 bitów można uzyskać przez przeszukiwanie tablicy na wyższych 8 bitach , pamiętając, że wysoki bit jest niejawny w większości reprezentacji zmiennoprzecinkowych, a dolny bit 8 powinien być zaokrąglony. Tabela zawiera 256 bajtów wstępnie obliczonych 8-bitowych wartości pierwiastka kwadratowego. Na przykład dla indeksu 11101101 ₂ reprezentującego 1.8515625 ₁₀ wpis to 10101110 ₂ reprezentujący 1.359375 ₁₀ , pierwiastek kwadratowy z 1.8515625 precyzja od ₁₀ do 8 bitów (2+ cyfry dziesiętne). ${\displaystyle a}$${\displaystyle a}$

Metoda babilońska

Wykresy semilogiczne porównujące szybkość zbieżności metody babilońskiej w celu obliczenia pierwiastka kwadratowego ze 100 dla różnych wstępnych domysłów. Negatywne domysły zbiegają się do ujemnego pierwiastka. Zauważ, że wartości bliższe pierwiastka zbiegają się szybciej, a wszystkie przybliżenia są zawyżone. W pliku SVG najedź kursorem na wykres, aby wyświetlić jego punkty.

Być może pierwszy algorytm używany do aproksymacji jest znany jako metoda babilońska , mimo że nie ma bezpośrednich dowodów poza poinformowanymi przypuszczeniami, że tytułowi matematycy babilońscy zastosowali tę metodę. Metoda ta jest również znana jako metoda Herona , na cześć greckiego matematyka Hero z Aleksandrii, który pierwszy w historii opisał tę metodę w swoim dziele Metrica z roku 60 ne . Podstawowa idea jest taka, że ​​jeśli x jest przeszacowaniem pierwiastka kwadratowego z nieujemnej liczby rzeczywistej S to${\displaystyle {\sqrt {S}}}$ S/xbędzie niedoszacowaniem lub odwrotnie, więc można racjonalnie oczekiwać, że średnia z tych dwóch liczb zapewni lepsze przybliżenie (chociaż formalny dowód tego twierdzenia zależy od nierówności średnich arytmetycznych i geometrycznych, która pokazuje, że ta średnia jest zawsze przeszacować pierwiastek kwadratowy, jak zauważono w artykule o pierwiastkach kwadratowych , zapewniając w ten sposób zbieżność). Jest to równoważne użyciu metody Newtona do rozwiązania . ${\ Displaystyle x ^ {2}-S = 0}$

Dokładniej, jeśli x jest naszym początkowym przypuszczeniem, a ε jest błędem w naszym oszacowaniu takim, że S = ( x + ε ) ² , wtedy możemy rozwinąć dwumian i znaleźć ${\displaystyle {\sqrt {S}}}$

${\ Displaystyle \ varepsilon = {\ Frac {Sx ^ {2}} {2x + \ varepsilon}} \ około {\ Frac {Sx ^ {2}} {2 x}}}$od .${\ Displaystyle \ varepsilon \ ll x}$

W związku z tym możemy zrekompensować błąd i zaktualizować nasze stare oszacowanie jako

${\ Displaystyle x + \ varepsilon \ ok x + {\ Frac {Sx ^ {2}} {2 x}} = {\ Frac {S + x ^ {2}} {2 x}} = {\ Frac {{\ Frac {S }{x}}+x}{2}}\equiv x_{\text{zmieniony}}}$

Ponieważ wyliczony błąd nie był dokładny, staje się to naszym kolejnym najlepszym przypuszczeniem. Proces aktualizacji jest powtarzany aż do uzyskania pożądanej dokładności. Jest to algorytm zbieżny do kwadratu , co oznacza, że ​​liczba poprawnych cyfr aproksymacji w przybliżeniu podwaja się z każdą iteracją. Przebiega w następujący sposób:

1. Zacznij od dowolnej dodatniej wartości początkowej x ₀ (im bliżej rzeczywistego pierwiastka kwadratowego z S , tym lepiej).
2. Niech x _{n + 1} będzie średnią z x _n iS/x _n(stosując średnią arytmetyczną do przybliżenia średniej geometrycznej ).
3. Powtarzaj krok 2, aż do uzyskania żądanej dokładności.

Może być również reprezentowany jako:

${\displaystyle x_{0}\ok {\sqrt {S}}}$

${\ Displaystyle x_ {n + 1} = {\ Frac {1} {2}} \ lewo (x_ {n} + {\ Frac {S} {x_ {n}}} \ po prawej),}$

${\ Displaystyle {\ sqrt {S}} = \ lim _ {n \ do \ infty} x_ {n}.}$

Algorytm ten działa równie dobrze w liczbach p -adycznych , ale nie może być użyty do identyfikacji rzeczywistych pierwiastków kwadratowych z p -adycznymi pierwiastkami kwadratowymi; można na przykład skonstruować tą metodą ciąg liczb wymiernych, który jest zbieżny do +3 w liczbach rzeczywistych, ale do -3 w 2-adics.

Przykład

Aby obliczyć √ S , gdzie S = 125348, do sześciu cyfr znaczących, użyj powyższej metody przybliżonego oszacowania, aby uzyskać

${\ Displaystyle {\ zacząć {wyrównany} {\ zacząć tablicę} x_ {0}& = 6 \ cdot 10 ^ {2}&& = 600.000 \\ [0,3 em] x_ {1}& = {\ Frac {1}{2}}\left(x_{0}+{\frac {S}{x_{0}}}\right)&={\frac {1}{2}}\left(600.000+{\ frac {125348}{600.000}}\right)&=404.457\\[0.3em]x_{2}&={\frac {1}{2}}\left(x_{1}+{\frac {S} {x_{1}}}\right)&={\frac {1}{2}}\left(404.457+{\frac {125348}{404.457}}\right)&=357.187\\[0.3em]x_ {3}&={\frac {1}{2}}\left(x_{2}+{\frac {S}{x_{2}}}\right)&={\frac {1}{2} }\left(357.187+{\frac {125348}{357.187}}\right)&=354.059\\[0.3em]x_{4}&={\frac {1}{2}}\left(x_{3 }+{\frac {S}{x_{3}}}\right)&={\frac {1}{2}}\left(354.059+{\frac {125348}{354.059}}\right)&= 354.045\\[0.3em]x_{5}&={\frac {1}{2}}\left(x_{4}+{\frac {S}{x_{4}}}\right)&={ \frac {1}{2}}\left(354.045+{\frac {125348}{354.045}}\right)&=354.045\end{array}}\end{aligned}}}$

W związku z tym √ 125348 ≈ 354,045 .

Konwergencja

Załóżmy, że x ₀ > 0 i S > 0. Wtedy dla dowolnej liczby naturalnej n , x _n > 0. Niech względny błąd w x _n będzie zdefiniowany przez

${\ Displaystyle \ varepsilon _ {n} = {\ Frac {x_ {n}} {\ sqrt {S}}} -1> -1}$

a zatem

${\ Displaystyle x_ {n} = {\ sqrt {S}} \ cdot (1+ \ varepsilon _ {n}).}$

Wtedy można wykazać, że

${\ Displaystyle \ varepsilon _ {n + 1} = {\ Frac {\ varepsilon _ {n} ^ {2}} {2 (1+ \ varepsilon _ {n})}} \ geq 0.}$

A zatem, że

${\ Displaystyle \ varepsilon _ {n + 2} \ leq \ min \ lewo \ {{\ Frac {\ varepsilon _ {n + 1} ^ {2}} {2}}, {\ Frac {\ varepsilon _ {n +1}}{2}}\prawo\}}$

iw konsekwencji zapewniona jest zbieżność, a kwadratowa .

Najgorszy przypadek konwergencji

Jeśli użyjemy powyższego przybliżonego oszacowania z metodą babilońską, to najmniej dokładne przypadki w kolejności rosnącej są następujące:

${\displaystyle {\begin {wyrównany}S&=1;&x_{0}&=2;&x_{1}&=1.250;&\varepsilon _{1}&=0.250.\\S&=10;&x_{0} &=2;&x_{1}&=3.500;&\varepsilon _{1}&<0.107.\\S&=10;&x_{0}&=6;&x_{1}&=3.833;&\varepsilon _{ 1}&<0.213.\\S&=100;&x_{0}&=6;&x_{1}&=11.333;&\varepsilon _{1}&<0.134.\end{aligned}}}$

Tak więc w każdym razie

${\ Displaystyle \ varepsilon _ {1} \ leq 2 ^ {-2}. \,}$

${\ Displaystyle \ varepsilon _ {2} <2 ^ {-5} < 10 ^ {-1}. \,}$

${\ Displaystyle \ varepsilon _ {3}<2 ^ {-11} <10 ^ {-3}. \,}$

${\ Displaystyle \ varepsilon _ {4}<2 ^ {-23} <10 ^ {-6}. \,}$

${\ Displaystyle \ varepsilon _ {5} <2 ^ {-47} <10 ^ {-14}. \,}$

${\ Displaystyle \ varepsilon _ {6} <2 ^ {-95} <10 ^ {-28}. \,}$

${\ Displaystyle \ varepsilon _ {7} <2 ^ {-191} <10 ^ {-57}. \,}$

${\ Displaystyle \ varepsilon _ {8} <2 ^ {-383} <10 ^ {-115}. \,}$

Błędy zaokrąglania spowolnią zbieżność. Zaleca się zachowanie co najmniej jednej dodatkowej cyfry poza pożądaną dokładnością obliczanego x _n , aby zminimalizować błąd zaokrąglenia.

Metoda Bachszali

Ta metoda znajdowania przybliżenia do pierwiastka kwadratowego została opisana w starożytnym indyjskim manuskrypcie matematycznym zwanym manuskryptem Bakhshali . Jest to równoważne dwóm iteracji metody babilońskiej zaczynającej się od x ₀ . Zatem algorytm jest zbieżny kwartalnie, co oznacza, że ​​liczba poprawnych cyfr aproksymacji wzrasta w przybliżeniu czterokrotnie przy każdej iteracji. Oryginalna prezentacja przy użyciu nowoczesnej notacji jest następująca: Aby obliczyć , niech x ₀ ² będzie początkowym przybliżeniem do S . Następnie kolejno powtarzaj jako: ${\displaystyle {\sqrt {S}}}$

${\ Displaystyle {\ zacząć {wyrównany} a_ {n} i = {\ Frac {S-x_ {n} ^ {2}} {2x_ {n}}} \ \ b_ {n} i = x_ {n} +a_{n},\\x_{n+1}&=b_{n}-{\frac {a_{n}^{2}}{2b_{n}}}=(x_{n}+a_{ n})-{\frac {a_{n}^{2}}{2(x_{n}+a_{n})}}.\end{wyrównany}}}$

Można to wykorzystać do skonstruowania wymiernego przybliżenia pierwiastka kwadratowego, zaczynając od liczby całkowitej. Jeśli x ₀ = N jest liczbą całkowitą wybraną tak, że N ² jest bliskie S , a d = S − N ² jest różnicą, której wartość bezwzględna jest minimalizowana, to pierwszą iterację można zapisać jako:

${\ Displaystyle {\ sqrt {S}} \ około N + {\ Frac {d} {2 N}} - {\ Frac {d ^ {2}} {8 N ^ {3} + 4 Nd}} = {\ Frac {8 N ^{4}+8N^{2}d+d^{2}}{8N^{3}+4Nd}}={\frac {N^{4}+6N^{2}S+S^{2 }}{4N^{3}+4NS}}={\frac {N^{2}(N^{2}+6S)+S^{2}}{4N(N^{2}+S)} }.}$

Metodę Bakhshali można uogólnić do obliczania dowolnego pierwiastka, w tym pierwiastka ułamkowego.

Przykład

Posługując się tym samym przykładem, który podano w przypadku metody babilońskiej, niech pierwsza iteracja daje: ${\ Displaystyle S = 125348.}$

${\ Displaystyle {\ zacząć {wyrównany} x_ {0}& = 600 \ \ a_ {1} i = {\ Frac {125348-600 ^ {2}} {2 \ razy 600}} & & = & -195.543 \ \ b_{1}&=600+(-195.543)&&=&404.456\\x_{1}&=404.456-{\frac {(-195.543)^{2}}{2\times 404.456}}&&=&357 .186\end{wyrównany}}}$

Podobnie druga iteracja daje

$( -3.126)&&=&354.060\\x_{2}&=354.06-{\frac {(-3.1269)^{2}}{2\times 354.06}}&&=&354.046\end{wyrównany}}}$

Obliczanie cyfra po cyfrze

Jest to metoda znajdowania każdej cyfry pierwiastka kwadratowego w sekwencji. Jest wolniejszy niż metoda babilońska, ale ma kilka zalet:

• Ręczne obliczenia mogą być łatwiejsze.
• Wiadomo, że każda znaleziona cyfra korzenia jest poprawna, tzn. nie trzeba jej później zmieniać.
• Jeśli pierwiastek kwadratowy ma rozwinięcie, które się kończy, algorytm kończy się po znalezieniu ostatniej cyfry. W ten sposób można go wykorzystać do sprawdzenia, czy dana liczba całkowita jest liczbą kwadratową .
• Algorytm działa dla dowolnej bazy i oczywiście sposób jego działania zależy od wybranej bazy.

Kości Napiera zawierają pomoc w wykonaniu tego algorytmu. Przesunięcie n p algorytm główny jest uogólnieniem tego sposobu.

Podstawowa zasada

Najpierw rozważmy przypadek znalezienia pierwiastka kwadratowego z liczby Z , czyli kwadratu liczby dwucyfrowej XY , gdzie X to cyfra dziesiątek, a Y to cyfra jednostek. Konkretnie:

Z = (10X + Y) ² = 100X ² + 20XY + Y ²

Teraz używając algorytmu cyfra po cyfrze, najpierw określamy wartość X . X jest największą cyfrą taką, że X ² jest mniejsze lub równe Z, z którego usunęliśmy dwie skrajne prawe cyfry.

W następnej iteracji, powiązać cyfry należy pomnożyć X przez 2, i umieścić go w miejscu dziesiątym, podczas gdy staramy się zorientować się, jaka jest wartość Y jest.

Ponieważ jest to prosty przypadek, w którym odpowiedzią jest pierwiastek kwadratowy XY , algorytm zatrzymuje się w tym miejscu.

Ten sam pomysł można następnie rozszerzyć na dowolne obliczenia pierwiastka kwadratowego. Załóżmy, że jesteśmy w stanie znaleźć pierwiastek kwadratowy z N , wyrażając go jako sumę n liczb dodatnich takich, że

${\ Displaystyle N = (a_ {1} + a_ {2} + a_ {3} + \ kropki + a_ {n}) ^ {2}.}$

Wielokrotnie stosując podstawową tożsamość

${\ Displaystyle (x + y) ^ {2} = x ^ {2} + 2 xy + y ^ {2}}$

termin po prawej stronie można rozszerzyć jako

${\ Displaystyle {\ zacząć {wyrównany} i (a_ {1} + a_ {2} + a_ {3} + \ kropki + a_ {n}) ^ {2} \ \ = & \, a_ {1} ^ { 2}+2a_{1}a_{2}+a_{2}^{2}+2(a_{1}+a_{2})a_{3}+a_{3}^{2}+\kropki + a_{n-1}^{2}+2\left(\sum _{i=1}^{n-1}a_{i}\right)a_{n}+a_{n}^{2}\ \=&\,a_{1}^{2}+[2a_{1}+a_{2}]a_{2}+[2(a_{1}+a_{2})+a_{3}]a_ {3}+\dotsb +\left[2\left(\sum _{i=1}^{n-1}a_{i}\right)+a_{n}\right]a_{n}.\end {wyrównany}}}$

To wyrażenie pozwala nam znaleźć pierwiastek kwadratowy poprzez sekwencyjne zgadywanie wartości s. Załóżmy, że liczby zostały już odgadnięte, wtedy m-ty wyraz prawej strony powyższego sumowania jest podany przez gdzie jest przybliżonym pierwiastkiem kwadratowym znalezionym do tej pory. Teraz każde nowe przypuszczenie powinno zadowolić rekurencję ${\displaystyle a_{i}}$${\displaystyle a_{1},\ldots,a_{m-1}}$${\ Displaystyle Y_ {m} = [2P_ {m-1} + a_ {m}] a_ {m},}$${\ Displaystyle P_ {m-1} = \ suma _ {i = 1} ^ {m-1} a_ {i}}$${\displaystyle a_{m}}$

${\ Displaystyle X_ {m} = X_ {m-1}-Y_ {m}}$

tak, że dla wszystkich z inicjalizacją Kiedy znaleziono dokładny pierwiastek kwadratowy; jeśli nie, to suma s daje odpowiednią aproksymację pierwiastka kwadratowego, gdzie jest błędem aproksymacji. ${\ Displaystyle X_ {m} \ geq 0}$${\displaystyle 1\leq m\leq n}$${\displaystyle X_{0}=N.}$${\ Displaystyle X_ {n} = 0,}$${\displaystyle a_{i}}$${\ Displaystyle X_ {n}}$

Na przykład w systemie liczb dziesiętnych mamy

${\ Displaystyle N = (a_ {1} \ cdot 10 ^ {n-1} + a_ {2} \ cdot 10 ^ {n-2} + \ cdots + a_ {n-1} \ cdot 10 + a_ {n })^{2},}$

gdzie są posiadacze miejsca i współczynniki . Na dowolnym m-tym etapie obliczania pierwiastka kwadratowego, przybliżony pierwiastek znaleziony do tej pory oraz termin sumowania są podane przez ${\ Displaystyle 10 ^ {ni}}$${\displaystyle a_{i}\w \{0,1,2,\ldots,9\}}$${\ Displaystyle P_ {m-1}}$${\ Displaystyle Y_ {m}}$

${\ Displaystyle P_ {m-1} = \ suma _ {i = 1} ^ {m-1} a_ {i} \ cdot 10 ^ {ni} = 10 ^ {n-m + 1} \ suma _ {i =1}^{m-1}a_{i}\cdot 10^{mi-1},}$

${\ Displaystyle Y_ {m} = [2P_ {m-1} + a_ {m} \ cdot 10 ^ {nm}] a_ {m} \ cdot 10 ^ {nm} = \ lewo [20 \ suma _ {i = 1}^{m-1}a_{i}\cdot 10^{mi-1}+a_{m}\right]a_{m}\cdot 10^{2(nm)}.}$

Tutaj, ponieważ wartość miejsca jest parzystą potęgą 10, musimy pracować tylko z parą najbardziej znaczących cyfr pozostałego wyrazu na dowolnym m-tym etapie. Poniższa sekcja kodyfikuje tę procedurę. ${\ Displaystyle Y_ {m}}$${\ Displaystyle X_ {m-1}}$

Jest oczywiste, że podobną metodę można zastosować do obliczenia pierwiastka kwadratowego w systemach liczbowych innych niż system liczb dziesiętnych. Na przykład znalezienie pierwiastka kwadratowego cyfra po cyfrze w systemie liczb binarnych jest dość wydajne, ponieważ wartość jest wyszukiwana z mniejszego zestawu cyfr binarnych {0,1}. To sprawia, że ​​obliczenia są szybsze, ponieważ na każdym etapie wartość jest albo for albo for . Fakt, że mamy tylko dwie możliwe opcje, również ułatwia ustalenie wartości na m-tym etapie obliczeń. Dzieje się tak dlatego, że musimy tylko sprawdzić, czy dla Jeśli ten warunek jest spełniony, to bierzemy ; jeśli nie, to również fakt, że mnożenie przez 2 jest wykonywane przez lewe przesunięcia bitowe, pomaga w obliczeniach. ${\displaystyle a_{i}}$${\ Displaystyle Y_ {m}}$${\ Displaystyle Y_ {m} = 0}$${\ Displaystyle a_ {m} = 0}$${\ Displaystyle Y_ {m} = 2P_ {m-1} + 1}$${\ Displaystyle a_ {m} = 1}$${\displaystyle a_{m}}$${\displaystyle a_{m}}$${\ Displaystyle Y_ {m} \ równoważnik X_ {m-1}}$${\ Displaystyle a_ {m} = 1.}$${\ Displaystyle a_ {m} = 1}$${\ Displaystyle a_ {m} = 0.}$

Dziesiętny (podstawa 10)

Zapisz oryginalną liczbę w postaci dziesiętnej. Liczby są pisane podobnie do algorytmu dzielenia długiego i tak jak w przypadku dzielenia długiego, pierwiastek zostanie zapisany w wierszu powyżej. Teraz podziel cyfry na pary, zaczynając od przecinka i idąc w lewo iw prawo. Punkt dziesiętny pierwiastka będzie powyżej punktu dziesiętnego kwadratu. Jedna cyfra pierwiastka pojawi się nad każdą parą cyfr kwadratu.

Rozpoczynając od skrajnej lewej pary cyfr, wykonaj następującą procedurę dla każdej pary:

1. Zaczynając od lewej, sprowadź w dół najbardziej znaczącą (od lewej) parę cyfr, która nie została jeszcze użyta (jeśli wszystkie cyfry zostały użyte, wpisz „00”) i zapisz je po prawej stronie reszty z poprzedniego kroku (na pierwszym kroku, nie będzie żadnej pozostałości). Innymi słowy, pomnóż resztę przez 100 i dodaj dwie cyfry. Będzie to aktualna wartość c .
2. Znajdź p , y i x , w następujący sposób:
   • Niech p będzie częścią pierwiastka znalezioną do tej pory , ignorując wszelkie przecinki dziesiętne. (W pierwszym kroku p = 0.)
   • Wyznacz największą cyfrę x taką, że . Użyjemy nowej zmiennej y = x (20 p + x ). ${\displaystyle x(20p+x)\leq c}$
     • Uwaga: 20 p + x to po prostu dwa razy p , z cyfrą x dołączoną po prawej stronie.
     • Uwaga: x można znaleźć, zgadując, co to jest c /(20· p ) i wykonując próbne obliczenie y , a następnie dostosowując x w górę lub w dół, jeśli to konieczne.
   • Umieść cyfrę jako następną cyfrę pierwiastka, tj. nad dwiema cyframi kwadratu, który właśnie sprowadziłeś. Zatem następne p będzie starym p razy 10 plus x .${\displaystyle x}$
3. Odejmij y od c, aby utworzyć nową resztę.
4. Jeśli reszta wynosi zero i nie ma więcej cyfr do obniżenia, algorytm się kończy. W przeciwnym razie wróć do kroku 1, aby wykonać kolejną iterację.

Przykłady

Znajdź pierwiastek kwadratowy z 152.2756.

          1  2. 3  4 
       /
     \/  01 52.27 56

         01                   1*1 <= 1 < 2*2                 x = 1
         01                     y = x*x = 1*1 = 1
         00 52                22*2 <= 52 < 23*3              x = 2
         00 44                  y = (20+x)*x = 22*2 = 44
            08 27             243*3 <= 827 < 244*4           x = 3
            07 29               y = (240+x)*x = 243*3 = 729
               98 56          2464*4 <= 9856 < 2465*5        x = 4
               98 56            y = (2460+x)*x = 2464*4 = 9856
               00 00          Algorithm terminates: Answer is 12.34

Binarny system liczbowy (podstawa 2)

Nieodłącznym elementem algorytmów cyfra po cyfrze jest wyszukiwanie i testowanie: znajdź cyfrę, , po dodaniu po prawej stronie bieżącego rozwiązania , taką, że , gdzie jest wartością, dla której pożądany jest pierwiastek. Rozwijanie: . Bieżąca wartość — lub zwykle reszta — może być skutecznie aktualizowana przyrostowo podczas pracy w trybie binarnym, ponieważ wartość będzie miała ustawiony pojedynczy bit (potęga 2), a operacje potrzebne do obliczenia i można je zastąpić szybsze operacje przesunięcia bitowego . ${\displaystyle \,e}$${\displaystyle \,r}$${\ Displaystyle \ (r + e) ​​\ cdot (r + e) ​​\ równoważnik x}$${\displaystyle \,x}$${\ Displaystyle \ r \ cdot r + 2re + e \ cdot e \ równoważnik x}$${\displaystyle \,r\cdot r}$${\displaystyle \,e}$${\ Displaystyle \ 2 \ cdot r \ cdot e}$${\displaystyle \,e\cdot e}$

Przykład

Tutaj otrzymujemy pierwiastek kwadratowy z 81, co po przeliczeniu na binarne daje 1010001. Liczby w lewej kolumnie dają opcję między tą liczbą a zerem, która ma być użyta do odejmowania na tym etapie obliczeń. Ostateczna odpowiedź to 1001, co po przecinku to 9.

             1 0 0 1
            ---------
           √ 1010001

      1      1
             1
            ---------
      101     01  
               0
             --------
      1001     100
                 0
             --------
      10001    10001
               10001
              -------
                   0

Daje to początek prostym implementacjom komputerowym, takim jak ta w C:

int32_t isqrt(int32_t num) {
    assert(("sqrt input should be non-negative", num > 0));
    int32_t res = 0;
    int32_t bit = 1 << 30; // The second-to-top bit is set.
                           // Same as ((unsigned) INT32_MAX + 1) / 2.

    // "bit" starts at the highest power of four <= the argument.
    while (bit > num)
        bit >>= 2;

    while (bit != 0) {
        if (num >= res + bit) {
            num -= res + bit;
            res = (res >> 1) + bit;
        } else
            res >>= 1;
        bit >>= 2;
    }
    return res;
}

Używając powyższego zapisu, zmienna „bit” odpowiada której is , zmienna „res” jest równa , a zmienna „num” jest równa prądowi, który jest różnicą liczby, z której chcemy uzyskać pierwiastek kwadratowy i kwadrat naszego obecnego przybliżenia ze wszystkimi bitami ustawionymi na . Tak więc w pierwszej pętli chcemy znaleźć najwyższą potęgę 4 w „bit”, aby znaleźć najwyższą potęgę 2 w . W drugiej pętli, jeśli liczba jest większa niż res + bit, to jest większa niż i możemy ją odjąć. Następna linia, chcemy dodać do której środki chcemy dodać do tak chcemy . Następnie zaktualizuj do inside res, co polega na podzieleniu przez 2 lub innym przesunięciu w prawo. Połączenie tych 2 w jedną linię prowadzi do . Jeśli nie jest większe lub równe, to po prostu aktualizujemy do wnętrza res i dzielimy przez 2. Następnie aktualizujemy do in bit dzieląc go przez 4. Końcowa iteracja drugiej pętli ma bit równy 1 i spowoduje aktualizację uruchomić jeden dodatkowy czas, usuwając czynnik 2 z res, czyniąc go naszym przybliżeniem liczby całkowitej dla pierwiastka. ${\ Displaystyle e_ {m} ^ {2}}$${\ Displaystyle (2 ^ {m}) ^ {2} = 4 ^ {m}}$${\ Displaystyle 2re_ {m}}$${\ Displaystyle X_ {m}}$${\ Displaystyle 2 ^ {m + 1}}$${\displaystyle e}$${\ Displaystyle X_ {m}}$${\ Displaystyle 2re_ {m} + e_ {m} ^ {2}}$${\displaystyle e_{m}}$${\ Displaystyle r}$${\ Displaystyle 2e_ {m} ^ {2}}$${\ Displaystyle 2re_ {m}}$res = res + bit<<1${\displaystyle e_{m}}$${\ Displaystyle e_ {m-1}}$res = res>>1 + bit${\ Displaystyle X_ {m}}$${\ Displaystyle 2re_ {m} + e_ {m} ^ {2}}$${\displaystyle e_{m}}$${\ Displaystyle e_ {m-1}}$${\displaystyle e_{m}}$${\ Displaystyle e_ {m-1}}$${\displaystyle e}$

Szybsze algorytmy, w postaci binarnej i dziesiętnej lub dowolnej innej podstawie, można realizować za pomocą tabel przeglądowych — w efekcie handlując większą ilością miejsca na dane w celu skrócenia czasu działania .

Tożsamość wykładnicza

Kalkulatory kieszonkowe zazwyczaj implementują dobre procedury do obliczania funkcji wykładniczej i logarytmu naturalnego , a następnie obliczają pierwiastek kwadratowy z S używając tożsamości znalezionej przy użyciu właściwości logarytmów ( ) i wykładników ( ): ${\ Displaystyle \ ln x ^ {n} = n \ ln x}$${\ Displaystyle e ^ {\ ln x} = x}$

${\ Displaystyle {\ sqrt {S}} = e ^ {{\ Frac {1} {2}} \ ln S}.}$

Mianownik ułamka odpowiada n-temu pierwiastkowi. W powyższym przypadku mianownik wynosi 2, stąd równanie określa, że ​​należy znaleźć pierwiastek kwadratowy. Ta sama tożsamość jest używana podczas obliczania pierwiastków kwadratowych za pomocą tabel logarytmicznych lub suwaków .

Metoda iteracyjna z dwiema zmiennymi

Ta metoda ma zastosowanie do znajdowania pierwiastka kwadratowego i zbieżności dla . Nie stanowi to jednak prawdziwego ograniczenia dla obliczeń komputerowych, ponieważ w reprezentacjach zmiennoprzecinkowych i stałoprzecinkowych o podstawie 2 trywialne jest pomnożenie przez liczbę całkowitą 4, a zatem przez odpowiednią potęgę 2, zmieniając wykładnik lub poprzez przesunięcie, odpowiednio. Dlatego można je przenieść do zakresu . Co więcej, poniższa metoda nie wykorzystuje ogólnych dzieleń, ale tylko dodawania, odejmowania, mnożenia i dzielenia przez potęgi dwójki, które znowu są trywialne do wykonania. Wadą tej metody jest kumulacja błędów numerycznych, w przeciwieństwie do metod iteracyjnych z pojedynczą zmienną, takich jak babilońska. ${\displaystyle 0<S<3\,\!}$${\displaystyle S\ok 1}$${\displaystyle S\,\!}$${\displaystyle {\sqrt {S}}}$${\displaystyle S\,\!}$${\displaystyle {\frac {1}{2}}\leq S<2}$

Etap inicjalizacji tej metody to

${\displaystyle a_{0}=S\,\!}$

${\displaystyle c_{0}=S-1\\!}$

podczas gdy iteracyjne kroki czytają

${\ Displaystyle a_ {n + 1} = a_ {n}-a_ {n} c_ {n} / 2 \, \!}$

${\ Displaystyle c_ {n + 1} = c_ {n} ^ {2} (c_ {n} -3) / 4 \ \!}$

Następnie (podczas gdy ). ${\displaystyle a_{n}\rightarrow {\sqrt {S}}}$${\displaystyle c_{n}\rightarrow 0}$

Zauważ, że zbieżność , a zatem także , jest kwadratowa. ${\displaystyle c_{n}\,\!}$${\displaystyle a_{n}\,\!}$

Dowód metody jest dość prosty. Najpierw przepisz iteracyjną definicję as ${\displaystyle c_{n}\,\!}$

${\ Displaystyle 1 + c_ {n + 1} = (1 + c_ {n}) (1-c_ {n} / 2) ^ {2} \, \!}$.

Wtedy łatwo jest udowodnić przez indukcję, że

${\ Displaystyle S (1 + c_ {n}) = a_ {n} ^ {2}}$

a zatem zbieżność do pożądanego wyniku zapewnia zbieżność do 0, co z kolei wynika z . ${\displaystyle a_{n}\,\!}$${\displaystyle {\sqrt {S}}}$${\displaystyle c_{n}\,\!}$${\displaystyle -1<c_{0}<2\,\!}$

Metoda ta została opracowana około 1950 roku przez MV Wilkesa , DJa Wheelera i S. Gilla do zastosowania w EDSAC , jednym z pierwszych komputerów elektronicznych. Metoda została później uogólniona, umożliwiając obliczanie pierwiastków niekwadratowych.

Metody iteracyjne dla odwrotności pierwiastków kwadratowych

Poniżej przedstawiono iteracyjne metody znajdowania odwrotnego pierwiastka kwadratowego z S, którym jest . Po znalezieniu znajdź przez proste mnożenie: . Te iteracje obejmują tylko mnożenie, a nie dzielenie. Dlatego są szybsze niż metoda babilońska . Nie są jednak stabilne. Jeśli wartość początkowa nie jest zbliżona do odwrotności pierwiastka kwadratowego, iteracje odbiegają od niej, a nie zbiegają do niej. Dlatego może być korzystne wykonanie iteracji metody babilońskiej na przybliżonym oszacowaniu przed rozpoczęciem stosowania tych metod. ${\ Displaystyle 1/{\ sqrt {S}}}$${\displaystyle {\sqrt {S}}}$${\ Displaystyle {\ sqrt {S}} = S \ cdot (1/{\ sqrt {S}})}$

• Zastosowanie metody Newtona do równania daje metodę, która zbiega się kwadratowo, wykorzystując trzy mnożenia na krok: ${\ Displaystyle (1 / x ^ {2}) - S = 0}$

  ${\ Displaystyle x_ {n + 1} = {\ Frac {x_ {n}} {2}} \ cdot (3-S \ cdot x_ {n} ^ {2}) = x_ {n} \ cdot \ lewo ( {\frac {3}{2}}-{\frac {S}{2}}\cdot x_{n}^{2}\prawo).}$

• Kolejną iterację uzyskuje się metodą Halleya , która jest metodą drugiego rzędu według Householdera . To zbiega się sześciennie , ale obejmuje pięć mnożeń na iterację:

  ${\ Displaystyle y_ {n} = S \ cdot x_ {n} ^ {2}}$, oraz

  ${\ Displaystyle x_ {n + 1} = {\ Frac {x_ {n}} {8}} \ cdot (15-y_ {n} \ cdot (10-3 \ cdot y_ {n})) = x_ {n }\cdot \left({\frac {15}{8}}-y_{n}\cdot \left({\frac {10}{8}}-{\frac {3}{8}}\cdot y_ {n}\prawda)\prawda)}$.

• Jeśli robisz arytmetykę stałoprzecinkową , mnożenie przez 3 i dzielenie przez 8 można zaimplementować za pomocą przesunięć i dodawania. Jeśli używasz zmiennoprzecinkowych, metodę Halleya można zredukować do czterech mnożeń na iterację poprzez wstępne obliczenie i dostosowanie wszystkich innych stałych w celu skompensowania: ${\displaystyle {\sqrt {\frac {3}{8}}}S}$

  ${\ Displaystyle y_ {n} = {\ sqrt {\ Frac {3} {8}}} S \ cdot x_ {n} ^ {2}}$, oraz

  ${\ Displaystyle x_ {n + 1} = x_ {n} \ cdot \ lewo ({\ Frac {15} {8}}-y_ {n} \ cdot \ lewo ({\ sqrt {\ Frac {25} {6) }}}-y_{n}\right)\right)}$.

Algorytm Goldschmidta

Niektóre komputery używają algorytmu Goldschmidta do jednoczesnego obliczania i . Algorytm Goldschmidta znajduje szybciej niż iteracja Newtona-Raphsona na komputerze za pomocą połączonej instrukcji mnożenia-dodaj i albo potokowej jednostki zmiennoprzecinkowej, albo dwóch niezależnych jednostek zmiennoprzecinkowych. ${\displaystyle {\sqrt {S}}}$${\ Displaystyle 1/{\ sqrt {S}}}$${\displaystyle {\sqrt {S}}}$

Zaczyna się pierwszy sposób pisania algorytmu Goldschmidta

${\displaystyle b_{0}=S}$

${\ Displaystyle Y_ {0}\ około 1/{\ sqrt {S}}}$ (zwykle przy użyciu wyszukiwania w tabeli)

${\displaystyle y_{0}=Y_{0}}$

${\displaystyle x_{0}=sy_{0}}$

i iteruje

${\ Displaystyle b_ {n + 1} = b_ {n} Y_ {n} ^ {2}}$

${\ Displaystyle Y_ {n + 1} = (3-b_ {n + 1}) / 2}$

${\ Displaystyle x_ {n + 1} = x_ {n} Y_ {n + 1}}$

${\ Displaystyle y_ {n + 1} = y_ {n} Y_ {n + 1}}$

dopóki jest wystarczająco bliski 1 lub ustalonej liczby iteracji. Iteracje zbiegają się do ${\displaystyle b_{i}}$

${\ Displaystyle \ lim _ {n \ do \ infty} x_ {n} = {\ sqrt {S}}}$, oraz

${\ Displaystyle \ lim _ {n \ do \ infty} y_ {n} = 1 / {\ sqrt {S}}}$.

Należy zauważyć, że możliwe jest pominięcie jednego i jednego z obliczeń, a jeśli oba są pożądane, można użyć ich na końcu zamiast obliczać je w każdej iteracji. ${\displaystyle x_{n}}$${\displaystyle y_{n}}$${\ Displaystyle x_ {n} = Sy_ {n}}$

Rozpoczyna się druga forma, wykorzystująca połączone operacje mnożenia i dodawania

${\ Displaystyle y_ {0}\ około 1/{\ sqrt {S}}}$ (zwykle przy użyciu wyszukiwania w tabeli)

${\displaystyle x_{0}=sy_{0}}$

${\displaystyle h_{0}=y_{0}/2}$

i iteruje

${\ Displaystyle r_ {n} = 0,5-x_ {n} h_ {n}}$

${\ Displaystyle x_ {n + 1} = x_ {n} + x_ {n} r_ {n}}$

${\ Displaystyle h_ {n + 1} = h_ {n} + h_ {n} r_ {n}}$

dopóki jest wystarczająco bliski 0 lub ustaloną liczbę iteracji. To zbiega się do ${\displaystyle r_{i}}$

${\ Displaystyle \ lim _ {n \ do \ infty} x_ {n} = {\ sqrt {S}}}$, oraz

${\ Displaystyle \ lim _ {n \ do \ infty} 2h_ {n} = 1 / {\ sqrt {S}}}$.

Seria Taylora

Jeśli N jest przybliżeniem , lepszym przybliżeniem można znaleźć za pomocą szeregu Taylora na pierwiastek kwadratowy z funkcji: ${\displaystyle {\sqrt {S}}}$

${\ Displaystyle {\ sqrt {N ^ {2} + d}} = N \ suma _ {n = 0} ^ {\ infty} {\ Frac {(-1) ^ {n} (2n)!} {( 1-2n)n!^{2}4^{n}}}{\frac {d^{n}}{N^{2n}}}=N\left(1+{\frac {d}{2N ^{2}}}-{\frac {d^{2}}{8N^{4}}}+{\frac {d^{3}}{16N^{6}}}-{\frac {5d ^{4}}{128N^{8}}}+\cdots \right)}$

Jako metoda iteracyjna, kolejność zbieżności jest równa liczbie użytych terminów. W dwóch terminach jest identyczna z metodą babilońską . W przypadku trzech wyrazów każda iteracja wymaga prawie tylu operacji, co przybliżenie Bachszali , ale zbiega się wolniej. Dlatego nie jest to szczególnie efektywny sposób obliczania. Aby zmaksymalizować szybkość zbieżności, wybierz N tak, aby był jak najmniejszy. ${\ Displaystyle {\ Frac {| d |} {N ^ {2}}} \,}$

Kontynuacja ekspansji frakcji

Kwadratowe liczby niewymierne (liczby postaci , gdzie a , b i c są liczbami całkowitymi), aw szczególności pierwiastki kwadratowe liczb całkowitych, mają okresowe ułamki ciągłe . Czasami pożądane jest znalezienie nie liczbowej wartości pierwiastka kwadratowego, ale raczej jego dalszego rozszerzania ułamka , a więc jego racjonalnego przybliżenia. Niech S będzie liczbą dodatnią, dla której musimy znaleźć pierwiastek kwadratowy. Następnie zakładając, że a jest liczbą, która służy jako wstępne odgadnięcie, a r jest pozostałym wyrazem, możemy napisać Ponieważ mamy , możemy wyrazić pierwiastek kwadratowy z S jako ${\ Displaystyle {\ Frac {a + {\ sqrt {b}}} {c}}}$${\ Displaystyle S = a ^ {2} + r.}$${\ Displaystyle Sa ^ {2} = ({\ sqrt {S}} + a) ({\ sqrt {S}} -a) = r}$

${\displaystyle {\sqrt {S}}=a+{\frac {r}{a+{\sqrt {S}}}}.}$

Stosując to wyrażenie for do mianownika ułamka, mamy ${\displaystyle {\sqrt {S}}}$

${\displaystyle {\sqrt {S}}=a+{\frac {r}{a+(a+{\frac {r}{a+{\sqrt {S}}}})}}=a+{\frac {r} {2a+{\frac {r}{a+{\sqrt {S}}}}}}.}$

Postępując w ten sposób, otrzymujemy uogólniony ułamek łańcuchowy dla pierwiastka kwadratowego as ${\ Displaystyle {\ sqrt {S}} = a + {\ cfrac {r} {2a + {\ cfrac {r} {2a + {\ cfrac {r} {2a + \ ddots}}}}}}}$

Pierwszym krokiem do oceny takiego ułamka w celu uzyskania pierwiastka jest wykonanie podstawień liczbowych dla pierwiastka żądanej liczby i wybranej liczby mianowników. Na przykład, w postaci kanonicznej jest 1 i √ 2 , to 1, więc liczbowa ułamka 3 mianowniku jest: ${\ Displaystyle r}$${\displaystyle a}$

${\ Displaystyle {\ sqrt {2}} \ około 1 + {\ cfrac {1} {2 + {\ cfrac {1} {2 + {\ cfrac {1} {2}}}}}}}$

Krok 2 polega na zmniejszeniu ułamka łańcuchowego od dołu do góry, o jeden mianownik na raz, aby uzyskać ułamek wymierny, którego licznik i mianownik są liczbami całkowitymi. Redukcja przebiega w ten sposób (biorąc pierwsze trzy mianowniki):

${\ Displaystyle 1 + {\ cfrac {1} {2 + {\ cfrac {1} {2 + {\ cfrac {1} {2}}}}} = 1 + {\ cfrac {1} {2 + { \cfrac {1}{\frac {5}{2}}}}}}$

${\ Displaystyle =1 + {\ cfrac {1} {2 + {\ cfrac {2} {5}}}} = 1 + {\ cfrac {1} {\ Frac {12} {5}}}}$

${\ Displaystyle =1+ {\ cfrac {5}{12}} = {\ Frac {17}{12}}}$

Na koniec (krok 3) podziel licznik przez mianownik ułamka wymiernego, aby uzyskać przybliżoną wartość pierwiastka:

${\ Displaystyle 17 \ dział 12 = 1,42}$ zaokrąglone do trzech cyfr precyzji.

Rzeczywista wartość √ 2 wynosi 1,41 do trzech cyfr znaczących. Błąd względny wynosi 0,17%, więc ułamek wymierny jest dobry z dokładnością do prawie trzech cyfr. Wzięcie większej liczby mianowników daje kolejno lepsze przybliżenia: cztery mianowniki dają ułamek , dobry do prawie 4 cyfr dokładności itp. ${\ Displaystyle {\ Frac {41} {29}} = 1,4137}$

Zwykle ułamek łańcuchowy dla danego pierwiastka kwadratowego jest sprawdzany, a nie rozwijany w miejscu, ponieważ jego rozwijanie jest nużące. Ułamki ciągłe są dostępne dla co najmniej pierwiastków kwadratowych małych liczb całkowitych i wspólnych stałych. W przypadku dowolnej liczby dziesiętnej wstępnie obliczone źródła mogą być bezużyteczne. Poniżej znajduje się tabela małych ułamków wymiernych zwanych zbieżnymi zredukowanymi z kanonicznych ułamków ciągłych dla pierwiastków kwadratowych kilku wspólnych stałych:

√ S	cd. frakcja	~dziesiętny	zbieżne
√ 2	${\displaystyle [1;{\nadkreślenie {2}}]}$	1.41421	${\ Displaystyle {\ Frac {3}{2}}, {\ Frac {7}{5}}, {\ Frac {17}{12}}, {\ Frac {41}{29}}, {\ Frac {99}{70}},{\frac {239}{169}}}$
√ 3	${\ Displaystyle [1; {\ overline {1,2}}]}$	1.73205	${\displaystyle {\frac {2}{1}},{\frac {5}{3}},{\frac {7}{4}},{\frac {19}{11}}, {\frac {26}{15}},{\frac {71}{41}},{\frac {97}{56}}}$
√ 5	${\ Displaystyle [2; {\ overline {4}}]}$	2.23607	${\ Displaystyle {\ Frac {9} {4}}, {\ Frac {38}{17}}, {\ Frac {161}{72}}}$
√ 6	${\ Displaystyle [2; {\ overline {2,4}}]}$	2,44949	${\ Displaystyle {\ Frac {5} {2}} {\ Frac {22} {9}} {\ Frac {49} {20}} {\ Frac {218} {89}}}$
√ 10	${\ Displaystyle [3; {\ overline {6}}]}$	3.16228	${\ Displaystyle {\ Frac {19}{6}}, {\ Frac {117}{37}}}$
${\displaystyle {\sqrt {\pi}}}$	${\displaystyle [1;1,3,2,1,1,6...]}$	1.77245	${\ Displaystyle {\ Frac {2}{1}}, {\ Frac {7} {4}}, {\ Frac {16}{9}}, {\ Frac {23}{13}}, {\ Frac {39}{22}}$
${\displaystyle {\sqrt {e}}}$	${\displaystyle [1;1,1,1,5,1,1...]}$	1,64872	${\displaystyle {\frac {2}{1}},{\frac {3}{2}},{\frac {8}{5}},{\frac {28}{17}}, {\frac {33}{20}},{\frac {61}{37}}}$
${\displaystyle {\sqrt {\phi}}}$	${\displaystyle [1;3,1,2,11,3,7...]}$	1.27202	${\displaystyle {\frac {4}{3}},{\frac {5}{4}},{\frac {14}{11}}}$

Uwaga: wszystkie zbieżności do mianownika 99 włącznie.

Ogólnie rzecz biorąc, im większy mianownik ułamka wymiernego, tym lepsze przybliżenie. Można również wykazać, że obcięcie ułamka łańcuchowego daje ułamek wymierny, który jest najlepszym przybliżeniem pierwiastka dowolnego ułamka z mianownikiem mniejszym lub równym mianownikowi tego ułamka - np. brak ułamka z mianownikiem mniejszym lub równym 99 jest równie dobrym przybliżeniem √ 2 jako 140/99.

Metoda sekwencji Lucas

sekwencja Lucas pierwszego rodzaju U _N ( P , P ) jest określone przez równanie rekurencyjne :

${\ Displaystyle U_ {n} (P, Q) = {\ zacząć {przypadki} 0 i {\ tekst {jeśli}} n = 0 \ \ 1 i {\ tekst {jeśli}} n = 1 \ \ P \ cdot U_ { n-1}(P,Q)-Q\cdot U_{n-2}(P,Q)&{\text{Inaczej}}\end{przypadki}}}$

a jego charakterystyczne równanie to:

${\ Displaystyle x ^ {2}-P \ cdot x + Q = 0}$

ma wyróżnik i korzenie:${\ Displaystyle D = P ^ {2}-4Q}$

${\ Displaystyle {\ zacząć {macierz} x_ {1} = {\ Frac {P + {\ sqrt {D}}} {2}}, & x_ {2} = {\ Frac {P-{\ sqrt {D}} }{2}}\end{matryca}}}$

wszystko to daje następującą wartość dodatnią:

${\ Displaystyle \ lim _ {n \ do \ infty} {\ Frac {U_ {n + 1}} {U_ {n}}} = x_ {1}}$

więc kiedy chcemy , możemy wybrać i , a następnie obliczyć używając i dla dużej wartości . Najbardziej efektywnym sposobem obliczenia i jest:${\displaystyle {\sqrt {a}}}$${\ Displaystyle P = 2}$${\ Displaystyle Q = 1-a}$${\displaystyle x_{1}=1+{\sqrt {a}}}$${\ Displaystyle U_ {n + 1}}$${\ Displaystyle U_ {n}}$${\ Displaystyle n}$${\ Displaystyle U_ {n + 1}}$${\ Displaystyle U_ {n}}$