Metoder til beregning af kvadratrødder

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 13. januar 2022; checks kræver 4 redigeringer .

Kvadratrodsmetoder er beregningsalgoritmer til at beregne de omtrentlige værdier af de vigtigste (eller ikke-negative) kvadratrødder (normalt betegnet som , eller ) af et reelt tal. Aritmetisk betyder det, at hvis et tal er givet , finder proceduren et tal, der, når det ganges med sig selv, giver . Algebraisk betyder dette proceduren til at finde en ikke-negativ rod af en ligning . Geometrisk betyder det, at man konstruerer en side af et kvadrat med et givet areal. ${\sqrt {S))$ ${\sqrt[{2}]{S))$ $S^{1/2}$ $S$ $S$ $x^{2}-S=0$

Ethvert reelt tal har to rødder [1] . Hovedværdien af kvadratroden af de fleste tal er et irrationelt tal med en uendelig række af decimaltal. Som et resultat kan decimalrepræsentationen af enhver sådan kvadratrod kun beregnes tilnærmelsesvis med begrænset præcision (decimaler). Men selvom vi tager kvadratroden af et heltal, så resultatet har en endelig repræsentation, kan nogle af de procedurer, der bruges til at beregne roden, kun returnere en række tilnærmelser med stigende præcision.

Den fortsatte brøkrepræsentation af et reelt tal kan bruges i stedet for decimal eller binær udvidelse, og denne repræsentation har den egenskab, at kvadratroden af ethvert rationelt tal (som ikke er et perfekt kvadrat) har en periode, dvs. en periodisk udvidelse svarende til hvordan rationelle tal har gentagne udvidelser af decimaltalsystemet.

De mest almindeligt accepterede analysemetoder er iterative og består af to trin: at finde en passende startværdi og derefter iterativt forfine indtil et bestemt stopkriterium er nået. Startværdien kan være et hvilket som helst tal, men hvis den er tættere på slutværdien, kræves der færre iterationer. Den mest berømte sådan metode, og endnu mere bekvem til programmering, er Newtons metode, som er baseret på beregningen af den afledede. Adskillige metoder, såsom manuel Horner-opdeling eller serieudvidelse, kræver ikke en startværdi. I nogle applikationer er det nødvendigt at finde heltal kvadratroden , som er kvadratroden afrundet til nærmeste heltal (i dette tilfælde kan en modificeret procedure bruges).

Den anvendte metode afhænger af, hvordan resultatet vil blive brugt (det vil sige, hvor nøjagtigt resultatet skal være), og hvilke værktøjer der er tilgængelige. Metoder kan groft opdeles i dem, der kan gøres mentalt, som kræver en blyant og papir, eller dem, der er implementeret som et program og kører på computere eller andre computerenheder. Konvergenshastigheden (hvor mange iterationer kræves for at opnå en given nøjagtighed), den beregningsmæssige kompleksitet af individuelle operationer (såsom division) eller iterationer og fordelingen af fejl (resultatets nøjagtighed) kan tages i betragtning.

Procedurer til at finde kvadratrødder (især roden af 2) har været kendt i det mindste siden det gamle Babylons tid (1600-tallet f.Kr.). Herons metode fra det 1. århundredes Egypten var den første verificerbare algoritme til at beregne kvadratroden. Moderne analytiske metoder begyndte at blive udviklet efter vedtagelsen af arabiske tal i Vesteuropa i den tidlige renæssance . I disse dage har næsten alle computerenheder en hurtig og nøjagtig kvadratrodsfunktion som en indbygget programmeringssprogkonstruktion, biblioteksfunktion eller hardwareerklæring, der er baseret på procedurerne beskrevet nedenfor.

Indledende score

Mange iterative kvadratrodsalgoritmer kræver en initial tilfældig værdi. Denne værdi skal være et positivt tal, der ikke er nul. Det skal være mellem 1 og , det tal, hvis kvadratrod vi leder efter, da kvadratroden skal være inden for disse grænser. Hvis startværdien er meget langt fra roden, vil algoritmen have brug for flere iterationer. Hvis du starter med (eller med ), vil det arbejde med ekstra iterationer bare for at få rækkefølgen af roden. Derfor er det nyttigt at have et groft skøn over roden, som kan have ringe nøjagtighed, men er let at beregne. Generelt gælder det, at jo mere nøjagtigt estimatet er, jo hurtigere er konvergensen. For Newtons metode (også kaldet Babylonsk eller Herons metode) giver en begyndelsesværdi lidt større end roden hurtigere konvergens end en begyndelsesværdi mindre end roden. $S$ $x_{0}=1$ $S$ ${\tfrac {1}{2}}\vert \log _{2}S\vert$

Generelt betragtes estimatet på et vilkårligt interval, hvor det er kendt, at det indeholder en rod (såsom ). At få et bedre skøn involverer enten at få smallere grænser for intervallet eller en bedre funktionel tilnærmelse til . Sidstnævnte betyder normalt at bruge højere ordens polynomier til tilnærmelsen, selvom ikke alle tilnærmelser bruger polynomier. Almindelige estimeringsmetoder er skalar, lineær, hyperbolsk og logaritmisk. Decimalsystemet bruges normalt til at estimere mentalt eller på papir. Det binære talsystem er mere velegnet til computerevalueringer. Ved evaluering behandles eksponenten og mantissen normalt separat. $[x_{0},S/x_{0}]$ $f(x).$

Decimalscore

Normalt er tallet udtrykt i eksponentiel form som , hvor , og n er et heltal, så kan et skøn over den mulige kvadratrod være , hvor . $S$ ${\displaystyle a\times 10^{2n))$ $1\leqslant a<100$ ${\sqrt {a}}\ gange 10^{n}$ $1\leqslant {\sqrt {a}}<10$

Skalære estimater

Skalære metoder opdeler hele området i bins, og scoren i hver bin er repræsenteret af et enkelt tal. Hvis området behandles som et enkelt interval, er det aritmetiske middelværdi (5,5) eller det geometriske middelværdi () acceptable estimater. De absolutte og relative estimater for disse estimater vil afvige. Generelt vil et enkelt tal være meget unøjagtigt. Mere nøjagtige estimater opdeler området i to og flere intervaller, men det skalære skøn er fortsat meget groft. ${\sqrt {10}}\ca. 3{,}16)\ gange 10^{n}$

For to intervaller, der er opdelt geometrisk, kan kvadratroden estimeres til [2] . ${\sqrt {S}}={\sqrt {a}}\ gange 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}}

Dette estimat har en maksimal absolut fejl ved punkt = 100 og en maksimal relativ fejl på 100 % ved punkt = 1. ${\displaystyle 4\cdot 10^{n))$

