Metoder för att beräkna kvadratrötter

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 januari 2022; kontroller kräver 4 redigeringar .

Kvadratrotsmetoder är beräkningsalgoritmer för att beräkna de ungefärliga värdena för de huvudsakliga (eller icke-negativa) kvadratrötterna (vanligtvis betecknade som , eller ) av ett reellt tal. Aritmetiskt betyder detta att om ett tal ges , hittar proceduren ett tal som, när det multipliceras med sig självt, ger . Algebraiskt betyder detta proceduren för att hitta en icke-negativ rot av en ekvation . Geometriskt innebär det att man konstruerar en sida av en kvadrat med en given area. ${\sqrt {S))$ ${\sqrt[{2}]{S))$ $S^{1/2}$ $S$ $S$ $x^{2}-S=0$

Vilket reellt tal som helst har två rötter [1] . Huvudvärdet av kvadratroten ur de flesta siffror är ett irrationellt tal med en oändlig följd av decimalsiffror. Som ett resultat kan decimalrepresentationen av en sådan kvadratrot endast beräknas ungefär med ändlig precision (decimaler). Men även om vi tar kvadratroten ur ett heltal, så att resultatet har en ändlig representation, kan vissa av procedurerna som används för att beräkna roten bara returnera en serie approximationer med ökande precision.

Den fortsatta bråkrepresentationen av ett reellt tal kan användas istället för decimal eller binär expansion och denna representation har egenskapen att kvadratroten av vilket rationellt tal som helst (som inte är en perfekt kvadrat) har en period, dvs en periodisk expansion som liknar hur rationella tal har upprepad expansion av decimaltalssystemet.

De vanligast accepterade analysmetoderna är iterativa och består av två steg: att hitta ett lämpligt startvärde och sedan iterativt förfina tills ett visst stoppkriterium uppnås. Startvärdet kan vara vilket tal som helst, men om det är närmare slutvärdet kommer färre iterationer att krävas. Den mest kända metoden, och ännu bekvämare för programmering, är Newtons metod, som är baserad på beräkningen av derivatan. Flera metoder, som manuell Horner-delning eller serieexpansion, kräver inget initialvärde. I vissa applikationer krävs det att hitta heltalskvadratroten , vilket är kvadratroten avrundad till närmaste heltal (i det här fallet kan en modifierad procedur användas).

Vilken metod som används beror på hur resultatet kommer att användas (det vill säga hur exakt resultatet måste vara) och vilka verktyg som finns tillgängliga. Metoder kan grovt delas upp i de som kan göras mentalt, som kräver en penna och papper, eller de som är implementerade som ett program och körs på datorer eller andra datorenheter. Konvergenshastigheten (hur många iterationer kommer att krävas för att uppnå en given noggrannhet), beräkningskomplexiteten för individuella operationer (som division) eller iterationer, och fördelningen av fel (noggrannheten hos resultatet) kan tas med i beräkningen.

Förfaranden för att hitta kvadratrötter (särskilt roten av 2) har varit kända åtminstone sedan det antika Babylons tid (1600-talet f.Kr.). Herons metod från 1:a århundradets Egypten var den första verifierbara algoritmen för att beräkna kvadratroten. Moderna analytiska metoder började utvecklas efter antagandet av arabiska siffror i Västeuropa under den tidiga renässansen . Nuförtiden har nästan alla datorenheter en snabb och exakt kvadratrotsfunktion som en inbyggd programmeringsspråkskonstruktion, biblioteksfunktion eller hårdvarusats som är baserad på procedurerna som beskrivs nedan.

Inledande poäng

Många iterativa kvadratrotsalgoritmer kräver ett initialt slumpmässigt värde. Detta värde måste vara ett positivt tal som inte är noll. Det måste vara mellan 1 och , talet vars kvadratrot vi letar efter, eftersom kvadratroten måste ligga inom dessa gränser. Om det initiala värdet är mycket långt från roten kommer algoritmen att behöva fler iterationer. Om du börjar med (eller med ), kommer det att fungera om extra iterationer bara för att få ordningen på roten. Därför är det användbart att ha en grov uppskattning av roten, som kan ha dålig noggrannhet, men är lätt att beräkna. I allmänhet gäller att ju mer exakt uppskattningen är, desto snabbare blir konvergensen. För Newtons metod (även kallad Babylonisk eller Herons metod) ger ett initialvärde något större än roten snabbare konvergens än ett initialvärde mindre än roten. $S$ $x_{0}=1$ $S$ ${\tfrac {1}{2}}\vert \log _{2}S\vert$

Generellt sett betraktas uppskattningen på ett godtyckligt intervall där det är känt att det innehåller en rot (som ). Att få en bättre uppskattning innebär antingen att få smalare gränser för intervallet eller en bättre funktionell approximation till . Det senare innebär vanligtvis att man använder högre ordningspolynom för approximationen, även om inte alla approximationer använder polynom. Vanliga skattningsmetoder är skalära, linjära, hyperboliska och logaritmiska. Decimalsystemet används vanligtvis för att uppskatta mentalt eller på papper. Det binära talsystemet är mer lämpat för datorutvärderingar. Vid utvärdering behandlas vanligtvis exponenten och mantissan separat. $[x_{0},S/x_{0}]$ $f(x).$

Decimalpoäng

Vanligtvis uttrycks talet i exponentiell form som , där , och n är ett heltal, då kan en uppskattning av den möjliga kvadratroten vara , där . $S$ ${\displaystyle a\times 10^{2n))$ $1\leqslant a<100$ ${\sqrt {a}}\times 10^{n}$ $1\leqslant {\sqrt {a}}<10$

Skalära uppskattningar

Skalära metoder delar upp hela intervallet i fack och poängen i varje fack representeras av ett enda nummer. Om intervallet behandlas som ett enda intervall är det aritmetiska medelvärdet (5,5) eller det geometriska medelvärdet () acceptabla uppskattningar. De absoluta och relativa uppskattningarna för dessa uppskattningar kommer att skilja sig åt. I allmänhet kommer ett enda tal att vara mycket felaktigt. Mer exakta uppskattningar delar upp intervallet i två och fler intervall, men den skalära uppskattningen fortsätter att vara mycket grov. ${\sqrt {10}}\approx 3{,}16)\times 10^{n}$

För två geometriskt uppdelade intervall kan kvadratroten uppskattas till [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}}

Denna uppskattning har ett maximalt absolut fel vid punkt = 100 och ett maximalt relativt fel på 100 % vid punkt = 1. ${\displaystyle 4\cdot 10^{n))$

