Metody výpočtu odmocnin

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 13. ledna 2022; kontroly vyžadují 4 úpravy .

Metody druhé odmocniny jsou výpočetní algoritmy pro výpočet přibližných hodnot hlavních (nebo nezáporných) odmocnin (obvykle označovaných jako , nebo ) reálného čísla. Aritmeticky to znamená, že pokud je zadáno číslo , procedura najde číslo, které po vynásobení samo sebou dává . Algebraicky to znamená postup hledání nezáporného kořene rovnice . Geometricky to znamená sestrojit stranu čtverce s danou plochou. ${\sqrt {S))$ ${\sqrt[{2}]{S))$ $S^{1/2}$ $S$ $S$ $x^{2}-S=0$

Každé reálné číslo má dva kořeny [1] . Hlavní hodnotou druhé odmocniny většiny čísel je iracionální číslo s nekonečnou posloupností desetinných číslic. V důsledku toho lze desetinnou reprezentaci jakékoli takové odmocniny vypočítat pouze přibližně s konečnou přesností (desetinná místa). I když však vezmeme druhou odmocninu z celého čísla, takže výsledek má konečnou reprezentaci, některé procedury používané k výpočtu odmocniny mohou vracet pouze řadu aproximací s rostoucí přesností.

Reprezentaci pokračovacího zlomku reálného čísla lze použít místo desetinného nebo binárního rozvoje a tato reprezentace má tu vlastnost, že druhá odmocnina jakéhokoli racionálního čísla (které není dokonalým čtvercem) má periodu, tj. periodický rozvoj podobný tomu, racionální čísla mají opakovaný rozvoj desítkové číselné soustavy.

Nejběžněji přijímané analytické metody jsou iterativní a sestávají ze dvou kroků: nalezení vhodné výchozí hodnoty a následného iterativního zpřesňování, dokud není dosaženo určitého zastavovacího kritéria. Počáteční hodnota může být libovolné číslo, ale pokud je blíže koncové hodnotě, bude potřeba méně iterací. Nejznámější takovou metodou a pro programování ještě pohodlnější je Newtonova metoda, která je založena na výpočtu derivace. Několik metod, jako je ruční dělení podle Hornera nebo rozšíření série, nevyžaduje počáteční hodnotu. V některých aplikacích je nutné najít celou odmocninu , což je druhá odmocnina zaokrouhlená na nejbližší celé číslo (v tomto případě lze použít upravený postup).

Použitá metoda závisí na tom, jak bude výsledek použit (tedy jak přesný musí být výsledek) a jaké nástroje jsou k dispozici. Metody lze zhruba rozdělit na ty, které lze provádět mentálně, které vyžadují tužku a papír, nebo ty, které jsou implementovány jako program a běží na počítačích nebo jiných výpočetních zařízeních. Zohlednit lze rychlost konvergence (kolik iterací bude potřeba k dosažení dané přesnosti), výpočetní náročnost jednotlivých operací (např. dělení) či iterací a rozložení chyb (přesnost výsledku).

Postupy hledání druhých odmocnin (zejména odmocniny 2) jsou známy přinejmenším od doby starověkého Babylonu (17. století př. n. l.). Heronova metoda z Egypta 1. století byla prvním ověřitelným algoritmem pro výpočet druhé odmocniny. Moderní analytické metody se začaly vyvíjet po přijetí arabských číslic v západní Evropě v rané renesanci . V dnešní době mají téměř všechna výpočetní zařízení rychlou a přesnou funkci druhé odmocniny jako vestavěný konstrukt programovacího jazyka, knihovní funkce nebo hardwarové prohlášení, které je založeno na níže popsaných postupech.

Počáteční skóre

Mnoho iterativních algoritmů druhé odmocniny vyžaduje počáteční náhodnou hodnotu. Tato hodnota musí být kladné nenulové číslo. Musí být mezi 1 a , číslem, jehož druhou odmocninu hledáme, protože druhá odmocnina musí být v těchto mezích. Pokud je počáteční hodnota velmi daleko od kořenové složky, bude algoritmus potřebovat více iterací. Pokud začnete s (nebo s ), bude to fungovat o dalších iteracích, jen abyste získali pořadí kořene. Proto je užitečné mít hrubý odhad kořene, který může mít špatnou přesnost, ale lze jej snadno vypočítat. Obecně platí, že čím přesnější odhad, tím rychlejší konvergence. U Newtonovy metody (také nazývané Babylonská nebo Heronova metoda) počáteční hodnota o něco větší než odmocnina poskytuje rychlejší konvergenci než počáteční hodnota menší než odmocnina. $S$ $x_{0}=1$ $S$ ${\tfrac {1}{2}}\vert \log _{2}S\vert$

Obecně řečeno, odhad je uvažován na libovolném intervalu, ve kterém je známo, že obsahuje kořen (například ). Získání lepšího odhadu zahrnuje buď získání užších mezí na intervalu nebo lepší funkční aproximaci k . To druhé obvykle znamená použití polynomů vyššího řádu pro aproximaci, i když ne všechny aproximace používají polynomy. Běžné metody odhadu jsou skalární, lineární, hyperbolické a logaritmické. Desítková soustava se obvykle používá pro odhad mentálně nebo na papíře. Binární číselná soustava je vhodnější pro počítačová vyhodnocení. Při hodnocení se exponent a mantisa obvykle řeší odděleně. $[x_{0},S/x_{0}]$ $f(x).$

Desetinné skóre

Obvykle je číslo vyjádřeno v exponenciálním tvaru jako , kde , a n je celé číslo, pak odhad možné druhé odmocniny může být , kde . $S$ ${\displaystyle a\times 10^{2n))$ $1\leqslant a<100$ ${\sqrt {a}}\times 10^{n}$ $1\leqslant {\sqrt {a}}<10$

Skalární odhady

Skalární metody rozdělují celý rozsah do přihrádek a skóre v každé přihrádce je reprezentováno jediným číslem. Pokud je rozsah považován za jeden interval, pak jsou přijatelné odhady aritmetický průměr (5,5) nebo geometrický průměr (). Absolutní a relativní odhady pro tyto odhady se budou lišit. Obecně platí, že jedno číslo bude velmi nepřesné. Více přesné odhady rozdělují rozsah do dvou a více intervalů, ale skalární odhad je i nadále velmi hrubý. ${\sqrt {10}}\cca 3{,}16)\times 10^{n}$

Pro dva intervaly rozdělené geometricky lze druhou odmocninu odhadnout jako [2] . ${\sqrt {S}}={\sqrt {a}}\times 10^{n}$

{\sqrt {S}}\approx {\begin{cases}2\cdot 10^{n}&{\text{if }}a<10,\\6\cdot 10^{n}&{ \text{if }}a\geqslant 10.\end{cases}}

Tento odhad má maximální absolutní chybu v bodě = 100 a maximální relativní chybu 100 % v bodě = 1. ${\displaystyle 4\cdot 10^{n))$

Například u rozkladu bude skóre . , s absolutní chybou 246 a relativní chybou téměř 70 %. $S=125348$ $12{,}5348\times 10^{4}$ ${\sqrt {S}}\cca 6\cdot 10^{2}=600$ ${\sqrt {125348}}=354{,}0$

Lineární odhad

Nejlepší odhad a standardní metoda je lineární aproximace funkce na malém oblouku. Pokud, jak je uvedeno výše, je exponent extrahován z čísla a interval je redukován na , můžete použít sečnu nebo tečnu někde podél oblouku k aproximaci, ale přímá regrese nejmenších čtverců bude přesnější. $y = x^2$ $S$ $[1 100]$

Přímka získaná metodou nejmenších čtverců minimalizuje průměrnou vzdálenost mezi odhadem a hodnotou funkce. Její rovnice je . Po transformaci a zaokrouhlení koeficientů pro zjednodušení výpočtů získáme $y=8{,}7x-10$ $x=0{,}115y+1{,}15$

{\sqrt {S}}\cca (a/10+1{,}2)\cdot 10^{n}

Toto je nejlepší průměrný odhad , který lze získat jedním pokusem o lineární aproximaci funkce v intervalu . Odhad má maximální absolutní chybu 1,2 v bodě a=100 a maximální relativní chybu 30 % v bodech S=1 a 10 [3] . $y=x^2$ $[1 100]$