For eksempel, for med en dekomponering , vil scoren være . , med en absolut fejl på 246 og en relativ fejl på næsten 70 %. $S=125348$ ${\displaystyle 12{,}5348\times 10^{4))$ ${\sqrt {S}}\approx 6\cdot 10^{2}=600$ ${\sqrt {125348}}=354{,}0$

Lineær estimering

Den bedste estimat og standardmetode er den lineære tilnærmelse af funktionen på en lille bue. Hvis eksponenten som ovenfor udtrækkes fra tallet , og intervallet reduceres til , kan du bruge en sekant eller tangent et sted langs buen til at tilnærme, men den direkte mindste kvadraters regression vil være mere præcis. $y = x^2$ $S$ $[1.100]$

Den rette linje, opnået ved metoden med mindste kvadrater, minimerer den gennemsnitlige afstand mellem estimatet og værdien af funktionen. Hendes ligning er . Efter transformation og afrunding af koefficienterne for at forenkle beregningerne, får vi $y=8{,}7x-10$ $x=0{,}115y+1{,}15$

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

Dette er det bedste gennemsnitsestimat , der kan opnås ved et forsøg på en lineær tilnærmelse af funktionen i intervallet . Estimatet har en maksimal absolut fejl på 1,2 ved punkt a=100 og en maksimal relativ fejl på 30 % ved punkt S=1 og 10 [3] . $y=x^2$ $[1.100]$

For at dividere med 10 skal du trække en fra eksponenten , eller billedligt talt flytte decimaltegnet en position til venstre. For denne formel giver enhver tilføjet konstant lig med 1 plus en lille stigning et tilfredsstillende skøn, så der er ingen grund til at huske det nøjagtige tal. Approksimation (afrundet eller ikke afrundet) ved hjælp af en ret linje, der trækker området fra med hensyn til nøjagtighed, giver ikke mere end ét korrekt tegn. Den relative fejl er mere end 1/2 2 , så den giver mindre end 2 bit information. Nøjagtigheden er stærkt begrænset, da regionen spænder over to størrelsesordener, hvilket er ret stort for denne form for estimering. $-en$ $[1.100]$

