Computere slås måske nok for at opføre sig intelligent, men at udføre matematiske beregninger er da vel deres styrke. Eller er det?

Google’s online lommeregneres fiasko og Excel’s tidligere tydelige manglende evne til at give korrekte svar på simple matematiske beregninger er begge velkendte problemer blandt programmører, men disse er ikke programfejl i ordets almindelige forstand.

I stedet er de bare en konsekvens af det faktum, at computere er elendige til matematik. Computere udfører matematiske beregninger på en ganske anden måde end de metoder, vi mennesker bruger til at regne med – og det betyder, at de jævnligt finder frem til et forkert svar.

Her undersøger vi nogle af de chokerende konsekvenser af denne åbenbaring, før vi dykker ned i grunden til, at computere er så dårlige til matematik.

Tæt på er ikke tæt nok

For de der stadig skal overbevises om, at computere ikke kan regne simpel matematik ud, lad os starte med et par eksempler. Først Google’s lommeregner. Hvis du aldrig har prøvet den før og vil have en fornemmelse af, hvordan den virker, så gå ind på www.google.dk, tast 5*9+(sqrt 9)^3 i søgefeltet og klik på ’Søg’. Her ser du, at den kommer med det korrekte svar: ’5*9+(sqrt 9)^3 = 72’. Lad os nu prøve en anden beregning. Tast 599.999.999.999.999 - 599.999.999.999.998. Tydeligvis skulle dette givet svaret 1. Utroligt nok svarer Google dog med dette: ’599.999.999.999.999 - 599.999.999.999.998 =0’.

Det er måske indlysende åbenbart for dig at svaret på denne beregning er 1 – men det er det åbenbart ikke for Google.

Kan dette blot være et sjældent og uheldigt eksempel? Okay, så prøver vi en anden enkel beregning (de dog har rettet nu). Hvis du tastede =850*77,1 ind i celle A1 i en Excel 2007 (upatchet) mappe (det virker ikke – eller burde det være, at det virker – i tidligere versioner af Excel). En smule mental matematik ville antyde, at svaret burde være i nærheden af 60.000; faktisk er det korrekte svar 65.535.

Excel havde dog et andet bud. Excel synes at resultatet af denne multiplikation er 100.000, hvilket er skudt 34.465 forbi. For at vise at det ikke er nogen engangsforestilling, så prøv at få et udvalg af online lommeregnere til at udregne 1,0 – 0,9 – 0,1. Du vil sandsynligvis opleve, at mindst halvdelen af dem kommer med svaret -2.77555756E-17 – som er en videnskabelig notation for -0,0000000000000000277555756. (Hvis alle dem, du prøver, giver det rigtige svar, så kig på www.calculator.net .)

Siden 1,0 – 0,9 – 0,1 giver 0, hvorfor er mange online lommeregnere så overbeviste om, at denne værdi i stedet er svaret?

Okay, dette svar er måske nok ikke langt fra det rigtige resultat 0, men hvorfor kan lommeregneren ikke finde det rigtige svar – et svar, der er åbenbart indlysende for enhver, der er bekendt med simpel regning?

Små fejl akkumuleres

Læs boksen ’Hvordan computere beregner’, og du vil se, at mange af de fejl, vi har set indtil nu, bunder i afrundingsfejl. Uoverensstemmelsen mellem det beregnede svar og det korrekte svar er ofte minimal, og du vil måske være tilbøjelig til at affærdige denne slags fejl som ubetydelige. Sådanne fejl kan dog hobe sig op og akkumuleres, og konsekvensen kan være seriøs.

Den 25. februar 1991, tre dage før slutningen på den første Golf-krig, ramte et irakisk Scud-missil en amerikansk flyveplads i Dhahran, Saudi-Arabien. 28 amerikanske soldater blev dræbt og mere end 100 andre blev såret.

Dengang var følsomme mål beskyttet af Patriot jord-til-luft forsvarssystemet, og et batteri af Patriot-missiler var udkommanderet til Dhahran-forlægningen, så det er relevant at spørge om, præcis hvad der gik galt. Svaret er systemets sporingssoftware, og problemet er ikke helt irrelevant til vores online lommeregner fejl.