Till exempel, för med en sönderdelning , blir poängen . , med ett absolut fel på 246 och ett relativt fel på nästan 70 %. $S=125348$ ${\displaystyle 12{,}5348\times 10^{4))$ ${\sqrt {S}}\approx 6\cdot 10^{2}=600$ ${\sqrt {125348}}=354{,}0$

Linjär uppskattning

Den bästa uppskattningen och standardmetoden är den linjära approximationen av funktionen på en liten båge. Om exponenten, som ovan, extraheras från talet och intervallet reduceras till , kan du använda en sekant eller tangent någonstans längs bågen för att approximera, men den direkta minsta kvadraters regression blir mer exakt. $y = x^2$ $S$ $[1 100]$

Den räta linjen, som erhålls med minsta kvadratmetoden, minimerar det genomsnittliga avståndet mellan skattningen och funktionens värde. Hennes ekvation är . Efter att ha transformerat och avrundat koefficienterna för att förenkla beräkningar får vi $y=8{,}7x-10$ $x=0{,}115y+1{,}15$

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

Detta är den bästa medeluppskattningen som kan erhållas genom ett försök till en linjär approximation av funktionen i intervallet . Uppskattningen har ett maximalt absolut fel på 1,2 vid punkten a=100 och ett maximalt relativfel på 30 % vid punkterna S=1 och 10 [3] . $y=x^2$ $[1 100]$

För att dividera med 10, subtrahera en från exponenten , eller, bildligt talat, flytta decimaltecknet en position åt vänster. För denna formel ger varje adderad konstant lika med 1 plus ett litet steg en tillfredsställande uppskattning, så det finns inget behov av att memorera det exakta talet. Approximation (avrundad eller inte avrundad) med en rät linje som subtraherar regionen vad gäller noggrannhet ger inte mer än ett korrekt tecken. Det relativa felet är mer än 1/2 2 , så det ger mindre än 2 bitar av information. Noggrannheten är kraftigt begränsad, eftersom regionen sträcker sig över två storleksordningar, vilket är ganska stort för denna typ av uppskattning. $a$ $[1 100]$

En betydligt bättre uppskattning kan erhållas genom att använda en bitvis linjär approximation, det vill säga att använda flera segment som approximerar den ursprungliga bågens subbåge. Ju fler segment som används, desto bättre approximation. Den vanligaste användningen av tangenter. Den kritiska punkten är hur man delar bågen och var man ska placera beröringspunkterna. En effektiv metod för att dividera bågen från y=1 till y=100 är geometrisk - för två intervall är intervallgränsen kvadratroten av det ursprungliga intervallet, 1 * 100, det vill säga och . Under tre intervaller kommer det att finnas kubrötter - , och , och så vidare. För två intervaller är detta ett mycket bekvämt nummer. Det är lätt att få tangentlinjer vid kontaktpunkterna och . Deras ekvationer är: och . Om vi vänder på ekvationerna får vi att kvadratrötterna är lika med och . Sedan för : $[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}}

De maximala absoluta värdena ligger i de högra gränserna för intervallen, vid punkterna a=10 och 100, och är lika med 0,54 respektive 1,7. De maximala relativa felen visas i slutet av intervallen, vid punkterna a=1, 10 och 100, och är lika med 17 %. 17 % eller 0,17. De är större än 1/10, så metoden ger en noggrannhet på mindre än en signifikant siffra.

Hyperbolisk uppskattning

I vissa fall kan den hyperboliska skattningen vara giltig, eftersom hyperbeln också är en konvex kurva och kan ligga längs bågen Y = x 2 bättre än en rät linje. Den hyperboliska skattaren är beräkningsmässigt svårare eftersom den kräver division med ett flyttal. En nästan optimal hyperbolisk approximation till x 2 på intervallet är . Efter transformation får vi . Sedan för : $[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}

Flyttalsindelningen måste vara exakt med en decimal, eftersom all utvärdering ger den precisionen, och en sådan division kan göras mentalt. Den hyperboliska skattningen är i genomsnitt bättre än den skalära eller linjära skattningen. Dess maximala absoluta fel är 1,58 vid punkt 100, och dess maximala relativa fel är 16,0 % vid punkt 10. I värsta fall är a=10 poängen 3,67. Om vi börjar vid 10 och applicerar Newton-Rapson iterationerna direkt, tar det två iterationer, som ger 3,66, innan vi når noggrannheten för den hyperboliska uppskattningen. För ett mer typiskt fall som 75 är den hyperboliska uppskattningen 8,00 och det krävs 5 Newton-Rapson-iterationer som börjar vid 75 för att få ett mer exakt resultat.

Aritmetisk utvärdering

En metod som liknar bitvis linjär approximation, men som bara använder aritmetiska operationer istället för algebraiska ekvationer, använder multiplikationstabellen omvänt - kvadratroten av tal mellan 1 och 100 är någonstans mellan 1 och 10, så eftersom vi vet att 25 är exakt kvadrat (5 × 5) och 36 är en exakt kvadrat (6 × 6), då börjar kvadratroten av ett tal som är större än 25 men mindre än 36 med talet 5. På samma sätt för tal mellan andra kvadrater. Denna metod ger den korrekta första siffran, men dess noggrannhet är bara en siffra - den första siffran i kvadratroten av 35 är till exempel 5, men själva roten av 35 är nästan lika med 6.

Det är bättre att dela intervallet mellan två rutor på mitten. Så roten av ett tal mellan 25 och halvvägs upp till 36 (vilket är 30,5) utvärderas till 5, andra tal större än 30,5 upp till 36 utvärderas till 6 [4] . Proceduren kräver mycket lite aritmetik för att hitta mitten av två produkter från tabellen. Här är en tabell över sådana siffror:

a	närmaste torg	$k={\sqrt {a))$ est.
1 till 2,5	1 (= 1 2 )	ett
2,5 till 6,5	4 (= 2 2 )	2
6,5 till 12,5	9 (= 3 2 )	3
12,5 till 20,5	16 (= 4 2 )	fyra
20,5 till 30,5	25 (= 5 2 )	5
30,5 till 42,5	36 (= 6 2 )	6
42,5 till 56,5	49 (= 72 )	7
56,5 till 72,5	64 (= 82 )	åtta
72,5 till 90,5	81 (= 9 2 )	9
90,5 till 100	100 (= 102 )	tio

Den sista operationen kommer att vara multiplikationen av poängen k med styrkan av tiotalet delat på hälften, så att för , ${\displaystyle S=a\cdot 10^{2n))$

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