Pro dělení 10 odečtěte jedničku od exponentu nebo, obrazně řečeno, posuňte desetinnou čárku o jednu pozici doleva. Pro tento vzorec jakákoli přidaná konstanta rovna 1 plus malý přírůstek poskytuje uspokojivý odhad, takže není potřeba si zapamatovat přesné číslo. Aproximace (zaokrouhlená nebo nezaokrouhlená) pomocí jedné přímky, která odečte oblast z hlediska přesnosti, nedává více než jedno správné znaménko. Relativní chyba je větší než 1/2 2 , takže poskytuje méně než 2 bity informace. Přesnost je značně omezená, protože oblast zabírá dva řády, což je pro tento druh odhadu poměrně velké. $A$ $[1 100]$

Výrazně lepší odhad lze získat pomocí dílčí lineární aproximace, tj. pomocí několika segmentů, které aproximují dílčí oblouk původního oblouku. Čím více segmentů je použito, tím lepší je aproximace. Nejběžnější použití tečen. Kritickým bodem je, jak rozdělit oblouk a kam umístit dotykové body. Efektivní metoda dělení oblouku od y=1 do y=100 je geometrická - pro dva intervaly je hranicí intervalu druhá odmocnina původního intervalu, 1 * 100, tedy a . Pro tři intervaly budou krychlové odmocniny - , a , a tak dále. Pro dva intervaly je to velmi výhodné číslo. Je snadné získat tečné čáry v bodech dotyku a . Jejich rovnice jsou: a . Obrácením rovnic dostaneme, že odmocniny se rovnají a . Potom pro : $[1,{\sqrt[{2}]{100}}]$ $[{\sqrt[{2}]{100)),100]$ $[1,{\sqrt[{3}]{100}],[{\sqrt[{3}]{100}},({\sqrt[{3}]{100}})^{ 2}]$ $[({\sqrt[{3}]{100)))^{2},100]$ ${\sqrt[{2}]{100}}=10$ $x={\sqrt {1*{\sqrt {10}}}}$ $x={\sqrt {10*{\sqrt {10))))$ $y=3{,}56x-3{,}16$ $y=11{,}2x-31{,}6$ $x=0{,}28y+0{,}89$ $x=0{,}089y+2{,}8$ ${\displaystyle S=a\cdot 10^{2n))$

{\sqrt {S}}\approx {\begin{cases}(0{,}28a+0{,}89)\cdot 10^{n}&{\text{if }}a<10, \\(0{,}089a+2{,}8)\cdot 10^{n}&{\text{if }}a\geqslant 10.\end{cases}}

Maximální absolutní hodnoty jsou v pravých hranicích intervalů, v bodech a=10 a 100, a jsou rovny 0,54 a 1,7. Maximální relativní chyby se objevují na koncích intervalů, v bodech a=1, 10 a 100, a jsou rovny 17 %. 17 % nebo 0,17. Jsou větší než 1/10, takže metoda dává přesnost menší než jedna platná číslice.

Hyperbolický odhad

V některých případech může být hyperbolický odhad platný, protože hyperbola je také konvexní křivka a může ležet podél oblouku Y = x 2 lépe než přímka. Hyperbolický odhad je výpočetně obtížnější, protože vyžaduje dělení číslem s plovoucí desetinnou čárkou. Téměř optimální hyperbolická aproximace k x 2 na intervalu je . Po transformaci dostaneme . Potom pro : $[1 100]$ $y=190/(10-x)-20$ $x=-190/(y+20)+10$ ${\displaystyle S=a\cdot 10^{2n))$

{\sqrt {S}}\approx \left({\frac {-190}{a+20}}+10\right)\cdot 10^{n}

Dělení s plovoucí desetinnou čárkou musí být přesné na jedno desetinné místo, protože všechna hodnocení tuto přesnost poskytují a takové rozdělení lze provést mentálně. Hyperbolický odhad je v průměru lepší než skalární nebo lineární odhad. Jeho maximální absolutní chyba je 1,58 v bodě 100 a jeho maximální relativní chyba je 16,0 % v bodě 10. Pro nejhorší případ a=10 je skóre 3,67. Pokud začneme na 10 a použijeme přímo Newton-Rapsonovy iterace, trvá to dvě iterace, které dávají 3,66, než dosáhneme přesnosti hyperbolického odhadu. Pro typičtější případ, jako je 75, je hyperbolický odhad 8,00 a k získání přesnějšího výsledku je potřeba 5 iterací Newton-Rapson počínaje 75.

Aritmetické vyhodnocení

Metoda podobná po částech lineární aproximace, ale používající pouze aritmetické operace místo algebraických rovnic, používá tabulku násobení obráceně - druhá odmocnina čísel mezi 1 a 100 je někde mezi 1 a 10, takže protože víme, že 25 je přesná čtverec (5 × 5) a 36 je přesný čtverec (6 × 6), pak druhá odmocnina čísla, které je větší než 25, ale menší než 36, začíná číslem 5. Podobně pro čísla mezi ostatními čtverci. Tato metoda dává správnou první číslici, ale její přesnost je pouze jedna číslice - první číslice odmocniny z 35 je například 5, ale samotná odmocnina z 35 je téměř rovna 6.

Je lepší rozdělit interval mezi dvěma čtverci na polovinu. Takže odmocnina libovolného čísla mezi 25 a polovinou cesty do 36 (což je 30,5) se vyhodnotí jako 5, ostatní čísla větší než 30,5 až do 36 se vyhodnotí jako 6 [4] . Postup vyžaduje velmi málo aritmetiky k nalezení středu dvou produktů z tabulky. Zde je tabulka takových čísel:

A	nejbližší náměstí	$k={\sqrt {a))$ odhad
1 až 2,5	1 (= 1 2 )	jeden
2,5 až 6,5	4 (= 2 2 )	2
6.5 až 12.5	9 (= 3 2 )	3
12.5 až 20.5	16 (= 4 2 )	čtyři
20.5 až 30.5	25 (= 5 2 )	5
30,5 až 42,5	36 (= 6 2 )	6
42,5 až 56,5	49 (= 72 )	7
56,5 až 72,5	64 (= 82 )	osm
72,5 až 90,5	81 (= 9 2 )	9
90,5 až 100	100 (= 102 )	deset

Poslední operací bude vynásobení skóre k mocninou desítek dělených napůl, takže pro , ${\displaystyle S=a\cdot 10^{2n))$

{\sqrt {S}}\cca k\cdot 10^{n}

Metoda poskytuje přesnost na jednu platnou číslici, protože zaokrouhluje na nejlepší první číslici.

Metodu lze ve většině případů rozšířit na 3 platné číslice interpolací mezi nejbližšími čtverci. Jestliže , pak je přibližně rovno k plus zlomek rovný rozdílu mezi a a dělený rozdílem mezi dvěma čtverci: ${\displaystyle k^{2}\leqslant a<(k+1)^{2))$ ${\sqrt {a}}$ $k^{2}$

{\sqrt {a}}\cca k+R

kde

{\displaystyle R={\frac {(ak^{2})}{(k+1)^{2}-k^{2))))

Konečná operace, jak je uvedeno výše, je vynásobení výsledku mocninou deseti děleno napůl

{\sqrt {S}}={\sqrt {a}}\cdot 10^{n}\přibližně (k+R)\cdot 10^{n}

Číslo k je desetinná číslice a R je zlomek, který se má převést na desetinné číslo. Zlomek má obvykle jednu číslici v čitateli a jednu nebo dvě číslice ve jmenovateli, takže převod na desetinu lze provést mentálně.

Příklad: najděte druhou odmocninu z 75. , takže a je 75 a n je 0. Na základě násobilky by druhá odmocnina mantisy měla být 8 se zlomkem , protože , a , je příliš velké. Takže k je 8 , přičemž zlomek je desetinnou reprezentací R . Zlomek R má jak čitatele, tak i jmenovatele. 11/17 je o něco menší než 12/18, což je 2/3 nebo 0,67, takže 0,66 je dobrý odhad (zde je v pořádku odhadnout, protože chyba je malá). Hodnota kořene je tedy . √ 75 až tři platná čísla by byla 8,66, takže skóre na tři platná čísla je dobré. Ne všechny odhady využívající tuto metodu jsou tak přesné, ale jsou si docela blízké. $75=75\times 10^{2\cdot 0}$ $8\times 8=64$ $9\times 9=81$ $75-k^{2}=11$ $81-k^{2}=17$ $8+0{,}66=8{,}66$

Binární ohodnocení

Když je práce vykonávána v binárním systému (řekněme v počítačovém procesoru), je vyjádřena jako , kde , druhou odmocninu lze odhadnout jako $S$ ${\displaystyle a\times 2^{2n))$ ${\displaystyle 0{,}1_{2}\leqslant a<10_{2))$ ${\sqrt {S}}={\sqrt {a}}\times 2^{n}$

{\sqrt {S}}\approx (0{,}485+0{,}485\cdot a)\cdot 2^{n}

což je regrese nejmenších čtverců přes 3 nejvýznamnější bity. má maximální absolutní chybu 0,0408 v bodě =2 a maximální relativní chybu 3,0 % v bodě =1. Pro výpočty je vhodný zaokrouhlený odhad (protože koeficienty jsou mocniny 2) ${\sqrt {a}}$ $A$ $A$

{\sqrt {S}}\approx (0{,}5+0{,}5\cdot a)\cdot 2^{n}

[5]

který má maximální absolutní chybu 0,086 v bodě 2 a maximální relativní chybu 6,1 % v bodech a . $a=0{,}5$ $a=2{,}0$

Pro binární aproximaci dává Od , odhad dává absolutní chybu 19 a relativní chybu 5,3 %. Relativní chyba je o něco menší než 1/2 4 , takže aproximace je přesná na 4+ bity. $S=125348=1\;1110\;1001\;1010\;0100_{2}=1{,}1110\;1001\;1010\;0100_{2}\times 2^{16}\,$ ${\sqrt {S}}\approx (0{,}5+0{,}5\cdot a)\cdot 2^{8}=1{,}0111\;0100\;1101\;0010_ {2}\cdot 1\;0000\;0000_{2}=1{,}456\cdot 256=372{,}8.$ ${\sqrt {125348}}=354{,}0$

Odhad pro až 8 bitů lze získat vyhledáním v tabulce pro nejvýznamnějších 8 bitů , protože nejvýznamnější bit je implicitní ve většině reprezentací s pohyblivou řádovou čárkou a nejméně významné bity po 8 bitech musí být zaokrouhleny. Tabulka obsahuje 256 bajtů předem vypočítaných 8bitových odmocnin. Například pro index 11101101 2 , což je 1,8515625 10 v desítkové soustavě , je hodnota v tabulce 10101110 2 , což je 1,359375 10 v desítkové soustavě , odmocnina z 1,8515625 bitů 10 až 10 až 10). $A$ $A$

