A négyzetgyök kiszámításának módszerei

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. január 13-án felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A négyzetgyök módszerek számítási algoritmusok egy valós szám fő (vagy nem negatív) négyzetgyökeinek (általában , vagy ) hozzávetőleges értékeinek kiszámítására . Aritmetikailag ez azt jelenti, hogy ha adott egy szám , akkor az eljárás talál egy számot, amely önmagával szorozva ad . Algebrailag ez azt az eljárást jelenti, amely egy egyenlet nem negatív gyökerét keresi . Geometriailag ez egy adott területű négyzet oldalának megszerkesztését jelenti. ${\sqrt {S))$ ${\sqrt[{2}]{S))$ $S^{1/2}$ $S$ $S$ $x^{2}-S=0$

Minden valós számnak két gyöke van [1] . A legtöbb szám négyzetgyökének fő értéke egy végtelen decimális számjegysorozatú irracionális szám. Ennek eredményeként bármely ilyen négyzetgyök decimális ábrázolása csak közelítőleg számítható ki véges pontossággal (tizedesjegyek). Azonban még ha egy egész szám négyzetgyökét vesszük is, így az eredmény véges reprezentációt kap, a gyökszámításhoz használt eljárások egy része egyre nagyobb pontossággal csak közelítéssorozatot tud visszaadni.

A valós szám folyamatos tört ábrázolása használható decimális vagy bináris bővítés helyett, és ennek az ábrázolásnak megvan az a tulajdonsága, hogy bármely racionális szám négyzetgyökének (ami nem tökéletes négyzet) van egy periódusa, azaz a periódusos kiterjesztése hasonló ahhoz, A racionális számoknak a decimális számrendszer ismétlődő kiterjesztése van.

A legáltalánosabban elfogadott analitikai módszerek iteratívak, és két lépésből állnak: megfelelő kiindulási érték megtalálása, majd iteratív finomítása egy bizonyos leállási feltétel eléréséig. A kezdőérték tetszőleges szám lehet, de ha közelebb van a végértékhez, akkor kevesebb iterációra lesz szükség. A leghíresebb ilyen módszer, és még kényelmesebb a programozáshoz, a Newton-módszer, amely a derivált számításán alapul. Számos módszer, mint például a kézi Horner-osztás vagy sorozatbővítés, nem igényel kezdeti értéket. Egyes alkalmazásokban meg kell találni az egész szám négyzetgyököt , ami a legközelebbi egész számra kerekített négyzetgyök (ebben az esetben egy módosított eljárás is használható).

Az alkalmazott módszer attól függ, hogy az eredményt hogyan fogják használni (vagyis mennyire kell pontosnak lennie az eredménynek), és milyen eszközök állnak rendelkezésre. A módszereket nagyjából fel lehet bontani a mentálisan kivitelezhető, ceruzát és papírt igénylő módszerekre, vagy olyanokra, amelyek programként valósulnak meg és futnak számítógépen vagy más számítástechnikai eszközön. Figyelembe vehető a konvergencia sebessége (hány iterációra lesz szükség egy adott pontosság eléréséhez), az egyes műveletek (például osztás) vagy iterációk számítási bonyolultsága, valamint a hibák eloszlása (az eredmény pontossága).

A négyzetgyökök (különösen a 2 gyökér) megtalálásának eljárásai legalább az ókori Babilon (Kr. e. 17. század) óta ismertek. Az 1. századi Egyiptomból származó Heron módszere volt az első ellenőrizhető algoritmus a négyzetgyök kiszámítására. A modern analitikai módszerek az arab számok kora-reneszánsz idején történő Nyugat-Európában történő átvétele után kezdődtek . Napjainkban szinte minden számítástechnikai eszköz rendelkezik gyors és pontos négyzetgyök funkcióval, mint beépített programozási nyelvi konstrukció, könyvtárfüggvény vagy hardverutasítás, amely az alábbiakban ismertetett eljárásokon alapul.

Kezdeti pontszám

Sok iteratív négyzetgyök algoritmushoz kezdeti véletlenszerű érték szükséges. Ennek az értéknek nullától eltérő pozitív számnak kell lennie. 1 és között kell lennie , az a szám, amelynek négyzetgyökét keressük, mivel a négyzetgyöknek ezen határokon belül kell lennie. Ha a kezdeti érték nagyon messze van a gyökértől, az algoritmusnak több iterációra lesz szüksége. Ha a (vagy -val ) kezded , akkor az extra iterációkat fog megoldani, csak hogy megkapd a gyökér sorrendjét. Ezért hasznos a gyökér durva becslése, amely lehet, hogy gyenge, de könnyen kiszámítható. Általában minél pontosabb a becslés, annál gyorsabb a konvergencia. A Newton-módszer (más néven Babilóniai vagy Heron-módszer) esetében a gyökérnél valamivel nagyobb kezdeti érték gyorsabb konvergenciát ad, mint a gyökérnél kisebb kezdeti érték. $S$ $x_{0}=1$ $S$ ${\tfrac {1}{2}}\vert \log _{2}S\vert$

Általánosságban elmondható, hogy a becslést egy tetszőleges intervallumon veszik figyelembe, amelyben ismert, hogy tartalmaz egy gyököt (például ). A jobb becsléshez az intervallum szűkebb korlátait vagy jobb funkcionális közelítését jelenti. Ez utóbbi általában azt jelenti, hogy magasabb rendű polinomokat használunk a közelítéshez, bár nem minden közelítés használ polinomokat. Az elterjedt becslési módszerek a skaláris, lineáris, hiperbolikus és logaritmikus. A decimális rendszert általában mentális vagy papíron történő becsléshez használják. A kettes számrendszer alkalmasabb számítógépes kiértékelésre. Értékeléskor a kitevőt és a mantisszát általában külön kezeljük. $[x_{0},S/x_{0}]$ $f(x).$

Tizedespontszám

Általában a számot exponenciális formában adjuk meg , ahol , és n egy egész szám , akkor a lehetséges négyzetgyök becslése lehet , ahol . $S$ ${\displaystyle a\times 10^{2n))$ $1\leqslant a<100$ ${\sqrt {a}}\times 10^{n}$ $1\leqslant {\sqrt {a}}<10$

Skaláris becslések

A skaláris módszerek a teljes tartományt tálcákra osztják, és az egyes sávokban elért pontszámot egyetlen szám jelzi. Ha a tartományt egyetlen intervallumként kezeljük, akkor a számtani átlag (5,5) vagy a geometriai átlag () elfogadható becslés. Az abszolút és relatív becslések ezeknél a becsléseknél különböznek. Általában egyetlen szám nagyon pontatlan. Tovább A pontos becslések két vagy több intervallumra osztják a tartományt, de a skaláris becslés továbbra is nagyon durva. ${\sqrt {10}}\approx 3{,}16)\times 10^{n}$

Két geometriailag felosztott intervallum esetén a négyzetgyök [2] értékkel becsülhető . ${\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}}

Ennek a becslésnek a maximális abszolút hibája = 100, a maximális relatív hibája pedig 100% az = 1 pontban. ${\displaystyle 4\cdot 10^{n))$

Például egy dekompozíció esetén a pontszám a következő lesz . 246-os abszolút hibával és közel 70%-os relatív hibával. $S=125348$ ${\displaystyle 12{,}5348\times 10^{4))$ ${\sqrt {S}}\approx 6\cdot 10^{2}=600$ ${\sqrt {125348}}=354{,}0$