Metoden ger en betydande sifferprecision eftersom den avrundar till bästa första siffra.

Metoden kan utökas till 3 signifikanta siffror i de flesta fall genom att interpolera mellan närmaste kvadrater. Om , då är ungefär lika med k plus en bråkdel lika med skillnaden mellan a och , dividerat med skillnaden mellan de två kvadraterna: $k^{2}\leqslant a<(k+1)^{2}$ ${\sqrt {a}}$ $k^{2}$

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

var

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

Den sista operationen, som ovan, är multiplikationen av resultatet med tiopotens delat på hälften

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

Talet k är decimalsiffran och R är bråket som ska omvandlas till decimalen. Ett bråk har vanligtvis en siffra i täljaren och en eller två siffror i nämnaren, så konvertering till en decimal kan göras mentalt.

Exempel: hitta kvadratroten ur 75. , så a är 75 och n är 0. Baserat på multiplikationstabellen ska kvadratroten ur mantissan vara 8 med en bråkdel eftersom , a , är för stor. Så k är 8 där bråkdelen är decimalrepresentationen av R . Bråket R har både en täljare och en nämnare. 11/17 är något mindre än 12/18, vilket är 2/3 eller 0,67, så 0,66 är en bra gissning (det är okej att göra en gissning här eftersom felet är litet). Så rotens värde är . √ 75 till tre signifikanta siffror skulle vara 8,66, så en poäng till tre signifikanta siffror är bra. Alla uppskattningar som använder denna metod är inte så exakta, men de är ganska nära. $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är utvärdering

När arbetet utförs i det binära systemet (säg i en datorprocessor) uttrycks det som , där , kvadratroten kan uppskattas som $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}

vilket är en minsta kvadraters regression över de 3 mest signifikanta bitarna. har ett maximalt absolut fel på 0,0408 vid punkt =2 och ett maximalt relativfel på 3,0 % vid punkt =1. För beräkningar är en avrundad uppskattning lämplig (eftersom koefficienterna är 2 potenser) ${\sqrt {a}}$ $a$ $a$

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

[5]

som har ett maximalt absolut fel på 0,086 vid punkt 2 och ett maximalt relativfel på 6,1 % vid poäng och . $a=0{,}5$ $a=2{,}0$

För den binära approximationen ger Since ger uppskattningen ett absolut fel på 19 och ett relativt fel på 5,3%. Det relativa felet är något mindre än 1/2 4 , så approximationen är korrekt till 4+ bitar. $S=125348=1\;1110\;1001\;1010\;0100_{2}=1{,}1110\;1001\;1010\;0100_{2}\ gånger 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$

En uppskattning för upp till 8 bitar kan erhållas genom att slå upp tabellen för de mest signifikanta 8 bitarna , givet att den mest signifikanta biten är implicit i de flesta flyttalsrepresentationer, och de minst signifikanta bitarna efter 8 bitar måste avrundas. Tabellen innehåller 256 byte av förberäknade 8-bitars kvadratrötter. Till exempel, för index 11101101 2 , som är 1,8515625 10 i decimal , är värdet i tabellen 10101110 2 , vilket är 1,359375 10 i decimal , kvadratroten ur 1,8515685 bitars tecken (+ decimala tecken 10 till 10) . $a$ $a$

Babyloniska metoden

Den kanske första algoritmen som används för approximation är den metod som är känd som den babyloniska metoden , även om det inte finns några direkta bevis, annat än hypotetiska slutsatser, för att babyloniska matematiker använde denna metod [6] . Metoden är också känd som Herons metod , efter den grekiske matematikern från det första århundradet Heron , som gav den första explicita beskrivningen av metoden i sitt 60-åriga verk Metrica [7] . Grundtekniken är att om x är större än kvadraten roten av ett icke-negativt reellt tal S , då blir det mindre rot och vice versa. Så det är rimligt att förvänta sig att medelvärdet av dessa två tal är närmare roten (det formella beviset för detta faktum är baserat på olikheten om det aritmetiska, geometriska och harmoniska medelvärdet , vilket visar att detta medelvärde alltid är större än kvadraten root, vilket säkerställer konvergens). Metoden motsvarar att använda Newtons metod för att lösa ekvationen . ${\sqrt {S))$ ${\tfrac {S}{x}}$ $x^{2}-S=0$

Mer exakt, om x är en initial gissning för , och felet i vår uppskattning är sådant att , kan vi utöka parenteserna och få ${\sqrt {S))$ $\varepsilon$ $S=(x+\varepsilon )^{2}$

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

eftersom .

\varepsilon \ll x

Därför kan vi kompensera för felet och uppdatera vår gamla uppskattning

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

Eftersom det beräknade felet inte var exakt kommer det att bli vår nästa uppskattning. Uppdateringsprocessen fortsätter tills vi når önskad noggrannhet. Det är en algoritm med kvadratisk konvergens , vilket innebär att antalet korrekta siffror i approximationen (i grova drag) fördubblas med varje iteration. Det fungerar så här:

Vi börjar med vilket positivt initialvärde som helst (ju närmare den sanna kvadratroten av S , desto bättre). $x_{0}$
Vi sätter lika med medelvärdet mellan och (vi använder det aritmetiska medelvärdet för att approximera det geometriska medelvärdet ). $x_{{n+1}}$ $x_{n}$ ${\displaystyle {\tfrac {S}{x_{n))))$
Upprepa steg 2 tills vi når önskad noggrannhet.

Algoritmen kan representeras enligt följande:

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

Algoritmen fungerar också bra för p -adiska tal , men kan inte användas för att identifiera riktiga kvadratrötter med p -adiska kvadratrötter. Man kan till exempel konstruera en sekvens av rationella tal erhållna med denna metod som konvergerar till +3 i fallet med reella tal, men till -3 i 2-adiska tal.

Exempel

För att beräkna √ S , där S = 125348, till sex signifikanta siffror, använd den grova uppskattningsmetoden som beskrivs ovan

{\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}}}\right) &={\frac {1}{2}}\left(354{,}045+{\frac {125348}{354{,}045}}\right)&=354{,}045\end{array} }\end{aligned}}

Därför . ${\sqrt {125348}}\approx 354{,}045$

Konvergens

Antag att x 0 > 0 och S > 0. Sedan för alla n x n > 0. Det relativa felet x n definieras som

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

och då

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

Nu kan man visa det

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

och följaktligen

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

och detta innebär garanterad konvergens, och denna konvergens är kvadratisk .

Konvergens i värsta fall

Om vi använder en grov uppskattningsmetod med den babyloniska metoden, så är de värsta fallen av noggrannhet i fallande ordning:

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