Babylonská metoda

Snad prvním algoritmem používaným pro aproximaci je metoda známá jako babylonská metoda , ačkoli neexistuje žádný přímý důkaz, jiný než hypotetický závěr, že babylonští matematici používali tuto metodu [6] . Tato metoda je také známá jako Heronova metoda podle řeckého matematika Herona z prvního století , který poprvé explicitně popsal metodu ve své 60leté práci Metrica [7] Základní technika spočívá v tom, že pokud je x větší než čtverec odmocnina nezáporného reálného čísla S , pak bude odmocnina menší a naopak. Je tedy rozumné očekávat, že průměr těchto dvou čísel bude blíže odmocnině (formální důkaz této skutečnosti je založen na nerovnosti o aritmetickém, geometrickém a harmonickém průměru , což ukazuje, že tento průměr je vždy větší než čtverec kořen, který zajišťuje konvergenci). Metoda je ekvivalentní použití Newtonovy metody k řešení rovnice . ${\sqrt {S))$ ${\tfrac {S}{x}}$ $x^{2}-S=0$

Přesněji, pokud x je počáteční odhad pro , a chyba v našem odhadu je taková, že , můžeme rozbalit závorky a získat ${\sqrt {S))$ $\varepsilon$ $S=(x+\varepsilon )^{2}$

\varepsilon ={\frac {Sx^{2}}{2x+\varepsilon }}\cca {\frac {Sx^{2}}{2x}},

protože .

\varepsilon \ll x

Proto můžeme chybu kompenzovat a aktualizovat náš starý odhad

x+\varepsilon \approx x+{\frac {Sx^{2}}{2x}}={\frac {S+x^{2}}{2x}}={\frac {{\frac {S }{x}}+x}{2}}\equiv x_{\text{updated}}

Protože vypočítaná chyba nebyla přesná, stane se naší další aproximací. Proces aktualizace pokračuje, dokud nedosáhneme požadované přesnosti. Jde o algoritmus s kvadratickou konvergencí , což znamená, že počet správných číslic aproximace (zhruba řečeno) se s každou iterací zdvojnásobuje. Funguje to takto:

Začneme s libovolnou kladnou počáteční hodnotou (čím blíže ke skutečné odmocnině S , tím lépe). $x_{0}$
Nastavíme rovno průměru mezi a ( pro aproximaci geometrického průměru používáme aritmetický průměr ). $x_{{n+1}}$ $x_{n}$ ${\displaystyle {\tfrac {S}{x_{n))))$
Opakujte krok 2, dokud nedosáhneme požadované přesnosti.

Algoritmus může být reprezentován následovně:

x_{0}\cca {\sqrt {S)),

x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right),

{\sqrt {S}}=\lim _{n\to \infty }x_{n}.

Algoritmus také funguje dobře pro p - adická čísla , ale nelze jej použít k identifikaci skutečných odmocnin s p -adickými odmocninami. Lze například sestrojit posloupnost racionálních čísel získaných touto metodou, která konverguje k +3 v případě reálných čísel, ale k -3 ve 2-adických číslech.

Příklad

Pro výpočet √ S , kde S = 125348, na šest platných číslic, použijte metodu hrubého odhadu popsanou výše

{\begin{aligned}{\begin{array}{rlll}x_{0}&=6\cdot 10^{2}&&=600{,}000\\[0,3em]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}}}\vpravo) &={\frac {1}{2}}\left(354{,}045+{\frac {125348}{354{,}045}}\right)&=354{,}045\end{array} }\end{aligned}}

Proto . ${\sqrt {125348}}\cca 354{,}045$

Konvergence

Předpokládejme, že x 0 > 0 a S > 0. Potom pro libovolné n x n > 0. Relativní chyba x n je definována jako

\varepsilon _{n}={\frac {x_{n}}{\sqrt {S}}}-1>-1

a pak

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

Nyní se to dá ukázat

\varepsilon _{n+1}={\frac {\varepsilon _{n}^{2}}{2(1+\varepsilon _{n}})))\geqslant 0.

a následně

\varepsilon _{n+2}\leqslant \min \left\({\frac {\varepsilon _{n+1}^{2)){2)),{\frac {\varepsilon _{n +1}}{2}}\right\}

a to znamená zaručenou konvergenci a tato konvergence je kvadratická .

Konvergence v nejhorším případě

Pokud použijeme metodu hrubého odhadu s babylonskou metodou, pak nejhorší případy přesnosti v sestupném pořadí jsou:

{\begin{aligned}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}}

A pak stejně

\varepsilon _{1}\leqslant 2^{-2}.\,

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

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

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

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

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

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

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

Chyby zaokrouhlování oslabují konvergenci. Doporučuje se uložit alespoň jednu číslici navíc nad požadovanou přesnost x n , aby se minimalizovaly chyby zaokrouhlování.

Bakhshali metoda

Tato metoda pro nalezení aproximace druhé odmocniny byla napsána ve starověkém indickém rukopisu zvaném Bakhshali manuscript . Metoda je ekvivalentní dvěma iteracím babylonské metody s počáteční hodnotou x 0 . Algoritmus je tedy kvadraticky konvergentní, což znamená, že počet platných znamének aproximace se s každou iterací zvyšuje asi čtyřikrát [8] . Reprezentace algoritmu v moderní notaci je následující: Vypočítejte , nechť x 0 2 je počáteční aproximace ke kořenu S . Iterace se provádějí postupně ${\sqrt {S))$

{\begin{aligned}a_{n}&={\frac {S-x_{n}^{2}}{2x_{n}}},\\b_{n}&=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{aligned}}

To lze použít k vytvoření racionální aproximace k druhé odmocnině, počínaje celým číslem. Pokud je celé číslo vybrané blízko k S a je to rozdíl, jehož absolutní hodnota je minimalizována, pak lze první iteraci zapsat následovně: $x_{0}=N$ $N^2$ $d=SN^{2}$

