Bedste svar
1. metode
= UNICHAR (8730) giver kvadratrodsymbolet i Microsoft Excel.
Testet i Excel 2016
2. metode
- Gå til Indsæt fane og klik på Symbolet fra Symbolgruppen.
- Vælg matematiske operatører fra undersæt under symboler, og brug kvadratrodsymbolet.
Svar
De fleste moderne CPUer leverer en kvadratrodoperation indbygget. Så med et typisk programmeringssprog på typisk moderne hardware, er det næsten helt sikkert, hvad operationen i sidste ende vil være.
Så lad os tale om den metode, som næsten alle moderne almindelige CPUer bruger.
Nummerrepræsentation
Det første, vi skal forstå, er, hvordan en computer faktisk repræsenterer den slags tal, vi taler om. De er gemt i en slags videnskabelig notation.
Nu den slags videnskabelige notation, som du måske er fortrolig med, hvor et tal som -134,5 er repræsenteret som -1.345 \ gange 10 ^ {2}.
Ethvert tal, der ikke er nul, kan repræsenteres i denne form, som konceptuelt har tre dele: -tegnet (det vil sige tallet er positiv eller negativ), mantissa (et tal mellem 1 og 10 inklusive 1 men ikke inklusive 10, i dette tilfælde 1.345) og eksponent (den effekt, som radixen hæves til, i dette tilfælde 2; bemærk, at eksponenten kan være negativ eller generelt nul).
Repræsentationen at næsten alle moderne computere bruger er meget ens, bortset fra at antallet er gemt ved hjælp af en binær repræsentation snarere end en decimal. Så ignorerer tegnbit og nul (da det at finde kvadratroden af nul er trivielt, og kvadratroden af et negativt tal ikke er et reelt tal), gemmes positive tal faktisk i form m \ gange 2 ^ {e} hvor m er et tal mellem 1 og 2 (inklusive 1, men ikke inklusive 2).
Denne repræsentation kaldes “flydende punkt” på grund af den måde, du kan flytte det binære punkt (analogt med decimaltegn, som du måske kender) rundt ved at justere eksponenten.
Årsagen til, at alt dette er vigtigt, er, at CPUen bruger repræsentationen til at beregne kvadratrødder. Antag at eksponenten er jævn. Derefter:
\ sqrt {m \ times 2 ^ {2 \ epsilon}} = \ sqrt {m} \ times 2 ^ {\ epsilon}
Tilsvarende, hvis eksponenten er ulige, så:
\ sqrt {m \ times 2 ^ {2 \ epsilon + 1}} = \ sqrt {2} \ sqrt {m} \ times 2 ^ {\ epsilon}
Husk, at m er i området [1,2]. Dette betyder, at vi har reduceret problemet til beregning af kvadratroden af et hvilket som helst tal til en af beregningen af kvadratroden af et tal i det område. Eller hvis vi ikke vil beregne \ sqrt {2} på forhånd, et tal i området [1,4]. Uanset hvad har vi dramatisk forenklet problemet, fordi vi nu kan bruge metoder, der opfører sig godt i det række af tal.
Multiplikation og division
Så nu vi er nået så langt, tror du måske (hvis du har kigget på de andre svar), at løsningen nu er at bruge en metode som Newton-Raphson-iteration til at beregne kvadratet rod. For at beregne kvadratroden af n skal du vælge et indledende gæt x\_0 og gentage det:
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ right)
Dette svar er forkert . Det er ikke forkert, fordi det giver dig et korrekt svar. Men det er forkert, fordi ingen selvrespekterende CPU-designer (eller nogen biblioteksforfatter, hvis de skulle implementere det i software), ville implementere floating-point kvadratroden på denne måde.
Opdelingen med to er meget billig operation i binær (som, husk, er base 2, så det skifter bare det binære punkt et sted). Den anden division er imidlertid en meget dyr operation, og i dette tilfælde skal du udføre operationen flere gange.
Division er faktisk så dyr, at moderne CPUer bruger en iterativ algoritme, der er ens til (men faktisk ikke) Newton-Raphson iteration at udføre division! Det er klart, at vi ikke ønsker at gøre dette i hardware, i en indre sløjfe.
På moderne computerhardware er det meget billigere at udføre en multiplikationsoperation end en divisionsoperation. Årsagen til det er lidt kompleks at forklare; det har at gøre med det faktum, at vi kan passe langt flere transistorer på en chip, end vi plejede at være i stand til, og multiplikation er et problem, som du effektivt kan flytte til mange transistorer. Slå Wallace træer op, hvis du er interesseret i detaljerne.
I hvert fald er pointen, at multiplikation er en forholdsvis billig operation. Så hvis vi kan implementere kvadratroden i form af multiplikation snarere end division, ville dette være bedre.
Newton-Raphson, tag to
Nu kommer den første nøgleindsigt: I stedet for at beregne kvadratroden skal du beregne gensidig af kvadratroden. I stedet for \ sqrt {n} skal du beregne \ frac {1} {\ sqrt {n}}. Det viser sig, at dette er et langt lettere nummer at beregne, og hvis du har brug for kvadratroden, skal du gange dette tal med n, og du er færdig.
Newton-Raphson-metoden til gensidig kvadratrod ser sådan ud . Hvis x\_0 er et indledende skøn til \ frac {1} {\ sqrt {n}}, skal du gentage:
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3 – n {x\_i} ^ 2 \ right)
Igen er divisionen med to ret billige, og alt andet er multiplikation og addition / subtraktion.
Dette er en fantastisk måde at implementere det i software. Desuden er det værd at påpege, at den gensidige kvadratrode faktisk er mere nyttig end kvadratroden i mange praktiske situationer (f.eks. Normalisering af en vektor ved hjælp af Pythagoras sætning), da at dividere med en kvadratrod er mindre effektiv end at multiplicere med en gensidig kvadrat root.
Sådan implementeres det dog normalt ikke i hardware.
Goldschmidts algoritme
Vi kan nu se på Goldschmidts algoritme, der beregner kvadratroden og den gensidige kvadratrod sammen.
Givet b\_0 = n, hvis vi kan finde en række tal Y\_i sådan, at b\_n = b\_0 { Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2 nærmer sig 1, så nærmer y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} \ frac {1} {\ sqrt {b\_0}} og x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} nærmer sig \ sqrt {b\_0}.
Serien, som vi bruger, er i det væsentlige Newton-Raphson opdateringstrin:
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3 – b\_i) \ end {align *}
Og så kan vi holde styr på kvadratroden:
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
Og den gensidige kvadratrod:
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
Men hvis vi holder styr på x\_i og y\_i, skal du observere, at b\_i = x\_ {i-1} y\_ {i-1}. Så vi behøver faktisk aldrig holde styr på b\_i:
\ begin {align *} Y\_i & = \ frac {1} {2} \ left (3 – b\_i \ right) \\ & = 1 + \ frac {1} {2} \ left (1 – b\_i \ right) \\ & = 1 + \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right ) \ end {align *}
Og nu skal vi heller ikke holde styr på Y\_i:
\ begin {align *} x\_i & = x\_ {i-1} \ venstre (1 + \ frac {1} {2} \ venstre (1 – x\_ {i-1} y\_ {i-1} \ højre) \ højre) \\ & = x\_ {i-1} + x\_ {i- 1} \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \\ y\_i & = y\_ {i-1} \ left (1 + \ frac {1 } {2} \ venstre (1 – x\_ {i-1} y\_ {i-1} \ højre) \ højre) \\ & = y\_ {i-1} + y\_ {i-1} \ frac {1} { 2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ end {align *}
Der er nogle overflødige beregninger her, som vi kan fjerne, hvilket antyder følgende algoritme. Givet Y som en tilnærmelse til \ frac {1} {\ sqrt {n}}, skal du indstille:
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
Derefter gentages:
\ begin {align *} r\_i & = \ frac {1} {2} \ left (1 – x\_i y\_i \ right) \\ x\_ {i +1} & = x\_i + x\_i r\_i \\ y\_ {i + 1} & = y\_i + y\_i r\_i \ end {align *}
Selvom delingen med to er billig, kan vi også undgå det ved at holde styr på h\_i = \ frac {1} {2} y\_i i stedet for y\_i. Dette er Goldschmidts algoritme.
Antag at Y er en tilnærmelse til \ frac {1} {\ sqrt {n}}. Sæt:
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
Herefter gentages:
\ start {align *} r\_i & = \ frac {1} {2} – x\_i h\_i \\ x\_ {i + 1} & = x\_i + x\_i r\_i \\ h\_ {i + 1} & = h\_i + h\_i r\_i \ end {align *}
Så konvergerer x\_i til \ sqrt {n} og h\_n konvergerer til \ frac {1} {2 \ sqrt {n}}.
Implementering af dette i hardware
Indtil videre så godt. Det er bestemt en meget simpel algoritme. Men hvorfor er det bedre?
Moderne CPUer har ofte et hurtigt kredsløb, der udfører en optimeret multiplicere-akkumulere operation , ofte kaldet fusioneret multiplicere- tilføj, eller FMA for kort. Hvis du har slået henvisningen til Wallace-træer op tidligere, skal det være klart for dig, hvordan FMA måske er næsten lige så effektiv som en lige multiplikationsoperation.
FMA er en af de mest nyttige primitiver at have. Hvis du f.eks. Har brug for at evaluere et polynom:
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
kan du bruge Horners regel, som i det væsentlige er en flok FMAer:
\ begin {align *} p\_ {n-1} & = a\_ {n-1} + x a\_n \\ p\_ {n-2} & = a\_ {n-2} + x p\_ {n-1} \\ & \ vdots \\ p\_1 & = a\_1 + x p\_2 \\ p\_0 & = a\_0 + x p\_1 \ end {align *}
Den indre sløjfe i Goldschmidts algoritme er tre FMAer og intet andet.Derfor er det en fordel: du har kun brug for en slags kredsløb (muligvis kun et kredsløb; bemærk at de to anden FMAer er uafhængige og så kan drage fordel af rørledning) plus nogle kontrollogik til at implementere alt. Og det er et kredsløb, der er nyttigt i mange andre operationer, så du spilder ikke meget hardware bare på kvadratroden.
Det næstsidste stykke af puslespillet er, hvordan man får en god initial estimat, og det korte svar er, at den bedste metode er at bruge en tabelopslag. Selv et bord i beskeden størrelse, fordi vi kun leder efter kvadratrødder i et så lille område, er ret effektivt.
Det sidste stykke af puslespillet er: Hvordan ved vi, når vi er færdige? iterating? Og svaret på det er, at vi kender nøjagtigheden af de tal, vi bruger, og hvor godt det oprindelige skøn er. Ud fra det kan vi beregne det maksimale antal iterationer, der kræves på forhånd. Så vi sløjfer faktisk ikke som sådan, vi laver bare iteration et fast antal gange.