Frank Vilhelmsen's blog

Unit of Least Precision February 09, 2010 13:31 6 months ago

Kigger ud af vinduet mens jeg leger med en matematisk formel og tænker på Unit in the last place Beregningen fortager en prognose over en rate pension. Den antager en masse udfra nogle parameter og returner et resultat i form af kroner og øre. Jeg er stoppet op for at tænke lidt over præcision og udtryk mellem formler og programmeringsprog. Problemet er at jeg operere med store decimaltal og jeg ved de er upræcise.

I første ilteration udnytter jeg Ruby som programmeringssprog fordi det handler udvikling af en formel og forståelse af problemområdet. Derefter skal de bedste formler overføres til Java som implementeringserpog og Javascript for hurtige forretningsvalidering. Undervej har jeg erfaret at jeg får forskellige resultater afhængig af platform og sprog.

Lad mig starte med et regnestykke. 0.1 + 0.1 + 0.1 = ?

System.out.println(0.1 + 0.1 + 0.1); # 0.30000000000000004

Resultatet er skuffende, og ikke de forventede 0.3 men et mere præcist resultat. Grunden er at Java konvertere værdien 0.1 til en double repræsentation og nu vil de mest ihærdige Java folk straks råbe løs om BigDecimal.

System.out.println(new BigDecimal(0.1).add(new BigDecimal(0.1)).add(new BigDecimal(0.1)));
# 0.3000000000000000166533453693773481063544750213623046875

Og det hjalp også lidt. Nu er resultatet langt mere præcist men stadig helt forkert.

Problemet er at et floating point tal er internt repræsenteret i binær form og decimaltallet 0,1 kan ikke præcist repræsenteres som “1,00011001100110”. Det er lidt det samme som at dele en hel (1) i 1/3 og 2/3. Derved får man en 0.333333 og en 0.666666. Når disse to lægges sammen bliver det kun en 0.9999999 og ikke en hel.

Men dette er kun første del af svaret. Vi må længere ind..

Der findes to typer af løsninger.

• Den mest åbenbare er at undlade at arbejde med tal hvori der indgår decimaler
• Den anden er at afrunde og beskære resultatet

Decimaler eller floating point er i sagens natur upræcise. De bør undgås hvis der i løsningen skal indgå super præcise svar. Fx ved beløb eller møntenhed kan løsningen være at holde alle en enheder på lavest mulig niveau. Øre frem for kroner. Det virker som en naturlig ting at gøre, specielt hvis man tænker over at vi jo aldrig holder danske kroner i 10 stks pakker.

Den anden metode er at skære de sidste mindst betydende decimaler af resultatet. Denne løsning bliver heller ikke præcis fordi der nu skal rundes af og jo flere kald der fortages jo flere metoder vil runde op eller ned ved afkortning af resultatet. Yderligere fejl findes der i de trigonometriske funktioner ikke der ikke er så teoretisk korrekte som man kunne forvente. Dette er et resultat af akkumulerede afrunding fejl i polynomium tilnærmelser der bruges internt til at beregne trigonometriske funktioner og logaritmer.

Lad og kigge på Eulers konstant E er den matematiske konstant tættest på det unikke reelle tal.

System.out.println(Math.E); # 2,718281828459045
System.out.println(Math.exp(1)); # 2,7182818284590455

Teoetisk burder disse to være ens i Java for at give resultater der er tæt på det teoretiske forventede. I ruby har Matz afrundet og afkortet en decimal tidligere for at ikke at løbe ind i akkumulerede fejl.

puts Math::E # 2,71828182845905
puts Math.exp(1) # 2,71828182845905

Log

Den naturlige algoritme er base e, hvor e er et irrationelt konstant på 2,71828182845905. Den naturlige algoritme er skrevet som ln(x) eller log(x). Logaritmen af et tal til et givet basis er eksponent som base skal hæves for at producere et antal. For eksempel, base-10-logaritmen af 1000 er 3, da 3 er den magt, som ti skal hæves med for at producere 1000: 103 = 1000, så log10(1000) = 3. Logaritmen til x til basen b er skrevet logb (x) eller, hvis basen er implicit, så log (x). Så for en række x, en base b og en eksponent y.

Math.log(Math::E) # 1.00 
Math.log10(1000) # 3.00 
Math.log10(5000) # 3.60 
Math.log10(10000) # 4.00 

Anvendelsen af logaritmer til komplicerede beregninger er en væsentlig motivation i deres oprindelige udvikling og i dette tilfælde antagelse af nye rater.

The Power of

Math.pow, ^ eller ** betyder alle at opløfte noget i potents. POW beregner den naturlige logaritme af x ved hjælp af polynomiel interpolation, så ganger med p, beregner e til denne opløftning. Den skal også sikre at begge operander er præcise heltal repræsenteret i double samt at resultatet er et heltal der kan repræsenteres i en dobbelt. I Java bør man undgå denne metoder hvis det lader sig gøre. Kildekoden til Math.pow er kompleks og i floating point. Som alle floating point metoder er resultaterne kun omtrentlige. Hvis du ønsker mere præcise resultater kan man bruge BigInteger eller BigDecimal. Ellers brug Knuth side 462 i The Art of Computer Programming bind 2 Seminumerical Algorithms. Den metode, der går tilbage til 200 f.Kr. i Indien.