{\sqrt {S}}\přibližně N+{\frac {d}{2N}}-{\frac {d^{2}}{8N^{3}+4Nd}}={\frac {8N ^{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)} }.

Bakhshaliho metoda může být zobecněna pro výpočet libovolného kořene, včetně zlomkových kořenů [9] .

Příklad

Použijme stejný příklad, který byl uveden pro babylonskou metodu. Nechť Pak dává první iterace $S=125348.$

{\begin{aligned}x_{0}&=600\\a_{1}&={\frac {125348-600^{2}}{2\times 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{aligned}}

Podobně dává druhá iterace

{\begin{aligned}a_{2}&={\frac {125348-357{,}186^{2}}{2\times 357{,}186}}&&=&-3{,} 126\\b_{2}&=357{,}186+(-3{,}126)&&=&354{,}060\\x_{2}&=354{,}06-{\frac {(- 3{,}1269)^{2}}{2\times 354{,}06}}&&=&354{,}046\end{aligned}}

Číslo podle čísla

Toto je metoda pro postupné hledání každé číslice odmocniny. Metoda je pomalejší než babylonská, ale má některé výhody

Je jednodušší vypočítat ručně.
Každý nalezený znak kořene je znám jako správný, to znamená, že se v dalších iteracích nezmění.
Pokud má reprezentace druhé odmocniny konečný počet číslic, algoritmus skončí po poslední nalezené číslici. Lze jej tedy použít k testování, že dané číslo je dokonalý čtverec .
Algoritmus pracuje v libovolné číselné soustavě a samozřejmě činnost algoritmu závisí na zvolené číselné soustavě.

Napierovy hole obsahují další zařízení pro provádění tohoto algoritmu. Algoritmus pro výpočet n-té kořenové číslice po číslici je zobecněním této metody.

Základní princip

Uvažujme nejprve případ nalezení druhé odmocniny čísla Z , což je druhá mocnina dvouciferného čísla XY , kde X je desítková číslice a Y je jedna číslice. My máme:

Z=(10X+Y)^{2}=100X^{2}+20XY+Y^{2}

Nejprve definujme hodnotu X . X je největší číslice taková, že X 2 nepřesahuje Z , ze které jsou poslední dvě číslice vypuštěny.

V další iteraci spojíme dvojici číslic tak, že X vynásobíme 2 a výsledek dáme na pozici desítek a pak se pokusíme zjistit, čemu se Y rovná .

Protože v našem případě je odpovědí přesná odmocnina, algoritmus se zastaví.

Stejný nápad lze rozšířit na výpočet libovolné druhé odmocniny. Představte si, že můžeme najít druhou odmocninu z N jako součet n kladných čísel takových, že

N=(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}.

Opětovným použitím identity

(x+y)^{2}=x^{2}+2xy+y^{2},

pravá strana může být reprezentována jako

{\begin{aligned}&(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}\\=&\,a_{1}^{ 2}+2a_{1}a_{2}+a_{2}^{2}+2(a_{1}+a_{2})a_{3}+a_{3}^{2}+\dotsb + 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 {zarovnaný}}

Tento výraz nám umožňuje najít druhou odmocninu postupným výběrem hodnot . Předpokládejme, že čísla již byla vybrána, pak je m-tý člen dán vztahem , kde je nalezená aproximace k druhé odmocnině. Nyní každý nový výběr musí vyhovovat rekurzi $a_{i}$ $a_{1},\ldots ,a_{m-1}$ $Y_{m}=[2P_{m-1}+a_{m}]a_{m},$ ${\displaystyle P_{m-1}=\sum _{i=1}^{m-1}a_{i))$ $dopoledne$

X_{m}=X_{m-1}-Y_{m},

takže pro všechny na počáteční hodnotě Pokud je nalezena přesná odmocnina. Pokud ne, pak součet dává vhodnou aproximaci k druhé odmocnině a bude to chyba aproximace. $X_{m}\geqslant 0$ $1\leqslant m\leqslant n,$ $X_{0}=N.$ $X_{n}=0,$ $a_{i}$ $X_n$

Například v desítkové soustavě máme

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

kde jsou ukazatele polohy číslic a koeficienty . V každém m-tém kroku výpočtu druhé odmocniny je nalezena přibližná druhá odmocnina. Velikostní a sčítací členy jsou dány vzorci $10^{ni}$ $a_{i}\in \{0,1,2,\ldots ,9\}$ $P_{m-1}$ $Y_{m}$

P_{m-1}=\sum _{i=1}^{m-1}a_{i}\cdot 10^{ni}=10^{n-m+1}\součet _{i =1}^{m-1}a_{i}\cdot 10^{mi-1},

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

Vzhledem k tomu, že indikátory polohy mají sudou mocninu 10, potřebujeme v libovolném m-tém kroku pracovat pouze s dvojicí nejvyšších číslic ve zbývajícím členu. Níže uvedená část organizuje tento postup. $Y_{m}$ $X_{m-1}$

Je zřejmé, že podobnou metodu lze použít k výpočtu druhé odmocniny v jakékoli číselné soustavě, ne nutně v desítkové soustavě. Například hledání druhé odmocniny číslici po číslici v binárním systému je docela efektivní, protože hodnota se hledá v malé sadě číslic {0,1}. Díky tomu je výpočet rychlejší, protože v každém kroku je hodnota rovna nebo rovna . Skutečnost, že existují pouze dvě možnosti pro , také usnadňuje výběr hodnoty v m-tém kroku výpočtu. Je to proto, že potřebujeme pouze zkontrolovat, že pro Pokud je tato podmínka splněna, vezmeme ; a pokud ne, pak bereme Také fakt, že násobení 2 se provádí posunem doleva, pomáhá ve výpočtech. $a_{i}$ $Y_{m}$ $Y_{m}=0$ $a_{m}=0$ $Y_{m}=2P_{m-1}+1$ $a_{m}=1$ $dopoledne$ $dopoledne$ ${\displaystyle Y_{m}\leqslant X_{m-1))$ $a_{m}=1.$ $a_{m}=1$ $a_{m}=0.$

Desetinná číselná soustava

Původní číslo zapišme v desítkovém tvaru. Čísla se zapisují podobným způsobem jako dělení pomocí algoritmu dlouhého dělení a stejně jako u dlouhého dělení bude druhá odmocnina zapsána na horní řádek. Nyní rozdělme čísla do dvojic, počínaje čárkou, na obou stranách. Desetinná čárka druhé odmocniny bude na desetinné čárce druhé mocniny. Jedna odmocnina se zapisuje přes dvojici odmocnin.

Začneme úplně vlevo a pro každou dvojici číslic provedeme následující postup:

Nejvyšší dvojici nepoužitých číslic sejmeme dolů (pokud jsou použity všechny číslice, napište "00") a zapíšeme je napravo od zbytku předchozího kroku (v prvním kroku není žádný zbytek). Jinými slovy, vynásobte zbytek 100 a přidejte dvě číslice. Toto bude aktuální hodnota c .
Najděte p , y a x takto:
- Nechť je součástí již nalezeného kořene , ignoruje desetinnou čárku. (Pro první krok p = 0.) ${\bold symbol {p}}$
- Určete největší číslo takové, že . Použijeme novou proměnnou . ${\tučný symbol {x}}$ $x(20p+x)\leqslant c$ ${\boldsymbol {y}}=x(20p+x)$
  - Všimněte si, že je to jen zdvojené p s číslicí x připojenou napravo . $20p+x$
  - Všimněte si, že x lze najít náhodným uhodnutím, jaké by mělo být c /(20• p ), při zkušebním výpočtu y se pak x vezme vyšší nebo nižší v závislosti na výsledku.
- Číslici umístíme jako další číslici odmocniny, tedy nad právě sníženou dvojici čtvercových číslic. Nyní se další hodnota p získá ze staré hodnoty pomocí vzorce . $X$ $p\times 10+x$
Odečtěte y od c a vytvořte nový zbytek.
Pokud je zbytek nula a nejsou k dispozici žádné další číslice pro posun dolů, algoritmus se zastaví. V opačném případě se vrátíme ke kroku 1 a provedeme další iteraci.

Příklady

Najděte druhou odmocninu 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 Algoritmus se zastaví: Odpověď 12.34

Binární číselná soustava

Tato sekce používá formalismus oddílu Výpočet číslice po číslici , s drobnými úpravami, že , a každá se rovná nebo . Nyní projdeme všechny od dolů k a vytvoříme přibližné řešení jako součet všech, pro které najdeme hodnotu. Abychom určili , zda nebo je rovno , vezmeme . Jestliže (tj. druhá mocnina naší aproximace včetně nepřesahuje původní čtverec), pak nastavíme , jinak nastavíme a . Abychom se vyhnuli kvadraturu v každém kroku, uložíme rozdíl a aktualizujeme ho při každé iteraci nastavením c . Zpočátku jsme nastavili pro největší s . $N^{2}=(a_{n}+\dotsb +a_{0})^{2}$ $dopoledne$ $2^{m}$ $0$
$2^{m}$ $2^{n}$ $2^0$ ${\displaystyle P_{m}=a_{n}+a_{n-1}+\ldots +a_{m))$ $a_{i}$
$dopoledne$ $2^{m}$ $0$ ${\displaystyle P_{m}=P_{m+1}+2^{m))$ ${\displaystyle P_{m}^{2}\leqslant N^{2))$ $2^{m}$ ${\displaystyle a_{m}=2^{m))$ $a_{m}=0$ $P_{m}=P_{m+1}$
${\displaystyle P_{m))$ ${\displaystyle X_{m}=N^{2}-P_{m}^{2))$ ${\displaystyle X_{m}=X_{m+1}-Y_{m))$ $Y_{m}=P_{m}-P_{m+1}=2P_{m+1}a_{m}+a_{m}^{2}$
$a_{n}=P_{n}=2^{n}$ $n$ ${\displaystyle (2^{n})^{2}=4^{n}\leqslant N^{2))$

Jako další optimalizaci ukládáme a , dva členy v případě, že není nula, v samostatných proměnných , : $P_{m+1}2^{m+1}$ $(2^{m})^{2}$ $Y_{m}$ $dopoledne$ ${\displaystyle c_{m))$ ${\displaystyle d_{m))$

c_{m}=P_{m+1}2^{m+1}

{\displaystyle d_{m}=(2^{m})^{2))

Y_{m}={\begin{cases}c_{m}+d_{m}&{\text{if }}a_{m}=2^{m}\\0&{\text{if } }a_{m}=0\end{cases}}

${\displaystyle c_{m))$ a lze je efektivně aktualizovat v každém kroku: ${\displaystyle d_{m))$

c_{m-1}=P_{m}2^{m}=(P_{m+1}+a_{m})2^{m}=P_{m+1}2^{m} +a_{m}2^{m}={\begin{cases}c_{m}/2+d_{m}&{\text{if }}a_{m}=2^{m}\\c_{ m}/2&{\text{if }}a_{m}=0\end{cases}}

d_{m-1}={\frac {d_{m}}{4}}

všimněte si, že

c_{-1}=P_{0}2^{0}=P_{0}=N

, což je konečný výsledek vrácený funkcí níže.

Implementace algoritmu v jazyce C [10] :

int32_t isqrt(int32_tn) { tvrdit(("vstupní hodnota musí být nezáporná", n > 0)); int32_t x = n; // int32_t c = 0; // // začíná nejvyšší mocninou čtyř <= n

X_{{n+1}}

c_n

d_{n}

int32_t d = 1 << 30; // Nastaví druhý nejvýznamnější bit na 1. // Stejné jako ((bez znaménka)INT32_MAX + 1) / 2. zatímco (d > n) d >>= 2; while (d != 0) // for { if (x >= c + d) // if , then { x -= c + d; // c = (c >> 1) + d; //

{\displaystyle d_{n}\tečky d_{0))

{\displaystyle X_{m+1}\geqslant Y_{m))

{\displaystyle a_{m}=2^{m))

{\displaystyle X_{m}=X_{m+1}-Y_{m))

c{m-1}=c_{m}/2+d_{m}(a_{=}2^{m})

} jinak c >>= 1; // d >>= 2; //

c_{m-1}=c_{m}/2(a_{m}=0)

d_{m-1}=d_{m}/4

} návrat c; //

c_{{-1}}

}

