Exakt division med flyttal

Det här är mer matematik än systemutveckling, därav placeringen.

I ett IEEE-flyttal lagras signifikanden i ett (fast) antal siffror och exponenten i resten. Standarden garanterar att avrundning sker mot ett av de två närmsta tal som kan lagras i flyttalet (vissa datorer avrundar nedåt, vissa mot 0 etc). Den garanterar också att avrundningsmetoden som används är densamma för alla operationer. Exakt addition och subtraktion borde inte vara några problem så länge man håller sig under gränsen för signifikandens precision (antalet siffror), minus en siffra antar jag, för om addition avrundar uppåt borde väl subtraktion avrunda nedåt eller vice versa?

Det hade varit trevligt om rationella tal skulle gå att jobba med och lagra i flyttal och förbli exakta så länge man håller antalet signifikanta siffor i täljaren plus antalet i nämnaren, under det antal som går att lagra i signifikanden. 1/n kan ju inte ge en längre period på decimalutvecklingen än n. Men fungerar det så? Kan man multiplicera och dividera fritt så länge något av delresultaten inte får fler signifikanta siffror i täljare + nämnare än vad som går att lagra, eller kommer felen att ackumuleras?

Eller ackumuleras bara fel när man blandar addition/subtraktion med multiplikation/division?

Tyvärr räknar datorer inte exakt. Heltal är inga problem om de är inom gränserna, men för bråk blir det nästan alltid fel. Det är bara bråk som är 1/2, 1/4 osv som blir exakta. Samma problem med decimala - ex 1/3 går ej att uttrycka exakt.
För ca 20 år sedan upptäckte en matematiker att Intels nya Pentium processor räknade fel.
Detta sysslar man med i numerisk analys. Hur mycket som ingår i programmeringskurser vet jag inte, men det är intressant och viktigt.

Det var bara under väldigt speciella förhållanden som Pentium räknade lite fel, det fixades snabbt.
Många andra processorer gör också fel och gör skumma saker.

Får inte alla som lär sig om flyttal lära sig om de problem med noggranhet som sker?
Fel sker men om det ens behöver tas hänsyn till varierar.

Har dålig koll på matematiken, men så länge det handlar om tal som kan uttryckas som en kvot mellan två heltal, alltså rationella tal, så bör det väl gå att spara det exakta värdet och använda det vid beräkningar samtidigt som man vid behov låter det presenteras som ett vanligt flyttal. Fast det kräver väl att man fixar en egen datatyp. Borde även vara möjligt att spara tal som ett godtyckligt långt, begränsat av din dators enorma minne, matematiskt uttryck som har en decimal presentation. Ex: omkretsen av ett hjul med diametern 5 är (sparas som) "5 * pi", vilket gör att man slipper problem om man senare av någon anledning ska dividera med pi. Vid utskrift av värdet utvärderas det till något lämpligt, ex 15,7.

Med en sådan representation skulle bråktalet behöva förkortas, t.ex. så långt som möjligt efter varje operation eller litegrann när operationen skulle flöda över. Det skulle inte gå att låta en multiplikation bara gångra täljaren och en division bara gångra nämnaren, då fylls de två heltalen efter några loopar. Faktoriseringen vid förkortningen tar tid men man kunde bygga upp talet som en lista på primfaktorer från början, istället för två heltal. Processorer borde ha en sådan rationell-datatyp internt, och mänskligheten borde börja skriva tal så för att slippa den initiala faktoriseringen vid input. Addition/subtraktion vore inga problem eftersom nämnarna redan är faktoriserade.


Den ultimata datatypen och en processor som kategoriserar och förenklar uttryck m.h.a alla (hittills) kända matematiska regler, vore coolt. Konstanterna pi och e, och de trigonometriska funktionerna, kan ju också uttryckas som summor av bråk. Visserligen oändliga. Ett problem vore som sagt loopning där uttrycket inte kan förenklas varje gång utan byggs upp i all oändlighet. Men man skulle kunna tala om för processorn varje gång man startar en ny "omgång" operationer på talet.

Jodå, en sådan klass har jag skrivit som överlagrar operatorerna + - * och / plus kanske någon till, och mycket riktigt också en faktoriseringsalgoritm.
En sådan klass är inte svårt att skriva, den är bara "rakt på".