Lineáris becslés

A legjobb becslés és standard módszer a függvény lineáris közelítése kis íven. Ha, mint fent, a kitevőt kivonjuk a számból , és az intervallumot -ra redukáljuk , akkor az ív mentén valahol szekánst vagy érintőt használhatunk a közelítéshez, de a közvetlen legkisebb négyzetek regressziója pontosabb lesz. $y = x^2$ $S$ $[1100]$

A legkisebb négyzetek módszerével kapott egyenes minimálisra csökkenti a becslés és a függvény értéke közötti átlagos távolságot. Az egyenlete . Az együtthatók átalakítása és kerekítése után a számítások egyszerűsítése érdekében megkapjuk $y=8{,}7x-10$ $x=0{,}115y+1{,}15$

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

Ez a legjobb átlagos becslés , amelyet az intervallum függvényének egy lineáris közelítésével kaphatunk . A becslés maximális abszolút hibája az a=100 pontban 1,2, az S=1 és 10 pontokban a maximális relatív hibája 30% [3] . $y=x^2$ $[1100]$

A 10-zel való osztáshoz vonjon ki egyet a kitevőből , vagy képletesen szólva mozgassa a tizedesvesszőt egy pozícióval balra. Ennél a képletnél minden hozzáadott állandó 1 plusz egy kis növekmény kielégítő becslést ad, így nem szükséges megjegyezni a pontos számot. A közelítés (lekerekítve vagy nem kerekítve) egyetlen egyenes használatával, amely kivonja a régiót a pontosság szempontjából, legfeljebb egy helyes előjelet ad. A relatív hiba nagyobb, mint 1/2 2 , tehát kevesebb, mint 2 bitnyi információt ad. A pontosság erősen korlátozott, mivel a régió két nagyságrendet ölel fel, ami elég nagy egy ilyen becsléshez. $a$ $[1100]$

Lényegesen jobb becslést kaphatunk darabonkénti lineáris közelítéssel, azaz több olyan szegmens felhasználásával, amelyek közelítik az eredeti ív alpontját. Minél több szegmenst használunk, annál jobb a közelítés. Az érintők leggyakoribb használata. A kritikus pont az ív felosztása és az érintési pontok elhelyezése. Az ív y=1-ről y=100-ra való felosztásának hatékony módszere a geometriai módszer – két intervallum esetén az intervallumhatár az eredeti intervallum négyzetgyöke, 1 * 100, azaz és . Három intervallumban lesznek kockagyökök - , és , és így tovább. Két intervallum esetén ez egy nagyon kényelmes szám. Könnyű érintővonalakat szerezni az érintkezési pontokon és . Egyenleteik: és . Az egyenleteket megfordítva azt kapjuk, hogy a négyzetgyökök egyenlőek és . Akkor ehhez : $[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}}

A maximális abszolút értékek az intervallumok jobb oldali határain, az a=10 és 100 pontokon vannak, és egyenlők 0,54 és 1,7. A maximális relatív hibák az intervallumok végén, az a=1, 10 és 100 pontokban jelennek meg, és egyenlők 17%. 17% vagy 0,17. 1/10-nél nagyobbak, így a módszer egy jelentős számjegynél kisebb pontosságot ad.

Hiperbolikus becslés

Egyes esetekben a hiperbolikus becslés érvényes lehet, mivel a hiperbola egyben konvex görbe is, és jobban feküdhet az Y = x 2 ív mentén , mint egy egyenes. A hiperbolikus becslő számítási szempontból nehezebb, mert lebegőpontos számmal kell osztani. Egy majdnem optimális hiperbolikus közelítés az intervallum x 2 - jéhez . Az átalakulás után megkapjuk . Akkor ehhez : $[1100]$ $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}

A lebegőpontos osztásnak egy tizedesjegyig pontosnak kell lennie, mivel minden értékelés ezt a pontosságot adja, és az ilyen osztás gondolatban is elvégezhető. A hiperbolikus becslés átlagosan jobb, mint a skaláris vagy lineáris becslés. Maximális abszolút hibája 1,58 a 100. pontban, maximális relatív hibája 16,0% a 10. pontban. A legrosszabb esetben a=10 a pontszám 3,67. Ha 10-ről indulunk, és közvetlenül alkalmazzuk a Newton-Rapson iterációkat, akkor két iterációra van szükség, amelyek 3,66-ot eredményeznek, mielőtt elérjük a hiperbolikus becslés pontosságát. Egy tipikusabb esetben, mint a 75, a hiperbolikus becslés 8,00, és 5 Newton-Rapson iteráció szükséges 75-től kezdve, hogy pontosabb eredményt kapjunk.

Aritmetikai értékelés

A darabonkénti lineáris közelítéshez hasonló, de az algebrai egyenletek helyett csak aritmetikai műveleteket használó módszer a szorzótáblát fordítva használja - az 1 és 100 közötti számok négyzetgyöke valahol 1 és 10 között van, tehát mivel tudjuk, hogy a 25 pontos négyzet (5 × 5) és a 36 egy pontos négyzet (6 × 6), akkor a 25-nél nagyobb, de 36-nál kisebb szám négyzetgyöke 5-tel kezdődik. Hasonlóképpen a többi négyzet közötti számok esetében is. Ez a módszer megadja a helyes első számjegyet, de a pontossága csak egy számjegy - a 35 négyzetgyökének első számjegye például 5, de maga a 35 gyöke majdnem egyenlő 6-tal.

Jobb, ha két négyzet közötti intervallumot kettéosztjuk. Tehát a 25 és félig 36 közötti szám gyöke (ami 30,5) 5-re, a többi 30,5-nél nagyobb szám 36-ig 6-ra [4] . Az eljárás nagyon kevés aritmetikát igényel két szorzat közepének megtalálásához a táblázatból. Itt van egy táblázat az ilyen számokról:

a	legközelebbi tér	$k={\sqrt {a))$ est.
1-től 2,5-ig	1 (= 1 2 )	egy
2,5-6,5	4 (= 2 2 )	2
6,5-12,5	9 (= 3 2 )	3
12,5-től 20,5-ig	16 (= 4 2 )	négy
20,5-30,5	25 (= 5 2 )	5
30,5-42,5	36 (= 6 2 )	6
42,5-től 56,5-ig	49 (= 72 )	7
56,5-72,5	64 (= 82 )	nyolc
72,5-től 90,5-ig	81 (= 9 2 )	9
90,5 és 100 között	100 (= 102 )	tíz

A végső művelet a k pontszám szorzása a tízesek hatványával, felezve úgy, hogy , ${\displaystyle S=a\cdot 10^{2n))$

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

A módszer egy jelentős számjegy pontosságot ad, mert a legjobb első számjegyre kerekít.

A módszer a legtöbb esetben a legközelebbi négyzetek közötti interpolációval 3 jelentős számjegyre bővíthető. Ha , akkor megközelítőleg egyenlő k-val plusz egy tört, amely egyenlő az a és közötti különbséggel , osztva a két négyzet különbségével: ${\displaystyle k^{2}\leqslant a<(k+1)^{2))$ ${\sqrt {a}}$ $k^{2}$

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

ahol

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

