APPLE faller divisjon

[Paul Curtis] over på Segger har en interessant serie med blogginnlegg om beregning divisjon. Dette pleide å være et varmere tema, men i dag mange datamaskiner eller språk har støtte for multiplikasjon og divisjon innebygd. men noen prosessorer mangler instruksjoner og et bibliotek for å gjøre det kan være mindre enn ideell. vite hvordan du skal rulle din egen kan tillate deg å optimalisere for hastighet eller plass. De nåværende avdrags deksler bruker Newtons algoritme for å gjøre divisjon.

Steve Martin hadde en berømt litt om hvordan bli millionær og aldri betale skatt. Han begynte med å si, “First … få en million dollar. Så …”Denne metoden er litt sånn siden du først må vite hvordan de skal formere før du kan dele. Den grunnleggende forutsetningen er todelt: Newtons metode kan du avgrense et estimat av en gjensidig ved påfølgende multiplikasjon og deretter multiplisere et tall en gjensidig er det samme som å dele. Med andre ord, hvis vi trenger å dele 34 med 6, kan du skrive 34/6 til 34 * 1/6 og svaret er det samme.

Newtons tilnærming for resiproke kan du ta en gjetning på svaret og deretter avgrense det gjennom en serie multiplikasjoner. Hver multiplikasjon skaper bedre nøyaktighet. Du kan bruke denne til å utføre en klassisk hastighet / plass trade-off. For eksempel er utleid bare anta vi ønsker å finne den motsvarende for en byte (formodentlig et fast punkt byte). En look-up table 256 elementer ville gi perfekt nøyaktighet og ville være veldig fort. Ingen flere matematikk er nødvendig. men hva med 32 bits? Nå bordet er litt for stor. men du kan slå opp, sier, de første 8 bitene av 32-bit nummer. Eller mer. Eller mindre. avhenger av hva som er viktig for deg.

Så nå har du en dårlig estimat av gjensidige. Sir Issac kan gjøre det bedre. For noen nummer en, kan du ta din estimat (x) og multiplisere dem sammen. Trekk som nummer fra 2 og du har en faktor å multiplisere din gamle estimat ved å få et nytt estimat. Hoppe fremover, er det klart hvis estimatet var rett, ville multiplikasjon gi deg en som ikke ville endre den gamle anslaget i det hele tatt. Hvis anslaget er slått av, vil du få en skaleringsfaktor.

Som en formel ser det ut som dette:

x = x * (2-a * x);
Så hvis du bestemmer deg for den gjensidige av 22 kan være 0,02, vil det første passet gir deg:

0,02 * (2-22 * 0,02) = 0,0312

0,0312 * (2-22 * 0,0312) = 0,0410

0,0410 * (2-22 * 0,0410) = 0,0450
Det riktige svaret er en periodisk desimaltall 0.0454545 og hvis du fortsetter, vil du komme dit.

Selvfølgelig, så må du multiplisere en mer tid til å gjøre divisjonen.

Vi likte at innlegget har en fastpunktsimplementering, og deretter undersøker den resulterende sammenstilling koden for ARM, RISC-V, og dsPIC30. Vel verdt en lese.

Vi elsker matematikk triks vi kan bruke i assembly. Hvis du arbeider på AVR og flyttall, ikke gå glipp av denne metoden.