Hvorfor er det vigtigt naturlige tal? Forstil dig en konto med pålydende 1,00 kr. og 100% i rente om året. Hvis renten konteres en gang om året bliver værdien fordoblet til 2,00 kroner. Meget flot. Men hvis renten konteres to gange om året bliver regnestykket til kr. 2.25. Hvis samme rente beregnes kvartalsvis ser regnestykke sådan ud: 1.00 × 1.25^4 = kr. 2.44. Månedlige afkast: 1.00 × 1,083^12 = kr. 2,61.

Her er simpel konto konteringsberegning i ruby hvori der bruges POW

1.00 * (1+((100.fdiv(1)) /100)) ** 1 # 2.0
1.00 * (1+((100.fdiv(2)) /100)) ** 2 # 2.25
1.00 * (1+((100.fdiv(4)) /100)) ** 4 # 2.44140625
1.00 * (1+((100.fdiv(52)) /100)) ** 52 # 2.69259695443717
1.00 * (1+((100.fdiv(400)) /100)) ** 400 # 2.71489174438123

Bernoulli bemærkede at denne sekvens har en grænse for flere og mindre konterings intervaller. Læg mærke til at forskel på kontering mellem uge og dag er minimal. Beregning siger at konteringsintervaller med rente på 1/n pr interval er lig store n, altså e. Dvs at kontinuerlig kontering vil aldrig kunne komme over e = 2,71828182845905. Meget interessant hvis man selv kan styre sin bank forretning.

Nu til beregningen af formlen. Tallet jeg skal opnå er “929117.930471227”. Og formlen ser sådan ud:

P  * (1- (1 / (1+R^Y))) / LN (1+R)

Hvis P er kr. 100000, Y er 10 år og R er li 1.5 procent i rente skal udfald være kr. 929118.- afrundet.

Ruby som programmeringssprog er et godt udgangspunkt idet sproget har en syntakst som ligger tæt op af de rigtige formler. Bemærk at opløftning i potents sker ved at **.

P * (1 - (1 / ((1 + R) ** Y))) / Math.log(1 + R)

Java er lidt mere omstændelig at arbejde med men det går sålænge man holder sig til double notationen.

P * (1 - (1 / (Math.pow((1 + R), Y)))) / Math.log(1 + R);

Java med BigDecimal er næsten ulæselig og ser slet ikke ud som base formlen mere.

new BigDecimal(P).multiply(ONE.subtract(ONE.divide((ONE.add(new BigDecimal(0.015))).pow(10)))).divide(new BigDecimal(Math.log(ONE.add(R))));

Javascript har en lidt anderledes med parenteser og det kan let blive kompliceret. Iørigt lod jeg mærke til at forskellige browser implementation beregnede forskellige hvis der fantes for mange indlejrede parenteser.

var P = 1 - (1 / Math.pow((1 + R), Y));
var balance = P / Math.log((1 + R));
var d = balance * amount;

Oversigt over de resultater fra eksekvering af formlen på de forskellige platforme.

Så mens sneen har lagt sig udenfor og temperaturen er langt under frysepunktet kan jeg samle mine tanker. Alle skriver og skriger om at man skal bruge BigDecimal, og tilsvarende ting i andre programmeringssprog, til ting som skal være præcise og især indenfor finans og økonomi.

Det er den største gang vrøvl!

IEEE 754 floating-point-tal som double og float er perfekte til næsten alle former for beregninger og formler. De tilbyder en vilkårlig præcision og god kompromis mellem hastighed og præcision. Alle beregninger med naturlige tal bruger flydende tal ligesom økonomiske prognoser basseret på trigonometriske funktioner og logaritmer. Det eneste sted jeg kan komme på hvor man gad at bruge BigDecimal er ved møntenhed. I de tilfælde har man nemlig brug for at kunne afrunde med en bestemt afrundingstrategi. Når man operere med naturlige tal går det faktisk ud over præcisionen ved de ikke trivielle beregninger ln, potents, cosinus. På en computer finders der ikke en nøjagtigt metode til at beregne flydende tal. At folk anbefaler at bruge bigdecimal til at udregne kvadratroden vha. Newtons metode der udspringer af konvergerende sekvens af tilnærmelser(konto), knuser min tro på den menneskelige intelligens. Jeg foretrækker at bruge IEEE dobbelt numre, velvidende at jeg kan stole på kun så mange cifre i det endelige resultat, end lever med en illusion af vilkårlig præcision, der bare ikke findes.

Du kan skabe en illusion af vilkårlig præcision ved at skære decimalerne af for at løse gåden om 0.1 + 0.1 + 0.1 = 0.3! Når jeg laver prognoser over mit aktieafkast vil jeg have alle decimaler med. Tak.

By Frank Vilhelmsen - 3 tags: java ruby javascript - 2 comments on Unit of Least Precision - Add comment

Papageorge February 10, 2010 09:32 6 months ago

Very interesting & well written Frankie!

Lars Tackmann February 10, 2010 09:44 6 months ago

You actually don’t have much choice in the matter. According to Dainsh data law its simply illegal to use iee754 arithmetic for transactions involving money. Its rather interesting that almost all modern language still does not use arbitrary precision arithmetic (http://gmplib.org/), one important exception is Haskell that actually have real reals (in the mathematical sense). I find it rather sad that even the most bleeding edge programming languages like F#, Scala or C# still messes up with something simple as “1 – 0.9”.