A végső művelet, mint fent, az eredmény szorzása tíz hatványával osztva

{\sqrt {S}}={\sqrt {a}}\cdot 10^{n}\approx (k+R)\cdot 10^{n}

A k szám a decimális számjegy, az R pedig a tizedessé alakítandó tört. A törtnek általában egy számjegye van a számlálóban és egy vagy két számjegyű a nevezőben, így a tizedesjegyre való átalakítás gondolatban is elvégezhető.

Példa: keresse meg 75. négyzetgyökét , tehát a 75, n pedig 0. A szorzótábla alapján a mantissza négyzetgyökének 8 -nak kell lennie törttel, mert az a túl nagy. Tehát k 8 , ahol a tört R decimális reprezentációja . Az R törtnek van számlálója és nevezője is. A 11/17 valamivel kisebb, mint a 12/18, ami 2/3 vagy 0,67, tehát a 0,66 jó tipp (itt nem árt tippelni, mivel a hiba kicsi). Tehát a gyökér értéke . √ 75 három jelentős számjegyhez 8,66, tehát a három jelentős számjegyhez tartozó pontszám jó. Nem minden becslés ezzel a módszerrel olyan pontos, de meglehetősen közel áll hozzá. $75=75\x 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áris kiértékelés

Ha a munkát a bináris rendszerben (mondjuk egy számítógépes processzorban) végzik el, akkor ezt a következőképpen fejezzük ki: , ahol , a négyzetgyök úgy becsülhető meg $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}

ami a legkisebb négyzetek regressziója a 3 legjelentősebb bit felett. maximális abszolút hibája 0,0408 a =2 pontban és maximális relatív hibája 3,0% az =1 pontban. A számításokhoz a kerekített becslés kényelmes (mivel az együtthatók 2 hatványai) ${\sqrt {a}}$ $a$ $a$

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

[5]

amelynek maximális abszolút hibája a 2. pontban 0,086, és a és pontokban a maximális relatív hibája 6,1 % . $a=0{,}5$ $a=2{,}0$

A bináris közelítéshez Mivel a becslés 19 abszolút hibát és 5,3%-os relatív hibát ad. A relatív hiba valamivel kisebb, mint 1/2 4 , tehát a közelítés 4+ bitre pontos. $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$

Legfeljebb 8 bites becslést kaphat, ha a táblázatban megkeresi a legjelentősebb 8 bitet , mivel a legtöbb lebegőpontos ábrázolásban a legjelentősebb bit implicit módon szerepel, és a 8 bit utáni legkisebb jelentőségű biteket kerekíteni kell. A táblázat 256 bájt előre kiszámított 8 bites négyzetgyököt tartalmaz. Például az 11101101 2 indexnél, amely decimálisan 1,8515625 10, a táblázatban szereplő érték 10101110 2 , ami 1,359375 10 decimálisban , az 1,8515625 jel négyzetgyöke (10-8 bites előjel). $a$ $a$

Babilóniai módszer

Talán az első közelítéshez használt algoritmus a babiloni módszerként ismert módszer , bár a hipotetikus következtetésen kívül nincs közvetlen bizonyíték arra, hogy a babiloni matematikusok ezt a módszert használták volna [6] . A módszert Heron-módszernek is nevezik, az első századi görög matematikus, Heron után, aki 60 éves Metrica című munkájában [7] adta meg a módszer első explicit leírását.Az alaptechnika az, hogy ha x nagyobb, mint a négyzet gyöke egy nem negatív S valós szám, akkor kisebb lesz a gyök és fordítva. Ezért indokolt azt várni, hogy ennek a két számnak az átlaga közelebb legyen a gyökhöz (ennek formális bizonyítása a számtani, geometriai és harmonikus átlag egyenlőtlenségén alapul , ami azt mutatja, hogy ez az átlag mindig nagyobb, mint a négyzet gyökér, amely biztosítja a konvergenciát). A módszer egyenértékű a Newton-módszer használatával az egyenlet megoldására . ${\sqrt {S))$ ${\tfrac {S}{x}}$ $x^{2}-S=0$

Pontosabban, ha x a kezdeti tippje , és a becslésünk hibája olyan, hogy , akkor kibonthatjuk a zárójeleket, és megkapjuk ${\sqrt {S))$ $\varepsilon$ $S=(x+\varepsilon )^{2}$

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

mert .

\varepsilon \ll x

Ezért kompenzálhatjuk a hibát és frissíthetjük régi becslésünket

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

Mivel a számított hiba nem volt pontos, ez lesz a következő közelítésünk. A frissítési folyamat addig folytatódik, amíg el nem érjük a kívánt pontosságot. Ez egy másodfokú konvergenciájú algoritmus , ami azt jelenti, hogy a közelítés helyes számjegyeinek száma (nagyjából) minden iterációval megduplázódik. Ez így működik:

Bármilyen pozitív kezdeti értékkel kezdjük (minél közelebb van S valódi négyzetgyökéhez , annál jobb). $x_{0}$
A és közötti átlagot egyenlőnek állítjuk be ( a geometriai átlag közelítésére a számtani átlagot használjuk ). $x_{{n+1}}$ $x_{n}$ ${\displaystyle {\tfrac {S}{x_{n))))$
Ismételje meg a 2. lépést, amíg el nem éri a kívánt pontosságot.

Az algoritmus a következőképpen ábrázolható:

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

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

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

Az algoritmus p - adikus számok esetén is jól működik , de nem használható valós négyzetgyökök p - adikus négyzetgyökök azonosítására. Például megalkotható az ezzel a módszerrel kapott racionális számsorozat, amely valós számok esetén +3-hoz, 2-adikus számokban -3-hoz konvergál.

Példa

A √ S kiszámításához , ahol S = 125348, hat jelentős számjegyre, használja a fent leírt durva becslési módszert

{\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}}\jobbra)&=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}}}\jobbra)&={\frac {1}{2}}\left(354{,}059+{\frac {125348}{354{,}059}}\jobbra)&=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}}\jobbra)&=354{,}045\end{tömb} }\end{igazított}}

Ezért . ${\sqrt {125348}}\kb. 354{,}045$

Konvergencia

Tegyük fel, hogy x 0 > 0 és S > 0. Ekkor tetszőleges n x n > 0 esetén. A relatív hiba x n :

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

és akkor

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

Most ezt meg lehet mutatni

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

és ebből következően

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

és ez garantált konvergenciát jelent, és ez a konvergencia másodfokú .

Konvergencia a legrosszabb esetben

Ha durva becslési módszert használunk a babiloni módszerrel, akkor csökkenő sorrendben a pontosság legrosszabb esetei a következők:

{\begin{aligned}S&=1;&x_{0}&=2;&x_{1}&=1{,}250;&\varepszilon _{1}&=0{,}250.\\ S&=10;&x_{0}&=2;&x_{1}&=3{,}500;&\varepszilon _{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{igazított}}

És akkor különben is

\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}.\,

A kerekítési hibák gyengítik a konvergenciát. Javasoljuk, hogy legalább egy plusz számjegyet tároljon a kívánt x n pontosság felett , hogy minimalizálja a kerekítési hibákat.

Bakhshali módszer