Och då i alla fall

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

Avrundningsfel försvagar konvergensen. Det rekommenderas att lagra minst en extra siffra ovanför önskad precision x n för att minimera avrundningsfel.

Bakhshali Method

Denna metod för att hitta kvadratrotens approximation skrevs i ett gammalt indisk manuskript som kallas Bakhshali-manuskriptet . Metoden motsvarar två iterationer av den babyloniska metoden med initialt värde x 0 . Algoritmen är alltså kvadratiskt konvergent, vilket innebär att antalet giltiga tecken för approximationen ökar med ungefär fyra gånger med varje iteration [8] . Representationen av algoritmen i modern notation är som följer: Beräkna , låt x 0 2 vara den initiala approximationen till roten S . Iterationer utförs sekventiellt ${\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}}

Detta kan användas för att bygga en rationell approximation till kvadratroten, som börjar med ett heltal. Om är ett heltal valt nära S och är skillnaden vars absoluta värde minimeras, kan den första iterationen skrivas på följande sätt: $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)} }.

Bakhshalis metod kan generaliseras för att beräkna en godtycklig rot, inklusive bråkrötter [9] .

Exempel

Låt oss använda samma exempel som gavs för den babyloniska metoden. Låt Då ger den första iterationen $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}}

På samma sätt ger den andra iterationen

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

Nummer efter nummer

Detta är en metod för att sekventiellt hitta varje siffra i kvadratroten. Metoden är långsammare än babylonisk, men har vissa fördelar

Det är lättare att beräkna manuellt.
Varje hittat tecken på roten är känt för att vara korrekt, det vill säga det kommer inte att ändras i nästa iterationer.
Om kvadratrotrepresentationen har ett ändligt antal siffror, avslutas algoritmen efter den senast hittade siffran. Således kan den användas för att testa att ett givet tal är en perfekt kvadrat .
Algoritmen fungerar i vilket talsystem som helst , och naturligtvis beror algoritmens funktion på det valda talsystemet.

Napiers stickor inkluderar ytterligare faciliteter för att utföra denna algoritm. Algoritmen för att beräkna den n:te rotsiffran för siffran är en generalisering av denna metod.

Grundläggande princip

Tänk först på fallet att hitta kvadratroten ur ett tal Z , som är kvadraten av ett tvåsiffrigt tal XY , där X är tiotalssiffran och Y är etttalssiffran. Vi har:

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

Låt oss först definiera värdet på X . X är den största siffran så att X 2 inte överstiger Z , från vilken de två sista siffrorna tas bort.

I nästa iteration kopplar vi ihop ett par siffror genom att multiplicera X med 2 och sätta resultatet i tiotalspositionen och sedan försöka ta reda på vad Y är lika med .

Eftersom svaret i vårt fall är den exakta kvadratroten, stannar algoritmen.

Samma idé kan utökas för att beräkna en godtycklig kvadratrot. Föreställ dig att vi kan hitta kvadratroten ur N som summan av n positiva tal så att

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

Genom att återanvända identiteten

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

den högra sidan kan representeras som

{\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(\summa _{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 {Justerat}}

Detta uttryck låter oss hitta kvadratroten genom successivt urval av värden . Antag att siffrorna redan har valts, då ges den m:te termen av , där är den hittade approximationen till kvadratroten. Nu måste varje nytt urval tillfredsställa rekursionen $a_{i}$ $a_{1},\ldots ,a_{m-1}$ $Y_{m}=[2P_{m-1}+a_{m}]a_{m},$ $P_{m-1}=\summa _{i=1}^{m-1}a_{i}$ $a_m$

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

så för alla vid startvärdet Om den exakta kvadratroten hittas. Om inte, så ger summan en lämplig approximation till kvadratroten och blir ett approximationsfel. $X_{m}\geqslant 0$ $1\leqslant m\leqslant n,$ $X_{0}=N.$ $X_{n}=0,$ $a_{i}$ $X_n$

Till exempel i decimal har vi

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

var är indikatorer för siffrornas position och koefficienterna . Vid varje m:te steg för att beräkna kvadratroten hittas en ungefärlig kvadratrot. Storleken och summeringstermerna ges av formlerna ${\displaystyle 10^{ni))$ $a_{i}\in \{0,1,2,\ldots ,9\}$ $P_{m-1}$ $Å_{m}$

P_{m-1}=\summa _{i=1}^{m-1}a_{i}\cdot 10^{ni}=10^{n-m+1}\summa _{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)}.

Eftersom positionsindikatorerna har en jämn styrka på 10, behöver vi bara arbeta med paret med högsta siffror under den återstående termen vid något månstegssteg. Avsnittet nedan organiserar denna procedur. $Å_{m}$ $X_{m-1}$

Uppenbarligen kan en liknande metod användas för att beräkna kvadratroten i vilket talsystem som helst, inte nödvändigtvis i decimal. Att hitta kvadratroten siffra för siffra i binärt är till exempel ganska effektivt eftersom värdet slås upp i den lilla uppsättningen siffror {0,1}. Detta gör beräkningen snabbare, eftersom värdet vid varje steg antingen är lika med eller lika med . Det faktum att det bara finns två möjligheter för gör det också lättare att välja ett värde i beräkningens månaste steg. Detta beror på att vi bara behöver kontrollera att för Om detta villkor är uppfyllt tar vi ; och om inte, så tar vi också det faktum att multiplikation med 2 utförs genom att flytta till vänster hjälper till i beräkningarna. $a_{i}$ $Å_{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.$

Decimaltalssystem

Låt oss skriva det ursprungliga talet i decimalform. Tal skrivs på ett liknande sätt som divisionen med en lång divisionsalgoritm , och som i lång division kommer kvadratroten att skrivas på den översta raden. Låt oss nu dela upp siffrorna i par, börja med kommatecken, på båda sidor om det. Kvadratrotens decimalkomma kommer att vara på kvadratens decimalkomma. En kvadratrotssiffra skrivs över ett par kvadratrotssiffror.

Med utgångspunkt från läget längst till vänster utför vi följande procedur för varje siffror:

Vi bär ner det högsta paret av oanvända siffror (om alla siffror används, skriv "00") och skriver dem till höger om resten av föregående steg (det finns ingen rest i det första steget). Med andra ord, multiplicera resten med 100 och lägg till två siffror. Detta kommer att vara det aktuella värdet av c .
Hitta p , y och x så här:
- Låt det vara en del av den redan hittade roten , ignorera decimalkomma. (För det första steget, p = 0.) ${\bold symbol {p}}$
- Bestäm det största antalet så att . Vi kommer att använda en ny variabel . ${\bold symbol {x}}$ $x(20p+x)\leqslant c$ ${\boldsymbol {y}}=x(20p+x)$
  - Observera att det bara är dubblat p med siffran x till höger . $20p+x$
  - Observera att x kan hittas genom att slumpmässigt gissa vad c /(20• p ) ska vara, med en provberäkning av y , sedan tas x högre eller lägre beroende på resultatet.
- Vi placerar siffran som nästa siffra i roten, det vill säga ovanför paret av kvadratsiffror som just har sänkts. Nu erhålls nästa värde på p från det gamla värdet med hjälp av formeln . $x$ $p\ gånger 10+x$
Subtrahera y från c för att bilda en ny rest.
Om resten är noll och det inte finns fler siffror att flytta ner, stoppas algoritmen. Annars går vi tillbaka till steg 1 och utför nästa iteration.

Exempel

Hitta kvadratroten av 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 Algoritmstopp: Svar 12.34

Binärt talsystem

Det här avsnittet använder formalismen i avsnittet Beräkna siffra för siffra , med mindre ändringar, att , och var och en är lika med eller . Nu går vi igenom allt från ner till och bygger en ungefärlig lösning som summan av alla som vi hittar ett värde för. För att avgöra om eller är lika med , tar vi . Om (det vill säga kvadraten på vår approximation inklusive inte överstiger den ursprungliga kvadraten), då sätter vi , annars sätter vi och . För att undvika kvadrering vid varje steg lagrar vi skillnaden och uppdaterar den vid varje iteration genom att ställa in c . Till en början ställde vi in på den största med . $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))$ ${\displaystyle 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))$