Det var dock länge sedan jag gjorde den, och jag tror att den ska ha postats till Dr Dobbs elr C++ Users Journal men koden kom inte med i publikation, utan det fanns en liten notis om den. Möjligen bara i något av deras forum. Den kunde iallafall expandera utrymmet som täljare och nämnare tog upp.

Jag använde den klassen för att räkna vissa matrisoperationer, tex inversion och multiplikation och representera talen korrekt.

Matematiska Institutionen i Sthlm liksom KTH tyckte den var lite kul att kämpa med

Men jag tror att jag hade problem med att skriva ut dessa tal med dåtidens skrivare minns dock ej varför.

I teorin så finns det faktiskt lite tid att spara med en sådan rationell klass, eftersom CPUn då hanterar heltal och inte behöver hantera flyttal och expandera decimalutvecklingen i varje steg. Och heltalshantering är ju snabbare.

Som ett numeriskt experiment så är den teoretiskt intressant eftersom den helt och hållet undviker felpropagering (felackumulering) i operationerna och i långa räknesekvenser om bara + - * och / ingår

Dock så kan ju inte sådana serieutvecklingar såsom sinus cosinus osv utvecklas som exakta rationella tal, utom bara sinus 90° = 1 och sinus 30° = 1/2, Eftersom man alltid erhåller en restterm och den är "oändligt lång" (*).
Fast klassens användbarhet som ett generellt verktyg det vet jag inte om det är så lyckosamt. NASA och CERN hörde i alla fall inte av sig - De klarar sig tydligen bra med flyttal

För att kunna hålla en godtyckligt stor täljare och nämnare i minnet får man sikta in sig på någon klass såsom BIGNUM eller liknande - Säkert hade jag själv gjort något eget ihopkok, variant av BIGNUM.
Annars om 128 bit räcker så finns ju __int128 i flera kompilatorers datatypset.

Jag provade att göra om koden till FORTRAN elr förmodligen C eftersom C++ inte fanns på stordatorer då, men koden kunde tydligen prestera ojämnt tidsmässigt på stora matriser. Vilket ju egentligen inte är så särskilt förvånande

(*) Minns dock inte beviset om resttermen mer än att man beräknar dess maximala värde.

Givetvis måste man förkorta bråket ibland. En fördel är att när du räknar ut några miljarder nya decimaler på pi så behöver du bara ändra på ett ställe i systemet, sedan anpassas alla tal som använder pi.

Det finns ju miljöer som kan hantera pi som en symbol och räkna med den på ett symboliskt sätt, och att man kan konvertera den till decimaltal när det behövs.

Frågan om hanteringen av decimaltal är intressant eftersom alla vanliga datorer änvänder IEEE 754 standarden där siffrorna är lagrade som bits på ett särskilt sätt, dock har ju somliga miniräknare istället använt "äkta decimaltal" tex för att ha perfekt kontroll på avrundning. Och att man då använt BCD som kodningsmetod och i regel ett fixt antal decimaler.


En klass som hanterar rationella tal har vissa likheter som en klass som kan hantera komplexa tal.

Serieutvecklingarna sköts ju bättre av FPU-enheten som är snabbare och bättre på det än att kalkylera med bråken. Om man nu ska skriva en rationell klass så gör man klokt i att begränsa "djupet" på beräkningarna att de inte "skenar iväg", dvs typ en "overflow exception" eller "infinite recursion exception", Alternativt är ju att sätta specifika flaggor som kan kollas vid slutet av exekveringen.

Flera math libs har ju diverse knep för att detektera division med noll, "oändlighet" osv

Intressant nog så finns det ju genvägar kring just multiplikation och division och det är ju att konvertera till logaritmer innan - vilket kan avsevärt snabba upp en hel radda med sådana operationer efter varandra, eftersom de räknas som additioner och subtraktioner. Dock så måste man ju hålla reda på tecknena +/- själv i så fall.

Just den här frågan om rationella tal som beräkningsmetod har ju tagits upp i bla datorgrafiken där man torde kunna ha en viss nytta av sådan