Uke 1 – regnetid, binære tall og tall på datamaskiner

Ukens spørsmål: Hvordan kan vi regne raskere – og hvorfor blir ikke \(0.1+0.2\) nøyaktig \(0.3\) på en datamaskin?

Begge halvdelene handler egentlig om det samme. En datamaskin «gjør» ikke matematikk; den utfører en algoritme med tall som er lagret på en bestemt måte. To algoritmer for samme matematiske oppgave kan koste svært forskjellig – det ser vi i 1.1 med Horners metode. De kan også gi forskjellig nøyaktighet – det ser vi i 1.3 med flyttall. For å forstå flyttall må vi først kunne skrive tall binært (1.2). Og for å snakke om nøyaktighet trenger vi et mål på hvor stor en feil er. Det begynner vi med.

Numerisk matematikk handler om å regne ut løsninger til matematiske problemer på en datamaskin. Løsningene er ofte tilnærmede.

I realistiske modeller finnes det ofte ingen enkel eksakt løsning. Selv når en eksakt formel finnes, kan den være for komplisert til å være praktisk nyttig.

En god numerisk metode må balansere

nøyaktighet – hvor nær er svaret den ønskede verdien?
stabilitet – hvordan påvirkes svaret av små feil?
regnetid – hvor mye arbeid krever beregningen?

For å måle hvor god en tilnærming er, bruker vi to feilmål. La \(x\) være den eksakte verdien og \(\hat{x}\) en tilnærming.

Den absolutte feilen er

\[ E_{\mathrm{abs}}=|x-\hat{x}|. \]

Den relative feilen er, når \(x\neq0\),

\[ E_{\mathrm{rel}}=\frac{|x-\hat{x}|}{|x|}. \]

Relativ feil kan også oppgis i prosent:

\[ 100E_{\mathrm{rel}}\%. \]

Et lite eksempel for hånd: For \(x=\frac13\) og \(\hat x=0.333\) er

\[ |x-\hat x|=\frac13-\frac{333}{1000}=\frac{1000-999}{3000}=\frac1{3000}\approx0.000333, \]

og den relative feilen er

\[ E_{\mathrm{rel}}=\frac{1/3000}{1/3}=\frac{3}{3000}=\frac1{1000}=0.1\,\%. \]

Cellen under regner ut det samme. Legg merke til at Python skriver den relative feilen som 0.0009999999999998899 og ikke nøyaktig 0.001: verken \(\frac13\) eller \(0.333\) kan lagres eksakt i datamaskinen. Hvorfor det er slik, ser vi i 1.3. Endre gjerne tallene og se hvordan de to feilmålene reagerer.

Tolkning

Absolutt feil måler avstanden mellom to tall.

Relativ feil måler feilen i forhold til størrelsen på tallet vi prøver å beregne.

Samme absolutte feil kan være liten i én situasjon og stor i en annen. Cellen bruker den samme absolutte feilen \(0.001\) for tre tall av svært ulik størrelse og regner ut den relative feilen for hvert av dem:

For \(x=0.01\) er en feil på \(0.001\) hele \(10\%\). For \(x=100\) er den samme absolutte feilen bare \(0.001\%\).

Hvilken feil skal vi bruke?

Bruk absolutt feil når størrelsen på avviket i seg selv er det viktige.
Bruk relativ feil når du vil sammenligne nøyaktighet for tall med ulik størrelse.
Når den eksakte verdien er \(0\), kan relativ feil ikke defineres på denne måten.

Et polynom av grad \(n\) har formen