Ezt a négyzetgyök közelítési módszert egy ősi indiai kéziratban írták, amelyet Bakhshali-kéziratnak neveztek . A módszer ekvivalens a babiloni módszer két iterációjával x 0 kezdeti értékkel . Így az algoritmus kvadratikusan konvergens, ami azt jelenti, hogy a közelítés érvényes előjeleinek száma minden iterációval körülbelül négyszeresére nő [8] . Az algoritmus modern jelöléssel való ábrázolása a következő: Számítsa ki , legyen x 0 2 az S gyök kezdeti közelítése . Az iterációkat szekvenciálisan hajtják végre ${\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{igazított}}

Ezzel fel lehet építeni egy racionális közelítést a négyzetgyökhöz, egész számmal kezdve. Ha egy S -hez közeli egész számot választunk, és az a különbség, amelynek abszolút értékét minimalizáljuk, akkor az első iteráció a következőképpen írható fel: $x_{0}=N$ $N^2$ $d=SN^{2}$

{\sqrt {S}}\approx 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)} }.

Bakhshali módszere általánosítható tetszőleges gyök kiszámítására, beleértve a törtgyököket is [9] .

Példa

Használjuk ugyanazt a példát, amelyet a babiloni módszerre adtunk. Legyen Akkor az első iteráció megadja $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}}

Hasonlóképpen a második iteráció is megadja

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

Számonkénti szám

Ez egy módszer a négyzetgyök egyes számjegyeinek szekvenciális megkeresésére. A módszer lassabb, mint a babiloni, de van néhány előnye

Könnyebb manuálisan számolni.
A gyökér minden egyes talált jele ismert, hogy helyes, vagyis a következő iterációk során nem változik meg.
Ha a négyzetgyök reprezentáció véges számú számjegyet tartalmaz, az algoritmus az utolsó talált számjegy után véget ér. Így ellenőrizhető, hogy egy adott szám tökéletes négyzet -e .
Az algoritmus bármilyen számrendszerben működik , és természetesen az algoritmus működése a választott számrendszertől függ.

A Napier botjai további lehetőségeket tartalmaznak ennek az algoritmusnak a végrehajtásához. Az n-edik gyökér számjegyenkénti kiszámítására szolgáló algoritmus ennek a módszernek az általánosítása.

Alapelv

Tekintsük először azt az esetet, amikor egy Z szám négyzetgyökét találjuk meg , amely egy XY kétjegyű szám négyzete , ahol X a tízes számjegy, Y pedig az egyes számjegy. Nekünk van:

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

Először is határozzuk meg X értékét . X a legnagyobb számjegy, amelynél az X 2 nem haladja meg a Z -t, amelyből az utolsó két számjegy kimarad.

A következő iterációban úgy kötünk össze egy számpárt, hogy megszorozzuk X -et 2-vel, és az eredményt tízes helyzetbe tesszük, majd megpróbáljuk kideríteni, hogy Y mennyivel egyenlő .

Mivel esetünkben a válasz a pontos négyzetgyök, az algoritmus leáll.

Ugyanez az ötlet kiterjeszthető tetszőleges négyzetgyök kiszámítására. Képzeljük el, hogy N négyzetgyökét n pozitív szám összegeként találhatjuk meg úgy, hogy

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

Az identitás újrafelhasználásával

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

a jobb oldalt úgy ábrázolhatjuk

{\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}+\pontok +\left[2\left(\sum _{i=1}^{n-1}a_{i}\right)+a_{n}\right]a_{n}.\end {igazított}}

Ez a kifejezés lehetővé teszi a négyzetgyök meghatározását az értékek egymást követő kiválasztásával . Tegyük fel, hogy a számok már ki vannak választva, akkor az m-edik tagot adja meg , ahol a négyzetgyök talált közelítése. Most minden új kijelölésnek meg kell felelnie a rekurziónak $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))$ $a_m$

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

tehát mindenre a kezdeti értéknél Ha a pontos négyzetgyök megtalálható. Ha nem, akkor az összeg megfelelő közelítést ad a négyzetgyökhöz, és közelítési hiba lesz. $X_{m}\geqslant 0$ $1\leqslant m\leqslant n,$ $X_{0}=N.$ $X_{n}=0,$ $a_{i}$ $X_n$

Például tizedesben van

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

ahol a számjegyek helyzetének mutatói és az együtthatók . A négyzetgyök kiszámításának minden m-edik lépésében egy közelítő négyzetgyök található. A nagyságrendet és az összegezhető tagokat a képletek adják meg ${\displaystyle 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}\sum _{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)}.

Mivel a helyzetjelzők páros hatványa 10, így bármelyik m-edik lépésben csak a maradék tag legmagasabb számjegypárjával kell dolgoznunk. Az alábbi szakasz ezt az eljárást szervezi. $Y_{m}$ $X_{m-1}$

Nyilvánvalóan hasonló módszerrel bármilyen számrendszerben ki lehet számítani a négyzetgyököt, nem feltétlenül decimálisan. Például a négyzetgyök számjegyenkénti megkeresése binárisan elég hatékony, mert az értéket a kis számjegykészletben (0,1}) keresi a rendszer. Ez gyorsabbá teszi a számítást, mivel minden lépésben az érték egyenlő vagy egyenlő azzal . Az a tény, hogy csak két lehetőség van, szintén megkönnyíti az érték kiválasztását a számítás m-edik lépésében. Ennek az az oka, hogy csak azt kell ellenőriznünk, hogy a Ha ez a feltétel teljesül, akkor a ; és ha nem, akkor azt is vesszük, hogy a 2-vel való szorzás balra tolással történik, segít a számításokban. $a_{i}$ $Y_{m}$ $Y_{m}=0$ $a_{m}=0$ $Y_{m}=2P_{m-1}+1$ $a_{m}=1$ $a_m$ $a_m$ ${\displaystyle Y_{m}\leqslant X_{m-1))$ $a_{m}=1.$ $a_{m}=1$ $a_{m}=0.$

Tizedes számrendszer

Írjuk fel az eredeti számot decimális formában. A számokat az osztáshoz hasonlóan egy hosszú osztási algoritmussal írjuk fel , és a hosszú osztáshoz hasonlóan a négyzetgyök a felső sorba kerül. Most bontsuk párokra a számokat, vesszővel kezdve, mindkét oldalán. A négyzetgyök tizedespontja a négyzet tizedespontján lesz. Egy négyzetgyök számjegyet írunk egy négyzetgyök számjegypárra.

A bal szélső pozícióból kiindulva minden egyes számpárnál a következő eljárást hajtjuk végre:

Levisszük a fel nem használt számjegyek legmagasabb párját (ha az összes számjegyet használjuk, írjunk "00"-t), és az előző lépés maradékától jobbra írjuk (az első lépésnél nincs maradék). Más szóval, szorozza meg a maradékot 100-zal, és adjon hozzá két számjegyet. Ez lesz a c aktuális értéke .
Keresse meg p , y és x értékét így:
- Legyen a már megtalált gyökér része , figyelmen kívül hagyva a tizedesvesszőt. (Az első lépésnél p = 0.) ${\bold symbol {p}}$
- Határozzuk meg a legnagyobb számot úgy, hogy . Új változót fogunk használni . ${\félkövér szimbólum {x}}$ $x(20p+x)\leqslant c$ ${\boldsymbol {y}}=x(20p+x)$
  - Jegyezzük meg, hogy a p csak megduplázódik , és a jobb oldalon hozzá van fűzve az x számjegy . $20p+x$
  - Vegyük észre, hogy x -et úgy találhatjuk meg, hogy véletlenszerűen kitaláljuk, mekkora legyen c /(20• p ) y próbaszámításával , majd x értéket az eredménytől függően magasabbra vagy alacsonyabbra vesszük.