Som en ytterligare optimering lagrar vi och , två termer i fallet när de inte är noll, i separata variabler , : $P_{m+1}2^{m+1}$ $(2^{m})^{2}$ $Å_{m}$ $a_m$ ${\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))$ och kan uppdateras effektivt vid varje steg: ${\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}}

Lägg märke till att

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

, vilket är slutresultatet som returneras av funktionen nedan.

Implementering av algoritmen i C-språk [10] :

int32_t isqrt(int32_tn) { assert(("indatavärde måste vara icke-negativt", n > 0)); int32_t x = n; // int32_t c = 0; // // börjar med den högsta potensen av fyra <= n

X_{{n+1}}

c_n

d_{n}

int32_t d = 1 << 30; // Sätt den näst mest signifikanta biten till 1. // Samma som ((osignerad)INT32_MAX + 1) / 2. medan (d > n) d >>= 2; while (d != 0) // för { if (x >= c + d) // if , then { 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})

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

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

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

} returnera c; //

c_{{-1}}

}

Det är möjligt att implementera en snabbare algoritm i både binär och decimal notation om tabeller används för urval, det vill säga implementeringen av principen att använda mer minne minskar exekveringstiden [11] .

Exponentiell identitet

Fickräknare implementerar vanligtvis bra exponentiella och naturliga logaritmprogram . Beräkningen av kvadratroten S görs sedan med hjälp av egenskaperna hos logaritmer ( ) och exponentialer ( ): $\ln x^{n}=n\ln x$ $e^{\ln x}=x$

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

Bråkens nämnare motsvarar den n :te roten. I vårt fall är nämnaren 2. Samma identitet används för att beräkna kvadratroten med hjälp av logaritmtabeller eller glidregler .

En iterativ metod med två variabler

Denna metod är tillämpbar för att hitta kvadratroten av och konvergerar bäst för . Detta är dock inte en signifikant begränsning för beräkning på datorer, eftersom det i flyttals- och fixpunktsrepresentationer av binära tal är trivialt att multiplicera med en heltalspotens 4 och sedan korrigera till den önskade potensen 2 genom att ändra exponenten respektive skiftet. Således kan den flyttas inom . Dessutom använder metoden nedan inte allmänna divisioner, utan endast addition, subtraktion, multiplikation och division med två potens. Den sista av dessa åtgärder är trivialt genomförd. Nackdelen med metoden är felackumulering, till skillnad från iterativa metoder med en variabel som babyloniska. $0<S<3\,\!$ $S\approx 1$ $S\,\!$ ${\sqrt {S))$ $S\,\!$ ${\frac {1}{2}}\leqslant S<2$

Inledande steg i metoden

a_{0}=S\,\!

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

Iterativa steg

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

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

Sedan (för ). $a_{n}\rightarrow {\sqrt {S))$ $c_{n}\rightarrow 0$

Observera att konvergens , och därför , är kvadratisk. $c_{n}\,\!$ $a_{n}\,\!$

Beviset för metoden är ganska enkelt. Vi skriver först om den iterativa definitionen som $c_{n}\,\!$

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

Nu, rakt på sak, är det bevisat att

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

och därför säkerställs konvergensen till det önskade resultatet av konvergensen till 0, som i sin tur följer av . $a_{n}\,\!$ ${\sqrt {S))$ $c_{n}\,\!$ $-1<c_{0}<2\,\!$

Denna metod utvecklades runt 1950 av M. W. Wilks , D. J. Wheeler och S. Gill [12] för användning i EDSAC , en av de första elektroniska datorerna [13] . Senare generaliserades metoden till icke-kvadratrötter [14] .

Iterativa metoder för att beräkna den reciproka av kvadratroten ur ett tal

Följande är iterativa metoder för att beräkna den reciproka av kvadratroten av S , det vill säga . Om ett sådant värde hittas hittar vi det helt enkelt genom att multiplicera: . Dessa iterationer använder endast multiplikation och använder inte divisioner. Eftersom metoderna är snabbare än den babyloniska metoden . Metoderna är dock instabila, om det initiala värdet inte är nära rotvärdets reciproka divergerar iterationerna. Därför kan det vara fördelaktigt att först iterera med den babyloniska metoden för en grov uppskattning av roten innan man börjar använda dessa metoder. $1/{\sqrt {S))$ ${\sqrt {S))$ ${\sqrt {S}}=S\cdot (1/{\sqrt {S}})$

Att tillämpa Newtons metod på ekvationen ger en metod som konvergerar kvadratiskt och använder tre multiplikationer vid varje steg: $(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).$
En annan iteration erhålls från Halley-metoden , som är Householder-metoden av andra ordningen. Metoden konvergerar kubiskt , men använder fem multiplikationer per iteration: ${\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}\right)\right)$ .
När man arbetar med fixpunktsnummer kan multiplikation med 3 och division med 8 implementeras genom skift och tillägg. När man arbetar med flyttal kan Halleys metod reduceras till fyra multiplikationer per iteration genom att förberäkna och justera alla andra konstanter för att kompensera: ${\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}\right)\right)$ .