Et væsentligt bedre estimat kan opnås ved at bruge en stykkevis lineær tilnærmelse, det vil sige ved at bruge flere segmenter, der tilnærmer subbuen af den oprindelige bue. Jo flere segmenter der bruges, jo bedre tilnærmelse. Den mest almindelige brug af tangenter. Det kritiske punkt er, hvordan man deler buen, og hvor man placerer berøringspunkterne. En effektiv metode til at dividere buen fra y=1 til y=100 er geometrisk - for to intervaller er intervalgrænsen kvadratroden af det oprindelige interval, 1 * 100, det vil sige og . I tre intervaller vil der være terningrødder - , og , og så videre. For to intervaller er dette et meget praktisk tal. Det er let at opnå tangentlinjer ved kontaktpunkterne og . Deres ligninger er: og . Vende ligningerne om, får vi, at kvadratrødderne er lig med og . Så for : $[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 maksimale absolutte værdier er i de højre grænser af intervallerne, i punkterne a=10 og 100, og er lig med henholdsvis 0,54 og 1,7. De maksimale relative fejl vises i enderne af intervallerne, i punkterne a=1, 10 og 100, og er lig med 17%. 17 % eller 0,17. De er større end 1/10, så metoden giver en nøjagtighed på mindre end et signifikant ciffer.

Hyperbolsk estimat

I nogle tilfælde kan det hyperbolske estimat være gyldigt, da hyperbelen også er en konveks kurve og kan ligge langs buen Y = x 2 bedre end en ret linje. Den hyperbolske estimator er beregningsmæssigt vanskeligere, fordi den kræver division med et flydende kommatal. En næsten optimal hyperbolsk tilnærmelse til x 2 på intervallet er . Efter transformation får vi . Så for : $[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}

Floating-point-inddelingen skal være nøjagtig med én decimal, da al evaluering giver den præcision, og sådan en division kan udføres mentalt. Det hyperbolske estimat er i gennemsnit bedre end det skalære eller lineære estimat. Dens maksimale absolutte fejl er 1,58 ved punkt 100, og dens maksimale relative fejl er 16,0 % ved punkt 10. I værste tilfælde er a=10 scoren 3,67. Hvis vi starter ved 10 og anvender Newton-Rapson iterationerne direkte, tager det to iterationer, som giver 3,66, før vi når nøjagtigheden af det hyperbolske estimat. For et mere typisk tilfælde som 75 er det hyperbolske estimat 8,00, og det tager 5 Newton-Rapson-iterationer, der starter ved 75 for at få et mere præcist resultat.

Aritmetisk evaluering

En metode svarende til stykkevis lineær tilnærmelse, men kun ved at bruge aritmetiske operationer i stedet for algebraiske ligninger, bruger multiplikationstabellen omvendt - kvadratroden af tal mellem 1 og 100 er et sted mellem 1 og 10, så da vi ved, at 25 er nøjagtigt kvadrat. (5 × 5) og 36 er et nøjagtigt kvadrat (6 × 6), så begynder kvadratroden af et tal, der er større end 25, men mindre end 36, med tallet 5. Tilsvarende for tal mellem andre kvadrater. Denne metode giver det korrekte første ciffer, men dets nøjagtighed er kun et ciffer - det første ciffer af kvadratroden af 35 er for eksempel 5, men selve roden af 35 er næsten lig med 6.

Det er bedre at dele intervallet mellem to firkanter i to. Så roden af ethvert tal mellem 25 og halvvejs op til 36 (som er 30,5) evalueres til 5, andre tal større end 30,5 op til 36 evalueres til 6 [4] . Proceduren kræver meget lidt aritmetik for at finde midten af to produkter fra bordet. Her er en tabel over sådanne tal:

-en	nærmeste plads	$k={\sqrt {a))$ anslået
1 til 2,5	1 (= 1 2 )	en
2,5 til 6,5	4 (= 2 2 )	2
6,5 til 12,5	9 (= 3 2 )	3
12,5 til 20,5	16 (= 4 2 )	fire
20,5 til 30,5	25 (= 5 2 )	5
30,5 til 42,5	36 (= 6 2 )	6
42,5 til 56,5	49 (= 72 )	7
56,5 til 72,5	64 (= 82 )	otte
72,5 til 90,5	81 (= 9 2 )	9
90,5 til 100	100 (= 102 )	ti

Den endelige operation vil være multiplikationen af partituren k med potensen af tiere divideret i halvdelen, således at for , ${\displaystyle S=a\cdot 10^{2n))$

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

Metoden giver et væsentligt cifferpræcision, fordi den runder af til det bedste første ciffer.

Metoden kan i de fleste tilfælde udvides til 3 signifikante cifre ved at interpolere mellem nærmeste kvadrater. Hvis , så er omtrent lig med k plus en brøk lig med forskellen mellem a og , divideret med forskellen mellem de to kvadrater: $k^{2}\leqslant a<(k+1)^{2}$ ${\sqrt {a}}$ $k^{2}$

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

hvor

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

Den endelige operation, som ovenfor, er multiplikationen af resultatet med en potens af ti divideret med det halve

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

Tallet k er decimaltallet, og R er brøken, der skal omregnes til decimaltallet. En brøk har normalt et ciffer i tælleren og et eller to cifre i nævneren, så konvertering til en decimal kan ske mentalt.

Eksempel: find kvadratroden af 75. , så a er 75 og n er 0. Baseret på multiplikationstabellen skal kvadratroden af mantissen være 8 med en brøk , fordi , a , er for stor. Så k er 8 , hvor brøken er decimalrepræsentationen af R . Brøken R har både en tæller og en nævner. 11/17 er lidt mindre end 12/18, som er 2/3 eller 0,67, så 0,66 er et godt gæt (det er okay at gætte her, da fejlen er lille). Så værdien af roden er . √ 75 til tre signifikante cifre ville være 8,66, så en score til tre signifikante cifre er godt. Ikke alle estimater ved hjælp af denne metode er så nøjagtige, men de er ret tæt på. $75=75\ gange 10^{2\cdot 0}$ $8\time 8=64$ $9\time 9=81$ $75-k^{2}=11$ $81-k^{2}=17$ $8+0{,}66=8{,}66$

Binær evaluering

Når arbejdet udføres i det binære system (f.eks. i en computerprocessor), udtrykkes det som , hvor , kvadratroden kan estimeres som $S$ ${\displaystyle a\times 2^{2n))$ ${\displaystyle 0{,}1_{2}\leqslant a<10_{2))$ ${\sqrt {S}}={\sqrt {a}}\ gange 2^{n}$

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

som er en mindste kvadraters regression over de 3 mest signifikante bits. har en maksimal absolut fejl på 0,0408 ved punkt =2 og en maksimal relativ fejl på 3,0 % ved punkt =1. Til beregninger er et afrundet estimat praktisk (fordi koefficienterne er potenser af 2) ${\sqrt {a}}$ $-en$ $-en$

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

[5]

som har en maksimal absolut fejl på 0,086 ved punkt 2 og en maksimal relativ fejl på 6,1 % ved punkt og . $a=0{,}5$ $a=2{,}0$

For den binære tilnærmelse giver Siden giver estimatet en absolut fejl på 19 og en relativ fejl på 5,3%. Den relative fejl er lidt mindre end 1/2 4 , så tilnærmelsen er nøjagtig til 4+ bit. $S=125348=1\;1110\;1001\;1010\;0100_{2}=1{,}1110\;1001\;1010\;0100_{2}\ gange 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$

Et estimat for op til 8 bit kan opnås ved at slå op i tabellen for de mest signifikante 8 bits , givet at den mest signifikante bit er implicit i de fleste flydende komma-repræsentationer, og de mindst signifikante bits efter 8 bit skal afrundes. Tabellen indeholder 256 bytes forudberegnet 8-bit kvadratrødder. For eksempel, for indeks 11101101 2 , som er 1,8515625 10 i decimal , er værdien i tabellen 10101110 2 , hvilket er 1,359375 10 i decimal , kvadratroden af 1,8515685 bit 10 til decimaltegn (+ decimaltegn 10). $-en$ $-en$

Babylonsk metode

Måske er den første algoritme , der bruges til tilnærmelse , metoden kendt som den babylonske metode , selvom der ikke er nogen direkte beviser, bortset fra hypotetisk slutning, på, at babylonske matematikere brugte denne metode [6] . Metoden er også kendt som Herons metode , efter den græske matematiker fra det første århundrede Heron , som gav den første eksplicitte beskrivelse af metoden i sit 60 år lange værk Metrica [7] .Den grundlæggende teknik er, at hvis x er større end kvadratet rod af et ikke-negativt reelt tal S , så vil det være mindre rod og omvendt. Så det er rimeligt at forvente, at gennemsnittet af disse to tal er tættere på roden (det formelle bevis for dette faktum er baseret på uligheden omkring det aritmetiske, geometriske og harmoniske middelværdi , hvilket viser, at dette gennemsnit altid er større end kvadratet root, som sikrer konvergens). Metoden svarer til at bruge Newtons metode til at løse ligningen . ${\sqrt {S))$ ${\tfrac {S}{x}}$ $x^{2}-S=0$

Mere præcist, hvis x er et indledende gæt for , og fejlen i vores estimat er sådan, at , kan vi udvide parenteserne og få ${\sqrt {S))$ $\varepsilon$ $S=(x+\varepsilon )^{2}$

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

fordi .

\varepsilon \ll x

Derfor kan vi kompensere for fejlen og opdatere vores gamle skøn

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

Da den beregnede fejl ikke var nøjagtig, vil det blive vores næste tilnærmelse. Opdateringsprocessen fortsætter, indtil vi når den ønskede nøjagtighed. Det er en algoritme med kvadratisk konvergens , hvilket betyder, at antallet af korrekte cifre i tilnærmelsen (groft sagt) fordobles med hver iteration. Det fungerer sådan her:

Vi starter med enhver positiv begyndelsesværdi (jo tættere på den sande kvadratrod af S , jo bedre). $x_{0}$
Vi sætter lig med gennemsnittet mellem og (vi bruger det aritmetiske middelværdi til at tilnærme det geometriske middelværdi ). $x_{{n+1}}$ $x_{n}$ ${\displaystyle {\tfrac {S}{x_{n))))$
Gentag trin 2, indtil vi når den ønskede nøjagtighed.

Algoritmen kan repræsenteres som følger:

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 fungerer også godt for p - adiske tal , men kan ikke bruges til at identificere rigtige kvadratrødder med p - adiske kvadratrødder. Man kan for eksempel konstruere en række rationelle tal opnået ved denne metode, der konvergerer til +3 i tilfælde af reelle tal, men til -3 i 2-adiske tal.

Eksempel

For at beregne √ S , hvor S = 125348, til seks signifikante cifre, skal du bruge den grove estimeringsmetode beskrevet ovenfor

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

Derfor . ${\sqrt {125348}}\approx 354{,}045$

Konvergens

Antag, at x 0 > 0 og S > 0. Så for enhver n x n > 0. Den relative fejl x n er defineret som

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

og så

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

Det kan det nu vise sig

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

og følgelig

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

og dette indebærer garanteret konvergens, og denne konvergens er kvadratisk .

Konvergens i værste fald

Hvis vi bruger en grov estimeringsmetode med den babylonske metode, så er de værste tilfælde af nøjagtighed i faldende rækkefølge:

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

Og så alligevel

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

Afrundingsfejl svækker konvergensen. Det anbefales at gemme mindst et ekstra ciffer over den ønskede præcision x n for at minimere afrundingsfejl.

Bakhshali-metoden

Denne metode til at finde kvadratrodstilnærmelsen blev skrevet i et gammelt indisk manuskript kaldet Bakhshali-manuskriptet . Metoden svarer til to iterationer af den babylonske metode med startværdi x 0 . Algoritmen er således kvadratisk konvergent, hvilket betyder, at antallet af gyldige tegn for tilnærmelsen stiger med cirka fire gange med hver iteration [8] . Repræsentationen af algoritmen i moderne notation er som følger: Beregn , lad x 0 2 være den indledende tilnærmelse til roden S . Iterationer udføres sekventielt ${\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}}