- A számjegyet a gyökér következő számjegyeként helyezzük el, vagyis az éppen leeresztett négyzetszámjegypár fölé. Most p következő értékét a régi értékből kapjuk a képlet segítségével . $x$ $p\times 10+x$
Vonja ki y -t c -ből , hogy új maradékot képezzen.
Ha a maradék nulla, és nincs több lefelé mozgatható számjegy, az algoritmus leáll. Ellenkező esetben visszatérünk az 1. lépéshez, és végrehajtjuk a következő iterációt.

Példák

Keresse meg a 152,2756 négyzetgyökét.

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 év = (20+x)*x = 22*2 = 44 08 27 243*3 <= 827 < 244*4 x = 3 07 29 év = (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 leáll: Válasz 12.34

Bináris számrendszer

Ez a szakasz a Számjegyenkénti számítás szakasz formalizmusát használja , kisebb módosításokkal, hogy , és mindegyik egyenlő vagy . Most végigfuttatjuk az összeset lefelétől , és hozzávetőleges megoldást készítünk mindazok összegeként, amelyeknek értéket találunk. Annak meghatározásához, hogy egyenlő-e vagy egyenlő -e , vesszük . Ha (vagyis a közelítésünk négyzete beleértve nem haladja meg az eredeti négyzetet), akkor beállítjuk , ellenkező esetben és . Az egyes lépéseknél a négyzetesítés elkerülése érdekében eltároljuk a különbséget , és minden iterációnál frissítjük a c beállításával . Kezdetben a legnagyobbat állítottuk be a -val . $N^{2}=(a_{n}+\dotsb +a_{0})^{2}$ $a_m$ $2^{m}$ $0$
$2^{m}$ $2^{n}$ $2^0$ ${\displaystyle P_{m}=a_{n}+a_{n-1}+\ldots +a_{m))$ $a_{i}$
$a_m$ $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$ $(2^{n})^{2}=4^{n}\leqslant N^{2}$

Kiegészítő optimalizálásként a és , két tagot tárolunk abban az esetben, ha nem nulla, külön változókban , : $P_{m+1}2^{m+1}$ $(2^{m})^{2}$ $Y_{m}$ $a_m$ ${\displaystyle c_{m))$ ${\displaystyle d_{m))$

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

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))$ és minden lépésben hatékonyan frissíthető: ${\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}}

vegye észre, az

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

, ami az alábbi függvény által visszaadott végeredmény.

Az algoritmus implementációja C nyelven [10] :

int32_t isqrt(int32_tn) { assert(("a bemeneti érték nem lehet negatív", n > 0)); int32_t x = n; // int32_t c = 0; // // négy <= n legnagyobb hatványával kezdődik

X_{{n+1}}

c_n

d_{n}

int32_t d = 1 << 30; // A második legjelentősebb bitet állítsa 1-re. // Ugyanaz, mint ((előjel nélküli)INT32_MAX + 1) / 2. míg (d > n) d >>= 2; while (d != 0) // for { if (x >= c + d) // if , akkor { x -= c + d; // c = (c >> 1) + d; //

{\displaystyle d_{n}\dots 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})

} más c >>= 1; // d >>= 2; //

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

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

} vissza c; //

c_{{-1}}

}

Gyorsabb algoritmus valósítható meg bináris és decimális jelölésben is, ha táblákat használunk a kijelöléshez, vagyis a több memóriahasználat elvének megvalósítása csökkenti a végrehajtási időt [11] .

Exponenciális identitás

A zsebszámológépek általában jó exponenciális és természetes logaritmus programokat valósítanak meg . Ezután az S négyzetgyök kiszámítása a logaritmusok ( ) és az exponenciálisok ( ) tulajdonságainak felhasználásával történik: $\ln x^{n}=n\ln x$ $e^{\ln x}=x$

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

A tört nevezője az n- edik gyökérnek felel meg. Esetünkben a nevező 2. Ugyanezt az azonosságot használjuk a négyzetgyök kiszámításához logaritmustáblázatok vagy diaszabályok segítségével .

Egy iteratív módszer két változóval

Ez a módszer a négyzetgyökének meghatározására alkalmazható, és a legjobban konvergál . Ez azonban nem jelent jelentős korlátot a számítógépes számítások számára, mivel a bináris számok lebegőpontos és fixpontos ábrázolásánál triviális 4 egész hatványával megszorozni, majd változtatással a 2 kívánt hatványára korrigálni. a kitevőt vagy eltolást, ill. Így belül eltolható . Sőt, az alábbi módszer nem általános osztást használ, hanem csak összeadást, kivonást, szorzást és kettő hatványával való osztást. Ezen műveletek közül az utolsót triviálisan hajtják végre. A módszer hátránya a hibahalmozódás, ellentétben az egyváltozós iteratív módszerekkel, mint például a babilóniai. $0<S<3\,\!$ $S\approx 1$ $S\,\!$ ${\sqrt {S))$ $S\,\!$ ${\frac {1}{2}}\leqslant S<2$

A módszer kezdeti lépése

a_{0}=S\,\!

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

Iteratív lépések

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

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

Ezután (for ). $a_{n}\rightarrow {\sqrt {S))$ $c_{n}\rightarrow 0$

Vegyük észre, hogy a konvergencia , és ezért , másodfokú. $c_{n}\,\!$ $a_{n}\,\!$

A módszer bizonyítása meglehetősen egyszerű. Először átírjuk az iteratív definíciót így $c_{n}\,\!$

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

Nos, ez bebizonyosodott

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

és ezért a kívánt eredményhez való konvergenciát a 0-hoz való konvergencia biztosítja, ami viszont abból következik . $a_{n}\,\!$ ${\sqrt {S))$ $c_{n}\,\!$ $-1<c_{0}<2\,\!$

Ezt a módszert 1950 körül fejlesztette ki M. W. Wilks , D. J. Wheeler és S. Gill [12] az EDSAC -ban, az egyik első elektronikus számítógépben [13] való használatra . Később a módszert általánosították a nem négyzetgyökökre [14] .

Iteratív módszerek egy szám négyzetgyökének reciproka kiszámítására

A következőkben iteratív módszereket mutatunk be S négyzetgyökének reciproka kiszámítására , azaz . Ha ilyen értéket találunk, akkor egyszerűen megszorozzuk: . Ezek az iterációk csak szorzást használnak, osztást nem. Mert a módszerek gyorsabbak a babiloni módszernél . A metódusok azonban instabilok, ha a kezdeti érték nincs közel a gyökérték reciprokájához, az iterációk eltérnek. Ezért előnyös lehet a babilóniai módszerrel iterálni a gyökér durva becsléséhez, mielőtt elkezdené ezeket a módszereket használni. $1/{\sqrt {S))$ ${\sqrt {S))$ ${\sqrt {S}}=S\cdot (1/{\sqrt {S}})$