Je možné implementovat rychlejší algoritmus v binárním i desítkovém zápisu, pokud se pro výběr použijí tabulky, to znamená, že implementace principu použití více paměti zkracuje dobu provádění [11] .

Exponenciální identita

Kapesní kalkulačky obvykle implementují dobré exponenciální a přirozené logaritmické programy . Výpočet druhé odmocniny S se pak provede pomocí vlastností logaritmů ( ) a exponenciál ( ): $\ln x^{n}=n\ln x$ $e^{\ln x}=x$

{\sqrt {S}}=e^{{\frac {1}{2}}\ln S}.

Jmenovatel zlomku odpovídá n-té odmocnině. V našem případě je jmenovatelem 2. Stejná identita se používá k výpočtu druhé odmocniny pomocí tabulek logaritmů nebo logaritmických pravidel .

Iterační metoda se dvěma proměnnými

Tato metoda je použitelná pro nalezení druhé odmocniny z a nejlépe konverguje pro . To však není významné omezení pro výpočty na počítačích, protože v reprezentaci binárních čísel s pohyblivou řádovou čárkou a pevnou řádovou čárkou je triviální násobit celočíselnou mocninou 4 a poté opravit na požadovanou mocninu 2 změnou exponent nebo posun. Lze jej tedy posunout v rámci . Níže uvedená metoda navíc nepoužívá obecné dělení, ale pouze sčítání, odčítání, násobení a dělení mocninou dvou. Poslední z těchto akcí se provádí triviálně. Nevýhodou metody je akumulace chyb, na rozdíl od iteračních metod s jednou proměnnou jako je babylonská. $0<S<3\,\!$ $S\cca 1$ $S\,\!$ ${\sqrt {S))$ $S\,\!$ ${\frac {1}{2}}\leqslant S<2$

Počáteční krok metody

a_{0}=S\,\!

c_{0}=S-1\,\!

Iterativní kroky

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

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

Potom (pro ). $a_{n}\rightarrow {\sqrt {S))$ $c_{n}\rightarrow 0$

Všimněte si, že konvergence , a tedy , je kvadratická. $c_{n}\,\!$ $a_{n}\,\!$

Důkaz metody je poměrně jednoduchý. Nejprve přepíšeme iterační definici jako $c_{n}\,\!$

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

Nyní je to přímo dokázáno

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

a proto konvergence k požadovanému výsledku je zajištěna konvergencí k 0, což zase vyplývá z . $a_{n}\,\!$ ${\sqrt {S))$ $c_{n}\,\!$ $-1<c_{0}<2\,\!$

Tato metoda byla vyvinuta kolem roku 1950 M. W. Wilksem , D. J. Wheelerem a S. Gillem [12] pro použití v EDSAC , jednom z prvních elektronických počítačů [13] . Později byla metoda zobecněna na neodmocniny [14] .

Iterační metody pro výpočet převrácené hodnoty druhé odmocniny čísla

Následují iterační metody pro výpočet převrácené hodnoty druhé odmocniny S , tedy . Pokud se taková hodnota najde, zjistíme ji jednoduše vynásobením: . Tyto iterace používají pouze násobení a nepoužívají dělení. Protože metody jsou rychlejší než babylonská metoda . Metody jsou však nestabilní, pokud počáteční hodnota není blízká převrácené hodnotě kořenové hodnoty, iterace se rozcházejí. Proto může být výhodné nejprve iterovat babylonskou metodou pro hrubý odhad kořene, než začnete tyto metody používat. $1/{\sqrt {S}}$ ${\sqrt {S))$ ${\sqrt {S}}=S\cdot (1/{\sqrt {S}})$

Aplikace Newtonovy metody na rovnici vede k metodě, která konverguje kvadraticky a používá tři násobení v každém kroku: $(1/x^{2})-S=0$ $x_{n+1}={\frac {x_{n}}{2}}\cdot (3-S\cdot x_{n}^{2})=x_{n}\cdot \left( {\frac {3}{2}}-{\frac {S}{2}}\cdot x_{n}^{2}\right).$
Další iteraci získáme z Halleyovy metody , což je Householderova metoda druhého řádu. Metoda konverguje kubicky , ale používá pět násobení na iteraci: $y_{n}=S\cdot x_{n}^{2}$ $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}\vpravo)\vpravo)$ .
Při práci s pevnými čísly lze násobení 3 a dělení 8 provádět pomocí posunů a sčítání. Při práci s plovoucí desetinnou čárkou lze Halleyovu metodu zredukovat na čtyři násobení na iteraci předběžným výpočtem a úpravou všech ostatních konstant pro kompenzaci: ${\sqrt {\frac {3}{8}}}S$ $y_{n}={\sqrt {\frac {3}{8}}}S\cdot x_{n}^{2}$ , $x_{n+1}=x_{n}\cdot \left({\frac {15}{8}}-y_{n}\cdot \left({\sqrt {\frac {25}{6 }}}-y_{n}\vpravo)\vpravo)$ .

