Multi-presisjon aritmetikk

Den aritmetiske multipresisjon refererer til alle teknikker implementert for å håndtere et dataprogramnummer (heltall, rasjonelt eller flytende hovedsakelig) av vilkårlig størrelse. Det er en gren av dataritmetikk .

Multi-presisjonsaritmetikk er i motsetning til enkel eller dobbel presisjonsaritmetikk, slik som det som er spesifisert av IEEE 754- standarden for flytende punktum. Enkel eller dobbel presisjonsaritmetikk handler bare om 32 eller 64 bit tall, for hvilke de grunnleggende operasjonene blir levert av prosessoren, mens aritmetikk med flere presisjoner handler om operasjoner på mengder av hvilken som helst størrelse (antall sifre), for hvilken den eneste grensen det tilgjengelige minnet .

Kompleksitet av standardfunksjoner

Mange algoritmer er utviklet for effektivt å utføre de vanlige operasjonene på tall som inneholder et veldig stort antall sifre; vi gir noen av dem, så vel som deres kompleksitet, som uttrykkes som en funksjon av n , antall sifre i de håndterte mengdene.

Addisjon og subtraksjon

Tillegg av to n- sifrede tall kan gjøres i O (n) -operasjoner med en naiv metode. Denne kostnaden er asymptotisk ubetydelig sammenlignet med andre kostnader, og blir derfor ofte oversett.

Multiplikasjon

I hjertet av dette feltet er algoritmer for rask multiplikasjon av store heltall. Faktisk bruker mange mer komplekse operasjoner, som begynner med inndelingen, multiplikasjonen av heltall som en byggestein, og effektiviteten til algoritmene som brukes, avhenger i hovedsak av den underliggende multiplikasjonen. Vi noterer kostnaden for å multiplisere to tall med n sifre. $M (n)$

Flere metoder forbedrer kompleksiteten til denne operasjonen sammenlignet med den grunnleggende metoden ("put a multiplication"). De mest avanserte er Schönhage-Strassen-algoritmen , som gir , og Fürer-algoritmen , som gir . $M (n) = O (n \ log n \ log \ log n)$ $M (n) = O (n \ log n 2 ^ {\ log ^ * n})$

Merk at disse kompleksitetene forstås asymptotisk; i praksis er de enkleste metodene (og med høyere asymptotisk kompleksitet) de raskeste på små eksempler. For eksempel er den grunnleggende metoden raskest for tall på noen få 32-biters ord , Karatsuba-algoritmen er den raskeste for tall på noen titalls ord, og Toom-Cook-algoritmen (3- Toom-Cook) er raskest for antall noen få hundre ord; for større tall (flere titusenvis av ord) er det imidlertid nødvendig å bruke Schönhage-Strassen-algoritmen.

Kvadrat

Å beregne a² er vanligvis raskere enn å beregne ab , hovedsakelig fordi noen mengder som brukes i multiplikasjonsalgoritmene er forenklet i dette spesifikke tilfellet. Merk at akselerasjonsfaktoren maksimalt er 2 (dvs. at en firkant koster halvparten så mye som et produkt), fordi vi kan beregne et produkt fra to firkanter ved hjelp av formelen . En god tilnærming er at kostnaden for en firkant er omtrent lik 0,67 ganger kostnaden for en multiplikasjon. $ab = \ frac {(a + b) ^ 2- (ab) ^ 2} {4}$

Newtons metode

Husk Newtons metode for å beregne et tall slik at : det består i å generere sekvensen ved gjentakelse $z$ $f (z) = 0$ $(z_k) _ {k \ in \ mathbb {N}}$