Ha a Newton-módszert alkalmazzuk az egyenletre, akkor egy olyan módszert kapunk, amely négyzetesen konvergál, és minden lépésben három szorzást használ: $(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).$
Egy másik iteráció a Halley-módszer , amely a másodrendű Householder módszer A módszer kockaszerűen konvergál , de iterációnként öt szorzást használ: ${\displaystyle 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}\jobbra)\jobbra)$ .
Ha fixpontos számokkal dolgozik, a 3-mal való szorzás és a 8-cal való osztás megvalósítható eltolásokkal és összeadásokkal. Lebegőpontos munka esetén a Halley-módszer iterációnként négy szorzásra redukálható az összes többi állandó előre kiszámításával és beállításával a kompenzáció érdekében: ${\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}\jobbra)\jobbra)$ .

Goldschmidt algoritmusa

Egyes számítógépek a Goldschmidt algoritmust használják a számításokhoz és egyidejűleg . A Goldschmidt-algoritmus gyorsabban talál, mint a Newton-Rapson iteráció azokon a számítógépeken, amelyek megosztott szorzás-összeadás műveletekkel rendelkeznek , és vagy egy csővezetékes lebegőpontos processzorral vagy két független lebegőpontos processzorral [15] . ${\sqrt {S))$ $1/{\sqrt {S))$ ${\sqrt {S))$

A Goldschmidt-algoritmus írásának első módja a következővel kezdődik

b_{0}=S

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

(általában táblázatkeresést használnak)

y_{0}=Y_{0}

x_{0}=Sy_{0}

és iterációkat hajtanak végre

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

amíg elég közel nem ér 1-hez, vagy fix számú iterációt nem hajtottak végre. Az iterációk konvergálnak $kettős}$

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

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

Vegye figyelembe, hogy elhagyhatja a vagy a számítását , és ha mindkettőt kívánja, használhatja a végén, ahelyett, hogy minden iterációnál kiértékelné. $x_{n}$ $y_{n}$ $x_{n}=Sy_{n}$

A második módszer, amely a kombinált szorzás-összeadás műveleteket használja, azzal kezdődik

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

(általában táblázatkeresést használnak)

x_{0}=Sy_{0}

h_{0}=y_{0}/2

és iterációkat hajtanak végre

{\displaystyle r_{n}=0{,}5-x_{n}ó_{n))

{\displaystyle x_{n+1}=x_{n}+x_{n}r_{n))

{\displaystyle h_{n+1}=h_{n}+h_{n}r_{n))

amíg elég közel nem kerül a 0-hoz, vagy fix számú iterációt hajtanak végre. Az értékek konvergálnak $r_{i}$

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

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

Taylor sorozat

Ha N egy közelítés , akkor a legjobb közelítés a négyzetgyök függvény Taylor-sorával érhető el : ${\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)

A konvergencia sorrendje megegyezik a sorozatban használt kifejezések számával. Ha két kifejezést használunk, a módszer egyenértékű a babiloni módszerrel . Ha három kifejezést használunk, minden iteráció csaknem annyi műveletet használ, mint a Bakhshali-közelítés , de a konvergencia gyengébb. Ezért ez a módszer nem túl hatékony számítási módszer. A konvergencia sebességének maximalizálása érdekében N -t a lehető legkisebbre kell választani. ${\frac {|d|}{N^{2))}\,$

Folytatva a tört bővítést

A másodfokú irracionalitások (a formájú számok , ahol a , b és c egész számok), és különösen az egész számok négyzetgyöke, periodikusan folytonos törtek . Néha nem az a cél, hogy megtaláljuk a négyzetgyök számértékét, hanem a tört törtté való bővítése , és így a racionális közelítése. Legyen S egy pozitív szám, amelynek gyökét meg kell találni. Legyen a kezdeti közelítés és r a maradék, akkor felírhatjuk , mivel van , így S négyzetgyökét úgy fejezhetjük ki ${\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}}}}.

Ha ezt a for kifejezést alkalmazzuk a tört nevezőjére, azt kapjuk ${\sqrt {S))$

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

kompakt jelölés

A folyamatos törtbővítés számlálója/nevezője (lásd balra) nehezen írható le, és nehezen illeszthető be a meglévő dokumentumformázó rendszerbe. Emiatt egy speciális jelölést fejlesztettek ki a folyamatos törtek egész és periodikus részeinek tömör ábrázolására. Az egyik ilyen konvenció a lexikális "tört vonalat" használja a számláló és a nevező közötti sáv ábrázolására, amely lehetővé teszi, hogy a tört függőleges helyett vízszintesen írható:

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

Itt minden vízszintes vonást (törtszámban) három vonás képvisel - két függőleges és egy vízszintes, amelyek elkülönülnek a -tól . $r$ $2a$

A még tömörebb jelölésnek speciális formája van

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

A periodikusan folytatódó törteknél (amelyek mindegyike négyzetgyök) az ismétlődő rész csak egyszer szerepel, az ismétlődő rész fölött egy sávval:

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

√ 2 esetén az érték 1, tehát az ábrázolás az lesz $a$

[1;{\overline {2}}]

Ezt az utat követve megkapjuk a négyzetgyök általánosított folytonos törtjét ${\sqrt {S}}=a+{\cfrac {r}{2a+{\cfrac {r}{2a+{\cfrac {r}{2a+\ddots ))))))$

Az ilyen tört négyzetgyök kiszámításához az első lépés a gyök helyettesítése és a nevezők számának kiválasztása. Például kanonikus formában 1 és √ 2 esetén 1, tehát a numerikusan folytatódott tört 3 nevező esetén $r$ $a$

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

2. lépés: A folytonos törtet feltekerjük, nevezőnként, hogy egy racionális törtet kapjunk, amelynek a számlálója és a nevezője egész szám. A hajtogatási folyamat ezután így néz ki (az első három nevezőt figyelembe véve):

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

Végül (3. lépés) elosztjuk a számlálót a racionális tört nevezőjével, hogy megkapjuk a gyökér közelítését:

17\div 12=1{,}42

három tizedesjegyre kerekítve.

A √ 2 gyök valós értéke 1,41 és három jelentős számjegy. A relatív hiba 0,17%, tehát a racionális tört közel három tizedesjegyig jó. Ha több nevezőt veszünk, akkor a közelítésben következetes javulást kapunk - négy nevező törtet ad, ami majdnem 4 számjegyű pontosságot ad, stb. ${\frac {41}{29}}=1{,}4137$

Folyamatos törtek állnak rendelkezésre táblázatokban legalább kis számokhoz és jól ismert állandókhoz. Tetszőleges decimális jelölésű számok esetén az előre kiszámított értékek valószínűleg haszontalanok. Az alábbi táblázat a kis racionális törteket, amelyeket konvergenseknek nevezünk , több állandó kanonikus folytonos törtéből származik:

√ S	folytatta a lövést	~tizedes	Megfelelő frakciók
√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))$

Megjegyzés: Az összes alkalmazható tört a 99-es nevezőig szerepel.

Általában minél nagyobb egy racionális tört nevezője, annál jobb a közelítés. Kimutatható az is, hogy egy folytatólagos tört levágása racionális törtet eredményez, amely jobban közelíti bármely olyan tört gyökét, amelynek nevezője kisebb vagy egyenlő, mint az adott tört nevezője. Például egyetlen 70-nél kisebb nevezővel rendelkező tört sem olyan jó, mint a 99/70 , amely megközelítőleg √2 .