For at undgå potentielt dyre falske alarmer, skal Patriot’s sofistikerede radar først spore et objekt, der har et Scud-missils karakteristika og så derefter spore det endnu engang i en position beregnet af systemet ud fra den antagelse, at den første stedbestemmelse virkelig var et Scud.

Først når denne anden stedbestemmelse giver en bekræftelse, bliver et missil opsendt for at opsnappe det. Beregningen af, hvor der skal kigges for bekræftelse af et indkommende missil, kræver kendskab til systemtiden, som er gemt som antallet af 0,1-sekund–tik, siden systemet blev tændt og startet.

Desværre kan 0,1 sekunder ikke udtrykkes nøjagtigt som et binært tal, så når det bliver klemt ind i et 24bit register – som brugt i Patriot-systemet – er det en lille smule ved siden af.

Alle disse afvigelser akkumuleres dog. Da missilangrebet skete, havde systemet kørt i omkring 100 timer, eller 3.600.000 tik for at være mere præcis. Da dette blev ganget med den lillebitte fejl, ledte det til en akkumuleret fejl på 0,3433 sekunder, og i løbet af denne tid ville Scud-missilet kunne nå 687m.

Radaren kiggede på det forkerte sted for at modtage en bekræftelse og så intet mål. Følgelig blev intet missil skudt af for at opsnappe det indkommende Scud – og 28 mennesker betalte med deres liv.

Afrundingsfejl fik et Patriot-missil som disse til at ramme ved siden af med tragiske følger.

Processoren der ikke kunne dividere

Udgivet i marts 1993, var Pentium’en Intel’s femte generation af x86-processorer. I modsætning til tidligere generationer, i hvilke i det mindste nogle af familiemedlemmerne kun kunne beregne i hele tal, havde alle en decimaltalsenhed (floating point unit - fpu). En fpu er et stykke indbygget hardware til decimaltalsberegning.

Dette gav Pentium en massiv hastighedsfordel, idet computere uden en fpu-aktiveret processor var nødt til at udføre denne slags beregninger ved hjælp af software-rutiner, der involverede mange heltalsberegninger. Uheldigvis var dét et forgiftet bæger for Intel.

I juni 1994, kort tid efter at have modtaget en Pentium-baseret computer, bemærkede Thomas Nicely – dengang matematikprofessor på Lynchburg College, Virginia – at et program, han havde skrevet, gav selvmodsigende resultater. Ved at køre samme program på flere maskiner, isolerede professor Nicely problemet til sin nye computers Pentium-processor og, i særdeleshed, til dens decimaltalsdivisions (floating point division - FDIV) instruktioner.

Selvom det kun påvirkede en lillebitte proportion af decimaltalsdivisioner, var fejlen, når den var værst, faktisk ret betydningsfuld. Division af 4.195.835 med 3.145.727 gav resultatet 1,3337 – hvilket repræsenterer en fejl i fjerde decimal, siden det korrekte svar faktisk er 1,3338.

Pentium’s FPU brugte noget kaldet SRT algoritmen for at udføre decimaltalsdivisioner. Selvom der er simplere og mere åbenlyse måder at dividere et decimaltal med et andet på, gav SRT algoritmen en væsentlig hastighedsfordel over tidligere algoritmer.

Hvis du ikke er matematiker, vil du nok finde en beskrivelse af, hvordan SRT virker, totalt uigennemsigtig. Lad os dog bare sige, at i stedet for at udarbejde alting ved hjælp af ’ren matematik’, så involverede det brugen af en opslagstabel. Tabellen indeholdt omkring 1.000 værdier, men på grund af en produktionsfejl manglede fem af disse værdier.

På trods af det faktum at Intel’s CEO Andy Grove regnede med at den gennemsnitlige bruger kun ville opleve problemet en gang hvert 27.000’nde år, var IBM’s estimat en gang hver 24’nde dag, og på baggrund af dette stoppede firmaet med at udsende Pentium-baserede computere.

