AFRONDEN Pieter Suurmond, 10 november 2004. ======== Een document over de vernietiging van informatie: het weggooien van bits. Vaak zul je moeten afronden. Het kan een tussentijdse afronding zijn, maar het beste rondt je natuurlijk alleen af op het allerlaatste moment. 1: DRIJVENDE KOMMA ================== Laten we eerst kijken naar het makkelijkere geval: het afronden van een getal met drijvende komma naar een geheel getal. In het allersimpelste geval knip je (na eventuele schaling) alles achter de komma eraf. In de programmeertaal C kan dat met een typecast: /* 1.1: FP->INT, TRUNCATE */ double f = ...; /* Convert a floating point number to an integer */ long i; /* by simply truncating the fractional part. */ /* Round down if f > 0.0. */ i = (long)f; /* But up if f < 0.0 (C, C++, Java, JavaScript). */ De fout kan hierbij oplopen tot bijna 1. In de taal C zijn er de standaard- bibliotheekfuncties floor(), ceil(), trunc(), remainder() enzovoorts waarmee ook het een en ander mogelijk is (zie ). In C++ is een template voor typecasts misschien nog fraaier: i = static_cast(f); Door naar het dichtstbijliggende gehele getal af te ronden wordt de maximale fout beperkt tot een half: /* 1.2: FP->INT, ROUND TO NEAREST */ float f = ...; short i; if (f < 0.0) /* -0.5 --> -1 */ i = (short)(f - 0.5); /* -0.1 --> 0 */ else /* 0.1 --> 0 */ i = (short)(f + 0.5); /* 0.5 --> 1 */ Positieve en negatieve getallen moeten we (dus) apart beschouwen. Problemen kunnen optreden door het optellen of aftrekken van een half (overflow of underflow). Op een huis-tuin-en-keuken-CPU moet je daartegen speciale voor- zieningen treffen, maar op een DSP-chip zoals de 5600x kan automatisch worden gelimiteerd naar maximale (of minimale) waarde. Dat wat betreft het omzetten van floats en doubles naar ints, shorts, longs, etc. 2: GEHELE GETALLEN ================== Met gehele getallen ligt het iets ingewikkelder. Studenten moeten vertrouwd raken met de twee-complement voorstelling en met de vaste komma notatie. In C++ is het kleinste datatype 1 byte groot, toch gebruiken we in de volgende voorbeelden een 'signed nibble': 4-bit getallen met teken worden afgerond naar 2-bit getallen (met teken). /* 2.1: TRUNCATE */ signed char n = 0xFF; /* -0.25 (sign extended upper nibble). */ n >>= 2; /* Arithmetic shift right 2 bits (/4). */ /* 4 bit to 2 bit using 2-complement (fixed-point) representation: 0: 00.00 --> 00 (0) 0.25: 00.01 --> 00 (0) 0.5: 00.10 --> 00 (0) 0.75: 00.11 --> 00 (0) The results are 'fair' in the 1: 01.00 --> 01 (1) the sense that the 16 different 1.25: 01.01 --> 01 (1) input patterns neatly map to 4 1.5: 01.10 --> 01 (1) groups of 4 output patterns. 1.75: 01.11 --> 01 (1) -2: 10.00 --> 10 (-2) (Not +2, we use a signed nibble!) -1.75: 10.01 --> 10 (-2) -1.5: 10.10 --> 10 (-2) -1.25: 10.11 --> 10 (-2) The maximum error reaches 0.75! -1: 11.00 --> 11 (-1) -0.75: 11.01 --> 11 (-1) -0.5: 11.10 --> 11 (-1) -0.25: 11.11 --> 11 (-1) */ Bovenstaande omzetting is eerlijk in de zin dat de 16 verschillende invoer- patronen netjes (in groepjes van 4) naar 4 verschillende uitvoerpatronen 'mappen'. De fout kan echter oplopen to 0.75. Om de fout te verkeinen kunnen we afronden naar het dichtstbijliggende getal: /* 2.2: ROUND TO NEAREST */ signed char n = ...; /* Don't forget to sign extend upper nibble. */ if ((n >= 0) || /* Always add 0.5 except for negative values */ ((n & 3) != 2)) /* where the fractional part is exactly 0.5. */ n += 2; /* We have a spare nibble against overflow. */ n >>= 2; /* Arithmetic shift right 2 bits. */ if (n > 1) n = 1; /* 1.5 and 1.75 need some extra care: limit. */ /* 4 bit to 2 bit, Pieter's convergent rounding: 0: 00.00 --> 00 (0) 0.25: 00.01 --> 00 (0) 0.5: 00.10 --> 00 (1) Up for positive halves. 0.75: 00.11 --> 01 (1) 1: 01.00 --> 01 (1) 1.25: 01.01 --> 01 (1) 1.5: 01.10 --> 01 (1) Up for positive: +2=overflow! limit to +1. 1.75: 01.11 --> 01 (1) +2=overflow! limit to +1. -2: 10.00 --> 10 (-2) -1.75: 10.01 --> 10 (-2) -1.5: 10.10 --> 10 (-2) Down for negative halves. -1.25: 10.11 --> 11 (-1) -1: 11.00 --> 11 (-1) -0.75: 11.01 --> 11 (-1) -0.5: 11.10 --> 11 (-1) Down for negative halves. -0.25: 11.11 --> 00 (0) */ We zien 2 vervelende overflow gevallen en een niet zo eerlijke verdeling van 16 naar 4. Het kan op nog andere manier, laten we eens kijken hoe een 56000 DSP het zou doen: /* 2.3: CONVERGENT ROUNDING AS THE 5600X (WOULD DO IT IF IT HAD NIBBLES) According to the Motorola DSP56000/56001 user's manual (figure 4-9), even halves are rounded down, whereas odd halves are rounded up. 0: 00.00 --> 00 (0) 0.25: 00.01 --> 00 (0) 0.5: 00.10 --> 00 (0) Down for even int-parts. 0.75: 00.11 --> 01 (1) 1: 01.00 --> 01 (1) 1.25: 01.01 --> 01 (1) 1.5: 01.10 --> 01 (1) Up for odd int-parts. +2=overflow! (auto)limit to +1. 1.75: 01.11 --> 01 (1) +2=overflow! (auto)limit to +1. -2: 10.00 --> 10 (-2) -1.75: 10.01 --> 10 (-2) -1.5: 10.10 --> 10 (-2) Down for even int-parts. -1.25: 10.11 --> 11 (-1) -1: 11.00 --> 11 (-1) -0.75: 11.01 --> 11 (-1) -0.5: 11.10 --> 00 (0) Up for odd int-parts -0.25: 11.11 --> 00 (0) */ De gevallen waarbij het fractionele deel precies een half is zijn speciaal. Bijvoorbeeld -3.5, dat ligt even dicht bij -3 als bij -4, en wat is nu wijs? In tabel 2.2 bepaalt het MSBit (het teken-bit) wat er gebeurt met precieze halven, en in tabel 2.3 bepaalt het LSBit (van het gehele deel) wat er gebeurt in deze speciale gevallen. Voor de gein kunnen we nog een laatste variant uitvoerig bestuderen: zoals de 56000, maar dan andersom. Veel beter wordt de verdeling (van 16 naar 4) echter niet. Het enige voordeel is misschien dat we 1 overflow->limit geval minder hebben. /* 2.4: ANTI-MOTOROLA CONVERGENT ROUNDING Opposite to Motorola's DSP56000 would be: even halves up, odd halves down. 0: 00.00 --> 00 (0) 0.25: 00.01 --> 00 (0) 0.5: 00.10 --> 01 (1) Up for even int-parts. 0.75: 00.11 --> 01 (1) 1: 01.00 --> 01 (1) 1.25: 01.01 --> 01 (1) 1.5: 01.10 --> 01 (1) Down for odd int-parts. 1.75: 01.11 --> 01 (1) +2=overflow! limit to +1. -2: 10.00 --> 10 (-2) -1.75: 10.01 --> 10 (-2) -1.5: 10.10 --> 11 (-1) Up for even int-parts. -1.25: 10.11 --> 11 (-1) -1: 11.00 --> 11 (-1) -0.75: 11.01 --> 11 (-1) -0.5: 11.10 --> 11 (-1) Down for odd int-parts -0.25: 11.11 --> 00 (0) */ Hoe we het ook doen (in de twee-complement notatie) blijft de maximale fout die op kan treden toch steeds 0.75. Bij meer dan 4 bits invoer komt 't effect natuurlijk (relatief) minder vaak voor, maar toch... ------------------------------------------------------------------------------ TENTAMENVRAGEN: 1) Hoeveel verschillende 4 naar 2 bit mappings zijn er in totaal? Hierboven zijn er slechts 4 uitgewerkt: tabel 2.1 t/m 2.4. Tel ook echt alle onzinnige mappings mee, waarbij bijvoorbeeld alles naar 0 mapt, naar 1, etc. 2) Geef C, C++ of Java code voor geval 2.3: 4 naar 2 bits afronding net zoals de DSP 5600x van Motorola. 3) Welke 2 regels geeft het volgende programma? unsigned char u = 0x81; // Uit het hoofd ja, zonder compu. signed char s = u; printf("%d\n", (int)u); printf("%d\n", (int)s); 4) Wanneer en waar heeft het zin om 'dither' te gebruiken? En hoe? ------------------------------------------------------------------------------