Lukács szekvenciamódszere

Az első típusú Lucas-sorozatot a rekurzív reláció határozza meg $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\cpont U_{n-2}(P,Q)&{\text{egyébként}}\end{cases}}$

karakterisztikus polinomja pedig az

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

, van diszkriminánsa és gyökerei $D=P^{2}-4Q$

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

Mindez a következő pozitív értéket adja

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

. Tehát ha meg akarjuk kapni , kiválaszthatjuk a és -t, majd a és segítségével számolhatunk nagy értékekre . A számítás leghatékonyabb módja és − ${\sqrt {a}}$ $P=2$ $Q=1-a$ $x_{1}=1+{\sqrt {a}}$ $U_{n+1}$ $ENSZ}$ $n$ $U_{n+1}$ $ENSZ}$

${\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{bmátrix}}$

Eredmény:

${\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{bmátrix}},$

majd itt : $n\to\infty$

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

A lebegőpontos ábrázolástól függő közelítések

A szám lebegőpontos számként jelenik meg: . Ezt a jelölési formátumot exponenciális jelölésnek is nevezik . Ennek a számnak a négyzetgyöke egyenlő , és hasonló képleteket lehet bemutatni a kockagyökökhöz és a logaritmusokhoz. Ez nem egyszerűsíti a feladatot, de ha csak közelítésre van szükség, akkor ez jó becslés a mantissza sorrendjére. Továbbá megértjük, hogy p néhány hatványa páratlannak bizonyulhat, akkor ahelyett, hogy az alap törthatványaival dolgoznánk, szorozunk vele, és kivonunk egyet a fokból, így párossá válik. A finomított ábrázolást a rendszer konvertálja a -ra , így a négyzetgyök . ${\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}$

Ha a mantisszának csak az egész részét vesszük, az 1-től 99-ig terjedő értékeket vehet fel, és ez indexként használható egy 99 előre kiszámított gyökből álló táblázatba a becslés befejezéséhez. A hexadecimális bázist használó számítógéphez szükség lehet nagyobb táblázatra, de a 2. bázis használatakor a táblázat csak három értékből fog állni - a mantissza finomított ábrázolásának egész részének lehetséges bitjei 01 lehetnek (ha a kitevő páros, így nincs eltolás, és vegye figyelembe, hogy a normalizált szám lebegőpontjában mindig van egy nem nulla magas számjegy), vagy ha a kitevő páratlan volt, 10 vagy 11, akkor ez az eredeti mantisszának az első két bitje. Ekkor a 6,25 (= binárisban 110,01) páros hatványra normalizálódik, így a mantissza bitpár 01, míg a 0,625 (= binárisban 0,101) páratlan hatványra normalizálódik, tehát szám-konverzióra van szükség , majd a bitpárra 10 lesz. Figyeljük meg, hogy a sorrend legkevésbé szignifikáns bitje tükröződik a mantissza párokba csoportosított legjelentősebb bitjében. A páros kitevőnek a legkisebb szignifikáns bitje nulla, és a négyes mantissza nulláról kezdődik, míg a páratlan kitevőnek 1 lesz a legkisebb jelentőségű bitben, a négyes mantissza pedig 1-gyel kezdődik. Tehát ha a kitevőt felezzük, akkor a egyenértékű a kitevő legkisebb szignifikáns bitjének eltolása a páronként csoportosított mantissza első bitjére. $1{,}1001\times 2^{2}$ $1{,}01\times 2^{-1}$ $10{,}1\x 2^{-2}$

A három elemből álló táblázat további mantissza bitekkel bővíthető. Számítógépek esetében azonban ahelyett, hogy az interpolációt táblázatban számolnánk ki, gyakran érdemes egy egyszerűbb számítási módot keresni, amely ugyanazt az eredményt adja. Most már minden a számábrázolási formátum pontos részleteitől és azoktól a műveletektől függ, amelyek elérhetők a szám egyes részeinek lekéréséhez és a velük való munkához. Például a Fortran tartalmaz egy funkciót EXPONENT(x)a diploma megszerzésére. A jó kezdeti közelítés megszerzésére fordított erőfeszítés megtérül a finomítási folyamat további iterációinak kiküszöbölésével, amelyek rossz közelítés esetén szükségesek.

Sok számítógép követi az IEEE lebegőpontos szabványt (vagy egy meglehetősen közeli reprezentációt), és nagyon gyors négyzetgyök közelítést kaphatunk Newton módszerének kiindulópontjaként. Ennek a közelítésnek a technikája abból fakad, hogy a lebegő számformátum (kettes bázis) közelíti a 2-es bázis logaritmust. $\log _{2}(m\times 2^{p})=p+\log _{2}(m)$

Tehát egy 32 bites IEEE lebegőpontos számhoz (amelyben a kitevő eltolása 127 [16] ) kaphat hozzávetőleges logaritmust, ha a számot 32 bites egész számként értelmezi, megszorozza és levonva a 127 eltolást, azaz $2^{-23}$

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

Például a hexadecimális 1.0 szám 0x3F800000, amely egész számként ábrázolható . A fenti képlet segítségével a várt módon kapja meg a -tól . Hasonlóképpen 0,5-öt kap az 1,5-ből (=0x3FC00000). $1065353216=127\cdot 2^{23}$ $1065353216\cdot 2^{-23}-127=0$ $\log _{2}(1{,}0)$

A négyzetgyök meghatározásához osszuk el a logaritmust 2-vel, és konvertáljuk vissza az eredményt. Az alábbi program bemutatja az ötletet. Vegye figyelembe, hogy a kitevő legkevésbé jelentős bitje szándékosan mantisszává van fordítva. A program lépéseinek igazolásának egyik módja, feltételezve, hogy ez a fokszám eltolása és a mantisszában tárolt bitek száma, az, hogy bebizonyítjuk $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}.

/* Tegyük fel, hogy a lebegő szám IEEE 754 formátumú */ #include <stdint.h> float sqrt_approx ( float z ) { egyesülés { float f ; uint32_t i ; } val = { z }; /* A típus konvertálása a bitábrázolás megváltoztatása nélkül */ /* * Bizonyítsuk be, hogy * ((((val.i / 2^m) - b) / 2) + b) * 2^m = ((val.i - 2^m) / 2) + ((b + 1) / 2) * 2^m) * ahol * b = teljesítményeltolás * m = bitek száma mantisszában */ val . i -= 1 << 23 ; /* Levonás 2^m. */ val . i >>= 1 ; /* Oszd 2-vel. */ val . i += 1 << 29 ; /* Hozzáadás ((b + 1) / 2) * 2^m. */ return val . f ; /* Újra lebegésként értelmezni */ }

A függvény magját képező három aritmetikai művelet egy sorban ábrázolható. A maximális relatív hiba csökkentése érdekében további finomításokat lehet hozzáadni. Így a három művelet, beleértve a valósra való redukciót, átírható így

val . i = ( 1 << 29 ) + ( érték i >> 1 ) - ( 1 << 22 ) + a ; _

ahol a egy eltolás a közelítési hibák csökkentésére. Például, ha a = 0, az eredmények pontosak 2 páros hatványaira (pl. 1,0), de más számok esetén az eredmény kissé nagy lesz (pl. 1,5 2,0 helyett 1,414... 6%-os hibával). A = -0x4B0D2 esetén a maximális relatív hiba ±3,5%-ra csökken.