Goldschmidts algoritm

Vissa datorer använder Goldschmidt-algoritmen för att beräkna och samtidigt . Goldschmidt-algoritmen hittar snabbare än Newton-Rapson-iterationen på datorer med delade multiplikations-add- operationer och antingen en flyttalsprocessor eller två oberoende flyttalsprocessorer [15] . ${\sqrt {S))$ $1/{\sqrt {S))$ ${\sqrt {S))$

Det första sättet att skriva Goldschmidt-algoritmen börjar med

b_{0}=S

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

(vanligtvis används tabelluppslag)

y_{0}=Y_{0}

x_{0}=Sy_{0}

och iterationer utförs

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

tills det är tillräckligt nära 1 eller ett fast antal iterationer har utförts. Iterationerna konvergerar till $bi}$

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

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

Observera att du kan utelämna beräkningen av eller och om båda önskas kan du använda den i slutet istället för att utvärdera vid varje iteration. $x_{n}$ $y_{n}$ $x_{n}=Sy_{n}$

Den andra metoden, som använder de kombinerade multiplikations-additionsoperationerna , börjar med

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

(vanligtvis används tabelluppslag)

x_{0}=Sy_{0}

h_{0}=y_{0}/2

och iterationer utförs

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

tills det kommer tillräckligt nära 0, eller ett fast antal iterationer utförs. Värdena konvergerar till $r_{i}$

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

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

Taylor-serien

Om N är en approximation till , kan den bästa approximationen hittas med hjälp av Taylor - serien av kvadratrotsfunktionen : ${\sqrt {S))$

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

Konvergensordningen är lika med antalet termer som används i serien. När man använder två termer är metoden likvärdig med den babyloniska metoden . När du använder tre termer använder varje iteration nästan lika många operationer som Bakhshali-approximationen använder , men konvergensen är svagare. Därför är denna metod inte en särskilt effektiv beräkningsmetod. För att maximera konvergenshastigheten bör N väljas så att den är så liten som möjligt. ${\frac {|d|}{N^{2))}\,$

Fortsatt bråkexpansion

Kvadratiska irrationaliteter (tal i formen , där a , b och c är heltal), och i synnerhet kvadratrötter av heltal, har periodiska fortsatta bråk . Ibland är målet inte att hitta det numeriska värdet av kvadratroten, utan att expandera den till en fortsatt bråkdel , och därav dess rationella approximation. Låt S vara ett positivt tal vars rot ska hittas. Låt nu a vara den initiala approximationen och r vara resten, då kan vi skriva Eftersom vi har , kan vi uttrycka kvadratroten ur S som ${\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}}}}.

Genom att tillämpa detta uttryck på bråkets nämnare får vi ${\sqrt {S))$

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

kompakt notation

Täljaren/nämnaren för den fortsatta bråkexpansionen (se vänster) är svår att skriva ner och även svår att passa in i det befintliga dokumentformateringssystemet. Av denna anledning har en speciell notation utvecklats för att kompakt representera heltal och periodiska delar av fortsatta bråk. En sådan konvention använder den lexikala "streckade linjen" för att representera stapeln mellan täljaren och nämnaren, vilket gör att bråket kan skrivas horisontellt istället för vertikalt:

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

Här representeras varje horisontellt streck (i bråkdel) av tre streck - två vertikala och ett horisontellt, som skiljer från . $r$ $2a$

En ännu mer kompakt notation har en speciell form

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

För periodiska fortsatta bråk (som alla är kvadratrötter) listas den repeterande delen endast en gång, med en stapel över den repeterande delen:

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

För √ 2 är värdet 1, så representationen blir det $a$

[1;{\overline {2}}]

Efter denna väg får vi den generaliserade fortsatta bråkdelen för kvadratroten ${\sqrt {S}}=a+{\cfrac {r}{2a+{\cfrac {r}{2a+{\cfrac {r}{2a+\ddots ))))))$

Det första steget i att beräkna ett sådant bråk för att få en kvadratrot är att ersätta roten och välja antalet nämnare. Till exempel, i kanonisk form är 1 och för √ 2 är 1, så det numeriskt fortsatta bråket för 3 nämnare är $r$ $a$

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

Steg 2. Det fortsatta bråket rullas upp, en nämnare i taget, för att få ett rationellt bråk vars täljare och nämnare är heltal. Vikningsprocessen ser sedan ut så här (med de tre första nämnarna):

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

Slutligen (steg 3) delar vi täljaren med nämnaren för det rationella bråket för att få en approximation av roten:

17\div 12=1{,}42

avrundat till tre decimaler.

Det verkliga värdet av roten √ 2 är 1,41 till tre signifikanta siffror. Det relativa felet är 0,17 %, så en rationell bråkdel är bra till nästan tre decimaler. Om vi tar fler nämnare får vi en konsekvent förbättring av approximationen - fyra nämnare ger en bråkdel , vilket ger nästan 4 siffrors noggrannhet osv. ${\frac {41}{29}}=1{,}4137$

Fortsatta bråk finns i tabeller för åtminstone små tal och välkända konstanter. För godtyckliga tal i decimalnotation är förberäknade värden troligen värdelösa. Följande tabell över små rationella fraktioner, kallade konvergenter , härleds från kanoniska fortsatta fraktioner för flera konstanter:

√S _	fortsatte skottet	~decimal	Lämpliga fraktioner
√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))$

Obs: Alla tillämpliga bråk listas upp till nämnaren 99.

I allmänhet gäller att ju större nämnaren för ett rationellt bråk är, desto bättre approximation. Det kan också visas att avskärning av ett fortsatt bråk resulterar i ett rationellt bråk, med en bättre approximation till roten av ett bråk med en nämnare mindre än eller lika med bråkets nämnare. Till exempel, ingen bråkdel med en nämnare mindre än 70 är lika bra som 99/70 som approximerar √2 .

Lukas sekvensmetod

Lucas-sekvensen av det första slaget definieras av den rekursiva relationen $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{annars}}\end{cases}}$

och dess karakteristiska polynom är

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

, det har en diskriminerande och rötter $D=P^{2}-4Q$

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

Allt detta ger följande positiva värde

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

