[Paul Curtis] sopra a Segger ha una interessante serie di post sul calcolo divisione. Questo usato per essere un argomento più caldo, ma al giorno d’oggi molti computer o linguaggi di programmazione hanno il supporto per la moltiplicazione e la divisione built-in. ma alcuni processori mancano le istruzioni e una biblioteca per farlo potrebbe essere tutt’altro che ideali. saper rotolare il proprio potrebbe consentire di ottimizzare per la velocità o lo spazio. Gli attuali coperture rata utilizzando l’algoritmo di Newton di fare la divisione.
Steve Martin ha avuto un famoso po ‘su come essere un milionario e mai pagare le tasse. Ha iniziato dicendo: “Prima … ottenere un milione di dollari. Poi …”Questo metodo è un po ‘così da quando bisogna prima saper moltiplicare prima di poter dividere. La premessa fondamentale è duplice: il metodo di Newton consentono di perfezionare una stima di una reciproca da moltiplicazioni successive e moltiplicando un numero reciproco è la stessa che divide. In altre parole, se abbiamo bisogno di dividere 34 per 6, si potrebbe riscrivere 34/6 a 34 * 1/6 e la risposta è la stessa.
approssimazione di Newton per reciproci permette di prendere un’indovinare la risposta e poi perfezionare attraverso una serie di moltiplicazioni. Ogni moltiplicazione crea una migliore precisione. È possibile utilizzare questo per eseguire una velocità classica / spazio trade-off. Per esempio, diciamo solo assumere vogliamo trovare il reciproco di un byte (presumibilmente un punto di byte fisso). Una tabella di look-up di 256 elementi fornirebbe una precisione perfetta e sarebbe molto veloce. Non più la matematica è necessario. ma per quanto riguarda 32 bit? ora il tavolo è semplicemente troppo grande. ma si potrebbe guardare in alto, ad esempio, i primi 8 bit del numero a 32 bit. O più. O meno. dipende da ciò che è importante per voi.
Così ora avete una povera stima del vostro reciproco. Sir Issac può renderlo migliore. Per alcuni il numero uno, Prendete la vostra stima (x) e si moltiplicano insieme. Sottrarre tale numero da 2 e si dispone di un fattore di moltiplicare il vostro vecchio stima di ottenere una nuova stima. Saltare avanti, è chiaro se la vostra stima aveva ragione, la moltiplicazione darebbe 1, che non avrebbe cambiato il vecchio stima a tutti. Se la stima è spento, si otterrà un fattore di scala.
Come una formula che appare così:
x = x * (2-a x *);
Quindi, se si decide il reciproco del 22 potrebbe essere .02, il primo passaggio vi darà:
0.02 * (2-22 * 0.02) = 0,0312
0,0312 * (2-22 * 0,0312) = 0,0410
* 0,0410 (2-22 * 0,0410) = 0,0450
La risposta giusta è un numero decimale periodico 0,0454,545 mila e se andare avanti, ci si arriva.
Naturalmente, poi si deve moltiplicare ancora una volta a fare la divisione.
Abbiamo apprezzato che il post dispone di un’implementazione in virgola fissa e quindi esamina il codice assembly risultante per ARM, RISC-V, e dsPIC30. Vale la pena di leggere.
Amiamo trucchi matematici che possiamo usare in linguaggio assembly. Se si sta lavorando su AVR e in virgola mobile, non perdetevi questo metodo.
No Responses