z_ {k + 1} = z_k - \ frac {f (z_k)} {f '(z_k)}.

Forutsatt at den første itererte er tilstrekkelig nær en null av hvor den deriverte ikke forsvinne, den sekvens kvadratisk konvergerer til denne null, hvilket innebærer at det antall signifikante sifre av hvilke faller sammen med de av (antatt ikke å være null) blir fordoblet ved hver iterasjon asymptotisk , eller at beregning av sifre av krever trinn. $z_0$ $z$ $f$ $f '(z)$ $z_ {k}$ $z$ $ikke$ $z$ $\ log n$

Hvis vi med F (n) betegner kostnadene for evalueringen til n sifre i nærheten av funksjonen , ser det ut til å gi en kompleksitetsalgoritme for å beregne z til n sifre. Men det er mulig å gjøre det bedre: siden vi vet at z k bare har 2 k eksakte sifre, er det overflødig å beregne z k + 1 opp til n sifre. Deretter beregner vi z 0 til nærmeste 1 siffer, deretter utfører vi beregningen av z 1 til 2 sifre osv., Og z k til nærmeste 2 k sifre. Vi får alltid et korrekt resultat på slutten, takket være selvkorrigeringsegenskapen til Newtons metode. Den totale kostnaden er da $f / f '$ $O (F (n) \ log n)$

{\ displaystyle F (1) + F (2) + F (4) + ... + F (2 ^ {k})}

med for å få n eksakte sifre.

2 ^ k> n

Hvis , er denne summen forenklet og er i virkeligheten i . $F (n) \ geq M (n)$ $O (F (n))$

Moralen er derfor at bruk av Newtons metode ved å doble presisjonen man arbeider ved gjør hvert trinn at algoritmen koster like mye (asymptotisk) som det siste trinnet. En anvendelse av dette resultatet er at kvadratrot og en inversjonskostnad , det vil si at disse operasjonene har samme asymptotiske kostnad som multiplikasjonen; dette resultatet oppnås ved å anvende Newtons metode på funksjonene f (x) = x 2 - z og f (x) = xz - 1 . $O (M (n))$

AGM-baserte metoder

Det aritmetisk-geometriske gjennomsnittet av to tall, bemerket , er definert av en sekvens som konvergerer kvadratisk; det vil si at vi kan beregne n eksakte sifre av i operasjoner. Imidlertid er ikke generalforsamlingen selvkorrigerende (i motsetning til Newtons metode), metoden i forrige avsnitt kan ikke brukes til å redusere denne kompleksiteten. $\ tekst {AGM} (a, b)$ $\ tekst {AGM} (a, b)$ $O (M (n) \ log n)$

To applikasjoner av AGM beregner desimalene til π og beregner logaritmefunksjonen . For det første gjør Brent-Salamin-algoritmen det mulig å beregne n desimaler av via en beregning av AGM, det vil si i operasjoner. Den andre funksjonen er knyttet til generalforsamlingen med formelen: $\ pi$ $O (M (n) \ log n)$

{\ displaystyle \ ln (z) = {\ frac {\ pi} {2 {\ text {AGM}} \ left (1, {\ frac {4} {z}} \ right)}} \ left (1+ \ left ({\ frac {1} {x ^ {2}}} \ høyre) \ høyre)}

som gir en tilnærming som gjør det mulig å beregne i operasjoner. $\ logg z$ $O (M (n) \ log n)$

Vi kan da bruke Newtons metode for å beregne den eksponensielle funksjonen i operasjoner, som også gir algoritmer for trigonometriske funksjoner. $\ exp (z)$ $O (M (n) \ log n)$

Binær splittelse

AGM-baserte algoritmer, selv om de er asymptotisk raske, kan være relativt ineffektive; faktisk er konstanten i O relativt stor. For verdier på n av liten eller til og med middels størrelse er det foretrukket å bruke den binære delingsmetoden . Denne metoden lar deg beregne bestemte serier (inkludert de som definerer eksponensielle og trigonometriske funksjoner) ved å dele summen i to og kalle metoden rekursivt på hver halvdel. Kompleksiteten er i beste fall , men konstanten i O er lavere enn for AGM-baserte metoder. $O (M (n) \ log ^ 2 n)$

Multi-presisjon beregningsbiblioteker

Teknisk sett ulike biblioteker gi effektive datastrukturer og operasjoner for multiprecision databehandling. Den vanligste er trolig GNU MP og GNU MPFR , både skriftlig i C . Java- språket har to klasser for å representere vilkårlig store tall: BigInteger for heltall og BigDecimal for desimaltall .

Merknader og referanser

For eksempel, i C-språk og i tilfelle av en 64-biters arkitektur, er det største heltallet det lange lange intet som er lagret på 8 byte (maksimal verdi på 264 , omtrent 1,8 × 10 19 ).
Richard P. Brent , Paul Zimmerman, Modern Computer Arithmetic , Cambridge University Press, 2010; figur 1.1, side 12.
Richard Brent, Paul Zimmerman, ibid. ; figur 1.2, side 13.
Richard Brent, Paul Zimmerman, ibid. , Kapittel 4.2
Richard Brent, Paul Zimmerman, ibid. , Kapittel 4.8
Richard Brent, Paul Zimmerman, ibid. , Kapittel 4.9

(no) Donald Knuth , The Art of Computer Programming , vol. 2: Seminumerical Algorithms , Reading (Mass.), Addison-Wesley, 762 s. ( ISBN 978-0-201-89684-8 , varsel BNF n o FRBNF37532795 ), Avsnitt 4.3.1: De klassiske algoritmene
Richard Brent, Paul Zimmerman, Modern Computer Arithmetic , Cambridge University Press, 2010. (Kapittel 1 og 4.)

Se også

dc ( desk calculator ), en Unix- kommando som tillater beregninger med vilkårlig presisjon i omvendt polsk notasjon
bc , samme sjanger, i gjeldende notasjon