. Så om vi vill få kan vi välja och och sedan beräkna med och för stora värden . Det mest effektiva sättet att beräkna och − ${\sqrt {a}}$ $P=2$ $Q=1-a$ $x_{1}=1+{\sqrt {a}}$ $U_{n+1}$ $Fn}$ $n$ $U_{n+1}$ $Fn}$

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

Resultat:

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

och sedan kl : $n\till\infty$

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

Approximationer beroende på flyttalsrepresentation

Talet representeras som ett flyttal som . Detta notationsformat kallas även exponentiell notation . Kvadratroten av detta tal är lika och liknande formler kan presenteras för kubrötter och logaritmer. Detta förenklar inte uppgiften, men om det bara krävs en uppskattning är det en bra uppskattning av mantissans ordning. Vidare förstår vi att vissa potenser av p kan visa sig vara udda, istället för att arbeta med bråkpotenser av basen multiplicerar vi med den och subtraherar en från graden, vilket gör den jämn. Den förfinade representationen konverteras till , så kvadratroten blir . ${\displaystyle m\times b^{p))$ ${\sqrt {m}}\times b^{\tfrac {p}{2}}$ $b^{\tfrac {p}{2))$ $3141{,}59=3{,}14159{\times }10^{3}$ ${\displaystyle 31{,}4159{\times }10^{2))$ ${\sqrt {31.4159}}{\times }10^{1}$

Om bara heltalsdelen av mantissan tas kan den ta värden från 1 till 99 och detta kan användas som ett index i en tabell med 99 förberäknade rötter för att slutföra uppskattningen. En dator som använder hexadecimal bas kan kräva en större tabell, men med bas 2 kommer tabellen bara att bestå av tre värden - de möjliga bitarna av heltalsdelen av den raffinerade representationen av mantissan kan vara 01 (om exponenten är jämn, så det finns ingen förskjutning, och observera att det normaliserade flyttaltalet alltid har en hög siffra som inte är noll), eller om exponenten var udda, 10 eller 11, är dessa de två första bitarna av den ursprungliga mantissan. Sedan normaliseras 6,25 (= 110,01 i binär) till en jämn potens, så mantissbitparet är 01, medan 0,625 (= 0,101 i binärt) normaliseras till en udda potens, så en talomvandling krävs till , och sedan bitparet kommer att vara 10. Observera att den minst signifikanta biten av ordningen återspeglas i den mest signifikanta biten av mantissan grupperad i par. En jämn exponent har den minst signifikanta biten noll och quad mantissan börjar på noll, medan en udda exponent kommer att ha en 1 i den minst signifikanta biten och quad mantissan börjar på 1. Så när exponenten halveras är det ekvivalent med att flytta den minst signifikanta biten av exponenten till den första biten av den parvis grupperade mantissan. $1{,}1001\times 2^{2}$ $1{,}01\times 2^{-1}$ $10{,}1\ gånger 2^{-2}$

En tabell med tre element kan utökas med ytterligare mantissbitar. Men när det gäller datorer, istället för att beräkna interpolationen i en tabell, är det ofta bättre att leta efter ett enklare sätt att beräkna som ger samma resultat. Allt beror nu på de exakta detaljerna i nummerpresentationsformatet och på de operationer som är tillgängliga för att få delar av numret och arbeta med dem. Fortran innehåller till exempel en funktion EXPONENT(x)för att erhålla en examen. Ansträngningen som läggs ner på att få en bra initial approximation lönar sig genom att eliminera de ytterligare iterationer av förfiningsprocessen som skulle krävas i fallet med en dålig approximation.

Många datorer följer IEEE flyttalsstandard (eller en ganska nära representation) och en mycket snabb kvadratrotsapproximation kan erhållas som utgångspunkt för Newtons metod. Tekniken för denna approximation härrör från det faktum att det flytande talformatet (bas två) approximerar bas 2-logaritmen. Det vill säga, $\log _{2}(m\times 2^{p})=p+\log _{2}(m)$

Så för ett 32-bitars IEEE-flyttalstal (där exponenten har en offset på 127 [16] ), kan du få en ungefärlig logaritm genom att tolka talet som ett 32-bitars heltal, multiplicera det med och subtrahera förskjutningen 127, dvs $2^{-23}$

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

Till exempel är talet 1,0 i hexadecimal 0x3F800000, vilket kan representeras som när det ses som ett heltal. Med formeln ovan får du som förväntat från . På samma sätt får du 0,5 av 1,5 (=0x3FC00000). $1065353216=127\cdot 2^{23}$ $1065353216\cdot 2^{-23}-127=0$ $\log _{2}(1{,}0)$

För att få kvadratroten, dividera logaritmen med 2 och konvertera tillbaka resultatet. Programmet nedan visar idén. Observera att den minst signifikanta biten av exponenten medvetet översätts till mantissan. Ett sätt att motivera stegen i detta program, förutsatt att det är förskjutningen av graden, och är antalet lagrade bitar i mantissan, är att bevisa $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}.

/* Anta att flytande tal är i IEEE 754-format */ #inkludera <stdint.h> float sqrt_approx ( float z ) { union { flyta f ; uint32_t i ; } val = { z }; /* Konvertera typen utan att ändra bitrepresentationen */ /* * Bevisa att * ((((val.i / 2^m) - b) / 2) + b) * 2^m = ((val.i - 2^m) / 2) + ((b + 1) / 2) * 2^m) * där * b = effektförskjutning * m = antal bitar i mantissan */ val . i -= 1 << 23 ; /* Subtrahera 2^m. */ val . i >>= 1 ; /* Dividera med 2. */ val . i += 1 << 29 ; /* Lägg till ((b + 1) / 2) * 2^m. */ returvärde . _ f ; /* Tolka som float igen */ }

De tre aritmetiska operationerna som utgör kärnan i funktionen kan representeras på en rad. En ytterligare förfining kan läggas till för att minska det maximala relativa felet. Således kan de tre operationerna, exklusive reduktionen till verklig, skrivas om som

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

där a är en offset för att minska approximationsfel. Till exempel, med a = 0 är resultaten exakta för jämna potenser av 2 (t.ex. 1,0), men för andra tal blir resultatet något stort (t.ex. 1,5 för 2,0 istället för 1,414... med ett 6% fel). För a = −0x4B0D2 reduceras det maximala relativa felet till ±3,5 %.

Om approximationen ska användas som utgångsvärde för Newtons metod i ekvationen , är den omvända formen som visas i nästa avsnitt att föredra. $(1/x^{2})-S=0$

Den reciproka av kvadratroten