\[ p(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n, \qquad a_n\neq0. \]

Å evaluere et polynom betyr å beregne \(p(x)\) for en bestemt verdi av \(x\).

Matematisk kan flere fremgangsmåter gi samme svar, men beregningsmessig kan de kreve svært ulikt arbeid. Når evalueringen gjentas mange ganger, blir antall multiplikasjoner og addisjoner viktig.

La oss se på hvordan vi kan evaluere et polynom på en effektiv måte. Vi bruker polynomet

\[ p(x)=3x^4-2x^3+3x^2+5x-2 \]

og ønsker å regne ut \(p\left(\frac{3}{2}\right)\).

Den «åpenbare» metoden

Setter vi inn \(x=\frac{3}{2}\) direkte, får vi

\[ p\left(\frac{3}{2}\right) = 3\left(\frac{3}{2}\right)^4 -2\left(\frac{3}{2}\right)^3 +3\left(\frac{3}{2}\right)^2 +5\left(\frac{3}{2}\right)-2 = \frac{331}{16}. \]

Mellomregningen er

\[ 3\cdot\frac{81}{16}-2\cdot\frac{27}{8}+3\cdot\frac94+5\cdot\frac32-2 =\frac{243-108+108+120-32}{16}=\frac{331}{16}. \]

Hvor mye arbeid var dette? Når hver potens regnes ut på nytt, krever \(3x^4=3\cdot x\cdot x\cdot x\cdot x\) fire multiplikasjoner, \(2x^3\) tre, \(3x^2\) to og \(5x\) én. Det er \(4+3+2+1=10\) multiplikasjoner. I tillegg kommer 4 addisjoner mellom de fem leddene, til sammen 14 regneoperasjoner.

For et polynom av grad \(n\) krever leddet \(a_kx^k\) på samme måte \(k\) multiplikasjoner. Til sammen blir det \(1+2+\cdots+n=\frac{n(n+1)}{2}\) multiplikasjoner, og med \(n\) addisjoner får vi

\[ \frac{n(n+1)}{2}+n=\frac{n^2+3n}{2} \]

regneoperasjoner.

En forbedring er å regne ut potensene av \(x\) først, og gjenbruke dem når neste potens skal beregnes: \(x^3=x^2\cdot x\), \(x^4=x^3\cdot x\). Da koster potensene \(x^2,\dots,x^n\) til sammen bare \(n-1\) multiplikasjoner. Så kommer \(n\) multiplikasjoner med koeffisientene og \(n\) addisjoner:

\[ (n-1)+n+n=3n-1. \]

For \(n=4\) blir det \(3+4+4=11\) regneoperasjoner i stedet for \(14\).

Gå i dybden: potenser først for \(p(3/2)\)

For \(x=\frac{3}{2}\) får vi

\[ \left(\frac{3}{2}\right)^2=\frac94,\qquad \left(\frac{3}{2}\right)^3=\frac{27}{8},\qquad \left(\frac{3}{2}\right)^4=\frac{81}{16}. \]

Deretter setter vi disse verdiene inn i polynomet:

\[ p\left(\frac32\right) = 3\frac{81}{16} -2\frac{27}{8} +3\frac94 +5\frac32 -2 =\frac{331}{16}, \]

med samme mellomregning som for den direkte metoden. Potensene kostet 3 multiplikasjoner, og å gange med koeffisientene kostet 4 til. Metoden krever altså 7 multiplikasjoner og 4 addisjoner, til sammen 11 regneoperasjoner.

Den mest effektive av metodene vi ser på, er Horners metode, også kalt nestet multiplikasjon.

Vi skriver først leddene i stigende rekkefølge etter potens:

\[ p(x)=-2+5x+3x^2-2x^3+3x^4. \]

Ved å trekke ut en faktor \(x\) gjentatte ganger kan polynomet skrives på nestet form:

\[ \begin{aligned} p(x) &=-2+x(5+3x-2x^2+3x^3)\\ &=-2+x(5+x(3-2x+3x^2))\\ &=-2+x(5+x(3+x(-2+3x))). \end{aligned} \]

Dermed kan vi evaluere \(p\left(\frac32\right)\) som

\[ p\left(\frac32\right) = -2+\frac32\left( 5+\frac32\left( 3+\frac32\left( -2+3\frac32 \right)\right)\right). \]

Vi regner innenfra og ut:

\[ \begin{aligned} -2+3\cdot\tfrac32&=-2+\tfrac92=\tfrac52,\\ 3+\tfrac32\cdot\tfrac52&=3+\tfrac{15}{4}=\tfrac{27}{4},\\ 5+\tfrac32\cdot\tfrac{27}{4}&=5+\tfrac{81}{8}=\tfrac{121}{8},\\ -2+\tfrac32\cdot\tfrac{121}{8}&=-2+\tfrac{363}{16}=\tfrac{331}{16}. \end{aligned} \]

Hver linje er én multiplikasjon og én addisjon. Grad \(4\) gir fire linjer, altså \(4\) multiplikasjoner og \(4\) addisjoner, til sammen \(8\) regneoperasjoner. Grad \(n\) gir \(n\) linjer, altså \(2n\) regneoperasjoner.

Oppskriften er: start med \(b=a_n\), og gjenta \(b\leftarrow a_k+x\,b\) for \(k=n-1,\dots,1,0\). Til slutt er \(b=p(x)\).

For et generelt polynom

\[ p(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n \]

får vi den nestede formen

\[ p(x) = a_0+x\left( a_1+x\left( a_2+x\left( a_3+\cdots+x(a_{n-1}+a_nx) \right)\right)\right). \]

Horners metode er et første eksempel på et viktig prinsipp i numerikk: samme matematiske problem kan løses med algoritmer som har svært ulik kostnad.

Tabellen viser hvor stor forskjellen blir når graden vokser. Tallene kommer rett fra de tre formlene vi har utledet:

\(n\)	direkte \(\frac{n^2+3n}{2}\)	potenser først \(3n-1\)	Horner \(2n\)
4	14	11	8
10	65	29	20
100	5 150	299	200
1000	501 500	2 999	2 000

For grad \(1000\) gjør den direkte metoden altså omtrent \(250\) ganger så mye arbeid som Horners metode.

Øv på dette: programmer Horners metode.

To poeng å ta med videre:

Enkle og grunnleggende ting må gjøres effektivt fordi vi ofte gjør dem mange ganger.
Den mest åpenbare metoden er ofte ikke den mest effektive.

Gå i dybden: et polynom med en manglende potens

Skriv

\[ q(x)=2x^3+3x+1 \]

på nestet form.

Vi setter først inn den manglende \(x^2\)-koeffisienten:

\[ q(x)=1+3x+0x^2+2x^3. \]

Da får vi

\[ q(x)=1+x(3+0x+2x^2) =1+x(3+x(0+2x)). \]

Nå skal du gjøre oppskriften fra Horners metode om til en løkke. Funksjonen skal regne ut et generelt polynom

\[ p(x)=a_0+a_1x+\cdots+a_nx^n. \]

Listen a inneholder koeffisientene i rekkefølgen [a0, a1, ..., an].

Datamaskiner lagrer tall på en annen måte enn vi vanligvis skriver dem.

Til daglig bruker vi sifrene \(0,1,\ldots,9\). Dette kalles titallssystemet. En datamaskin bruker i stedet bare to sifre: \(0\) og \(1\). Dette kalles totallssystemet, eller det binære tallsystemet.

Forskjellen er egentlig mindre enn den ser ut til. I titallssystemet ganges hvert siffer med en potens av \(10\), avhengig av plassen det står på. For eksempel

\[ 2507 = 2\cdot1000+5\cdot100+0\cdot10+7\cdot1 = 2\cdot10^3+5\cdot10^2+0\cdot10^1+7\cdot10^0. \]

I det binære tallsystemet gjør vi akkurat det samme, men bruker potenser av \(2\) i stedet for potenser av \(10\).

For eksempel er tallet \(b=(101100)_2\), skrevet i totallssystemet, lik

\[ \begin{aligned} b=(101100)_2 &=1\cdot2^5+0\cdot2^4+1\cdot2^3+1\cdot2^2+0\cdot2^1+0\cdot2^0\\ &=32+8+4\\ &=44. \end{aligned} \]

Det nedsenkede tallet \(2\) forteller hvilken base tallsystemet har, det vil si hvor mange ulike sifre det bruker. Basen er tallet vi tar potenser av. Altså

\[ b=(101100)_2=(44)_{10} \]

Tallene inne i datamaskinen lagres i tallsystemet med base \(2\), eller kortere sagt binært.

Eksemplet med \((101100)_2=44\) viser hele oppskriften: hvert siffer ganges med sin potens av \(2\), og så legger vi sammen.

Vi kan også uttrykke andre tall enn heltall. Generelt kan et binært tall skrives som

\[ \ldots b_3b_2b_1b_0.b_{-1}b_{-2}\ldots, \]

der hvert \(b_i\) er enten \(0\) eller \(1\). I titallssystemet tilsvarer dette

\[ \ldots +b_2 2^2+b_1 2^1+b_0 2^0 +b_{-1}2^{-1}+b_{-2}2^{-2} +\cdots. \]

Tallet \(5\) kan skrives som

\[ 5=(101)_2. \]

Brøken \(\frac34\) kan skrives som

\[ \frac34=(0.11)_2. \]

Dette ser vi fordi

\[ (0.11)_2 = 0\cdot2^0+1\cdot2^{-1}+1\cdot2^{-2} = \frac12+\frac14 = \frac34. \]

La oss konvertere \(53.7\) til totallssystemet. Vi skriver først

\[ 53.7=53+0.7 \]

og konverterer heltallsdelen og brøkdelen hver for seg.

Heltallsdelen

For heltallsdelen deler vi gjentatte ganger på \(2\) og tar vare på restene:

\[ \begin{aligned} 53 &= 2\cdot26+1,\\ 26 &= 2\cdot13+0,\\ 13 &= 2\cdot6+1,\\ 6 &= 2\cdot3+0,\\ 3 &= 2\cdot1+1,\\ 1 &= 2\cdot0+1. \end{aligned} \]

Leser vi restene nedenfra og opp, får vi

\[ (53)_{10}=(110101)_2. \]

Fremgangsmåten er altså:

Del på \(2\) til kvotienten blir null.
Ta vare på restene underveis.
Les restene nedenfra og opp.

Det virker fordi resten ved deling på \(2\) alltid er det siste binære sifferet.

Gå i dybden: hvorfor gir restene sifrene?

Skriv \(53=b_5 2^5+\dots+b_1 2+b_0\). Alle leddene unntatt \(b_0\) er delelige med \(2\), så resten ved deling på \(2\) er nettopp det siste sifferet \(b_0\). Kvotienten \(26=b_5 2^4+\dots+b_1\) inneholder de øvrige sifrene, og vi gjentar. Derfor kommer sifrene ut bakfra, og vi leser restene nedenfra og opp.

Brøkdelen

For brøkdelen gjør vi det «motsatte»: Vi ganger gjentatte ganger med \(2\) og tar vare på heltallsdelene. Det virker fordi å gange med \(2\) flytter binærpunktet ett hakk mot høyre.

\[ \begin{aligned} 0.7\cdot2 &= 1.4,\\ 0.4\cdot2 &= 0.8,\\ 0.8\cdot2 &= 1.6,\\ 0.6\cdot2 &= 1.2,\\ 0.2\cdot2 &= 0.4. \end{aligned} \]

Herfra begynner mønsteret \(0.4\to0.8\to0.6\to0.2\to0.4\) å gjenta seg. Derfor fortsetter de tilsvarende binære sifrene periodisk.

Leser vi heltallsdelene ovenfra og ned, får vi

\[ (0.7)_{10} = (0.101100110011\ldots)_2 = (0.1\overline{0110})_2. \]

Gå i dybden: hvorfor gir heltallsdelene sifrene?

Ganger vi \((0.b_{-1}b_{-2}\ldots)_2\) med \(2\), flytter binærpunktet seg ett hakk: \((b_{-1}.b_{-2}\ldots)_2\). Heltallsdelen er derfor neste siffer \(b_{-1}\), og det som står etter binærpunktet, er et nytt tall mellom \(0\) og \(1\) som vi behandler på samme måte.

Til sammen får vi derfor

\[ (53.7)_{10} = (110101.101100110011\ldots)_2 = (110101.1\overline{0110})_2. \]

At \(0.7\) får uendelig mange binære sifre, blir viktig i 1.3: en datamaskin har bare plass til endelig mange.

Øv på dette: regn om mellom tallsystemene.

Fra totallssystemet til titallssystemet

Gang hvert siffer med sin potens av \(2\) og legg sammen, som i eksemplet med \((101100)_2=44\). Først et heltall:

Fra binært tall til titallssystemet

Sifrene etter binærpunktet står for \(2^{-1}=\frac12\), \(2^{-2}=\frac14\), \(2^{-3}=\frac18\) og så videre. Du kan svare med brøk eller desimaltall.

Binær brøk til titallssystemet

Til slutt programmerer du omregningen for heltall. Skriv funksjonen uten å bruke int(). Gå gjennom sifrene fra venstre mot høyre og bygg opp verdien. Tips: For et siffer b gir b == "1" enten True, som regnes som 1, eller False, som regnes som 0.

Fra titallssystemet til totallssystemet

Gang brøkdelen gjentatte ganger med \(2\) og ta vare på heltallsdelene, som for \(0.7\) i teksten. Skriv bare sifrene etter binærpunktet.

Fra titallsbrøk til binær brøk

For heltall bruker vi gjentatt divisjon med \(2\), som for \(53\) i teksten. Skriv en funksjon som gjør dette. Funksjonen skal returnere svaret som en streng. Ikke bruk bin().

I 1.2 så vi at et så enkelt tall som \(0.7\) får uendelig mange binære sifre. En datamaskin har bare plass til endelig mange. Hva gjør den da? Før vi ser på teorien, lar vi Python vise oss hva som skjer.

Cellen regner ut fem små uttrykk som du lett klarer i hodet. Resten av 1.3 forklarer, ett for ett, hvorfor svarene blir som de blir. Målet er å finne linjene der datamaskinen og matematikken er uenige.

Kjør cellen og legg merke til linjene som overrasker deg.
Bytt ut 0.1 med 0.5, 0.2 med 0.25 og 0.3 med 0.75. Blir svarene nå eksakte?
Bytt ut 1.0 med 2.0 i de to siste uttrykkene (både i teksten og i regnestykket). Hva endrer seg?

Hva viser forsøket? \(0.5\) og \(0.25\) har endelig mange binære sifre og regnes eksakt, men \(0.1\) og \(0.2\) kan ikke lagres eksakt. Og et lite tall kan forsvinne helt ved siden av et stort: ettallet i \(10^{16}+1\) forsvinner, mens toeren i \(10^{16}+2\) overlever. Begge deler forklarer vi i fanene «Avrunding», «Maskinepsilon» og «Avstand mellom flyttall».

En datamaskin har bare endelig plass, og kan derfor bare lagre et endelig utvalg av de reelle tallene. For eksempel er

\[ 0.1=(0.00011001100110011\ldots)_2. \]

Mønsteret fortsetter i det uendelige. Dermed kan \(0.1\) ikke lagres eksakt som et vanlig binært flyttall.

Hovedidé

Et maskinrepresentert flyttall er ikke «et vilkårlig reelt tall inne i maskinen». Det er ett av et stort, men endelig antall representerbare tall.

Standarden som brukes på nesten alle moderne datamaskiner heter IEEE 754. Python float bruker formatet IEEE 754 double precision (64 bit), og det er dette formatet vi undersøker i resten av 1.3.

Gå i dybden: float, double og flyttall

Her er noen begreper som lett blandes sammen:

ord	hva betyr det?
flyttall	fellesnavn for tall lagret med fortegn, signifikante sifre og eksponent
single precision	IEEE 754-format med 32 bit; kalles ofte `float` i språk som C
double precision	IEEE 754-format med 64 bit; kalles ofte `double` i språk som C
Python `float`	Pythons vanlige flyttallstype; på vanlige Python-systemer bruker den double precision (64 bit)

I denne teksten bruker vi derfor:

flyttall når vi snakker generelt,
double precision eller IEEE 754 binary64 når vi snakker om selve 64-bitsformatet,
Python float når vi konkret snakker om en verdi eller type i Python.

Viktig

Navnet float betyr altså ikke nødvendigvis 32 bit. I C er float vanligvis single precision, mens Python float normalt bruker double precision.

Før vi kan forstå bitene i IEEE 754, må vi kunne skrive et binært tall på normalisert form:

\[ \pm 1.b_1b_2b_3\ldots\times2^e. \]

Dette er den binære versjonen av vitenskapelig notasjon.

Lite eksempel: \(9\)

Vi har

\[ 9=(1001)_2. \]

Flytt binærpunktet tre plasser mot venstre:

\[ 1001_2=1.001_2\times2^3. \]

Dermed er den normaliserte formen

\[ 9=(1.001)_2\times2^3. \]

Gå i dybden: ett eksempel til, tallet \(23\)

Vi har

\[ 23=(10111)_2. \]

Flytt binærpunktet fire plasser:

\[ 10111_2=1.0111_2\times2^4. \]

Altså

\[ 23=(1.0111)_2\times2^4. \]

Oppskrift

Skriv tallet binært.
Sett binærpunktet etter den første 1-eren.
Tell hvor mange plasser punktet ble flyttet.
Antall plasser blir eksponenten \(e\).

Cellen under følger den samme oppskriften i Python: den skriver tallet binært med bin, setter punktet etter den første biten og teller hvor mange plasser punktet flyttet seg. Kontroller at den gir det samme som vi fant for hånd for \(9\), og bytt gjerne ut listen med egne tall.

Hvorfor starter formen alltid med 1?

I et normalisert binært tall er første siffer alltid 1. IEEE 754 trenger derfor ikke lagre denne biten eksplisitt. Den er implisitt. Denne eneren kalles derfor også skjult bit, og mantissebitene kalles også brøkbiter.

Nå ser vi hvordan datamaskinen lagrer et tall på normalisert form. IEEE 754 double precision (binary64) bruker 64 bit:

del	bit	hva lagres?
fortegn \(S\)	1	positivt eller negativt
eksponent \(E\)	11	størrelsesorden
mantissefelt \(M\)	52	sifrene etter binærpunktet i signifikanden

For et vanlig normalisert tall representerer disse bitene

\[ (-1)^S(1.M)_2\,2^e. \]

Eksponenten lagres med bias 1023:

\[ E=e+1023. \]

Lite eksempel: tallet \(9\)

Fra forrige fane har vi

\[ 9=(1.001)_2\times2^3. \]

Dermed:

Tallet er positivt, så \(S=0\).
Eksponenten er \(e=3\).
Den lagrede eksponenten blir

\[ E=3+1023=1026. \]

\(1026\) skrevet med 11 binære bit er

\[ 1026=1024+2=(10000000010)_2. \]

Mantissen kommer fra sifrene etter den første 1-eren:

\[ 1.\color{#0b6efd}{001}000\ldots \]

Den første 1-eren lagres ikke.

Skjematisk:

\[ \underbrace{0}_{S}\quad \underbrace{10000000010}_{E}\quad \underbrace{001000\ldots000}_{M}. \]

For tallet \(1=(1.000\ldots)_2\times2^0\) er på samme måte \(S=0\), \(e=0\), \(E=1023\), og alle mantissebitene er \(0\).

Nå lar vi Python hente de faktiske 64 bitene fra noen float-verdier. Hjelperen show_bits skriver ut de tre feltene \(S\), \(E\) og \(M\); hvordan den gjør det, kan du se i Gå i dybden under. Følg spesielt 9.0: resultatet skal stemme med regningen over.

Se også på de siste bitene for 0.1: mønsteret 1001 1001 … skulle ha fortsatt, men den siste gruppen er 1010. Der er tallet rundet opp, så lagret 0.1 er litt større enn \(1/10\). Det ser du igjen i neste fane.

52 eller 53 signifikante bit?

Mantissefeltet har 52 lagrede bit. Sammen med den implisitte ledende 1-eren gir dette 53 binære signifikante bit i signifikanden for normaliserte tall.

Gå i dybden: slik henter Python de 64 bitene

Modulen struct kan pakke en float som de 8 bytene datamaskinen faktisk lagrer, og lese de samme bytene som ett 64-bits heltall. Skriver vi heltallet med 64 binære sifre, kan vi dele det i de tre feltene. Cellen gjør dette for tallet \(9\); show_bits gjør det samme for hvert tall.

Øv på dette: les og skriv bitmønstre i mini-maskinen.

Tallet \(0.1\) trenger uendelig mange binære sifre. IEEE 754 må derfor velge et flyttall i nærheten. I forrige fane så vi at det lagrede tallet er rundet opp.

IEEE 754 bruker normalt round to nearest, ties to even:

finn de to nærmeste representerbare flyttallene,
velg det nærmeste,
ved nøyaktig uavgjort velges det som ender på partall (even), altså det der den siste mantissebiten er \(0\).

Vi skriver \(\mathrm{fl}(x)\) for flyttallet som faktisk lagres når vi vil lagre \(x\), for eksempel \(\mathrm{fl}(0.1)\neq0.1\). Samme idé virker i titallssystemet: med fire signifikante sifre er \(\mathrm{fl}(2/3)=0.6667\).

Hvilke flyttall kan IEEE 754 velge mellom for \(0.1\)? Cellen finner de to naboene til den lagrede 0.1 med math.nextafter. Så regner den ut med eksakte brøker (Fraction) hvor den matematiske verdien \(1/10\) ligger mellom dem, målt i «lokale steg» fra ett flyttall til det neste. Hjelperen plot_neighbours tegner resultatet.

Eksakt \(1/10\) ligger \(0.4\) steg til venstre for den lagrede verdien og \(0.6\) steg fra venstre nabo. Den lagrede verdien er altså nærmest, og den er litt større enn \(1/10\). Det er disse diskrete naboflyttallene avrundingen velger mellom.

Gå i dybden: hvilken brøk er egentlig lagret?

Hvert flyttall er en brøk med en toerpotens i nevneren. Python kan vise den eksakte brøken som faktisk er lagret for 0.1, og hvor langt den ligger fra \(1/10\):

Det lagrede tallet ligger svært nær \(1/10\), men er ikke likt \(1/10\). Nevneren er \(2^{55}\).

Øv på dette: rund av i mini-maskinen.

Hvor liten endring kan vi gjøre på tallet \(1\) før datamaskinen ikke lenger klarer å se forskjellen? Målet er å finne det minste steget over \(1\) som datamaskinen kan se.

Python-eksperiment

Cellen legger \(\delta=2^{-k}\) til \(1\) for \(k=45,\dots,57\) og sjekker om resultatet fortsatt er større enn \(1\). Gjett først hvor overgangen kommer, og kjør så cellen.

Du bør se en tydelig overgang:

for \(k\le52\) blir \(1+\delta\) større enn \(1\),
fra \(k=53\) avrundes \(1+\delta\) tilbake til akkurat 1.0.

Dette viser at representerbare double-verdier ikke ligger kontinuerlig på tallinjen. Rundt \(1\) finnes det et minste positivt steg til neste større representerbare verdi.

Definisjon

For IEEE 754 double precision (binary64) er maskinepsilon

\[ \varepsilon_{\mathrm{mach}} = 2^{-52} \approx 2.22\cdot10^{-16}. \]

Det er avstanden fra \(1\) til det minste representerbare double-tallet som er større enn \(1\):

\[ 1+\varepsilon_{\mathrm{mach}}. \]

Maskinepsilon kalles også maskinpresisjon; det ordet møter du i senere uker.

Hvorfor akkurat \(2^{-52}\)? Tallet \(1\) er \((1.00\ldots0)_2\times2^0\), med alle de 52 mantissebitene lik \(0\). Det minste tallet over \(1\) får vi ved å gjøre den siste av de 52 bitene til \(1\):

\[ (1.\underbrace{00\ldots0}_{51}1)_2=1+2^{-52}. \]

Noe tall imellom finnes ikke, for mantissefeltet har ikke flere plasser.

Hva da med \(1+\frac{\varepsilon_{\mathrm{mach}}}{2}\)? Det ligger nøyaktig midt mellom nabotallene \(1\) og \(1+\varepsilon_{\mathrm{mach}}\). Da avgjør regelen ties to even fra fanen «Avrunding»: vi velger nabotallet der den siste mantissebiten er \(0\). For \(1\) er den \(0\), for \(1+\varepsilon_{\mathrm{mach}}\) er den \(1\) – altså lagres \(1\). Det er overgangen du så ved \(2^{-53}\) i forsøket.

Hva forteller maskinepsilon?

Maskinepsilon beskriver presisjonen rundt tallet 1.

Det betyr ikke at avstanden mellom flyttall alltid er \(2^{-52}\). Avstanden vokser når størrelsen på tallene vokser. Det undersøker vi i neste fane.

Gå i dybden: kontroller definisjonen med sys.float_info

Python lagrer egenskapene til float i sys.float_info. Cellen sammenligner Pythons maskinepsilon med \(2^{-52}\) og med avstanden fra \(1\) til neste double, og kontrollerer de to påstandene over.

Øv på dette: maskinepsilon i mini-maskinen.

Maskinepsilon forteller hvor tett flyttallene ligger rundt \(1\). Men prosjekt 1 og mange beregninger bruker mye større og mye mindre tall. Ligger flyttallene like tett overalt? Cellen bruker math.ulp(x), avstanden fra \(x\) til neste flyttall, på tall fra \(2^{-20}\) til \(2^{60}\), og tester til slutt hva som skjer med \(+1\) og \(+2\) rundt \(2^{53}\). Målet er å se hvordan avstanden henger sammen med størrelsen på tallet.

Kjør cellen og les av avstanden rundt \(2^{0}\) og rundt \(2^{20}\).
Hvor mange ganger større blir avstanden når tallet blir \(2^{20}\) ganger større?

Hva viser forsøket? Avstanden vokser i samme takt som tallet: blir tallet \(2^{20}\) ganger større, blir avstanden også \(2^{20}\) ganger større. Det følger av samme regning som for \(\varepsilon_{\mathrm{mach}}\). Et tall mellom \(2^e\) og \(2^{e+1}\) er \((1.b_1\ldots b_{52})_2\times2^e\), og endrer vi den siste biten, endres tallet med

\[ 2^{-52}\cdot2^e=\varepsilon_{\mathrm{mach}}\cdot2^e. \]

Avstanden er altså omtrent \(\varepsilon_{\mathrm{mach}}\) ganger størrelsen på tallet:

mellom \(1\) og \(2\): \(2^{-52}\approx2.2\cdot10^{-16}\),
rundt \(1000\) (mellom \(2^9\) og \(2^{10}\)): \(2^{9-52}=2^{-43}\approx1.1\cdot10^{-13}\),
mellom \(2^{53}\approx9.0\cdot10^{15}\) og \(2^{54}\): \(2^{53-52}=2\). Tallet \(10^{16}\) ligger her.

Samme regning virker i alle binære formater: med \(p\) mantissebiter og eksponent \(e\) er avstanden mellom to nabotall \(2^{-p}\cdot2^e\).

Tallene mellom \(2^e\) og \(2^{e+1}\) er altså \(2^e,\ 2^e+\Delta,\ 2^e+2\Delta,\ldots\) med \(\Delta=2^{-52}\cdot2^e\), og tallet \(2^e+M\Delta\) har mantissefeltet \(M\) (lest som heltall). Siste mantissebit er \(0\) nøyaktig når \(M\) er et partall, så ved uavgjort velger ties to even nabotallet med partall \(M\). Rundt \(2^{53}\) er \(\Delta=2\): \(2^{53}+2\) har \(M=1\), mens \(2^{53}+4\) har \(M=2\).

Da ligger \(2^{53}+1\) nøyaktig midt mellom nabotallene \(2^{53}\) (med \(M=0\)) og \(2^{53}+2\) (med \(M=1\)), og ties to even velger \(2^{53}\), der alle mantissebitene er \(0\). Det er derfor

2.0**53 + 1 == 2.0**53

er sant i double precision, selv om det selvfølgelig er usant i eksakt matematikk.

Når forsvinner et lite tall?

Når vi regner ut \(a+b\), rundes svaret av til nærmeste flyttall. Er \(|b|\) mindre enn halve avstanden fra \(a\) til nabotallet på den siden \(b\) peker mot, er det nærmeste flyttallet \(a\) selv – og \(b\) er borte. Er \(|b|\) nøyaktig halve avstanden, avgjør ties to even. (Rett under en toerpotens ligger flyttallene dobbelt så tett: 1 - 1e-16 gir 0.9999999999999999, selv om 1 + 1e-16 gir 1.0.)

Rundt \(1\) er grensen \(\varepsilon_{\mathrm{mach}}/2\approx1.1\cdot10^{-16}\): 1 + 1e-16 gir 1.0, men 1 + 1.5e-16 gir 1.0000000000000002.
Rundt \(10^{16}\) er avstanden \(2\), så \(1\) er nøyaktig halve avstanden. \(10^{16}\) og \(2^{53}\) er begge delelige med \(4\), så \(M=(10^{16}-2^{53})/2\) er et partall og siste mantissebit er \(0\). Derfor runder ties to even 1e16 + 1.0 til 1e+16 – som i den aller første cellen i 1.3.

Øv på dette: avstanden for en fast eksponent og når forsvinner et lite tall?

I den første cellen i 1.3 forsvant \(1\) ved siden av \(10^{16}\). Nå bruker vi det samme fenomenet til å vise at regnerekkefølgen kan endre svaret. I eksakt matematikk gjelder

\[ (a+b)+c=a+(b+c). \]

Med endelig presisjon kan mellomresultatene avrundes. Cellen regner ut begge rekkefølgene for \(a=10^{16}\), \(b=-10^{16}\) og \(c=1\):

Hva skjedde?

I (a+b)+c blir a+b eksakt 0.0, og så legges 1.0 til.
I a+(b+c) er avstanden mellom flyttallene rundt -1e16 lik \(2\). Da ligger \(-10^{16}+1\) nøyaktig midt mellom to nabotall, og ties to even runder tilbake til -1e16.
Dermed blir a+(b+c) lik 1e16 - 1e16 = 0.0. Tallet \(1\) forsvant allerede i b+c.

Øv på dette: få mini-maskinen til å regne feil.

Også mange små avrundingsfeil kan hope seg opp. Cellen legger til 0.1 \(n\) ganger på den enkleste mulige måten, total = total + 0.1, for \(n=10,100,\dots,100\,000\). Til sammenligning summerer den de samme tallene med math.fsum. Denne funksjonen summerer flyttall nesten eksakt, og vi bruker den som fasit; hvordan den er programmert, trenger du ikke vite.

Hver enkelt avrundingsfeil er svært liten. Men når vi utfører mange operasjoner etter hverandre, kan feilene akkumuleres: for \(n=100\,000\) er feilen omtrent \(2\cdot10^{-8}\). math.fsum bruker en mer robust summeringsalgoritme og får feil \(0\) for alle \(n\) her.

Hvorfor vokser feilen? Hver addisjon runder av summen til nærmeste flyttall, med en feil på opptil halve avstanden mellom nabotallene rundt summen. Når summen blir større, blir avstanden større (forrige fane), så hvert nye \(0.1\) mister flere av sine siste sifre.

Sammenligning av flyttall

Unngå som regel a == b når a og b er resultater av beregninger. Test heller om de er nær hverandre:

import math
math.isclose(a, b)

Nyttige listeverktøy

Når du vil undersøke summer selv, er disse Python-verktøyene nyttige:

xs = [3.0, -1.0, 2.0]
[0.5] * 3                    # [0.5, 0.5, 0.5]
xs + [4.0]                   # slå sammen to lister
sorted(xs)                   # fra minst til størst
sorted(xs, reverse=True)     # fra størst til minst
sorted(xs, key=abs)          # etter absoluttverdi
[x for x in xs if x > 0]     # bare de positive tallene

IEEE 754 har også inf, -inf og nan (Not a Number), og subnormale tall nær null. Vi trenger dem ikke denne uken; i prosjekt 1 er inf og nan til og med forbudt.

Gå i dybden: inf, nan og subnormale tall

IEEE 754 har også verdier utenfor de vanlige endelige reelle tallene. Cellen lager dem og viser hvordan de oppfører seg i regning og sammenligning:

inf og -inf representerer positiv og negativ uendelig.
NaN betyr Not a Number.
NaN er ikke lik seg selv; bruk math.isnan(...) for å teste den.

IEEE 754 har også subnormale tall nær null. De gjør overgangen til null gradvis, men med redusert presisjon. Cellen går ett representerbart steg mot null fra det minste positive normaliserte tallet:

For dette kurset er det viktigst å vite at subnormale tall finnes; vi trenger ikke lære bitmønsteret deres i detalj.

Subtraksjon av to nesten like tall kalles kansellering: de ledende sifrene opphever hverandre. Selve subtraksjonen er ofte eksakt, men det som blir igjen, domineres av avrundingsfeil som allerede var der. Vi får tap av signifikante sifre.

Se på

\[ \sqrt{1+x}-1. \]

Matematisk kan vi gange og dele med det konjugerte uttrykket:

\[ \sqrt{1+x}-1 =\frac{(\sqrt{1+x}-1)(\sqrt{1+x}+1)}{\sqrt{1+x}+1} =\frac{(1+x)-1}{\sqrt{1+x}+1} =\frac{x}{\sqrt{1+x}+1}. \]

I telleren brukte vi \((s-1)(s+1)=s^2-1\) med \(s=\sqrt{1+x}\).

De to uttrykkene er matematisk identiske, men numerisk kan de være svært forskjellige. Vi lar nå \(x\) bli mindre og mindre og regner ut begge formene. Den omskrevne formen har ingen subtraksjon, så vi bruker den som fasit. Målet er å se hvor mange riktige sifre den direkte formen beholder.

Kjør cellen og sammenlign kolonnene linje for linje.
Ved hvilken \(x\) stemmer bare de første fire sifrene? Når blir den direkte formen helt feil?

Hva viser forsøket? Ta \(x=10^{-12}\). Da er \(\sqrt{1+x}=1.0000000000005\), og dette tallet er lagret med en avrundingsfeil av størrelse rundt \(10^{-16}\) (avstanden mellom flyttall nær \(1\)). Når vi trekker fra \(1\), forsvinner de tolv ledende sifrene, men feilen blir igjen. Sammenlignet med svaret \(5\cdot10^{-13}\) er \(10^{-16}\) omtrent \(2\cdot10^{-4}\), så bare de første tre–fire sifrene kan stemme. I tabellen står det \(5.0004\ldots\) mot \(5.0000\ldots\). For \(x\le10^{-16}\) blir 1 + x rundet til 1.0, og den direkte formen gir 0.0. Også i eksemplet med regnerekkefølgen i forrige fane var det kansellering: i \(a+(b+c)\) opphevet \(10^{16}\) og \(-10^{16}\) hverandre, og da ble det synlig at \(1\) allerede hadde forsvunnet i \(b+c\).

Tabellen viste noen få \(x\). Cellen under regner ut den relative feilen i den direkte formen for alle \(x=10^{-1},\dots,10^{-18}\), med den omskrevne formen som fasit, slik at vi ser hvor fort sifrene forsvinner:

Kurven stiger, ikke helt jevnt, fra omtrent \(10^{-15}\) til \(1\): ved \(x=10^{-12}\) er den relative feilen omtrent \(10^{-4}\), og ved \(x=10^{-16}\) er den \(100\,\%\).

Viktig mønster

Når du ser subtraksjon av nesten like tall (kansellering), bør du spørre om uttrykket kan omskrives.

Øv på dette: kansellering med fire sifre.

Gå i dybden: et liknende eksempel med cosinus

Et liknende eksempel er

\[ \frac{1-\cos x}{\sin^2x}. \]

For små \(x\) er \(\cos x\) nær \(1\), så telleren gir kansellering. Vi bruker \(\sin^2x=1-\cos^2x=(1-\cos x)(1+\cos x)\):

\[ \frac{1-\cos x}{\sin^2x} =\frac{1-\cos x}{(1-\cos x)(1+\cos x)} =\frac{1}{1+\cos x}, \]

som unngår subtraksjonen \(1-\cos x\).

Samme forsøk som over: vi lar \(x\) gå mot \(0\) og sammenligner de to formene. Begge skal gå mot \(\frac12\).

For \(x=10^{-8}\) blir math.cos(x) rundet til nøyaktig 1.0, og den direkte formen gir 0.0 i stedet for \(\frac12\).

Svar på ukens spørsmål

Vi spurte: Hvordan kan vi regne raskere – og hvorfor blir ikke \(0.1+0.2\) nøyaktig \(0.3\) på en datamaskin?

Raskere: Horners metode regner ut et polynom av grad \(n\) med \(2n\) regneoperasjoner i stedet for \((n^2+3n)/2\) – samme matematikk, en smartere algoritme.
\(0.1+0.2\): \(0.1\) og \(0.2\) har uendelig mange binære sifre og lagres som nærmeste flyttall. Summen rundes av én gang til og havner på nabotallet over det flyttallet som ligger nærmest \(0.3\). Hver regneoperasjon kan gi en feil på opptil halve avstanden mellom nabotallene – rundt \(1\) er det \(\varepsilon_{\mathrm{mach}}/2\approx1.1\cdot10^{-16}\).

I begge tilfeller er det algoritmen og tallformatet, ikke selve matematikken, som bestemmer hva datamaskinen gjør.

Kort oppsummert:

Et flyttall er ett av endelig mange tall, og avstanden til nabotallet er omtrent \(\varepsilon_{\mathrm{mach}}\) ganger tallet.
Hver regneoperasjon runder av til nærmeste flyttall: små tall kan forsvinne, og regnerekkefølgen kan endre svaret.
Subtraksjon av nesten like tall (kansellering) gjør gamle avrundingsfeil store; skriv da om uttrykket hvis du kan.

Gå i dybden: åtte ting å huske

Når du arbeider numerisk, husk:

Et maskinrepresentert flyttall er ett av et endelig antall representerbare tall.
Mange enkle desimaltall kan ikke representeres eksakt.
Hver regneoperasjon kan gi avrunding.
Små tall kan forsvinne ved siden av svært store tall: et tall under halve avstanden til nabotallet forsvinner.
Subtraksjon av nesten like tall (kansellering) kan gi tap av signifikante sifre.
Matematisk ekvivalente uttrykk kan ha svært ulik numerisk kvalitet.
Regnerekkefølgen kan påvirke svaret.
Sammenlign helst beregnede Python-float-verdier med en toleranse.

Numerisk tankegang

Det er ikke nok at en formel er matematisk riktig. Vi må også spørre om den gir en stabil beregning med endelig presisjon.

I prosjekt 1 – Floating-point attack bruker du nettopp disse mekanismene: du lager tall som får en helt vanlig summering til å regne feil, og forklarer hvor informasjonen forsvinner.

Vil du øve på eksamensoppgaver om flyttall? Se Eksamensoppgaver: flyttall og numerisk stabilitet.

Gå i dybden: undersøk et hvilket som helst flyttall

Funksjonen under samler verktøyene fra 1.3: den eksakte brøken, den heksadesimale formen, avstanden til neste flyttall (ulp) og de to naboene. Endre tallet og kjør på nytt.

Så langt har vi hovedsakelig arbeidet med double precision (64 bit). Det gir god presisjon, men hvert tall krever også 64 bit lagringsplass.

I kunstig intelligens kan en modell inneholde milliarder av tall. Da begynner antall bit per tall å bety mye.

format	bit per tall	ca. lagring for \(10^9\) tall
FP64	64	8 GB
FP32	32	4 GB
FP16	16	2 GB
FP8	8	1 GB
FP4	4	0.5 GB

Med færre bit må vi i større grad velge mellom rekkevidde og presisjon. Det er den samme avveiningen vi har sett i denne uken: avstanden mellom nabotall er \(2^{-p}\cdot2^e\), så færre mantissebiter \(p\) gir større avstand, og flere mulige eksponenter \(e\) gir et større område.

Flere eksponentbiter gir større rekkevidde. Flere mantissebiter gir bedre presisjon.

Gå i dybden: to varianter av FP8

FP8 (beskrevet i AMDs dokumentasjon) finnes for eksempel i variantene

\[ \boxed{E4M3} \qquad\text{og}\qquad \boxed{E5M2}. \]

E4M3: 1 fortegnsbit, 4 eksponentbiter og 3 mantissebiter.
E5M2: 1 fortegnsbit, 5 eksponentbiter og 2 mantissebiter.

E5M2 bruker altså flere bit på eksponenten og får større rekkevidde. E4M3 bruker flere bit på mantissen og får bedre presisjon innenfor et mindre område.

Gå i dybden: FP4 og kvantisering

Færre bit per tall betyr ikke bare mindre lagring. Det blir også mindre data som må flyttes mellom minne og prosessor, og spesialisert maskinvare kan utføre flere lavpresisjonsoperasjoner samtidig.

Kilde for formatene

Beskrivelsene av FP8 og FP4 her er hentet fra AMDs dokumentasjon:

AMD ROCm: Low precision floating point types

Vi bruker bare formatbeskrivelsene og motivasjonen her. Programmeringseksemplene på denne siden er vanlig Python.

Hvor lavt kan vi gå?

I AI brukes blant annet formater som

\[ \text{FP32}\rightarrow\text{FP16}\rightarrow\text{FP8} \rightarrow\text{FP6}\rightarrow\text{FP4}. \]

FP4 – bare fire bit

AMD beskriver også FP4 E2M1:

\[ \boxed{S}\boxed{EE}\boxed{M}. \]

Det betyr

1 fortegnsbit,
2 eksponentbiter,
bare 1 mantissebit.

FP4 er spesielt interessant for lagring av vekter i store språkmodeller og vision transformers. Sammenlignet med FP16 krever hver lagret verdi bare en fjerdedel så mange bit.

Formatet ligner på mini-maskinen i Oppgaver. Forskjellen er at ekstremt små tallformater ikke bare er pedagogiske leketøy: de brukes for å gjøre store AI-modeller mindre og beregningene mer effektive.

Et lite Python-eksempel

Vi trenger ikke spesiell AI-maskinvare for å demonstrere hovedideen. Anta at vi bare tillater noen få mulige verdier. Cellen erstatter hver «vekt» med den tillatte verdien som ligger nærmest, akkurat som avrunding til nærmeste flyttall:

Vi har mistet mye presisjon. Likevel er de fleste fortegn og omtrentlige størrelser fortsatt bevart; bare den minste vekten, \(0.06\), er blitt \(0\).

Å erstatte verdier med et mye mindre sett av mulige representasjoner er en form for kvantisering.

Hvorfor kan dette fungere?

Et nevralt nettverk gjør enorme mengder beregninger. Det viktige er vanligvis ikke at én enkelt multiplikasjon har 15 korrekte desimaler, men at hele modellen fortsatt gir gode resultater.

Derfor kan det være lønnsomt å ofre noe numerisk presisjon for å få

mindre modeller,
mindre minnetrafikk,
raskere beregninger,
muligheten til å kjøre større modeller på samme maskinvare.

Men lav presisjon er ikke gratis. Hvis vi går for langt, kan avrundingsfeilene bli for store og modellen bli dårligere.

Samme idé – helt annen skala

Gjennom hele uken har vi spurt hvorfor \(0.1+0.2\) ikke blir nøyaktig \(0.3\) – hva som skjer når datamaskinen ikke kan representere et tall nøyaktig.

I AI kan spørsmålet nesten snus:

Hvor lite presisjon klarer vi oss med?

FP16, FP8 og FP4 viser at begrenset presisjon ikke bare er et problem vi må leve med. Den kan også brukes bevisst for å spare minne og beregningstid.

Her bygger vi en mini-versjon av en flyttallsmaskin. Poenget er at formatet er så lite at vi faktisk kan se alle tallene maskinen kjenner.

Vi bruker et forenklet format med

\[ \boxed{S}\quad\boxed{EEE}\quad\boxed{MMMM} \]

der

\(S\) er én fortegnsbit,
\(E\) er 3 eksponentbiter,
\(M\) er 4 mantissebiter,
bias er \(3\).

Vi bruker bare normaliserte tall med

\[ E=1,2,\ldots,6. \]

Bitmønstrene \(E=0\) og \(E=7\) ser vi bort fra. Vi ignorerer altså subnormale tall, inf og NaN i denne mini-maskinen.

Et tall tolkes som

\[ (-1)^S\left(1+\frac{M}{16}\right)2^{E-3}, \]

der \(M\) er heltallsverdien til de fire mantissebitene.

Hvorfor gjøre dette?

IEEE 754 double har så mange bit at det er vanskelig å «se» hele tallsystemet. Mini-maskinen følger samme hovedidé, men har så få tall at vi kan liste dem opp, tegne dem og bryte regnereglene med små, forståelige eksempler.

Vi starter med å lese bitmønstre.

For eksempel

\[ 0\;|\;100\;|\;0110 \]

gir

\[ S=0,\qquad E=(100)_2=4,\qquad e=4-3=1, \]

\[ M=(0110)_2=6. \]

Dermed

\[ x=(1+6/16)2^1=2.75. \]

For å dekode et bitmønster leser vi derfor de tre feltene hver for seg: fortegnsbiten \(S\), de tre eksponentbitene \(E\) og de fire mantissebitene \(M\). Deretter regner vi ut \(e=E-3\) og setter verdiene inn i mini-maskinens formel.

Les de tre feltene og regn ut verdien, som i eksemplet over.

Dekod et mini-flyttall

Nå går vi motsatt vei. Hvis et tall allerede er representerbart, kan vi skrive det som

\[ \pm(1.MMMM)_2\,2^e, \]

finne \(E=e+3\), og deretter skrive \(S\), \(E\) og \(M\) som bit.

Nå går vi motsatt vei: fyll inn fortegn, eksponentfelt og mantissefelt. Skriv inn \(S\), \(E\) og \(M\) som bitstreng, det vil si sekvensen av \(0\) og \(1\).

Kod et tall i mini-formatet

Mini-maskinen har bare

\[ 6\cdot16=96 \]

positive normaliserte tall. Det er lite nok til at vi kan tegne hele tallinjen.

Skriv funksjonen slik at den returnerer alle de 96 positive normaliserte tallene, sortert fra minst til størst.

Når vi tegner alle de positive tallene, blir noe som var vanskelig å se i binary64 helt tydelig.

Her lager vi ikke tallene på nytt. Bruk funksjonen du nettopp skrev som verktøy: lim den inn øverst i cellen. Hjelperen plot_number_line tegner tallene som prikker på en tallinje. Kjører du cellen før funksjonen er limt inn, får du NameError: name 'positive_mini_values' is not defined. Det betyr bare at funksjonen mangler.

Poenget er at din egen liste nå blir datagrunnlaget for figuren. Se spesielt på avstanden mellom punktene nær \(0.25\), \(1\), \(4\) og \(8\).

Spørsmål: Ligger tallene jevnt fordelt? Hva skjer med avstanden når eksponenten øker?

Et vanlig reelt tall trenger ikke være blant de 96 positive eller 96 negative verdiene maskinen kjenner.

Da må vi velge det nærmeste representerbare tallet.

For eksempel ligger \(1.1\) mellom

\[ 1.0625 \quad\text{og}\quad 1.125. \]

Det nærmeste er \(1.125\), så mini-maskinen vil lagre

\[ 1.1\longmapsto1.125. \]

Avrunding i mini-maskinen betyr altså å velge den representerbare verdien med minst avstand til tallet som skal lagres.

Ligger tallet nøyaktig midt mellom to mini-tall, bruker vi samme regel som IEEE 754, ties to even: vi velger tallet der den siste mantissebiten er \(0\). Eksempel: \(9.25=(1001.01)_2=(1.00101)_2\times2^3\). Med fire mantissebiter ligger det midt mellom \((1.0010)_2\times2^3=9\) og \((1.0011)_2\times2^3=9.5\). Siste bit er \(0\) for \(9\), så mini-maskinen lagrer \(9.25\longmapsto9\). I bitform er det \(0\;|\;110\;|\;0010\), fordi \(E=3+3=6=(110)_2\).

Bruk regelen over på nye tall: finn de to mini-tallene som \(x\) ligger mellom, og velg det nærmeste. Ligger \(x\) nøyaktig midt mellom, avgjør ties to even.

Rund til nærmeste mini-flyttall

Nå lar vi Python gjøre denne avrundingen. Vi trenger både positive og negative mini-flyttall.

Kopier din egen positive_mini_values() fra forrige fane inn i kodevinduet. Deretter lager du all_mini_values() og mini_float().

Når du først har laget et verktøy, bruker vi det videre i stedet for å servere løsningen på nytt.

Når koden din i denne oppgaven virker, har du laget en liten verktøykasse:

positive_mini_values()
        ↓
all_mini_values()
        ↓
mini_float(x)

Ta vare på funksjonene. I neste fane skal mini-maskinen begynne å regne.

Til slutt i denne fanen: hva er maskinepsilon i et lite format? Regn som for binary64 i fanen «Maskinepsilon».

I mini-maskinen er \(1=(1.0000)_2\times2^0\). Det neste tallet får vi ved å gjøre den siste av de fire mantissebitene til \(1\):

\[ (1.0001)_2=1+\frac1{16}. \]

Avstanden fra \(1\) til neste tall er altså \(\frac1{16}\). Gjør samme regning for formater med et annet antall mantissebiter \(p\).

Maskinepsilon for små binære formater

Sammenlign dette med binary64:

\[ p=52 \quad\Longrightarrow\quad \varepsilon_{\mathrm{mach}}=2^{-52}. \]

Det er samme idé. Den virkelige maskinen har bare langt flere mantissebiter.

Nå har du selv bygget representasjonen og avrundingen. Da kan vi endelig la mini-maskinen regne.

Mini-addisjon gjør tre ting:

begge tallene rundes til mini-formatet,
de legges sammen,
resultatet rundes tilbake til mini-formatet.

Det eneste nye verktøyet vi gir deg er selve addisjonen, funksjonen mini_add i cellen under. Legg merke til at mini_add bruker din mini_float. Lim inn funksjonene dine øverst i cellen under før du kjører den. Kjører du cellen før funksjonene er limt inn, får du NameError: name 'mini_float' is not defined. Det betyr bare at funksjonen mangler.

Cellen viser allerede ett par der

\[ a\oplus b=a. \]

Finn flere: forsvinner \(b=0.25\) for alle \(a\) mellom \(8\) og \(15.5\)? Hva sier ties to even? Her trenger vi ikke tall som \(10^{16}\). Mini-formatet er så grovt at fenomenet blir synlig med små tall.

Forklar resultatene i cellen ved å se på avstanden mellom mini-tallene rundt \(a\): rundt \(1\) er den \(\frac1{16}\), rundt \(4\) er den \(\frac14\), og rundt \(8\) er den \(\frac12\). Ved \(a=8\) er \(b=0.25\) nøyaktig halve avstanden. Hva gjør din mini_float da, og hva ville regelen ties to even fra fanen «3. Avrunding i mini-maskinen» gitt?

Obs: Prøver du \(b=0.1\), forsvinner \(b\) uansett hva \(a\) er, men av en annen grunn: \(0.1\) er mindre enn halvparten av det minste positive mini-tallet \(0.25\) og rundes selv til \(0\), fordi mini-maskinen ikke har subnormale tall.

Til slutt skal Python lete etter brudd på regelen \((a+b)+c=a+(b+c)\). Skriv en funksjon som leter gjennom alle tripler fra en gitt liste og returnerer én trippel

\[ (a,b,c) \]

der

\[ (a\oplus b)\oplus c \neq a\oplus(b\oplus c). \]

Når du har funnet en trippel, regn gjennom begge parenteseringene for hånd med mini-formatet. Det er den viktigste delen av oppgaven: Python finner moteksemplet, men du skal kunne forklare hvor de to beregningsveiene blir forskjellige.

Verktøykassen er en del av oppgaven

Gjennom oppgavene bygger du

\[ \texttt{positive\_mini\_values} \longrightarrow \texttt{all\_mini\_values} \longrightarrow \texttt{mini\_float} \longrightarrow \texttt{mini\_add}. \]

Senere oppgaver bruker tidligere resultater. Derfor må du av og til kopiere en funksjon du allerede har skrevet. Det er med vilje: vi bygger videre på arbeidet ditt uten å vise fasiten i neste kodevindu.

Koblingen tilbake til IEEE 754

Mini-maskinen er ikke IEEE 754. Vi har med vilje fjernet spesialtilfeller og redusert antall bit kraftig.

Men de viktigste mekanismene er de samme:

bare endelig mange tall kan representeres,
avstanden mellom tallene avhenger av eksponenten,
resultater må avrundes tilbake til et representerbart tall,
små bidrag kan forsvinne,
regnerekkefølge kan påvirke resultatet.

Det er derfor den lille maskinen er nyttig: vi kan se hele mekanismen uten å drukne i 64 bit.

Vil du øve på eksamensoppgaver om flyttall? Se Eksamensoppgaver: flyttall og numerisk stabilitet.

Denne fanen handler om binary64, ikke mini-maskinen. I oppgavene øver du på reglene fra fanene «Avstand mellom flyttall», «Avrunding» og «Tap av signifikans». Du trenger ikke Python; alt kan regnes for hånd.

Avstanden for en fast eksponent

I binary64 har mantissefeltet 52 bit. Alle tall i intervallet nedenfor har samme eksponent \(e\). Finn \(e\) og bruk den, slik vi gjorde for \(\varepsilon_{\mathrm{mach}}\), til å finne avstanden mellom to nabotall i intervallet.

Avstanden mellom nabotall i binary64

Når forsvinner et lite tall?

Datamaskinen regner ut \(a+b\) i binary64 og runder til nærmeste flyttall, med ties to even ved uavgjort. Finn først avstanden fra \(a\) til neste flyttall over \(a\), og avgjør så hvilket flyttall summen rundes til. Oppgi hvor mye den lagrede summen er større enn \(a\), altså \(\mathrm{fl}(a+b)-a\).

Hva blir igjen av det lille tallet?

Kontroller gjerne svaret ditt i en av kodecellene i fanen «Avstand mellom flyttall», for eksempel med (2.0**53 + 3) - 2.0**53.

Kansellering med fire sifre

Samme idé virker i titallssystemet. Vi bruker et desimalt format med fire signifikante sifre: hvert tall lagres som \(\mathrm{fl}(x)\), avrundet til nærmeste tall med fire signifikante sifre, og resultatet av en subtraksjon avrundes på samme måte. (Ingen av tallene her ligger midt mellom to tall med fire sifre. I eksamensoppgaven med fire sifre rundes uavgjort bort fra null.) Lagre \(x\) og \(y\), trekk de lagrede verdiene fra hverandre, og sammenlign med den eksakte differansen.

Lagre og subtraher med fire signifikante sifre

Hvor mange av sifrene i den maskinelle differansen er riktige? Hvor stor er den relative feilen? Sammenlign med \(\sqrt{1+x}-1\) i fanen «Tap av signifikans».