Dette kan bruges til at bygge en rationel tilnærmelse til kvadratroden, startende med et heltal. Hvis er et heltal valgt tæt på S og er forskellen, hvis absolutte værdi bliver minimeret, så kan den første iteration skrives som følger: $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 metode kan generaliseres til at beregne en vilkårlig rod, herunder brøkrødder [9] .

Eksempel

Lad os bruge det samme eksempel, som blev givet for den babylonske metode. Lad Så giver den første iteration $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å samme måde giver den anden iteration

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

Dette er en metode til sekventielt at finde hvert ciffer i kvadratroden. Metoden er langsommere end babylonsk, men har nogle fordele

Det er nemmere at beregne manuelt.
Hvert fundet tegn på roden er kendt for at være korrekt, det vil sige, det vil ikke blive ændret i de næste iterationer.
Hvis kvadratrodsrepræsentationen har et endeligt antal cifre, afsluttes algoritmen efter det sidst fundet ciffer. Det kan således bruges til at teste, at et givet tal er et perfekt kvadrat .
Algoritmen fungerer i ethvert talsystem , og selvfølgelig afhænger algoritmens funktion af det valgte talsystem.

Napiers pinde inkluderer yderligere faciliteter til at udføre denne algoritme. Algoritmen til at beregne det n'te rodciffer for ciffer er en generalisering af denne metode.

Grundlæggende princip

Overvej først tilfældet med at finde kvadratroden af et tal Z , som er kvadratet af et tocifret tal XY , hvor X er tier-cifferet og Y er et-tallet. Vi har:

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

Lad os først definere værdien af X . X er det største ciffer, således at X 2 ikke overstiger Z , hvorfra de sidste to cifre er droppet.

I den næste iteration forbinder vi et par cifre ved at gange X med 2 og sætte resultatet i tier-positionen og derefter forsøge at finde ud af, hvad Y er lig med .

Da svaret i vores tilfælde er den nøjagtige kvadratrod, stopper algoritmen.

Den samme idé kan udvides til at beregne en vilkårlig kvadratrod. Forestil dig, at vi kan finde kvadratroden af N som summen af n positive tal således

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

Ved at genbruge identiteten

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

højre side kan repræsenteres 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\venstre(\sum _{i=1}^{n-1}a_{i}\right)a_{n}+a_{n}^{2}\ \=&\,a_{1}^{2}+[2a_{1}+a_{2}]a_{2}+[2(a_{1}+a_{2})+a_{3}]a_ {3}+\dotsb +\left[2\left(\sum _{i=1}^{n-1}a_{i}\right)+a_{n}\right]a_{n}.\end {aligned}}

Dette udtryk giver os mulighed for at finde kvadratroden ved successivt valg af værdier . Antag, at tallene allerede er udvalgt, så er det m. led givet af , hvor er den fundne tilnærmelse til kvadratroden. Nu skal hver ny markering tilfredsstille rekursionen $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))$ $er$

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

så for alle ved startværdien Hvis den nøjagtige kvadratrod findes. Hvis ikke, så giver summen en passende tilnærmelse til kvadratroden og vil være en tilnærmelsesfejl. $X_{m}\geqslant 0$ $1\leqslant m\leqslant n,$ $X_{0}=N.$ $X_{n}=0,$ $a_{i}$ $X_n$

For eksempel har vi i decimal

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

hvor er indikatorer for positionen af cifrene, og koefficienterne . Ved hvert m-te trin i beregningen af kvadratroden findes en omtrentlig kvadratrod. Størrelses- og summeringsled er givet af formlerne ${\displaystyle 10^{ni))$ $a_{i}\in \{0,1,2,\ldots ,9\}$ $P_{m-1}$ $Å_{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)}.

Da positionsindikatorerne har en jævn styrke på 10, behøver vi kun at arbejde med parret af højeste cifre i den resterende term på ethvert månedstrin. Afsnittet nedenfor organiserer denne procedure. $Å_{m}$ $X_{m-1}$

Naturligvis kan en lignende metode bruges til at beregne kvadratroden i ethvert talsystem, ikke nødvendigvis i decimal. For eksempel er det ret effektivt at finde kvadratroden ciffer for ciffer i binær, fordi værdien slås op i det lille sæt af cifre {0,1}. Dette gør beregningen hurtigere, da værdien ved hvert trin enten er lig med eller lig med . At der kun er to muligheder for , gør det også nemmere at vælge en værdi på månedstrinnet i beregningen. Dette skyldes, at vi kun skal kontrollere, at for Hvis denne betingelse er opfyldt, tager vi ; og hvis ikke, så tager vi også det faktum, at multiplikation med 2 udføres ved at flytte til venstre, hjælper i beregningerne. $a_{i}$ $Å_{m}$ $Y_{m}=0$ $a_{m}=0$ $Y_{m}=2P_{m-1}+1$ $a_{m}=1$ $er$ $er$ ${\displaystyle Y_{m}\leqslant X_{m-1))$ $a_{m}=1.$ $a_{m}=1$ $a_{m}=0.$

Decimaltalssystem

Lad os skrive det oprindelige tal i decimalform. Tal skrives på samme måde som divisionen med en lang divisionsalgoritme , og som i lang division vil kvadratroden blive skrevet på den øverste linje. Lad os nu opdele tallene i par, begyndende med et komma, på begge sider af det. Decimalpunktet for kvadratroden vil være på kvadratets decimalpunkt. Et kvadratrodsciffer skrives over et par kvadratrodscifre.

Startende fra den yderste venstre position udfører vi følgende procedure for hvert par cifre:

Vi fører det højeste par af ubrugte cifre ned (hvis alle cifrene er brugt, skriv "00") og skriver dem til højre for resten af det forrige trin (der er ingen rest i det første trin). Med andre ord, gange resten med 100 og tilføje to cifre. Dette vil være den aktuelle værdi af c .
Find p , y og x sådan her:
- Lad det være en del af den allerede fundne rod , og ignorer decimaltegnet. (For det første trin, p = 0.) ${\fed symbol {p}}$
- Bestem det største antal , således at . Vi vil bruge en ny variabel . ${\fed symbol {x}}$ $x(20p+x)\leqslant c$ ${\boldsymbol {y}}=x(20p+x)$
  - Bemærk, at det blot er fordoblet p med cifret x tilføjet til højre . $20p+x$
  - Bemærk at x kan findes ved tilfældigt at gætte hvad c /(20• p ) skal være, med en prøveberegning af y , så tages x højere eller lavere afhængigt af resultatet.
- Vi placerer cifferet som det næste ciffer i roden, det vil sige over parret af kvadratcifre, der lige er blevet sænket. Nu fås den næste værdi af p fra den gamle værdi ved hjælp af formlen . $x$ $p\ gange 10+x$
Træk y fra c for at danne en ny rest.
Hvis resten er nul, og der ikke er flere cifre at flytte ned, stopper algoritmen. Ellers vender vi tilbage til trin 1 og udfører den næste iteration.

Eksempler

Find kvadratroden af 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 Algoritmestop: Svar 12.34

Binært talsystem

Denne sektion bruger formalismen i sektionen Beregning af ciffer for ciffer , med mindre ændringer, at , og hver er lig med eller . Nu gennemgår vi alt fra ned til og bygger en tilnærmet løsning som summen af alle , som vi finder en værdi for. For at bestemme om eller er lig med , tager vi . Hvis (det vil sige kvadratet af vores tilnærmelse inklusive ikke overstiger det oprindelige kvadrat), så sætter vi , ellers sætter vi og . For at undgå kvadrering ved hvert trin gemmer vi forskellen og opdaterer den ved hver iteration ved at indstille c . I første omgang satte vi efter den største med . $N^{2}=(a_{n}+\dotsb +a_{0})^{2}$ $er$ $2^{m}$ $0$
$2^{m}$ $2^{n}$ $2^0$ ${\displaystyle P_{m}=a_{n}+a_{n-1}+\ldots +a_{m))$ $a_{i}$
$er$ $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$ $(2^{n})^{2}=4^{n}\leqslant N^{2}$

Som en yderligere optimering gemmer vi og , to udtryk i tilfældet, når de ikke er nul, i separate variable , : $P_{m+1}2^{m+1}$ $(2^{m})^{2}$ $Å_{m}$ $er$ ${\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))$ og kan opdateres effektivt ved hvert trin: ${\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æg mærke til det

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

, som er slutresultatet returneret af funktionen nedenfor.

Implementering af algoritmen i C-sprog [10] :

int32_t isqrt(int32_tn) { assert(("inputværdi skal være ikke-negativ", n > 0)); int32_t x = n; // int32_t c = 0; // // starter med den højeste potens af fire <= n

X_{{n+1}}

c_n

d_{n}

int32_t d = 1 << 30; // Indstil den næstmest signifikante bit til 1. // Samme som ((usigneret)INT32_MAX + 1) / 2. mens (d > n) d >>= 2; while (d != 0) // for { 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})

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

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

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

} retur c; //

c_{{-1}}

}

Det er muligt at implementere en hurtigere algoritme i både binær og decimal notation, hvis tabeller bruges til udvælgelse, det vil sige, at implementeringen af princippet om at bruge mere hukommelse reducerer eksekveringstiden [11] .

Eksponentiel identitet

Lommeregnere implementerer normalt gode eksponentielle og naturlige logaritmeprogrammer . Beregningen af kvadratroden S udføres derefter ved hjælp af egenskaberne for logaritmer ( ) og eksponentialer ( ): $\ln x^{n}=n\ln x$ $e^{\ln x}=x$

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

Brøkens nævner svarer til den n'te rod. I vores tilfælde er nævneren 2. Den samme identitet bruges til at beregne kvadratroden ved hjælp af tabeller med logaritmer eller diasregler .

En iterativ metode med to variable

Denne metode er anvendelig til at finde kvadratroden af og konvergerer bedst for . Dette er dog ikke en væsentlig begrænsning for beregning på computere, da det i flydende- og fastpunktsrepræsentationer af binære tal er trivielt at gange med en heltalspotens på 4 og derefter korrigere til den ønskede potens af 2 ved at ændre henholdsvis eksponenten eller skiftet. Den kan således flyttes indenfor . Desuden bruger metoden nedenfor ikke generelle divisioner, men kun addition, subtraktion, multiplikation og division med en potens af to. Den sidste af disse handlinger er trivielt implementeret. Ulempen ved metoden er fejlakkumulering, i modsætning til iterative metoder med én variabel som babylonsk. $0<S<3\,\!$ $S\approx 1$ $S\,\!$ ${\sqrt {S))$ $S\,\!$ ${\frac {1}{2}}\leqslant S<2$

Metodens indledende trin

a_{0}=S\,\!

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

Iterative trin

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

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

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

Bemærk, at konvergens , og derfor , er kvadratisk. $c_{n}\,\!$ $a_{n}\,\!$

Beviset for metoden er ret simpelt. Vi omskriver først den iterative definition som $c_{n}\,\!$

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

Nu, frontalt, er det bevist det

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

og derfor sikres konvergensen til det ønskede resultat ved konvergensen til 0, som igen følger af . $a_{n}\,\!$ ${\sqrt {S))$ $c_{n}\,\!$ $-1<c_{0}<2\,\!$

Denne metode blev udviklet omkring 1950 af M. W. Wilks , D. J. Wheeler og S. Gill [12] til brug i EDSAC , en af de første elektroniske computere [13] . Senere blev metoden generaliseret til ikke-kvadratrødder [14] .

Iterative metoder til at beregne den reciproke af kvadratroden af et tal

Følgende er iterative metoder til at beregne den reciproke af kvadratroden af S , dvs. Hvis en sådan værdi findes, finder vi den blot ved at gange: . Disse iterationer bruger kun multiplikation og bruger ikke divisioner. Fordi metoderne er hurtigere end den babylonske metode . Metoderne er dog ustabile, hvis startværdien ikke er tæt på den reciproke af rodværdien, divergerer iterationerne. Derfor kan det være en fordel først at iterere med den babylonske metode for at få et groft skøn over roden, før man begynder at bruge disse metoder. $1/{\sqrt {S}}$ ${\sqrt {S))$ ${\sqrt {S}}=S\cdot (1/{\sqrt {S}})$