Goldschmidtův algoritmus

Některé počítače používají k výpočtu a současně Goldschmidtův algoritmus . Goldschmidtův algoritmus najde rychleji než iterace Newton-Rapson na počítačích se sdílenými operacemi sčítání násobení a buď zřetězeným procesorem s pohyblivou řádovou čárkou nebo dvěma nezávislými procesory s pohyblivou řádovou čárkou [15] . ${\sqrt {S))$ $1/{\sqrt {S}}$ ${\sqrt {S))$

První způsob, jak napsat Goldschmidtův algoritmus, začíná

b_{0}=S

Y_{0}\cca 1/{\sqrt {S))

(obvykle se používá vyhledávání v tabulce)

y_{0}=Y_{0}

x_{0}=Sy_{0}

a provádějí se iterace

{\displaystyle b_{n+1}=b_{n}Y_{n}^{2))

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

x_{n+1}=x_{n}Y_{n+1}

y_{n+1}=y_{n}Y_{n+1}

dokud se dostatečně neblíží 1 nebo dokud nebude proveden pevný počet iterací. Iterace konvergují k $bi}$

\lim _{n\to \infty }x_{n}={\sqrt {S))

\lim _{n\to \infty }y_{n}=1/{\sqrt {S))

Všimněte si, že můžete vynechat výpočet nebo , a pokud chcete obojí, můžete jej použít na konci namísto vyhodnocování při každé iteraci. $x_{n}$ $y_{n}$ $x_{n}=Sy_{n}$

Druhá metoda, využívající kombinované operace násobení a sčítání , začíná s

y_{0}\cca 1/{\sqrt {S))

(obvykle se používá vyhledávání v tabulce)

x_{0}=Sy_{0}

h_{0}=y_{0}/2

a provádějí se iterace

{\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))

dokud se dostatečně nepřiblíží k 0, nebo se provede pevný počet iterací. Hodnoty se sbližují $r_{i}$

\lim _{n\to \infty }x_{n}={\sqrt {S))

\lim _{n\to \infty }2h_{n}=1/{\sqrt {S))

Taylor Series

Pokud je N aproximací k , nejlepší aproximaci lze nalézt pomocí Taylorovy řady funkce druhé odmocniny : ${\sqrt {S))$

{\sqrt {N^{2}+d}}=N\sum _{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)

Pořadí konvergence se rovná počtu členů použitých v řadě. Při použití dvou termínů je metoda ekvivalentní babylonské metodě . Při použití tří termínů každá iterace používá téměř tolik operací jako Bakhshaliho aproximace , ale konvergence je slabší. Proto tato metoda není zvláště efektivní metodou výpočtu. Pro maximalizaci rychlosti konvergence by N mělo být zvoleno tak , aby bylo co nejmenší. ${\frac {|d|}{N^{2))}\,$

Pokračující expanze frakce

Kvadratické iracionality (čísla ve tvaru , kde a , b a c jsou celá čísla), a zejména druhé odmocniny celých čísel, mají periodické pokračování zlomků . Někdy není cílem najít číselnou hodnotu druhé odmocniny, ale rozšířit ji na pokračující zlomek , a tedy její racionální aproximaci. Nechť S je kladné číslo, jehož kořen má být nalezen. Nyní nechť a je počáteční aproximace a r je zbytek, pak můžeme napsat Protože máme , můžeme vyjádřit druhou odmocninu z S jako ${\frac {a+{\sqrt {b}}}{c}}$ $S=a^{2}+r.$ $Sa^{2}=({\sqrt {S}}+a)({\sqrt {S}}-a)=r$

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

Aplikováním tohoto výrazu pro na jmenovatel zlomku získáme ${\sqrt {S))$

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

kompaktní notace

Čitatel/jmenovatel expanze pokračovacího zlomku (viz vlevo) se obtížně zapisuje a také se obtížně vejde do stávajícího systému formátování dokumentu. Z tohoto důvodu byla vyvinuta speciální notace, která kompaktně reprezentuje celé číslo a periodické části spojitých zlomků. Jedna taková konvence používá lexikální „přerušovanou čáru“ k reprezentaci pruhu mezi čitatelem a jmenovatelem, což umožňuje, aby byl zlomek zapsán vodorovně místo svisle:

{\sqrt {S}}=a+{\frac {r|}{|2a}}+{\frac {r|}{|2a}}+{\frac {r|}{|2a}} +\cdots

Zde je každý horizontální tah (ve zlomku) reprezentován třemi tahy - dvěma vertikálními a jedním horizontálním, které se oddělují od . $r$ $2a$

Ještě kompaktnější zápis má zvláštní podobu

[a;2a,2a,2a,...]

U periodických pokračovacích zlomků (což jsou všechny odmocniny) je opakující se část uvedena pouze jednou s pruhem nad opakující se částí:

[a;{\overline {2a}}]

Pro √ 2 je hodnota 1, takže reprezentace bude $A$

[1;{\overline {2}}]

Po této cestě dostaneme zobecněný pokračovací zlomek pro druhou odmocninu ${\sqrt {S}}=a+{\cfrac {r}{2a+{\cfrac {r}{2a+{\cfrac {r}{2a+\ddots ))))))$

Prvním krokem při výpočtu takového zlomku pro získání druhé odmocniny je dosazení odmocniny a výběr počtu jmenovatelů. Například v kanonickém tvaru je 1 a pro √ 2 je 1, takže číselně pokračující zlomek pro 3 jmenovatele je $r$ $A$

{\sqrt {2}}\cca 1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}

Krok 2. Pokračovací zlomek se sroluje, jeden jmenovatel po druhém, aby se získal racionální zlomek, jehož čitatel a jmenovatel jsou celá čísla. Proces skládání pak vypadá takto (při použití prvních tří jmenovatelů):

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))))

=1+{\cfrac {5}{12}}={\frac {17}{12}}

Nakonec (krok 3) vydělíme čitatele jmenovatelem racionálního zlomku, abychom získali aproximaci kořene:

17\div 12=1{,}42

zaokrouhleno na tři desetinná místa.

Skutečná hodnota odmocniny √ 2 je 1,41 až tři platné číslice. Relativní chyba je 0,17 %, takže racionální zlomek je dobrý na téměř tři desetinná místa. Pokud vezmeme více jmenovatelů, dostaneme konzistentní zlepšení v aproximaci - čtyři jmenovatelé dávají zlomek , což dává téměř 4 číslice přesnosti atd. ${\frac {41}{29}}=1{,}4137$

Pokračující zlomky jsou k dispozici v tabulkách pro alespoň malá čísla a dobře známé konstanty. Pro libovolná čísla v desítkovém zápisu jsou předem vypočítané hodnoty s největší pravděpodobností k ničemu. Následující tabulka malých racionálních zlomků, nazývaných konvergenty , je odvozena z kanonických spojitých zlomků pro několik konstant:

√ S	pokračoval výstřel	~desetinné	Vhodné frakce
√2 _	$[1;{\overline {2}}]$	1,41421	${\frac {3}{2)),{\frac {7}{5)),{\frac {17}{12)),{\frac {41}{29)),{\frac {99}{70}}$
√ 3	$[1;{\overline {1,2}}]$	1,73205	${\frac {2}{1)),{\frac {5}{3)),{\frac {7}{4)),{\frac {19}{11)),{\frac {26}{15)),{\frac {71}{41)),{\frac {97}{56}}$
√5 _	$[2;{\overline {4}}]$	2,23607	${\frac {9}{4)),{\frac {38}{17)),{\frac {161}{72))$
√ 6	$[2;{\overline {2,4}}]$	2,44949	${\frac {5}{2)),{\frac {22}{9)),{\frac {49}{20)),{\frac {218}{89))$
√ 10	$[3;{\overline {6}}]$	3,16228	${\frac {19}{6)),{\frac {117}{37}}$
${\sqrt {\pi ))$	$[1;1,3,2,1,1,6...]$	1,77245	${\frac {2}{1)),{\frac {7}{4)),{\frac {16}{9)),{\frac {23}{13)),{\frac {39}{22}}$
${\sqrt {e))$	$[1;1,1,1,5,1,1...]$	1,64872	${\frac {2}{1)),{\frac {3}{2)),{\frac {5}{3)),{\frac {28}{17)),{\frac {33}{20)),{\frac {61}{37}}$
${\sqrt {\phi ))$	$[1;3,1,2,11,3,7...]$	1,27202	${\frac {4}{3)),{\frac {5}{4)),{\frac {14}{11))$