En variant av ovanstående procedur presenteras nedan och kan användas för att beräkna inversen av kvadratroten, dvs. Denna variant skrevs av Greg Walsh. Skiftapproximationen ger ett relativt fel på mindre än 4 % och felet reduceras till 0,15 % efter en iteration av Newtons metod [17] . Inom datorgrafik är detta ett mycket effektivt sätt att normalisera en vektor. $x^{-{1 \över 2}}$

float invSqrt ( float x ) { float xhalf = 0,5f * x ; union { flyta x ; int i ; } u ; u . x = x ; u . i = 0x5f375a86 - ( u . i >> 1 ); /* Nästa rad kan upprepas ett godtyckligt antal gånger för att öka precisionen */ u . x = u . x * ( 1,5f - x halv * u . x * u . x ); returnera u . x ; }

Vissa VLSI implementerar att hitta den reciproka av kvadratroten med hjälp av en polynomuppskattning följt av Goldschmidt-iteration [18] .

Roten till ett negativt eller komplext tal

Om , då är dess huvudrot lika med $S<0$

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

Om , där a och b är reella tal och , då dess huvudsakliga rot är lika med $S=a+bi$ $b\neq 0$

{\sqrt {S}}={\sqrt {\frac {\vert S\vert +a}{2}}}\,+\,\operatörsnamn {sgn}(b){\sqrt {\frac {\vert S\vert -a}{2))}\,\,i\,.

Detta kan kontrolleras genom att kvadrera [19] [20] . Här

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

är modulen för talet S . Huvudroten av ett komplext tal definieras som en rot med en icke-negativ reell del.

Se även

Algoritm alpha max plus beta min
heltals kvadratrot

Anteckningar

↑ Förutom huvudroten finns det en negativ kvadratrot som är lika i absolut värde som huvudroten, men med motsatt tecken, utom i fallet noll, då det finns två identiska nollrötter.
↑ Faktorer två och sex används eftersom de approximerar det geometriska medelvärdet av de lägre och övre möjliga värdena med ett givet antal siffror: och . ${\sqrt {{\sqrt {1}}\cdot {\sqrt {10}}}}={\sqrt[{4}]{10}}\approx 1{,}78\,$ ${\sqrt {{\sqrt {10}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{1000}}\approx 5{,}62\,$
↑ Den oavrundade uppskattningen har ett maximalt absolut fel på 2,65 vid punkt 100 och ett maximalt relativfel på 26,5 % vid punkterna y=1, 10 och 100
↑ Om talet är exakt halvvägs mellan två rutor, som 30,5, ta det större talet, som i vårt fall är 6
↑ Detta är ekvationen för tangentlinjen till y=x 2 i punkten y=1.
↑ Fowler och Robson 1998 , sid. 376.
↑ Heath, 1921 , sid. 323–324.
↑ Bailey, Borwein, 2012 , sid. 646–657.
↑ Bucking down till Bakhshali-manuskriptet . Simply Curious blogg (5 juni 2018). Hämtad 21 december 2020. Arkiverad från originalet 26 oktober 2020. (obestämd)
↑ Snabb heltalskvadratrot av Mr. Woo's abacus-algoritm (arkiverad)
↑ Heltals kvadratrotsfunktion . Hämtad 30 december 2021. Arkiverad från originalet 30 september 2007. (obestämd)
↑ Wilkes, Wheeler, Gill, 1951 .
↑ Campbell-Kelly, 2009 .
↑ Gower, 1958 , sid. 142-143, 1958.
↑ Markstein, Peter (november 2004). Programvaruavdelning och kvadratrot med Goldschmidts algoritmer (PDF) . 6:e konferensen om verkliga tal och datorer . Dagstuhl , Tyskland. CiteSeerX 10.1.1.85.9648 . Arkiverad (PDF) från originalet 2022-04-28 . Hämtad 2021-12-30 . Utfasad parameter används |deadlink=( hjälp )
↑ 127 läggs till talets exponent, vilket gör att exponenten kan tolkas som ett tal utan tecken.
↑ Fast Inverse Square Root Arkiverad 6 februari 2009 på Wayback Machine av Chris Lomont
↑ "Höghastighets dubbelprecisionsberäkning av ömsesidig, division, kvadratrot och omvänd kvadratrot" av José-Alejandro Piñeiro och Javier Díaz Bruguera 2002 (abstrakt)
↑ Abramowitz, Stegun, 1964 , sid. 17.
↑ Cooke, 2008 , sid. 59.

Litteratur

David Fowler, Eleanor Robson. Square Root Approximations in Old Babylonian Mathematics: YBC 7289 in Context // Historia Mathematica. - 1998. - T. 25 , nr. 4 . - doi : 10.1006/hmat.1998.2209 .
Thomas Little Heath . En historia av grekisk matematik. - Oxford: Clarendon Press, 1921. - V. 2. - S. 323-324.
David Bailey, Jonathan Borwein. Ancient Indian Square Roots: An Exercise in Forensic Paleo-Mathematics // American Mathematical Monthly. - 2012. - T. 119 , nr. 8 .
Miltonn Abramowitz, Irene A. Stegun. Avsnitt 3.7.26 // Handbok för matematiska funktioner med formler, grafer och matematiska tabeller . - Courier Dover Publications, 1964. - P. 17. - ISBN 978-0-486-61272-0 .
JC Gower. En anteckning om en iterativ metod för rotextraktion // The Computer Journal. - 1958. - T. 1 1 , nr. 3 .
M. Campbell-Kelly. Origin of Computing // Scientific American. - 2009. - September.
Roger Cooke. Klassisk algebra: dess natur, ursprung och användningsområden . - John Wiley and Sons, 2008. - ISBN 978-0-470-25952-8 .
MV Wilkes, DJ Wheeler, S. Gill. Förberedelse av program för en elektronisk digital dator. — Addison-Wesley, 1951.

Metoder för att beräkna kvadratrötter

Inledande poäng

Decimalpoäng

Binär utvärdering

Babyloniska metoden

Exempel

Konvergens

Bakhshali Method

Exempel

Nummer efter nummer

Grundläggande princip

Decimaltalssystem

Binärt talsystem

Exponentiell identitet

En iterativ metod med två variabler

Iterativa metoder för att beräkna den reciproka av kvadratroten ur ett tal

Goldschmidts algoritm

Taylor-serien

Fortsatt bråkexpansion

Lukas sekvensmetod

Approximationer beroende på flyttalsrepresentation

Den reciproka av kvadratroten

Roten till ett negativt eller komplext tal

Se även

Anteckningar

Litteratur

Referenser Weisstein, Eric W. Kvadratrotsalgoritmer (engelska) på Wolfram MathWorld- webbplatsen .