Anvendelse af Newtons metode på ligningen giver en metode, der konvergerer kvadratisk og bruger tre multiplikationer på hvert trin: $(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 anden iteration fås fra Halley-metoden , som er Householder-metoden af anden orden. Metoden konvergerer kubisk , men bruger fem multiplikationer per iteration: $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 arbejder med fastpunkttal , kan multiplikation med 3 og division med 8 implementeres ved skift og additioner. Når man arbejder med flydende komma, kan Halleys metode reduceres til fire multiplikationer per iteration ved at forudberegne og justere alle andre konstanter for at kompensere: ${\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 algoritme

Nogle computere bruger Goldschmidt-algoritmen til at beregne og samtidig . Goldschmidt-algoritmen finder hurtigere end Newton-Rapson-iterationen på computere med delte multiplikations-add- operationer og enten en pipelinet flydende komma-processor eller to uafhængige flydende komma-processorer [15] . ${\sqrt {S))$ $1/{\sqrt {S}}$ ${\sqrt {S))$

Den første måde at skrive Goldschmidt-algoritmen på starter med

b_{0}=S

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

(normalt bruges tabelopslag)

y_{0}=Y_{0}

x_{0}=Sy_{0}

og gentagelser udføres

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

indtil det er tæt nok på 1 eller et fast antal iterationer er blevet udført. Iterationerne konvergerer til $b_{i}$

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

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

Bemærk, at du kan udelade beregningen af eller , og hvis begge ønskes, kan du bruge det til sidst i stedet for at evaluere ved hver iteration. $x_{n}$ $y_{n}$ $x_{n}=Sy_{n}$

Den anden metode, der bruger de kombinerede multiplikations-additionsoperationer , starter med

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

(normalt bruges tabelopslag)

x_{0}=Sy_{0}

h_{0}=y_{0}/2

og gentagelser udføres

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

indtil den kommer tæt nok på 0, eller der udføres et fast antal iterationer. Værdierne konvergerer til $r_{i}$

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

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

Taylor-serien

Hvis N er en tilnærmelse til , kan den bedste tilnærmelse findes ved at bruge Taylor - serien af kvadratrodsfunktionen : ${\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\venstre(1+{\frac {d}{2N ^{2))}-{\frac {d^{2}}{8N^{4}}}+{\frac {d^{3}}{16N^{6}}}-{\frac {5d ^{4}}{128N^{8}}}+\cdots \right)

Konvergensrækkefølgen er lig med antallet af termer, der bruges i serien. Når man bruger to udtryk, svarer metoden til den babylonske metode . Når du bruger tre udtryk, bruger hver iteration næsten lige så mange operationer, som Bakhshali-tilnærmelsen bruger , men konvergensen er svagere. Derfor er denne metode ikke en særlig effektiv beregningsmetode. For at maksimere konvergenshastigheden bør N vælges til at være så lille som muligt. ${\frac {|d|}{N^{2))}\,$

Fortsat brøkudvidelse

Kvadratiske irrationaliteter (tal af formen , hvor a , b og c er heltal), og især kvadratrødder af heltal, har periodiske fortsatte brøker . Nogle gange er målet ikke at finde den numeriske værdi af kvadratroden, men at udvide den til en fortsat brøk , og dermed dens rationelle tilnærmelse. Lad S være et positivt tal, hvis rod skal findes. Lad nu a være den indledende tilnærmelse og r være resten, så kan vi skrive Da vi har , kan vi udtrykke kvadratroden af 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}}}}.

Ved at anvende dette udtryk for på nævneren af brøken 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ælleren/nævneren for den fortsatte brøkudvidelse (se venstre) er svær at skrive ned og også svær at passe ind i det eksisterende dokumentformateringssystem. Af denne grund er der udviklet en speciel notation til kompakt at repræsentere heltal og periodiske dele af fortsatte brøker. En sådan konvention bruger den leksikalske "stiplede linje" til at repræsentere stregen mellem tælleren og nævneren, hvilket gør det muligt at skrive brøken vandret i stedet for lodret:

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

Her er hvert vandret streg (i brøk) repræsenteret af tre streger - to lodrette og et vandret, som adskilles fra . $r$ $2a$

En endnu mere kompakt notation har en særlig form

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

For periodiske fortsatte brøker (som alle er kvadratrødder) er den gentagne del kun angivet én gang med en streg over den gentagne del:

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

For √ 2 er værdien 1, så repræsentationen bliver $-en$

[1;{\overline {2}}]

Ved at følge denne vej får vi den generaliserede fortsatte brøk for kvadratroden ${\sqrt {S}}=a+{\cfrac {r}{2a+{\cfrac {r}{2a+{\cfrac {r}{2a+\ddots ))))))$

Det første trin i at beregne en sådan brøk for at opnå en kvadratrod er at erstatte roden og vælge antallet af nævnere. For eksempel er i kanonisk form 1 og for √ 2 er 1, så den numeriske fortsatte brøk for 3 nævnere er $r$ $-en$

{\sqrt {2}}\ca. 1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}

Trin 2. Den fortsatte brøk rulles op, én nævner ad gangen, for at få en rationel brøk, hvis tæller og nævner er hele tal. Foldeprocessen ser derefter sådan ud (med de første tre nævnere):

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

Til sidst (trin 3) dividerer vi tælleren med nævneren af den rationelle brøk for at få en tilnærmelse af roden:

17\div 12=1{,}42

afrundet til tre decimaler.

Den reelle værdi af roden √ 2 er 1,41 til tre signifikante cifre. Den relative fejl er 0,17 %, så en rationel brøk er god til næsten tre decimaler. Tager vi flere nævnere, får vi en konsekvent forbedring i tilnærmelsen - fire nævnere giver en brøk , hvilket giver næsten 4 cifres nøjagtighed osv. ${\frac {41}{29}}=1{,}4137$

Fortsatte brøker er tilgængelige i tabeller for mindst små tal og velkendte konstanter. For vilkårlige tal i decimalnotation er forudberegnede værdier højst sandsynligt ubrugelige. Følgende tabel over små rationelle fraktioner, kaldet konvergenter , er afledt af kanoniske fortsatte fraktioner for flere konstanter:

√S _	fortsatte skud	~decimal	Egnede 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))$

Bemærk: Alle relevante brøker er opført op til nævneren 99.

Generelt gælder det, at jo større nævneren af en rationel brøk er, jo bedre er tilnærmelsen. Det kan også vises, at afskæring af en fortsat brøk resulterer i en rationel brøk, med en bedre tilnærmelse til roden af enhver brøk med en nævner mindre end eller lig med den brøks nævner. For eksempel er ingen brøk med en nævner mindre end 70 så god som 99/70 , der tilnærmer √2 .

Lukes sekvensmetode

Lucas-sekvensen af den første slags er defineret af den rekursive relation $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{ellers}}\end{cases}}$

og dets karakteristiske polynomium er

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