Poznámka: Všechny použitelné zlomky jsou uvedeny až do jmenovatele 99.

Obecně platí, že čím větší je jmenovatel racionálního zlomku, tím lepší je aproximace. Lze také ukázat, že odříznutí pokračování zlomku vede k racionálnímu zlomku s lepší aproximací ke kořeni kteréhokoli zlomku se jmenovatelem menším nebo rovným jmenovateli tohoto zlomku. Například žádný zlomek se jmenovatelem menším než 70 není tak dobrý jako 99/70 aproximující √2 .

Lukášova sekvenční metoda

Lucasova posloupnost prvního druhu je definována rekurzivní relací $U_{n}(P,Q)$

$U_{n}(P,Q)={\begin{cases}0&{\text{if }}n=0\\1&{\text{if }}n=1\\P\cdot U_{ n-1}(P,Q)-Q\cdot U_{n-2}(P,Q)&{\text{jinak}}\end{cases}}$

a jeho charakteristickým polynomem je

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

, má diskriminant a kořeny $D=P^{2}-4Q$

${\begin{matrix}x_{1}={\dfrac {P+{\sqrt {D))}{2)),&x_{2}={\dfrac {P-{\sqrt {D)) }{2}}\end{matrix}}}$

To vše dává následující kladnou hodnotu

$\lim _{n\to \infty }{\dfrac {U_{n+1}}{U_{n}}}=x_{1}$

. Pokud tedy chceme získat , můžeme si vybrat a a poté vypočítat pomocí a pro velké hodnoty . Nejúčinnější způsob výpočtu a − ${\sqrt {a}}$ $P=2$ $Q=1-a$ $x_{1}=1+{\sqrt {a))$ $U_{n+1}$ $U_{n}$ $n$ $U_{n+1}$ $U_{n}$

${\begin{bmatrix}U_{n}\\U_{n+1}\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin {bmatrix}U_{n-1}\\U_{n}\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}^{n}\cdot {\begin{bmatrix }} }U_{0}\\U_{1}\end{bmatrix}}$

Výsledek:

${\begin{bmatrix}0&1\\a-1&2\end{bmatrix}}^{n}\cdot {\begin{bmatrix}0\\1\end{bmatrix}}={\begin{bmatrix} U_{n}\\U_{n+1}\end{bmatrix}},$

a poté na : $n\to\infty$

${\sqrt {a}}={\frac {U_{n+1}}{U_{n}}}-1$

Aproximace závislé na reprezentaci s pohyblivou řádovou čárkou

Číslo je reprezentováno jako číslo s plovoucí desetinnou čárkou jako . Tento formát zápisu se také nazývá exponenciální zápis . Druhá odmocnina tohoto čísla se rovná a podobné vzorce lze použít pro odmocniny a logaritmy. To nezjednodušuje úlohu, ale pokud je vyžadována pouze aproximace, pak je to dobrý odhad řádu mantisy. Dále chápeme, že některé mocniny p se mohou ukázat jako liché, pak místo práce se zlomkovými mocninami základu jím násobíme a odečítáme jedničku od stupně, čímž je sudá. Zpřesněná reprezentace se převede na , takže druhá odmocnina bude . ${\displaystyle m\times b^{p))$ ${\sqrt {m}}\times b^{\tfrac {p}{2}}$ $b^{\tfrac {p}{2))$ ${\displaystyle 3141{,}59=3{,}14159{\times }10^{3))$ $31{,}4159{\times }10^{2}$ ${\sqrt {31.4159}}{\times }10^{1}$

Pokud se vezme pouze celočíselná část mantisy, může nabývat hodnot od 1 do 99 a lze ji použít jako index do tabulky 99 předem vypočítaných kořenů pro dokončení odhadu. Počítač využívající hexadecimální základ může vyžadovat větší tabulku, ale při použití základu 2 bude tabulka sestávat pouze ze tří hodnot - možné bity celočíselné části upřesněné reprezentace mantisy mohou být 01 (pokud je exponent sudý, takže nedochází k posunu a všimněte si, že normalizované číslo s pohyblivou řádovou čárkou má vždy nenulovou vysokou číslici), nebo pokud byl exponent lichý, 10 nebo 11, jedná se o první dva bity původní mantisy. Poté se 6,25 (= 110,01 v binárním systému) normalizuje na sudou mocninu, takže pár bitů mantisy je 01, zatímco 0,625 (= 0,101 v binárním kódu) se normalizuje na lichou mocninu, takže je vyžadován převod čísla na , a poté dvojice bitů bude 10. Všimněte si, že nejméně významný bit řádu se odráží v nejvýznamnějším bitu mantisy seskupené do párů. Sudý exponent má nejméně významný bit nula a čtyřnásobná mantisa bude začínat na nule, zatímco lichý exponent bude mít 1 v nejméně významném bitu a čtyřnásobná mantisa bude začínat na 1. Takže když je exponent poloviční, je ekvivalentní posunutí nejméně významného bitu exponentu na první bit párově seskupené mantisy. $1{,}1001\times 2^{2}$ $1{,}01\times 2^{-1}$ $10{,}1\times 2^{-2}$

Stůl se třemi prvky lze rozšířit o další mantisové bity. V případě počítačů je však často lepší namísto výpočtu interpolace v tabulce hledat jednodušší způsob výpočtu, který dává stejné výsledky. Vše nyní závisí na přesných detailech formátu reprezentace čísel a na operacích, které jsou k dispozici pro získání částí čísla a práci s nimi. Například Fortran obsahuje funkci EXPONENT(x)pro získání titulu. Úsilí vynaložené na získání dobré počáteční aproximace se vyplatí eliminací dalších iterací procesu zpřesňování, které by byly vyžadovány v případě špatné aproximace.

Mnoho počítačů se řídí standardem IEEE s pohyblivou řádovou čárkou (nebo poměrně blízkou reprezentací) a jako výchozí bod pro Newtonovu metodu lze získat velmi rychlou aproximaci druhé odmocniny. Technika této aproximace vychází ze skutečnosti, že formát plovoucího čísla (základ dva) aproximuje logaritmus základu 2. To znamená, $\log _{2}(m\times 2^{p})=p+\log _{2}(m)$

Takže pro 32bitové číslo IEEE s plovoucí desetinnou čárkou (ve kterém má exponent offset 127 [16] ), můžete získat přibližný logaritmus interpretací čísla jako 32bitového celého čísla, vynásobením a odečtením ofsetu 127, tzn $2^{-23}$

x_{\text{int}}\cdot 2^{-23}-127\approx \log _{2}(x).

Například číslo 1.0 v šestnáctkové soustavě je 0x3F800000, což může být reprezentováno jako při pohledu jako celé číslo. Pomocí výše uvedeného vzorce získáte podle očekávání od . Podobně získáte 0,5 z 1,5 (=0x3FC00000). $1065353216=127\cdot 2^{23}$ $1065353216\cdot 2^{-23}-127=0$ $\log _{2}(1{,}0)$

Chcete-li získat druhou odmocninu, vydělte logaritmus 2 a převeďte výsledek zpět. Níže uvedený program tuto myšlenku demonstruje. Všimněte si, že nejméně významný bit exponentu je záměrně přeložen do mantisy. Jedním ze způsobů, jak ospravedlnit kroky tohoto programu, za předpokladu, že se jedná o posun stupně a počet uložených bitů v mantise, je dokázat $b$ $n$

(((x_{\text{int}}/2^{n}-b)/2)+b)\cdot 2^{n}=(x_{\text{int}}-2^{ n})/2+((b+1)/2)\cdot 2^{n}.