Intel gik til sidst med til at udskifte defekte Pentium’er med nogen, der virkede. De fleste tog ikke imod tilbuddet, men forsinkelsen fik teknisk orienterede brugere til at bruge Intel som skydeskive for vittigheder. Den følgende er typisk: Spørgsmål: Hvor mange Pentium-designere skal der til for at skifte en pære? Svar: 1,99904274017, men det er præcist nok til ikke-tekniske mennesker.

Intel’s Pentium kunne give svar på decimaltalsdivisioner, der var forkerte i det fjerde decimal.

En milliard op i 32.767 går ikke

De fejl, vi hidtil har set, har drejet sig om decimaltal, hvor nøjagtighed går tabt, hvis der ikke er nok bit til at gemme mantissen. Okay, disse fejl kan akkumulere, men i bund og grund er de bare afrundingsfejl, og sandsynligheden for ikke at have bits nok til at gemme eksponenten er relativt lille, givet at maksimumværdien, de kan gemme, er absolut enorm. Når heltal er involveret, kan effekten faktisk være langt mere alvorlig.

I boksen ’Sådan regner computere’ forklarer vi, at et 64bit heltal kan gemme en maksimal positiv værd på 9.223.372.036.854.775.807. Hvis du prøver at lægge 1 til en heltalsværdi, som allerede er lige så stor som maksimumværdien, så mister du ikke bare den ekstra værdi, men heltallet flyder over.

Med andre ord, for så vidt angår en computer, der arbejder i 64bit beregningsoperationer, er 9.223.372.036.854.775.807 + 1 = -9.223.372.036.854.775.807 (bemærk minus-tegnet).

Noget meget tilsvarende skete ombord på det europæiske rumcenters Ariane V raket på dennes jomfrurejse. Faktisk var den pågældende regneoperation, hvis du kan kalde den det, endnu simplere end at lægge 1 til.

Det drejede sig snarere om at kopiere et tal, der havde været gemt som et decimaltal, til en anden placering, der var defineret som et heltal – og endda et 16bit heltal (maksimum positive værdi er 32.767). Uheldigvis var tallet allerede for stort til at passe ind i denne heltalsplacering og følgelig løb det over.

Den nøjagtige sekvens af begivenheder, der fulgte, er temmelig kompleks, men for at gøre en lang historie kort var slutresultatet, at Ariane V blev noget af det dyreste fyrværkeri i historien.

Programmører kalder det et overløb; i virkeligheden var det dårlig beregning der fik dette rumskib til $370 millioner til at eksplodere.

På vagt over for kludder

Denne gennemgang af nogle af computerberegningens mest forbavsende smuttere er måske kommet som lidt af en lærerig oplevelse for dig. Hvis det er tilfældet, så spekulerer du måske på, hvorvidt morgendagens computere kan undgå at lave sådanne elementære fejl.

Overraskende kunne alle de fejl, der her er nævnt – og med undtagelse af Pentium decimaltalsfejlen, som var forårsaget af en hardwarefejl – måske være forhindret. I den forstand kan de alle betegnes som softwarefejl. Lad os tage heltalsoverløbet på Ariane V raketten som et eksempel.

At et heltal kan løbe over, er ikke en processorfejl, da det er den måde, det skal virke på. Når som helst et heltal flyder over, sætter processoren dog noget kaldet et flag, som programmet kan undersøge. I tilfældet med Ariane-softwaren tjekkede programmet ikke for et overløb; hvis det havde, kunne det have foretaget en korrigerende handling.

Selvfølgelig vil der altid være en grænse for, hvor stort et heltal kan være, og hvor stor en præcision et decimaltal kan have – og dette afhænger af processoren.

Alle nutidens computere er dog almene regnemaskiner, hvilket betyder, at de kan løse ethvert problem, der involverer logik og matematik. Så hvis en processors interne instruktioner ikke kan operere med store nok heltal eller decimaltal med tilstrækkelig præcision, så er det altid muligt for programmøren at implementere regnerutiner, som kan. Der vil dog være en byttehandel på bekostning af hastighed, hvilket er hvorfor det ikke almindeligvis bliver gjort.