, det har en diskriminant og rødder $D=P^{2}-4Q$

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

Alt dette giver følgende positive værdi

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

. Så hvis vi ønsker at få , kan vi vælge og og derefter beregne ved hjælp af og for store værdier . Den mest effektive måde at beregne og − ${\sqrt {a}}$ $P=2$ $Q=1-a$ $x_{1}=1+{\sqrt {a))$ $U_{n+1}$ $U_{n}$ $n$ $U_{n+1}$ $U_{n}$

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

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

og derefter kl : $n\til\infty$

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

Approksimationer afhængige af flydende komma-repræsentation

Tallet er repræsenteret som et flydende kommatal som . Dette notationsformat kaldes også eksponentiel notation . Kvadratroden af dette tal er lig , og lignende formler kan præsenteres for terningrødder og logaritmer. Dette forenkler ikke opgaven, men hvis der kun kræves en tilnærmelse, så er det et godt skøn over rækkefølgen af mantissen. Yderligere forstår vi, at nogle potenser af p kan vise sig at være ulige, så i stedet for at arbejde med brøkpotenser af grundfladen, multiplicerer vi med den og trækker en fra graden, så den bliver lige. Den raffinerede repræsentation konverteres til , så kvadratroden bliver . ${\displaystyle m\time b^{p))$ ${\sqrt {m}}\ gange b^{\tfrac {p}{2}}$ $b^{\tfrac {p}{2))$ ${\displaystyle 3141{,}59=3{,}14159{\times }10^{3))$ ${\displaystyle 31{,}4159{\times }10^{2))$ ${\sqrt {31.4159}}{\times }10^{1}$

Hvis kun den heltallige del af mantissen tages, kan den tage værdier fra 1 til 99, og dette kan bruges som et indeks i en tabel med 99 forudberegnede rødder for at fuldende estimatet. En computer, der bruger hexadecimal base, kan kræve en større tabel, men ved brug af base 2 vil tabellen kun bestå af tre værdier - de mulige bits af heltalsdelen af den raffinerede repræsentation af mantissen kan være 01 (hvis eksponenten er lige, så der er ingen forskydning, og bemærk, at det normaliserede antal flydende komma altid har et højt ciffer, der ikke er nul), eller hvis eksponenten var ulige, 10 eller 11, er disse de første to bits af den oprindelige mantisse. Så normaliseres 6,25 (= 110,01 i binært) til en lige potens, så mantissebitparret er 01, mens 0,625 (= 0,101 i binært) normaliseres til en ulige potens, så der kræves en talkonvertering til , og derefter bitparret vil være 10. Bemærk, at den mindst signifikante bit af rækkefølgen afspejles i den mest signifikante bit af mantissen grupperet i par. En lige eksponent har den mindst signifikante bit af nul, og quad-mantissen vil starte ved nul, mens en ulige eksponent vil have et 1 i den mindst betydende bit, og quad-mantissen vil starte ved 1. Så når eksponenten er halveret, er den svarende til at flytte den mindst signifikante bit af eksponenten til den første bit af den parvis grupperede mantisse. $1{,}1001\ gange 2^{2}$ $1{,}01\ gange 2^{-1}$ $10{,}1\ gange 2^{-2}$

Et bord med tre elementer kan udvides til at omfatte yderligere mantissebits. Men når det drejer sig om computere, er det i stedet for at beregne interpolationen i en tabel ofte bedre at kigge efter en enklere måde at regne på, der giver de samme resultater. Alt afhænger nu af de nøjagtige detaljer i talrepræsentationsformatet og af de operationer, der er tilgængelige for at få dele af nummeret og arbejde med dem. Fortran indeholder for eksempel en funktion EXPONENT(x)til at opnå en grad. Den indsats, der bruges på at få en god indledende tilnærmelse, betaler sig ved at eliminere de yderligere gentagelser af forfiningsprocessen, der ville være påkrævet i tilfælde af en dårlig tilnærmelse.

Mange computere følger IEEE floating point-standarden (eller en ret tæt repræsentation), og en meget hurtig kvadratrodstilnærmelse kan opnås som udgangspunkt for Newtons metode. Teknikken til denne tilnærmelse stammer fra det faktum, at det flydende talformat (grundtal 2) tilnærmer sig basis 2-logaritmen. Det vil sige, $\log _{2}(m\ gange 2^{p})=p+\log _{2}(m)$

Så for et 32-bit IEEE flydende kommatal (hvor eksponenten har en offset på 127 [16] ), kan du få en omtrentlig logaritme ved at fortolke tallet som et 32-bit heltal, gange det med og subtrahering af forskydningen 127, dvs $2^{-23}$

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

For eksempel er tallet 1,0 i hexadecimal 0x3F800000, som kan repræsenteres som, når det ses som et heltal. Ved at bruge ovenstående formel får du som forventet fra . På samme måde får du 0,5 ud af 1,5 (=0x3FC00000). $1065353216=127\cdot 2^{23}$ $1065353216\cdot 2^{-23}-127=0$ $\log _{2}(1{,}0)$

For at få kvadratroden skal du dividere logaritmen med 2 og konvertere resultatet tilbage. Nedenstående program demonstrerer ideen. Bemærk, at den mindst signifikante bit af eksponenten er bevidst oversat til mantissen. En måde at retfærdiggøre trinene i dette program, forudsat at det er forskydningen af graden, og er antallet af lagrede bits i mantissen, er at bevise $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}.

/* Antag, at det flydende tal er i IEEE 754-format */ #include <stdint.h> float sqrt_approx ( float z ) { union { flyde f ; uint32_t i ; } val = { z }; /* Konverter typen uden at ændre bitrepræsentationen */ /* * Bevis at * ((((val.i / 2^m) - b) / 2) + b) * 2^m = ((val.i - 2^m) / 2) + ((b + 1) / 2) * 2^m) * hvor * b = effektforskydning * m = antal bits i mantisse */ val . i -= 1 << 23 ; /* Træk 2^m fra. */ val . i >>= 1 ; /* Divider med 2. */ val . i += 1 << 29 ; /* Tilføj ((b + 1) / 2) * 2^m. */ returværdi . _ f ; /* Fortolk som float igen */ }

De tre regneoperationer, der udgør kernen i funktionen, kan repræsenteres på én linje. En yderligere forfining kan tilføjes for at reducere den maksimale relative fejl. Således kan de tre operationer, ikke inklusive reduktionen til reel, omskrives som

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

hvor a er en offset for at reducere tilnærmelsesfejl. For eksempel, med a = 0 er resultaterne nøjagtige for lige potenser af 2 (f.eks. 1,0), men for andre tal vil resultatet være noget stort (f.eks. 1,5 for 2,0 i stedet for 1,414... med en 6% fejl). For a = −0x4B0D2 reduceres den maksimale relative fejl til ±3,5 %.

