Cel mai bun răspuns
Prima metodă
= UNICHAR (8730) dă simbolul rădăcină pătrată în Microsoft Excel.
Testat în Excel 2016
A doua metodă
- Accesați Inserați fila și faceți clic pe Simbol din grupul Simboluri.
- Sub simboluri selectați Operatori matematici din subset și utilizați simbolul rădăcină pătrată.
Răspuns
Majoritatea procesoarelor moderne oferă o operație rădăcină pătrată în mod nativ. Deci, cu un limbaj de programare tipic pe hardware-ul modern tipic, aproape sigur va fi operația în cele din urmă.
Deci, să vorbim despre metoda pe care o folosesc aproape toate procesorii moderni de uz general.
Reprezentarea numerelor
Primul lucru pe care trebuie să îl înțelegem este modul în care un computer reprezintă de fapt tipul de numere despre care vorbim. Acestea sunt stocate într-un fel de notație științifică.
Acum, tipul de notație științifică cu care s-ar putea să fiți familiarizat cu un număr ca -134,5 este reprezentat ca -1,345 \ ori 10 ^ {2}.
Orice număr care nu este zero poate fi reprezentat în această formă, care are în mod conceptual trei părți: semnul (adică este numărul pozitiv sau negativ), mantissa (un număr între 1 și 10, inclusiv 1 dar neincluzând 10, în acest caz 1.345) și exponent (puterea la care este ridicată raza, în acest caz 2; rețineți că exponentul poate fi negativ sau zero în general).
Reprezentarea că aproape toate computerele moderne folosesc este foarte similar, cu excepția faptului că numărul este stocat folosind o reprezentare binară mai degrabă decât una zecimală. Deci, ignorând bitul de semn și zero (deoarece găsirea rădăcinii pătrate a lui zero este banală, iar rădăcina pătrată a unui număr negativ nu este un număr real), numerele pozitive sunt de fapt stocate sub forma m \ times 2 ^ {e} unde m este un număr între 1 și 2 (inclusiv 1, dar nu include 2).
Această reprezentare este denumită „virgulă mobilă”, datorită modului în care puteți muta punctul binar (analog cu punct zecimal cu care ați putea fi familiarizați) prin ajustarea exponentului.
Motivul pentru care toate acestea sunt importante este că CPU utilizează reprezentarea pentru a ajuta la calcularea rădăcinilor pătrate. Să presupunem că exponentul este egal. Apoi:
\ sqrt {m \ times 2 ^ {2 \ epsilon}} = \ sqrt {m} \ times 2 ^ {\ epsilon}
În mod similar, dacă exponentul este ciudat, apoi:
\ sqrt {m \ times 2 ^ {2 \ epsilon + 1}} = \ sqrt {2} \ sqrt {m} \ times 2 ^ {\ epsilon}
Amintiți-vă că m este în intervalul [1,2). Aceasta înseamnă că am redus problema la calcularea rădăcinii pătrate a oricărui număr la una din calcularea rădăcinii pătrate a unui număr din intervalul respectiv. Sau, dacă nu dorim să precomputăm \ sqrt {2}, un număr din intervalul [1,4). Oricum, am simplificat dramatic problema, deoarece acum putem folosi metode care se comportă bine în acea gamă de numere.
Înmulțirea și divizarea
Deci, acum că am ajuns până aici, s-ar putea să credeți (dacă ați analizat celelalte răspunsuri) că soluția este acum să utilizați o metodă precum iterația Newton-Raphson pentru a calcula pătratul rădăcină. Pentru a calcula rădăcina pătrată a lui n, alegeți o estimare inițială x\_0 și iterați:
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ right)
Acest răspuns este greșit . Ei bine, nu este greșit că vă va oferi un răspuns corect. Dar este greșit că niciun proiectant de CPU care se respectă (sau orice scriitor de bibliotecă dacă ar trebui să-l implementeze în software) nu ar implementa rădăcina pătrată în virgulă mobilă în acest fel.
Împărțirea în doi este foarte ieftină operație în binar (care, amintiți-vă, este baza 2, deci este doar schimbarea punctului binar cu un singur loc). Cu toate acestea, cealaltă diviziune este o operațiune foarte costisitoare și, în acest caz, trebuie să efectuați operația de mai multe ori.
Diviziunea este atât de costisitoare, de fapt, încât procesoarele moderne folosesc un algoritm iterativ similar la (dar nu de fapt) iterația Newton-Raphson pentru a efectua divizarea! În mod clar, nu dorim să facem acest lucru în hardware, într-o buclă interioară.
Pe hardware-ul computerului modern, este mult mai ieftin de realizat o operație de multiplicare decât o operație de divizare. Motivul pentru care este un pic complex de explicat; are de-a face cu faptul că putem încadra mult mai multe tranzistori pe un cip decât am reușit până acum, iar multiplicarea este o problemă pe care o puteți trece eficient pe o mulțime de tranzistori. Căutați copaci Wallace dacă sunteți interesat de detalii.
În orice caz, ideea este că multiplicarea este o operațiune relativ ieftină. Deci, dacă putem implementa operațiunea rădăcină pătrată în termeni de multiplicare mai degrabă decât de divizare, acest lucru ar fi mai bine.
Newton-Raphson, luați două
Acum vine prima perspectivă cheie: În loc să calculați rădăcina pătrată, calculați reciproc al rădăcinii pătrate. Adică, în loc de \ sqrt {n}, calculați \ frac {1} {\ sqrt {n}}. Se pare că acesta este un număr mult mai ușor de calculat și, dacă aveți nevoie de rădăcina pătrată, înmulțiți acest număr cu n și ați terminat.
Metoda Newton-Raphson pentru rădăcina pătrată reciprocă arată astfel . Dacă x\_0 este o estimare inițială pentru \ frac {1} {\ sqrt {n}}, iterați:
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3 – n {x\_i} ^ 2 \ right)
Din nou, împărțirea la doi este destul de ieftină și orice altceva este multiplicare și adunare / scădere.
Acesta este un mod excelent de a implementa în software. Mai mult, merită subliniat faptul că în multe situații practice (de exemplu, normalizarea unui vector folosind teorema lui Pitagora), rădăcina pătrată reciprocă este de fapt mai utilă decât rădăcina pătrată, deoarece împărțirea la o rădăcină pătrată este mai puțin eficientă decât înmulțirea cu un pătrat root.
Cu toate acestea, acesta nu este modul în care este implementat de obicei în hardware.
Algoritmul Goldschmidt
Acum putem analiza algoritmul Goldschmidt, care calculează împreună rădăcina pătrată și rădăcina pătrată reciprocă.
Dat fiind b\_0 = n, dacă putem găsi o serie de numere Y\_i astfel încât b\_n = b\_0 { Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2 se apropie de 1, apoi y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} se va apropia de \ frac {1} {\ sqrt {b\_0}} și x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} vor aborda \ sqrt {b\_0}.
Seria pe care o folosim este în esență Pasul de actualizare Newton-Raphson:
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3 – b\_i) \ end {align *}
Și atunci putem urmări rădăcina pătrată:
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
Și rădăcina pătrată reciprocă:
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
Dar dacă ținem evidența x\_i și y\_i, observați că b\_i = x\_ {i-1} y\_ {i-1}. Deci, nu trebuie niciodată să ținem cont de 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 *}
Și acum, nici nu trebuie să ținem evidența Y\_i:
\ begin {align *} x\_i & = x\_ {i-1} \ left (1 + \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ right) \\ & = 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 *}
Există câteva calcule redundante, pe care le putem elimina, sugerând următoarele algoritm. Dat fiind Y ca o aproximare la \ frac {1} {\ sqrt {n}}, setați:
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
Apoi iterați:
\ 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 *}
Chiar dacă împărțirea în doi este ieftină, putem evita și asta prin urmărirea h\_i = \ frac {1} {2} y\_i în loc de y\_i. Acesta este algoritmul Goldschmidt.
Să presupunem că Y este o aproximare la \ frac {1} {\ sqrt {n}}. Setare:
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
Apoi iterați:
\ 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 *}
Apoi x\_i converge în \ sqrt {n} și h\_n converge în \ frac {1} {2 \ sqrt {n}}.
Implementarea acestui lucru în hardware
Până acum, bine. Este cu siguranță un algoritm foarte simplu. Dar de ce este mai bine?
CPU-urile moderne au adesea un circuit rapid care efectuează o operație optimizată de operație de multiplicare-acumulare , adesea numită fused multiply- add, sau FMA pe scurt. Dacă ați căutat mai devreme referința la copacii Wallace, ar trebui să vă fie clar cum FMA ar putea fi aproape la fel de eficient ca o operație de multiplicare dreaptă.
FMA este una dintre cele mai utile primitive pe care le aveți în jur. Dacă trebuie să evaluați un polinom, de exemplu:
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
puteți utiliza Horner regulă, care este în esență o grămadă de 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 *}
Bucla interioară a algoritmului Goldschmidt este de trei FMA și nimic altceva.De aceea este un avantaj: aveți nevoie doar de un singur tip de circuit (posibil doar un singur circuit; rețineți că al doilea două FMA sunt independente și deci pot beneficia de conducte) plus o logică de control pentru a implementa totul. Și este un circuit util în multe alte operații, deci nu pierdeți foarte mult hardware doar în operația rădăcină pătrată.
A doua-ultima piesă a puzzle-ului este cum să obțineți o inițială bună estimare, iar răspunsul scurt este că cea mai bună metodă este utilizarea unei căutări de tabel. Chiar și un tabel de dimensiuni modeste, deoarece căutăm doar rădăcini pătrate într-o gamă atât de mică, este destul de eficient.
Ultima piesă a puzzle-ului este: De unde știm când am terminat iterație? Și răspunsul la asta este că știm precizia numerelor pe care le folosim și cât de bună este estimarea inițială. Din aceasta, putem stabili numărul maxim de iterații necesare în prealabil. Deci, nu facem buclă ca atare, ci facem doar iterația de un număr fix de ori.