Hvor smart softwaren end er, og hvor meget hukommelse du end bruger til at gemme decimaltal, vil resultatet af nogle divisioner aldrig blive præcise. Vi har set hvordan 1 delt med 10 er en uendelig streng i binært, og, i almindelige tilfælde, vil et skift til decimaltalsberegning heller ikke hjælpe: 1 delt med 10 kan gemmes præcist i decimaltal, men 1 delt med 3 giver 0,3333333.. i det uendelige.

Sagens kerne er, at hvad end det er en nummerbase, du vælger, så vil nogle divisioner producere resultater, som aldrig kan blive gemt præcist som en begrænset række af tal. Selv dette er dog ikke en stopklods. Husk hvordan 1,0 – 0,9 – 0,1 ofte gav et unøjagtigt resultat på grund af afrundingsfejl, selv om vi med det samme ved, at svaret er 0?

Altså, det er ganske muligt at skrive software, som gemmer resultatet af en division som et rationelt tal. Med andre ord, du udfører faktisk ikke divisionen – du gemmer bare de to tal. I efterfølgende regneoperationer behandles disse værdier som brøker, ganske som du lærte det i skolen, og resultatet vil blive nøjagtigt.

Så computere dumper måske til matematik, men der er altid en løsning tilgængelig til at omgå deres naturlige svaghed. I det tilfælde er det så sikkert mere præcist at sige, at computerprogrammører dumper til matematik – eller i al fald nogen af dem gør.

Sådan regner computere

Computere tilgår matematikberegninger meget anderledes, end vi gør.

Selvom computere kan håndtere heltal, så gemmer de tal i decimalformat, fordi det er så meget mere effektivt i hukommelsesforbrug. Lad os se på dobbeltpræcisions decimaltalrepræsentationen som et eksempel. Det bruger 64 bit for at gemme hvert tal og tillader værdier fra omkring -10308 til 10308 (minus og plus 1 begge fulgt af 308 nuller) at blive gemt.

Desuden kan minimale værdier så små som plus eller minus 10-308 (det er et decimaltal fulgt af 307 nuller og så et 1) gemmes. Til sammenligning, hvis de samme 64 bit blev brugt til at gemme heltal, ville værdimængden gå fra -9.223.372.036.854.775.807 til +9.223.372.036.854.775.807, og decimalværdier kunne ikke repræsenteres.

Hemmeligheden bag denne tilsyneladende forbløffende effektivitet er tilnærmelse. Af de 64 bit repræsenterer den ene fortegnet (altså om værdien er positiv eller negativ), 52 bit repræsenterer mantissen (det er det faktiske tal) og de tilbageværende 11 bits repræsenterer eksponenten (hvor mange nuller der er eller hvor kommategnet er).

Sådan regner computere

Så selvom en langt større række af tal kan gemmes med anvendelse af decimaltalsnotation, er præcisionen faktisk mindre, end hvad der kan opnås med heltalsformat, siden kun 52 bit er til rådighed.

Selv den mest avancerede processor i dag håndterer matematisk beregning på en måde, der kan resultere i små afrundingsfejl.

Faktisk repræsenterer 52 bit binær information et 16bit decimaltal, så alle værdier, der afviger kun i deres 17’nde plads efter kommaet, vil blive set som identiske. Situationen, hvor Google tror, at 599.999.999.999.999 - 599.999.999.999.998 giver 0, er tilsvarende, selvom det er tydeligt, at Google’s lommeregner faktisk bruger mindre end de almindelige 52 bit til mantissen.

Det, at nogle lommeregnere giver et resultat, der ikke er nul, på beregningen 1,0 – 0,9 – 0,1, ser måske anderledes ud, siden vi ikke ser ud til at være i nærheden af grænsen på 64bit decimaltalsberegning.

Det er dog kun, hvis man glemmer et vigtigt faktum – at computere arbejder binært. Selvom 0,1 måske nok kun har et betydende decimalciffer, så er mantissen en gentagende sekvens i binær notation. Dette betyder, at 0,1 aldrig kan repræsenteres præcist i binært, uanset hvor mange bit, du bruger.