Hvis tilnærmelsen skal bruges som startværdi for Newtons metode i ligningen , så er den inverse form vist i næste afsnit at foretrække. $(1/x^{2})-S=0$

Den gensidige af kvadratroden

En variant af ovenstående fremgangsmåde er præsenteret nedenfor og kan bruges til at beregne det omvendte af kvadratroden, dvs. Denne variant er skrevet af Greg Walsh. Skifttilnærmelsen giver en relativ fejl på mindre end 4 % og fejlen reduceres til 0,15 % efter én iteration af Newtons metode [17] . I computergrafik er dette en meget effektiv måde at normalisere en vektor på. $x^{-{1 \over 2}}$

float invSqrt ( float x ) { float xhalv = 0,5f * x ; union { flyde x ; int i ; } u ; u . x = x ; u . i = 0x5f375a86 - ( u . i >> 1 ); /* Den næste linje kan gentages et vilkårligt antal gange for at øge præcisionen */ u . x = u . x * ( 1,5f - xhalv * u . x * u . x ); returnere u . x ; }

Nogle VLSI implementerer at finde den reciproke af kvadratroden ved hjælp af et polynomieestimat efterfulgt af Goldschmidt iteration [18] .

Roden af et negativt eller komplekst tal

Hvis , så er dens hovedrod lig med $S<0$

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

Hvis , hvor a og b er reelle tal og , Så er dens hovedrod lig med $S=a+bi$ $b\neq 0$

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

Dette kan kontrolleres ved at kvadrere [19] [20] . Her

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

er modulet af tallet S . Hovedroden af et komplekst tal er defineret som en rod med en ikke-negativ reel del.

Se også

Algoritme alpha max plus beta min
heltals kvadratrod

Noter

↑ Ud over hovedroden er der en negativ kvadratrod, der i absolut værdi er lig med hovedroden, men med det modsatte fortegn, undtagen i tilfælde af nul, hvor der er to identiske nulrødder.
↑ Faktorer to og seks bruges, fordi de tilnærmer den geometriske middelværdi af de nedre og øvre mulige værdier med et givet antal cifre: og . ${\sqrt {{\sqrt {1}}\cdot {\sqrt {10}}}}={\sqrt[{4}]{10}}\ca. 1{,}78\,$ ${\sqrt {{\sqrt {10}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{1000}}\ca. 5{,}62\,$
↑ Det uafrundede estimat har en maksimal absolut fejl på 2,65 ved punkt 100 og en maksimal relativ fejl på 26,5 % ved punkt y=1, 10 og 100
↑ Hvis tallet er nøjagtigt halvvejs mellem to kvadrater, f.eks. 30,5, tag det største tal, som i vores tilfælde er 6
↑ Dette er ligningen for tangentlinjen til y=x 2 i punktet y=1.
↑ Fowler og Robson 1998 , s. 376.
↑ Heath, 1921 , s. 323-324.
↑ Bailey, Borwein, 2012 , s. 646-657.
↑ Bucking down til Bakhshali-manuskriptet . Simply Curious blog (5. juni 2018). Hentet 21. december 2020. Arkiveret fra originalen 26. oktober 2020. (ubestemt)
↑ Hurtig heltal kvadratrod af Mr. Woo's abacus-algoritme (arkiveret)
↑ Heltals kvadratrodsfunktion . Hentet 30. december 2021. Arkiveret fra originalen 30. september 2007. (ubestemt)
↑ Wilkes, Wheeler, Gill, 1951 .
↑ Campbell-Kelly, 2009 .
↑ Gower, 1958 , s. 142-143, 1958.
↑ Markstein, Peter (november 2004). Softwaredivision og kvadratrod ved hjælp af Goldschmidts algoritmer (PDF) . 6. konference om reelle tal og computere . Dagstuhl , Tyskland. CiteSeerX 10.1.1.85.9648 . Arkiveret (PDF) fra originalen 2022-04-28 . Hentet 2021-12-30 . Forældet parameter brugt |deadlink=( hjælp )
↑ 127 tilføjes til tallets eksponent, hvilket gør det muligt at tolke eksponenten som et tal uden fortegn.
↑ Fast Inverse Square Root Arkiveret 6. februar 2009 på Wayback Machine af Chris Lomont
↑ "Højhastighedsdobbeltpræcisionsberegning af gensidig, division, kvadratrod og omvendt kvadratrod" af José-Alejandro Piñeiro og Javier Díaz Bruguera 2002 (abstrakt)
↑ Abramowitz, Stegun, 1964 , s. 17.
↑ Cooke, 2008 , s. 59.

Litteratur

David Fowler, Eleanor Robson. Square Root Approximations in Old Babylonian Mathematics: YBC 7289 in Context // Historia Mathematica. - 1998. - T. 25 , no. 4 . - doi : 10.1006/hmat.1998.2209 .
Thomas Lille Hede . En historie om græsk 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 , no. 8 .
Miltonn Abramowitz, Irene A. Stegun. Afsnit 3.7.26 // Håndbog i matematiske funktioner med formler, grafer og matematiske tabeller . - Courier Dover Publications, 1964. - S. 17. - ISBN 978-0-486-61272-0 .
JC Gower. En note om en iterativ metode til rodudvinding // Computer Journal. - 1958. - T. 1 1 , Nr. 3 .
M. Campbell-Kelly. Origin of Computing // Scientific American. - 2009. - September.
Roger Cooke. Klassisk algebra: dens natur, oprindelse og anvendelser . - John Wiley and Sons, 2008. - ISBN 978-0-470-25952-8 .
MV Wilkes, DJ Wheeler, S. Gill. Udarbejdelse af programmer til en elektronisk digital computer. — Addison-Wesley, 1951.

Metoder til beregning af kvadratrødder

Indledende score

Decimalscore

Binær evaluering

Babylonsk metode

Eksempel

Konvergens

Bakhshali-metoden

Eksempel

Nummer efter nummer

Grundlæggende princip

Decimaltalssystem

Binært talsystem

Eksponentiel identitet

En iterativ metode med to variable

Iterative metoder til at beregne den reciproke af kvadratroden af ​​et tal

Goldschmidts algoritme

Taylor-serien

Fortsat brøkudvidelse

Lukes sekvensmetode

Approksimationer afhængige af flydende komma-repræsentation

Den gensidige af kvadratroden

Roden af ​​et negativt eller komplekst tal

Se også

Noter

Litteratur

Referencer Weisstein, Eric W. Kvadratrodsalgoritmer (engelsk) på Wolfram MathWorld- webstedet .

Iterative metoder til at beregne den reciproke af kvadratroden af et tal

Roden af et negativt eller komplekst tal