Ha a közelítést a Newton-módszer kezdőértékeként kell használni az egyenletben , akkor a következő részben bemutatott inverz alak előnyösebb. $(1/x^{2})-S=0$

A négyzetgyök reciproka

Az alábbiakban bemutatjuk a fenti eljárás egy változatát, amely felhasználható a négyzetgyök inverzének kiszámításához, azaz . Ezt a változatot Greg Walsh írta. Az eltolási közelítés 4%-nál kisebb relatív hibát ad, és a hiba 0,15%-ra csökken a Newton-módszer egy iterációja után [17] . A számítógépes grafikában ez egy nagyon hatékony módja a vektorok normalizálásának. $x^{-{1 \over 2}}$

float invSqrt ( float x ) { float xhalf = 0,5f * x ; szakszervezet { float x ; int i ; } u ; u . x = x ; u . i = 0x5f375a86 - ( u . i >> 1 ); /* A következő sor tetszőleges számú alkalommal megismételhető a pontosság növelése érdekében */ u . x = u . x * ( 1,5f - xhalf * u . x * u . x ); térj vissza . x ; }

Néhány VLSI megvalósítja a négyzetgyök reciprokának meghatározását polinomiális becsléssel, majd Goldschmidt-iterációval [18] .

Egy negatív vagy komplex szám gyöke

Ha , akkor a fő gyöke egyenlő $S<0$

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

Ha , ahol a és b valós számok és , akkor a fő gyöke egyenlő $S=a+bi$ $b\neq 0$

{\sqrt {S}}={\sqrt {\frac {\vert S\vert +a}{2}}}\,+\,\operátornév {sgn}(b){\sqrt {\frac {\vert S\vert -a}{2))}\,\,i\,.

Ez a [19] [20] négyzetre emelésével ellenőrizhető . Itt

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

az S szám modulusa . Egy komplex szám főgyöke nem negatív valós résszel rendelkező gyökként van definiálva.

Lásd még

Algoritmus alfa max plusz béta min
egész négyzetgyök

Jegyzetek

↑ A főgyökön kívül van egy negatív négyzetgyök, amely abszolút értékben egyenlő a főgyökkel, de ellenkező előjellel, kivéve a nulla esetét, amikor két azonos nulla gyök van.
↑ A kettes és a hatos faktort azért használjuk, mert ezek adott számjegyekkel közelítik az alsó és felső lehetséges értékek geometriai átlagát : és . ${\sqrt {{\sqrt {1}}\cdot {\sqrt {10}}}}={\sqrt[{4}]{10}}\kb 1{,}78\,$ ${\sqrt {{\sqrt {10}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{1000}}\kb. 5{,}62\,$
↑ A kerekítetlen becslés maximális abszolút hibája 2,65 a 100. pontban, és maximális relatív hibája 26,5% az y=1, 10 és 100 pontokban
↑ Ha a szám pontosan félúton van két négyzet között, például 30,5, akkor vegyük a nagyobb számot, ami esetünkben 6
↑ Ez az y=x 2 érintő egyenes egyenlete az y=1 pontban.
↑ Fowler és Robson 1998 , p. 376.
↑ Heath, 1921 , p. 323–324.
↑ Bailey, Borwein, 2012 , p. 646–657.
↑ Visszatérve a Bahsali kézirathoz . Simply Curious blog (2018. június 5.). Letöltve: 2020. december 21. Az eredetiből archiválva : 2020. október 26. (határozatlan)
↑ Gyors egész négyzetgyök, Mr. Woo's abacus algoritmus (archivált)
↑ Egész négyzetgyök függvény . Letöltve: 2021. december 30. Az eredetiből archiválva : 2007. szeptember 30. (határozatlan)
↑ Wilkes, Wheeler, Gill, 1951 .
↑ Campbell-Kelly, 2009 .
↑ Gower, 1958 , p. 142-143, 1958.
↑ Markstein, Peter (2004. november). Szoftverfelosztás és négyzetgyök Goldschmidt algoritmusaival (PDF) . 6. konferencia a valós számokról és a számítógépekről . Dagstuhl , Németország. CiteSeerX 10.1.1.85.9648 . Archivált (PDF) az eredetiből ekkor: 2022-04-28 . Letöltve: 2021-12-30 . Elavult használt paraméter |deadlink=( súgó )
↑ 127-et adunk a szám kitevőjéhez, ami lehetővé teszi, hogy a kitevőt előjel nélküli számként értelmezzük.
↑ Fast Inverse Square Root archiválva : 2009. február 6., a Wayback Machine -ben, Chris Lomont
↑ "Reciprok, osztás, négyzetgyök és fordított négyzetgyök nagy sebességű kettős pontosságú számítása" , José-Alejandro Piñeiro és Javier Díaz Bruguera 2002 (absztrakt)
↑ Abramowitz, Stegun, 1964 , p. 17.
↑ Cooke, 2008 , p. 59.

Irodalom

David Fowler, Eleanor Robson. Négyzetgyök közelítések a régi babiloni matematikában: YBC 7289 összefüggésben // Historia Mathematica. - 1998. - T. 25 , sz. 4 . - doi : 10.1006/hmat.1998.2209 .
Thomas Little Heath A görög matematika története. - Oxford: Clarendon Press, 1921. - V. 2. - S. 323-324.
David Bailey, Jonathan Borwein. Ősi indián négyzetgyökerek: gyakorlat a törvényszéki paleo-matematikában // American Mathematical Monthly. - 2012. - T. 119 , sz. 8 .
Miltonn Abramowitz, Irene A. Stegun. 3.7.26. szakasz // Matematikai függvények kézikönyve képletekkel, grafikonokkal és matematikai táblázatokkal . - Courier Dover Publications, 1964. - P. 17. - ISBN 978-0-486-61272-0 .
JC Gower. Megjegyzés a gyökérkivonás iteratív módszeréhez // The Computer Journal. - 1958. - T. 1 1 , sz. 3 .
M. Campbell-Kelly. A számítástechnika eredete // Scientific American. - 2009. - szeptember.
Roger Cooke. Klasszikus algebra: természete, eredete és felhasználása . - John Wiley and Sons, 2008. - ISBN 978-0-470-25952-8 .
MV Wilkes, DJ Wheeler, S. Gill. Programok készítése elektronikus digitális számítógéphez. - Addison-Wesley, 1951.

A négyzetgyök kiszámításának módszerei

Kezdeti pontszám

Tizedespontszám

Bináris kiértékelés

Babilóniai módszer

Példa

Konvergencia

Bakhshali módszer

Példa

Számonkénti szám

Alapelv

Tizedes számrendszer

Bináris számrendszer

Exponenciális identitás

Egy iteratív módszer két változóval

Iteratív módszerek egy szám négyzetgyökének reciproka kiszámítására

Goldschmidt algoritmusa

Taylor sorozat

Folytatva a tört bővítést

Lukács szekvenciamódszere

A lebegőpontos ábrázolástól függő közelítések

A négyzetgyök reciproka

Egy negatív vagy komplex szám gyöke

Lásd még

Jegyzetek

Irodalom

Hivatkozások Weisstein, Eric W. Négyzetgyök-algoritmusok (angol) a Wolfram MathWorld oldalon .