Beste svaret
1. metode
= UNICHAR (8730) gir kvadratrotsymbolet i Microsoft Excel.
Testet i Excel 2016
2. metode
- Gå til Sett inn fane og klikk på Symbolet fra Symbolgruppen.
- Under Symbols velger du matematiske operatører fra delmengde og bruker Square root-symbolet.
Svar
De fleste moderne CPUer gir en kvadratrotoperasjon naturlig. Så med et typisk programmeringsspråk på typisk moderne maskinvare, er det nesten helt sikkert det operasjonen til slutt vil være.
Så la oss snakke om metoden som nesten alle moderne allmeny-CPUer bruker.
Antallrepresentasjon
Det første vi trenger å forstå er hvordan en datamaskin faktisk representerer den slags tall vi snakker om. De er lagret i en slags vitenskapelig notasjon.
Nå den typen vitenskapelige notasjon som du kanskje er kjent med der et tall som -134,5 er representert som -1,345 \ ganger 10 ^ {2}.
Ethvert tall som ikke er null kan vises i denne formen, som konseptuelt har tre deler: tegnet (det vil si tallet positiv eller negativ), mantissa (et tall mellom 1 og 10, inkludert 1, men ikke inkludert 10, i dette tilfellet 1.345), og eksponent (kraften som radixen heves til, i dette tilfellet 2; merk at eksponenten kan være negativ eller null generelt).
Representasjonen at nesten alle moderne datamaskiner bruker er veldig like, bortsett fra at tallet lagres ved hjelp av en binær representasjon i stedet for en desimal. Så ignorerer tegnbit og null (siden det å finne kvadratroten til null er trivielt, og kvadratroten til et negativt tall ikke er et reelt tall), blir positive tall faktisk lagret i form m \ ganger 2 ^ {e} hvor m er et tall mellom 1 og 2 (inkludert 1 men ikke inkludert 2).
Denne representasjonen blir referert til som «flytende punkt» på grunn av måten du kan flytte binærpunktet (analogt med desimaltegn som du kanskje er kjent med) rundt ved å justere eksponenten.
Årsaken til at alt dette er viktig er at CPU bruker representasjonen til å beregne kvadratrøtter. Anta at eksponenten er jevn. Deretter:
\ sqrt {m \ times 2 ^ {2 \ epsilon}} = \ sqrt {m} \ times 2 ^ {\ epsilon}
Tilsvarende, hvis eksponenten er rart, 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 betyr at vi har redusert problemet med å beregne kvadratroten til et hvilket som helst tall til en av beregningen av kvadratroten til et tall i det området. Eller hvis vi ikke vil beregne \ sqrt {2} på forhånd, et tall i området [1,4]. Uansett har vi dramatisk forenklet problemet, fordi vi nå kan bruke metoder som oppfører seg bra i det tallområdet.
Multiplikasjon og divisjon
Så nå som vi har kommet så langt, tenker du kanskje (hvis du har sett på de andre svarene) at løsningen nå er å bruke en metode som Newton-Raphson iterasjon for å beregne kvadratet rot. For å beregne kvadratroten til n, velg en første gjetning x\_0 og gjenta:
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ right)
Dette svaret er feil . Det er ikke galt ved at det gir deg et riktig svar. Men det er galt ved at ingen selvrespekterende CPU-designer (eller noen bibliotekskribent hvis de måtte implementere den i programvare) ville implementere floating-point kvadratrot på denne måten.
Divisjonen med to er veldig billig operasjon i binær (som, husk, er base 2, så det er bare å skifte binærpunktet ett sted). Den andre divisjonen er imidlertid en veldig kostbar operasjon, og i dette tilfellet må du utføre operasjonen flere ganger.
Divisjon er faktisk så dyr at moderne CPUer bruker en iterativ algoritme som er lik til (men ikke faktisk) Newton-Raphson iterasjon om å utføre divisjon! Det er klart at vi ikke ønsker å gjøre dette i maskinvare, i en indre sløyfe.
På moderne datamaskinvare er det mye billigere å utføre en multiplikasjonsoperasjon enn en divisjonsoperasjon. Årsaken til er litt komplisert å forklare; det har å gjøre med det faktum at vi kan plassere langt flere transistorer på en brikke enn vi pleide å være i stand til, og multiplikasjon er et problem at du kan bevege deg på mange transistorer effektivt. Slå opp Wallace-trær hvis du er interessert i detaljene.
I alle fall er poenget at multiplikasjon er en relativt billig operasjon. Så hvis vi kan implementere kvadratrotoperasjonen i form av multiplikasjon i stedet for divisjon, ville dette vært bedre.
Newton-Raphson, ta to
Nå kommer den første nøkkelinnblikket: I stedet for å beregne kvadratroten, må du beregne gjensidig av kvadratroten. I stedet for \ sqrt {n}, beregner du \ frac {1} {\ sqrt {n}}. Det viser seg at dette er et langt enklere tall å beregne, og hvis du trenger kvadratroten, multipliser dette tallet med n og du er ferdig.
Newton-Raphson-metoden for gjensidig kvadratrot ser slik ut . Hvis x\_0 er et første estimat til \ frac {1} {\ sqrt {n}}, gjentas:
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3 – n {x\_i} ^ 2 \ right)
Igjen er divisjonen med to ganske billig, og alt annet er multiplikasjon og addisjon / subtraksjon.
Dette er en fin måte å implementere det i programvare. Videre er det verdt å påpeke at den gjensidige kvadratroten faktisk er mer nyttig enn kvadratroten, siden det å dele med en kvadratrot er mindre effektiv enn å multiplisere med et gjensidig kvadrat. root.
Dette er imidlertid ikke slik det vanligvis implementeres i maskinvare.
Goldschmidts algoritme
Vi kan nå se på Goldschmidts algoritme, som beregner kvadratroten og den gjensidige kvadratroten sammen.
Gitt b\_0 = n, hvis vi finner en serie tall Y\_i slik at b\_n = b\_0 { Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2 nærmer seg 1, så y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} nærmer seg \ frac {1} {\ sqrt {b\_0}} og x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} vil nærme seg \ sqrt {b\_0}.
Serien vi bruker er egentlig den Newton-Raphson oppdateringstrinn:
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3 – b\_i) \ end {align *}
And så kan vi holde oversikt over kvadratroten:
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
Og den gjensidige kvadratroten:
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
Men hvis vi holder rede på x\_i og y\_i, må du observere at b\_i = x\_ {i-1} y\_ {i-1}. Så vi trenger faktisk aldri å holde rede 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 nå trenger vi heller ikke å holde rede på Y\_i:
\ begin {align *} x\_i & = x\_ {i-1} \ venstre (1 + \ frac {1} {2} \ venstre (1 – x\_ {i-1} y\_ {i-1} \ høyre) \ høyre) \\ & = 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} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ right) \\ & = y\_ {i-1} + y\_ {i-1} \ frac {1} { 2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ end {align *}
Det er noe overflødig beregning her, som vi kan fjerne, noe som foreslår følgende algoritme. Gitt Y som en tilnærming til \ frac {1} {\ sqrt {n}}, sett:
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
Så gjenta:
\ begynn {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 *}
Selv om divisjonen med to er billig, kan vi unngå det også ved å holde rede på h\_i = \ frac {1} {2} y\_i i stedet for y\_i. Dette er Goldschmidts algoritme.
Anta at Y er en tilnærming til \ frac {1} {\ sqrt {n}}. Sett:
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
Så gjenta:
\ begin {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 av dette i maskinvare
Så langt er det bra. Det er absolutt en veldig enkel algoritme. Men hvorfor er det bedre?
Moderne CPUer har ofte en rask krets som utfører en optimalisert multipliser-akkumuler-operasjon , ofte kalt smeltet multipliser add, eller FMA for kort. Hvis du har slått opp referansen til Wallace-trær tidligere, bør det være klart for deg hvordan FMA kan være nesten like effektiv som en rett multiplikasjonsoperasjon.
FMA er en av de mest nyttige primitivene å ha rundt. Hvis du trenger å evaluere et polynom, for eksempel:
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
kan du bruke Horners regel, som egentlig er en haug med FMA:
\ 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øyfen til Goldschmidts algoritme er tre FMA-er og ingenting annet.Det er derfor det er en fordel: du trenger bare en slags krets (muligens bare en krets; merk at de to andre FMA-ene er uavhengige og kan ha fordeler av rørledninger) pluss litt kontrolllogikk for å implementere alt. Og det er en krets som er nyttig i mange andre operasjoner, så du kaster ikke bort mye maskinvare bare på kvadratrotoperasjonen.
Det nest siste stykket i puslespillet er hvordan du får en god initial estimat, og det korte svaret er at den beste metoden er å bruke en tabelloppslag. Selv et beskjedent bord, fordi vi bare leter etter kvadratrøtter i et så lite område, er ganske effektivt.
Den siste biten i puslespillet er: Hvordan vet vi når vi er ferdige? gjentakende? Og svaret på det er at vi vet nøyaktigheten til tallene vi bruker, og hvor godt det opprinnelige estimatet er. Fra det kan vi regne ut det maksimale antallet gjentakelser som kreves på forhånd. Så vi slår faktisk ikke slik, vi gjør bare iterasjonen et fast antall ganger.