/* Předpokládejme, že plovoucí číslo je ve formátu IEEE 754 */ #include <stdint.h> float sqrt_approx ( float z ) { union { float f ; uint32_t i ; } val = { z }; /* Převede typ bez změny bitové reprezentace */ /* * Dokažte, že * ((((val.i / 2^m) - b) / 2) + b) * 2^m = ((val.i - 2^m) / 2) + ((b + 1) / 2) * 2^m) * kde * b = offset výkonu * m = počet bitů v mantise */ val . i- = 1 << 23 ; /* Odečtěte 2^m. */ val . i >>= 1 ; /* Dělit 2. */ val . i += 1 << 29 ; /* Přidejte ((b + 1) / 2) * 2^m. */ vrátit val . f ; /* Znovu interpretovat jako plovoucí */ }

Tři aritmetické operace, které tvoří jádro funkce, lze znázornit na jednom řádku. Pro snížení maximální relativní chyby lze přidat další upřesnění. Tyto tři operace, bez redukce na reálné, lze tedy přepsat jako

val . i = ( 1 << 29 ) + ( val . i >> 1 ) - ( 1 << 22 ) + a ;

kde a je posun pro snížení aproximačních chyb. Například s a = 0 jsou výsledky přesné pro sudé mocniny 2 (např. 1,0), ale pro ostatní čísla bude výsledek poněkud velký (např. 1,5 pro 2,0 místo 1,414... s 6% chybou). Pro a = −0x4B0D2 je maximální relativní chyba snížena na ±3,5 %.

Pokud má být aproximace použita jako počáteční hodnota pro Newtonovu metodu v rovnici , pak je vhodnější inverzní tvar uvedený v další části. $(1/x^{2})-S=0$

Převrácená hodnota odmocniny

Varianta výše uvedeného postupu je uvedena níže a lze ji použít k výpočtu převrácené hodnoty odmocniny, tj . Tuto variantu napsal Greg Walsh. Aproximace posunu dává relativní chybu menší než 4 % a chyba se po jedné iteraci Newtonovy metody sníží na 0,15 % [17] . V počítačové grafice je to velmi účinný způsob normalizace vektoru. $x^{-{1 \over 2}}$

float invSqrt ( float x ) { float xhalf = 0,5f * x ; unie { plovák x ; int i ; } u ; u . x = x ; u . i = 0x5f375a86 - ( u . i >> 1 ); /* Další řádek lze opakovat libovolněkrát pro zvýšení přesnosti */ u . x = u . x * ( 1,5f - xpolovina * u . x * u . x ); vrátit u . x ; }

Některé VLSI implementují nalezení reciproké hodnoty druhé odmocniny pomocí polynomiálního odhadu následovaného Goldschmidtovou iterací [18] .

Odmocnina záporného nebo komplexního čísla

Jestliže , pak jeho hlavní kořen je roven $S<0$

{\sqrt {S}}={\sqrt {\vert S\vert }}\,\,i\,.

Jestliže , kde a a b jsou reálná čísla a , pak je jeho hlavní kořen rovna $S=a+bi$ $b\neq 0$

{\sqrt {S}}={\sqrt {\frac {\vert S\vert +a}{2}}}\,+\,\název operátora {sgn}(b){\sqrt {\frac {\vert S\vert -a}{2))}\,\,i\,.

To lze zkontrolovat pomocí kvadratury [19] [20] . Tady

{\displaystyle \vert S\vert ={\sqrt {a^{2}+b^{2))))

je modul čísla S . Hlavní odmocnina komplexního čísla je definována jako odmocnina s nezápornou reálnou částí.

Viz také

Algoritmus alpha max plus beta min
celá odmocnina

Poznámky

↑ Kromě hlavní odmocniny existuje i záporná druhá odmocnina, která se v absolutní hodnotě rovná hlavní odmocnině, ale s opačným znaménkem, kromě případu nuly, kdy existují dva stejné nulové odmocniny.
↑ Faktory dva a šest se používají, protože aproximují geometrický průměr dolních a horních možných hodnot s daným počtem číslic: a . ${\sqrt {{\sqrt {1}}\cdot {\sqrt {10}}}}={\sqrt[{4}]{10}}\cca 1{,}78\,$ ${\sqrt {{\sqrt {10}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{1000}}\cca 5{,}62\,$
↑ Nezaokrouhlený odhad má maximální absolutní chybu 2,65 v bodě 100 a maximální relativní chybu 26,5 % v bodech y=1, 10 a 100
↑ Pokud je číslo přesně v polovině mezi dvěma čtverci, například 30,5, vezměte větší číslo, což je v našem případě 6
↑ Toto je rovnice tečny k y=x 2 v bodě y=1.
↑ Fowler a Robson 1998 , str. 376.
↑ Heath, 1921 , str. 323–324.
↑ Bailey, Borwein, 2012 , str. 646–657.
↑ Pokles k bachšálskému rukopisu . Blog Simply Curious (5. června 2018). Získáno 21. prosince 2020. Archivováno z originálu dne 26. října 2020. (neurčitý)
↑ Rychlá celočíselná odmocnina od Mr. Wooův algoritmus počítadla (archivováno)
↑ Funkce celá odmocnina . Získáno 30. prosince 2021. Archivováno z originálu dne 30. září 2007. (neurčitý)
↑ Wilkes, Wheeler, Gill, 1951 .
↑ Campbell-Kelly, 2009 .
↑ Gower, 1958 , s. 142-143, 1958.
↑ Markstein, Peter (listopad 2004). Softwarová divize a druhá odmocnina pomocí Goldschmidtových algoritmů (PDF) . 6. konference o reálných číslech a počítačích . Dagstuhl , Německo. CiteSeerX 10.1.1.85.9648 . Archivováno (PDF) z originálu 2022-04-28 . Staženo 2021-12-30 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ K exponentu čísla se přidá 127, což umožňuje interpretovat exponent jako číslo bez znaménka.
↑ Fast Inverse Square Root Archived 6. února 2009 na Wayback Machine od Chrise Lomonta
↑ „Vysokorychlostní dvojitý přesný výpočet reciproké, dělení, druhé odmocniny a inverzní druhé odmocniny“ od José-Alejandra Piñeira a Javiera Díaze Bruguery 2002 (abstrakt)
↑ Abramowitz, Stegun, 1964 , s. 17.
↑ Cooke, 2008 , str. 59.

Literatura

David Fowler, Eleanor Robson. Aproximace druhé odmocniny ve starobabylonské matematice: YBC 7289 v kontextu // Historia Mathematica. - 1998. - T. 25 , no. 4 . - doi : 10.1006/hmat.1998.2209 .
Thomas Little Heath . Historie řecké matematiky. - Oxford: Clarendon Press, 1921. - V. 2. - S. 323-324.
David Bailey, Jonathan Borwein. Starověké indické čtvercové odmocniny: Cvičení z forenzní paleo-matematiky // Americký matematický měsíčník. - 2012. - T. 119 , č.p. 8 .
Miltonn Abramowitz, Irene A. Stegun. Oddíl 3.7.26 // Příručka matematických funkcí se vzorci, grafy a matematickými tabulkami . - Courier Dover Publications, 1964. - S. 17. - ISBN 978-0-486-61272-0 .
JC Gower. Poznámka k iterační metodě pro extrakci kořenů // The Computer Journal. - 1958. - T. 1 1 , čís. 3 .
M. Campbell-Kelly. Origin of Computing // Scientific American. - 2009. - září.
Roger Cooke. Klasická algebra: její povaha, původ a použití . - John Wiley and Sons, 2008. - ISBN 978-0-470-25952-8 .
MV Wilkes, DJ Wheeler, S. Gill. Příprava programů pro elektronický digitální počítač. — Addison-Wesley, 1951.

Metody výpočtu odmocnin

Počáteční skóre

Desetinné skóre

Binární ohodnocení

Babylonská metoda

Příklad

Konvergence

Bakhshali metoda

Příklad

Číslo podle čísla

Základní princip

Desetinná číselná soustava

Binární číselná soustava

Exponenciální identita

Iterační metoda se dvěma proměnnými

Iterační metody pro výpočet převrácené hodnoty druhé odmocniny čísla

Goldschmidtův algoritmus

Taylor Series

Pokračující expanze frakce

Lukášova sekvenční metoda

Aproximace závislé na reprezentaci s pohyblivou řádovou čárkou

Převrácená hodnota odmocniny

Odmocnina záporného nebo komplexního čísla

Viz také

Poznámky

Literatura

Odkazy Weisstein, Eric W. Algoritmy druhé odmocniny (anglicky) na webu Wolfram MathWorld .