Onderwerpen Inleiding Algemeen – 12 – Getallen
I Getallen I Representaties I Rekenen I Problemen
Piet van Oostrum 12 dec 2001
INL/Alg-12
1
JJ J I II J
•
X
Getallen
INL/Alg-12
1
JJ J I II J
•
X
Soorten getallen
I Wat is een getal?
I Natuurlijke getallen: 0, 1, 2, . . .
I Experiment: met Python 6.3 ⇒ 6.2999999999999998 0.1*3 ⇒ 0.30000000000000004
I Gehele getallen: . . . , -2, -1, 0, 1, 2, . . . I Rationale getallen (breuken): m/n, m, n geheel Worden in computers niet vaak gebruikt: m, n worden snel erg groot
I Java: net iets anders
I Re¨ele getallen: Hiervan zijn er heel veel: ook niet-berekenbare In computers beperken we ons tot een kleine deelverzameling hiervan Daarom meestal benaderingen
I Wat is hier aan de hand? I Een getal is een abstract wiskundig begrip I Een abstractie van het begrip ‘hoeveelheid’
I Complexe getallen: x + y i, (x, y re¨eel) worden veel in de natuurkunde en soortgelijke takken van wetenschap gebruikt
I Wat wij zien zijn representaties van getallen: 123 is de decimale representatie van een getal CXXIII is de romeinse representatie van hetzelfde getal
I Quaternionen: generalisatie van complexe: x + y i + z j + u k, I Octavionen (octonionen) met 8 re¨ele componenten
INL/Alg-12
2
JJ J I II J
•
X
Natuurlijke getallen
INL/Alg-12
3
JJ J I II J
X
Voorbeelden
I We representeren natuurlijke getallen meestal met een positioneel systeem:
I Als het grondtal niet uit de context duidelijk is schrijven we ddddddg
I We kiezen een grondtal g (vaak g = 10)
I decimaal: algemeen bekend
I Elk cijfer heeft een g maal zo grote waarde als hetzelfde cijfer een plaats rechts ervan
I binair (g = 2) wordt meestal in computers gebruikt 10112 = 1110 Meestal n = 32, soms n = 16, 64
I Bijv. 237 = 2*100+3*10+7*1 (g = 10)
I octaal (g = 8) makkelijk vanuit binair: neem telkens 3 bits samen
I De waarde van dn−1dn−2 . . . d1d0 is n−1 X
I hexadecimaal (g = 16) ook makkelijk vanuit binair: neem telkens 4 bits samen een byte = 2 hexadecimale cijfers voor de cijfers 10 t/m 15 nemen we A-F
di · g i
i=0
I Voor n cijfers zijn de mogelijke waarden 0 t/m g n − 1
INL/Alg-12
•
4
6410 = 1008 6416 = 10010 JJ J I II J
•
X
INL/Alg-12
slides12.pdf — December 14, 2001 — 1
5
JJ J I II J
•
X
Optellen van binaire getallen
Optelschakeling
I Optellen gaat net als op de basisschool: van rechts naar links de cijfers optellen en evt. ‘onthouden en doorgeven’:
xi
yi
I voorbeeld: 10112 + 1012 1001 101 1110 1 onthouden I Optellingstabel: a b a+b 0 0 00 0 1 01 1 0 01 1 1 10
XOR
AND
XOR
AND
ci OR
Formules: rechtse cijfer = aXORb = (a ∨ b ∧ ¬(a ∧ b)) = (a ∧ ¬b) ∨ (¬a ∧ b) linkse cijfers = a ∧ b; dit cijfer moet links erbij geteld worden (carry),
I Bij alle behalve de meest rechtse moeten 3 bits opgeteld worden INL/Alg-12
6
JJ J I II J
•
X
Negatieve getallen – 1
I Als we ook negatieve getallen willen representeren moeten we ca. de helft van onze representaties daarvoor reserveren I Probleem: 0 is niet positief en niet negatief (+0 = −0), dus ´e´en van de twee heeft een getal teveel, of we krijgen twee representaties voor 0 (zowel +0 als −0) I Representatie: teken + absolute waarde reserveer ´e´en bit voor het teken (bijv. 0 = +, 1 = −) de rest van de bits voor de absolute waarde van het getal Probleem: electronische schakelingen voor optellen en aftrekken worden ingewikkeld
8
JJ J I II J
•
X
Overflow
JJ J I II J
•
X
I Representatie: 1-complement een negatief getal wordt voorgesteld door alle bits van het positieve getal omgekeerd vb: 1110 = 10112 ⇒ −1110 = . . . 111101002 Probleem 1: Er zijn twee representaties voor 0: +0 en −0 Probleem 2: Bij het optellen moet de carry van de linkse bits rechts er weer bijgeteld worden (end-around carry ) Dit kan problemen met de timing geven. I Representatie: 2-complement Dit is momenteel het meest gebruikte systeem de representatie van een negatief getal krijg je door 1 op te tellen bij de 1-complement representatie dus −1 = . . . 1111112, −2 = . . . 1111102, etc. Er is nu slechts ´e´en 0 Optellen gaat precies zoals voor positieve getallen! Probleem: er is ´e´en negatief getal meer dan positieve! −2n Dit getal heeft geen absolute waarde INL/Alg-12
9
JJ J I II J
•
X
•
X
Conversie van representatie naar getal
I Als een resultaat van een operatie (optellen, aftrekken, vermenigvuldigen) niet meer past in de hoeveelheid gereserveerd bits noemen we dit overflow I Bij optellen ontdek je dit doordat je twee getallen met hetzelfde teken optelt en het resultaat heeft het andere teken I Als je een positief en een negatief getal optelt is er nooit overflow I Bij overflow is het resultaat 2n te groot of te klein
INL/Alg-12
7
Negatieve getallen – 2
I We beperken ons voorlopig tot binaire representaties
INL/Alg-12
INL/Alg-12
10
JJ J I II J
•
X
static int tonumber (String in, int g) { int result = 0; int aantal = in.length(); for (int i = 0; i < aantal; i++) { int digit; char c = in.charAt(i); if (c >= ’A’ && c <=’Z’) digit = c - ’A’ +10; else if (c >= ’a’ && c <=’z’) digit = c - ’a’ +10; else digit = c - ’0’; result = result*g+digit; } return result; } INL/Alg-12
slides12.pdf — December 14, 2001 — 2
11
JJ J I II J
Conversie naar representatie
Resultaten
static String tostring(int in, int g) { String result = ""; boolean neg = false; if (in<0) { neg = true; in = -in; } do {int digit = in % g; in = in/g; if (digit < 10) result = (char)(digit+’0’) + result; else result = (char)(digit-10+’A’) + result; } while (in != 0); if (neg) result = ’-’ + result; return result; } INL/Alg-12
12
JJ J I II J
System.out.println System.out.println System.out.println System.out.println System.out.println
(tonumber("34567", 10)); (tonumber("64", 16)); (tostring(100, 16)); (tostring(-123456, 10)); (tostring(0, 23));
geeft als resultaat: 34567 100 64 -123456 0
•
X
Decimale representaties – 1
INL/Alg-12
13
JJ J I II J
•
X
Decimale representaties – 2
I Voor sommige toepassingen (zakelijke software) is een decimale representatie soms efficienter: Er wordt vaak weinig gerekend (btw uitrekenen e.d) Wel veel in- en uitvoer De conversies kosten dan relatief veel tijd
I ASCII getal = 259 2 0 0 1 1 0 0 1 0 5 0 0 1 1 0 1 0 1 9 0 0 1 1 1 0 0 1
I In dat geval wordt vaak een decimale representatie in de computer gebruikt
I alleen 2 0 5 0 9 0
I Omdat de decimale cijfers toch weer binair opgeslagen moeten worden spreken we dan van Binary-Coded Decimal (BCD) I Er zijn dan nog verschillende keuzes mogelijk: Sla gewoon de ASCII tekens van de cijfers op Sla alleen de getalswaarde van de cijfers op, ´e´en per byte Stop twee cijfers in ´e´en byte (packed decimal)
cijfers 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1
I packed decimal 02 0 0 0 0 59 0 1 0 1
0 0 1 0 1 0 0 1
De halve bytes worden ook wel nibbles genoemd. De eerste nibble wordt vaak gebruikt om het teken aan te geven. Voor + en − worden dan speciale bitpatronen gebruikt. INL/Alg-12
14
JJ J I II J
•
X
Scaled Numbers – 1
INL/Alg-12
15
JJ J I II J
•
X
Scaled Numbers – 2
I Voor niet-gehele getallen zijn er verschillende mogelijkheden I Net als bij decimale getallen kunnen we binair getallen met een punt gebruiken: 3.2510 = 11.012 I In de computer slaan de we de punt niet op. Neem bijv 16 bits voor het gehele deel en 16 bits voor de breuk: 0000000000000011 0100000000000000
I In plaats van de punt in het midden te zetten kunnen we die ook ergens anders zetten (denken) I Omdat we getallen representeren als ints die een vaste factor (2k ) groter zijn spreken we van scaled numbers of scaled arithmetic I We kunnen zelfs een compleet andere factor nemen (niet 2k )
I Als we dit samen in een 32-bits woord zetten hebben we eigenlijk een int die 216 maal zo groot is als het bedoelde getal.
I Voorbeeld: Als we met geldbedragen (euro’s) rekenen kunnen we een factor 100 nemen; en in feite met eurocenten rekenen.
I Optellen en aftrekken blijven hetzelfde: 216x + 216y = 216(x + y)
I Als we nauwkeurig met lengtes moeten rekenen kunnen we een factor 100000 nemen (feitelijk met 1/100 mm rekenen).
I Bij vermenigvuldigen en delen moeten we echter een factor 216 corrigeren: 216x × 216y = 216(216(x × y)) 216x/216y = (216(x/y))/216
I Probleem: Als we in een berekening zowel heel grote als heel kleine getallen nodig hebben moeten we met verschillende schaalfactoren werken
I Niet elke decimale breuk is binair weer te geven bijv. 0.110 = 0.0011001100110011 . . .2 INL/Alg-12
16
JJ J I II J
•
X
INL/Alg-12
slides12.pdf — December 14, 2001 — 3
17
JJ J I II J
•
X
Floating point
Problemen met floating point
I Voorbeeld: als het grondtal 10 is, de mantisse is 5 en de exponent is 3 dan is de waarde van het getal 5 · 103
I Als we een binaire representatie gebruiken (g = 2) Niet elk getal kan gerepresenteerd worden De meeste getallen moeten benaderd worden Bijv. 0.1 wordt benaderd door 0.10000000000000001 en 0.3 door 0.29999999999999999 3 ∗ 0.1 − 0.3 = 5.5511151231257827e − 17
I Algemeen als het grondtal g is, de mantisse m en de exponent e, dan is de waarde van het getal m · g e
I Operaties geven ook een benaderd resultaat Soms ‘verdwijnt’ een deel gewoon:
I Floating point lost dit probleem op door de schaalfactor in de representatie te coderen I Een getal wordt voorgesteld door een mantisse en een exponent (bij een bepaald grondtal).
>>> >>> >>> >>> 2.0 >>> 0.0
I Rekenen wordt nu een stuk moeilijker: Bijv bij een optelling of aftrekking moeten de exponenten eerst gelijk gemaakt worden: 5 · 103 + 7 · 105 = 5 · 103 + 700 · 103 = 705 · 103 INL/Alg-12
18
JJ J I II J
•
X
Floating point representaties
x=2.0 y=1e-20 z=x+y z z-x
INL/Alg-12
19
JJ J I II J
•
X
Normalisatie
I Tegenwoordig wordt bijna altijd de IEEE 754 representatie gebruikt
I Een getal kan verschillende floating point representaties hebben: 5 · 103 = 50 · 102 = 500 · 101 = 0.05 · 105
I Dit is een binaire representatie (g = 2)
I Welke kiezen we in de computer?
I Deze is ontworpen om zoveel mogelijk problemen met het rekenen met floating point getallen te vermijden
I In het algemeen wordt een genormaliseerde representatie genomen, waarbij er 1 cijfer voor de punt staat in de mantisse: Dus 5 · 103 in het voorbeeld
I Hiervoor hadden veel computers rariteiten (bijv. bij heel kleine getallen) I Twee vormen in gebruik: single precision (32 bit, float): 1 bit teken, 8 bits exponent, 23 bits mantisse double precision (64 bit, double): 1 bit teken, 11 bits exponent, 52 bits mantisse Daarnaast nog ‘extended’ met extra mantissebits
I Een andere goede keus zou zijn om altijd direct achter de punt te beginnen met een cijfer 6= 0 (behalve bij 0 zelf): Dus 0.5 · 104
I De meeste computers nu hebben dit ingebouwd in de CPU INL/Alg-12
20
JJ J I II J
•
X
Binaire normalisatie
21
JJ J I II J
•
X
Binaire representatie
I In een binaire genormaliseerde representatie is het cijfer voor de punt altijd 1 (behalve bij het getal 0). I Je kunt dan ruimte besparen door deze niet op te slaan maar erbij te denken
I Om negatieve exponenten ook goede ruimte te geven wordt de exponent meestal omhooggeschoven zodat de negatieve exponenten een lage representatie hebben en positieve exponenten een hoge I Dit wordt de bias genoemd
I Neem 0.37510 0.37510 = 0.2510 + 0.12510 = 0.01002 + 0.00102 = 0.01102
I Als we 3 bits voor de exponent zouden gebruiken kunnen we de exponent bijv 4 opschuiven:
−2
I Genormaliseerd wordt dit 1.1000 · 2
I exponent −2 wordt dan opgeslagen als −2 + 4 = 2.
I De 1 voor de punt slaan we niet op
I Als we ook nog een bit voor het teken ervoor zetten (0 = +, 1 = −) wordt ons getal: 0 0 1 0 1 0 0 0 teken exp mant
I We slaan dus op: (als we 4 bits voor de mantisse gebruiken) mantisse = 1000 en exponent = −2
INL/Alg-12
INL/Alg-12
22
JJ J I II J
•
X
INL/Alg-12
slides12.pdf — December 14, 2001 — 4
23
JJ J I II J
•
X
Binaire representatie
IEEE representatie
I Let op: het getal 0 kan op deze wijze niet weergegeven worden I We zouden ervoor kunnen kiezen om de representatie met alleen 0 bits als het getal 0 te interpreteren (in plaats van als 1 · 2−4 = 1/16 = 0.0625)
I Single precision: teken: 1 bit, exponent: 8 bits (bias 127), mantisse 23 bits I Double precision: teken: 1 bit, exponent: 11 bits (bias 1023), mantisse 52 bits I exponenten met allen nullen of alleen enen (hoogste en laagste waarde) worden voor speciale doelen gebruikt (bijv. oneindig) I 0 wordt voorgesteld door allemaal nullen I Getallen met een zeer kleine absolute waarde worden niet genormaliseerd (anders zouden ze niet passen): gedenormaliseerde getallen
INL/Alg-12
24
JJ J I II J
•
X
Floating Point Operaties
INL/Alg-12
25
JJ J I II J
•
X
Afronden
I Bij operaties op floating point getallen (optellen, vermenigvuldigen etc.) is het vaak niet mogelijk om het resultaat exact weer te geven I In dat geval moet een benadering gegeven worden I Meestal wordt het getal genomen dacht het dichtst bij het ‘echte’ resultaat ligt I De IEEE standaard schrijft een aantal rounding modes voor waaruit het programma kan kiezen Afronden naar het dichtstbijzijnde te representeren getal Afronden naar boven (in de richting van +∞) Afronden naar beneden (in de richting van −∞) Afronden naar 0 toe
I Afronden gaat altijd uit van het theoretische (wiskundige) resultaat I Bij het afronden naar dichtsbijzijnde is de fout maximaal de helft van de waarde van het meest rechtse cijfer in de mantisse I Bij de andere afrondingen maximaal de waarde van dit cijfer (ULP = Units in the Last Place) I Als het grondtal g is, de exponent e en de mantisse heeft n bits achter de punt dan is de ULP = g −n · g e I Voorbeeld: Als g = 10, n = 2 en we ronden naar beneden af dan worden de echte resultaten tussen 2.340000000000000 . . . en 2.349999999999999 . . . . I De fout is dan maximaal 0.01. Als er een exponent is dan moet nog de factor g e toegepast worden I Bij afronden naar dichtstbijzijnde is de maximale fout 0.005.
INL/Alg-12
26
JJ J I II J
•
X
Voorbeelden van Operaties
INL/Alg-12
27
•
X
•
X
Zonder extra cijfers
I In deze voorbeelden gaan we uit van grondtal 10, mantisse van 3 cijfers
I Kunnen we de berekening doen zonder extra cijfers?
I Bijvoorbeeld π = 3.141592 . . . wordt afgerond op 3.14
I Als we de extra cijfers gewoon weggooien:
12
JJ J I II J
−5
I Stel x = 2.15 · 10 , y = 1.25 · 10 . We willen x − y uitrekenen:
x = 2.15 ×1012 y = 0.00 ×1012 x − y = 2.15 ×1012
I We gaan eerst het theoretische resultaat uitrekenen I We moeten de exponenten gelijk maken:
I Echter zie het volgende voorbeeld: x = 10.1, y = 9.93
x = 2.15 ×1012 y = 0.0000000000000000125 ×1012 x − y = 2.1499999999999999875 ×1012
x = 1.01 ×101 y = 0.99 ×101 x − y = 0.02 ×101
Afgerond x − y = 2.15 · 1012
I Het echte resultaat is echter 0.17 i.p.v. 0.2. De fout is 30 ulps!!
I We hebben al die cijfer voor niets uitgerekend I Bovendien kan het aantal extra cijfers zeer groot worden I Dit zou exorbitant veel hardware kosten INL/Alg-12
28
JJ J I II J
•
X
INL/Alg-12
slides12.pdf — December 14, 2001 — 5
29
JJ J I II J
Guard digit
Overflow/underflow
I Met ´e´en cijfer extra kunnen we het veel beter doen:
I Overflow treedt op als de absolute waarde van het resultaat groter is dan het grootste te representeren getal
x = 1.010 ×101 y = 0.993 ×101 x − y = 0.017 ×101
I Meestal wordt dan een exception gegenereerd of de waarde ±∞ als resultaat genomen I Underflow treedt op als de waarde van het resultaat kleiner is dan het kleinste te representeren positieve getal
I Maar ook hier gaat het soms fout, bijv. bij 110 − 8.59: 2
x = 1.100 ×10 y = 0.085 ×102 x − y = 1.015 ×102
I Meestal wordt dan een exception gegenereerd of 0 als waarde genomen I Bij delen door 0 wordt wordt ±∞ als waarde opgeleverd
Het echte resultaat is 1.0141 · 102 en zou dus afgerond moeten worden op 1.014 · 102.
I behalve bij 0/0, dit lever de speciale waarde NaN (Not a Number).
I Er kan bewezen worden dat met ´e´en guard digit de fout in het antwoord nooit meer is dan de waarde van het rechtse cijfer (1 ulp) INL/Alg-12
30
JJ J I II J
•
X
Vertalen van decimale representatie
INL/Alg-12
31
JJ J I II J
•
Vertalen van decimale representatie
I We gaan nu weer uit van binaire representatie in het geheugen
I Bij al deze operaties kunnen afrondfouten optreden (i.h.b bij het berekenen van 10e)
I Extern representeren we getallen als dddd.ddddEddd evt aangevuld met tekens en het exponent gedeelte optioneel
I De totale fout kan te groot worden
I We hebben gezien dat niet iedere decimale representatie exact binair weergegeven kan worden (bijv. 0.1)
I Het is beter om de berekening te doen in een grotere precisie (extended)
I Bij het omzetten moet idealiter het dichtsbijzijnde floating point getal gekozen worden
I De waarden 10e kunnen ook met tabellen gedaan worden
I Of eerst als long integers te berekenen
I Zie literatuur op het Internet (‘How to read floating point numbers accurately’)
I Bij het omzetten moeten diverse operaties uitgevoerd worden: Mantisse omzetten Plaats van de punt verdisconteren Exponent meerekenen
INL/Alg-12
32
JJ J I II J
•
X
Vertaling naar decimale representatie
JJ J I II J
•
X
I Je kunt onverwachte resultaten krijgen vanwege de afrondfouten I Voor sommige toepassingen is het niet geschikt (bijv. rekenen met geldbedragen)
I Hier ook problemen met nauwkeurigheid I Extra probleem: hoeveel cijfers moeten we afdrukken in de mantisse? Als we te weinig cijfers afdrukken dan is het resultaat niet echt nauwkeurig Als we veel cijfers afdrukken dan krijgen we artefacten als 0.10000000000000001 Minder cijfers afdrukken lost het probleem niet op maar verdoezelt het!! Idealiter wil je die representatie afdrukken die bij (correct) inlezen weer exact hetzelfde getal oplevert Dit is vrij tricky Zie de literatuur op het Internet (‘How to print floating point numbers accurately’) JJ J I II J
33
I Voor sommige toepassingen moet je wel met floating point getallen werken
I De mantisse kan omgezet worden als een (long) integer met de punt op de juiste plaats ingevoegd
34
INL/Alg-12
Conclusie
I Eerst vermenigvuldigen met geschikte factor 10k om de punt op de juiste plaats te krijgen
INL/Alg-12
X
•
X
I Je moet geen floating point getallen gebruiken als je niet weet wat de problemen zijn. I Voor sommige toepassing zou een decimaal floating point systeem beter zijn.
INL/Alg-12
slides12.pdf — December 14, 2001 — 6
35
JJ J I II J
•
X
