Migliore risposta
Primo metodo
= UNICHAR (8730) fornisce il simbolo della radice quadrata in Microsoft Excel.
Testato in Excel 2016
Secondo metodo
- Vai a Inserisci scheda e fai clic sul Simbolo dal gruppo Simboli.
- In Simboli seleziona Operatori matematici da Sottoinsieme e utilizza il simbolo radice quadrata.
Risposta
La maggior parte delle CPU moderne fornisce nativamente unoperazione di radice quadrata. Quindi, con un tipico linguaggio di programmazione su un tipico hardware moderno, questo è quasi certamente ciò che sarà alla fine loperazione.
Quindi parliamo del metodo utilizzato da quasi tutte le moderne CPU generiche.
Rappresentazione numerica
La prima cosa che dobbiamo capire è come un computer rappresenta effettivamente il tipo di numeri di cui stiamo parlando. Sono memorizzati in una sorta di notazione scientifica.
Ora il tipo di notazione scientifica con cui potresti avere familiarità dove un numero come -134,5 è rappresentato come -1,345 \ volte 10 ^ {2}.
Qualsiasi numero diverso da zero può essere rappresentato in questa forma, che concettualmente ha tre parti: il segno (cioè, è il numero positivo o negativo), la mantissa (un numero compreso tra 1 e 10, incluso 1 ma non 10, in questo caso 1,345) e il esponente (la potenza alla quale viene elevata la radice, in questo caso 2; nota che lesponente può essere negativo o zero in generale).
La rappresentazione che quasi tutti i computer moderni utilizzano è molto simile, tranne per il fatto che il numero viene memorizzato utilizzando una rappresentazione binaria anziché una decimale. Quindi ignorando il segno bit e zero (poiché trovare la radice quadrata di zero è banale e la radice quadrata di un numero negativo non è un numero reale), i numeri positivi vengono effettivamente memorizzati nella forma m \ times 2 ^ {e} dove m è un numero compreso tra 1 e 2 (incluso 1 ma non incluso 2).
Questa rappresentazione è denominata “virgola mobile”, a causa del modo in cui è possibile spostare il punto binario (analogo al punto decimale con cui potresti avere familiarità) regolando lesponente.
Il motivo per cui tutto questo è importante è perché la CPU usa la rappresentazione per aiutare a calcolare le radici quadrate. Supponiamo che lesponente sia pari. Quindi:
\ sqrt {m \ times 2 ^ {2 \ epsilon}} = \ sqrt {m} \ times 2 ^ {\ epsilon}
Allo stesso modo, se lesponente è dispari, quindi:
\ sqrt {m \ times 2 ^ {2 \ epsilon + 1}} = \ sqrt {2} \ sqrt {m} \ times 2 ^ {\ epsilon}
Ricorda che m è compreso nellintervallo [1,2). Ciò significa che abbiamo ridotto il problema al calcolo della radice quadrata di qualsiasi numero a quello del calcolo della radice quadrata di un numero in quellintervallo. Oppure, se non vogliamo precalcolare \ sqrt {2}, un numero nellintervallo [1,4). In ogni caso, abbiamo notevolmente semplificato il problema, perché ora possiamo usare metodi che si comportano bene in quellintervallo di numeri.
Moltiplicazione e divisione
Quindi, ora che siamo arrivati a questo punto, potresti pensare (se hai guardato le altre risposte) che la soluzione ora sia usare un metodo come literazione di Newton-Raphson per calcolare il quadrato radice. Per calcolare la radice quadrata di n, scegli unipotesi iniziale x\_0 e ripeti:
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ right)
Questa risposta è sbagliata . Bene, non è sbagliato in quanto ti darà una risposta corretta. Ma è sbagliato in quanto nessun progettista di CPU che si rispetti (o qualsiasi autore di librerie se dovesse implementarlo nel software) implementerebbe la radice quadrata in virgola mobile in questo modo.
La divisione per due è molto economica operazione in binario (che, ricordate, è in base 2, quindi sta solo spostando il punto binario di una posizione). Tuttavia, laltra divisione è unoperazione molto costosa e, in questo caso, è necessario eseguire loperazione più volte.
La divisione è così costosa, infatti, che le CPU moderne utilizzano un algoritmo iterativo simile a (ma non effettivamente) literazione di Newton-Raphson per eseguire la divisione! Chiaramente non vogliamo farlo nellhardware, in un ciclo interno.
Sullhardware dei computer moderni, è molto più economico da eseguire unoperazione di moltiplicazione di unoperazione di divisione. Il motivo è un po complesso da spiegare; ha a che fare con il fatto che possiamo inserire molti più transistor su un chip di quanto non fossimo in grado di fare prima, e la moltiplicazione è un problema che puoi spostare su molti transistor in modo efficiente. Cerca gli alberi di Wallace se sei interessato ai dettagli.
In ogni caso, il punto è che la moltiplicazione è unoperazione relativamente economica. Quindi, se possiamo implementare loperazione della radice quadrata in termini di moltiplicazione anziché divisione, sarebbe meglio.
Newton-Raphson, prendi due
Ora arriva la prima intuizione chiave: invece di calcolare la radice quadrata, calcola il reciproco della radice quadrata. Cioè, invece di \ sqrt {n}, calcola \ frac {1} {\ sqrt {n}}. Si scopre che questo è un numero molto più facile da calcolare e, se hai bisogno della radice quadrata, moltiplica questo numero per ne hai finito.
Il metodo di Newton-Raphson per la radice quadrata reciproca ha questo aspetto . Se x\_0 è una stima iniziale di \ frac {1} {\ sqrt {n}}, itera:
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3 – n {x\_i} ^ 2 \ right)
Di nuovo, la divisione per due è abbastanza economica e tutto il resto è moltiplicazione e addizione / sottrazione.
Questo è un ottimo modo per implementare nel software. Inoltre, vale la pena sottolineare che in molte situazioni pratiche (ad esempio normalizzando un vettore usando il teorema di Pitagora), la radice quadrata reciproca è effettivamente più utile della radice quadrata, poiché la divisione per una radice quadrata è meno efficiente che moltiplicare per un quadrato reciproco root.
Tuttavia, questo non è il modo in cui viene solitamente implementato nellhardware.
Algoritmo di Goldschmidt
Ora possiamo guardare lalgoritmo di Goldschmidt, che calcola la radice quadrata e la radice quadrata reciproca insieme.
Dato b\_0 = n, se possiamo trovare una serie di numeri Y\_i tale che b\_n = b\_0 { Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2 si avvicina a 1, quindi y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} si avvicina a \ frac {1} {\ sqrt {b\_0}} e x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} si avvicineranno a \ sqrt {b\_0}.
La serie che usiamo è essenzialmente la Passaggio di aggiornamento di Newton-Raphson:
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3 – b\_i) \ end {align *}
E quindi possiamo tenere traccia della radice quadrata:
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
E la radice quadrata reciproca:
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
Ma se teniamo traccia di x\_i e y\_i, osserviamo che b\_i = x\_ {i-1} y\_ {i-1}. Quindi non dobbiamo mai tenere traccia di 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 *}
E ora, né abbiamo bisogno di tenere traccia di Y\_i:
\ begin {align *} x\_i & = x\_ {i-1} \ sinistra (1 + \ frac {1} {2} \ sinistra (1 – x\_ {i-1} y\_ {i-1} \ destra) \ destra) \\ & = 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 *}
Ci sono alcuni calcoli ridondanti qui, che possiamo rimuovere, suggerendo quanto segue algoritmo. Dato Y come approssimazione di \ frac {1} {\ sqrt {n}}, imposta:
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
Quindi iterare:
\ 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 *}
Anche se la divisione per due è economica, possiamo evitarlo anche tenendo traccia di h\_i = \ frac {1} {2} y\_i invece di y\_i. Questo è lalgoritmo di Goldschmidt.
Supponi che Y sia unapprossimazione di \ frac {1} {\ sqrt {n}}. Imposta:
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
Quindi iterare:
\ 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 *}
Quindi x\_i converge a \ sqrt {n} e h\_n converge a \ frac {1} {2 \ sqrt {n}}.
Implementazione nellhardware
Fin qui tutto bene. È certamente un algoritmo molto semplice. Ma perché è meglio?
Le moderne CPU hanno spesso un circuito veloce che esegue unoperazione ottimizzata multiply-accumulate , spesso chiamata fused multiply- aggiungi, o FMA in breve. Se hai cercato prima il riferimento agli alberi di Wallace, dovrebbe esserti chiaro come FMA potrebbe essere efficiente quasi quanto unoperazione di moltiplicazione diretta.
FMA è una delle primitive più utili da avere in giro. Se devi valutare un polinomio, ad esempio:
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
puoi usare Horner regola, che è essenzialmente un gruppo di 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 *}
Il ciclo interno dellalgoritmo di Goldschmidt è costituito da tre FMA e nientaltro.Ecco perché è un vantaggio: hai solo bisogno di un tipo di circuito (possibilmente un solo circuito; nota che i secondi due FMA sono indipendenti e quindi possono beneficiare del pipelining) più una logica di controllo per implementare tutto. Ed è un circuito che è utile in molte altre operazioni, quindi non stai sprecando molto hardware solo per loperazione di radice quadrata.
Il penultimo pezzo del puzzle è come ottenere una buona iniziale stima, e la risposta breve è che il metodo migliore è utilizzare una ricerca nella tabella. Anche un tavolo di dimensioni modeste, perché cerchiamo solo radici quadrate in un intervallo così piccolo, è abbastanza efficiente.
Lultimo pezzo del puzzle è: come facciamo a sapere quando abbiamo finito iterando? E la risposta è che conosciamo la precisione dei numeri che stiamo utilizzando e quanto è buona la stima iniziale. Da ciò, possiamo calcolare in anticipo il numero massimo di iterazioni richieste. Quindi non eseguiamo effettivamente il ciclo in quanto tali, facciamo solo literazione un numero fisso di volte.