Continuo vs Discreto
Su un computer, l'insieme continuo ed infinito dei numeri reali può essere, per ovvi motivi, solo approssimato con un insieme finito e discreto. Questo vuol dire che solo un sottoinsieme molto ristretto di numeri reali è esattamente rappresentabile e memorizzabile in memoria. La stragrande maggioranza dei numeri reali, invece, deve accontentarsi di una buona approssimazione. Quindi, se ad esempio definiamo una variabile e le assegniamo il valore $12.53$ non è detto che questo coincida proprio con uno dei valori esattamente rappresentabili nel sistema in uso. Nella maggior parte dei casi sarà approssimato al valore più vicino esattamente rappresentabile.
Virgola Fissa
Per iniziare, è utile guardare brevemente prima la rappresentazione dei numeri in virgola fissa. Un numero in virgola fissa $f$ di $p$ bit avrà $m$ bit (i più significativi) per la parte intera ed $n$ bit (i meno significativi) per la parte frazionaria.
Il valore decimale di $f$ si può ricavare come somma dei valori posizionali dei suoi $p$ bit. In questo caso consideriamo tutti i bit impostati a $1$ e la parte intera come un numero con segno in complemento a due:
$-1\times2^{m-1}+\dots +1\times2^0 + 1\times2^{-1} + \dots + 1\times2^{-n}$
Da notare che tutti i valori esattamente rappresentabili da una variabile a virgola fissa sono equidistanti: la differenza, in valore assoluto, tra un valore ed uno qualsiasi tra il suo successivo o precedente è quella descritta dal bit meno significativo della parte frazionaria, che ha valore $2^{-n}$ e che indica quindi lo scarto tra un valore e quello precedente o successivo.
Questo comporta il fatto che, se un numero non esattamente rappresentabile in virgola fissa è approssimato con quello rappresentabile più vicino, l'errore massimo di approssimazione si ha quando questo si trova esattamente a metà tra due numeri esattamente rappresentabili. L'errore massimo quindi sarà uguale alla metà della differenza tra due numeri successivi qualsiasi esattamente rappresentabili.
Virgola Mobile
Lo standard IEEE 754 definisce formato e rappresentazione dei numeri a virgola mobile. Si prenderà in considerazione solo il tipo a precisione singola (float, 32 bit) ma le stesse considerazioni valgono per tipi di qualunque precisione: doppia (double, 64 bit) o dimezzata (half precision, 16 bit) . Ma prima di arrivarci è utile vedere brevemente come i numeri a virgola mobile possono essere definiti in notazione scientifica. Proprio come un numero decimale $d$ si può definire nella sua notazione scientifica come
$d = \pm(i+m)\times10^e$
con $1 \le i \le 9$ parte intera di $d$, $m$ parte frazionaria ed $e$ esponente, allo stesso modo un numero in virgola mobile $f$ può essere scritto in notazione scientifica come
\begin{equation}\label{eq:1}f = (-1)^s(1 + m)\times 2^e\end{equation}
con $m$ detta mantissa, che indica la parte frazionaria di $f$, e con $s$ ed $e$ esponenti. Aver visto come funzionano i numeri in virgola fissa è stato utile in quando la mantissa funziona praticamente come un numero a virgola fissa di $p = m + n$ bit con $m=1$ uguale all' $1$ del fattore $(1+m)$ di \eqref{eq:1} che indica quindi la parte intera di $f$ (cosa che ha anche una logica dato che, in maniera simile ai numeri decimali, la parte intera $i$ di un numero binario scritto in notazione scientifica deve essere $1 \le i \le 1$, e cioè $i = 1$). Ma questo $1$, che occuperebbe il bit più significativo della mantissa è implicito e mai memorizzato realmente in esso. Solo gli $n$ bit della parte frazionaria occupano tutti i $p$ bit della mantissa, guadagnando di fatto un bit di precisione in più per la parte frazionaria ($n = p$).
Prendendo, come detto, in esame il tipo float, i 32 bit che lo compongono sono divisi in 23 bit, i meno significativi, di mantissa, i successivi 8 bit sono relativi all'esponente $e$, mentre l'ultimo è riservato ad $s$, esponente di $(-1)$ e che quindi indica il segno di $f$.
$S$, $E$ ed $M$ stanno ad indicare le rappresentazioni intere senza segno di $s$, $e$ ed $m$, rispettivamente. E' utile ora calcolare l'intervallo di valori validi per mantissa $m$ ed esponente $e$.
Partendo prima da $m$, guardando \eqref{eq:1} si nota che deve essere $0\le m < 1$ dato che, se $m \ge 1$, conterrebbe non solo la parte frazionaria ma anche una o più unità che andrebbero a sommarsi alla parte intera di $f$ (cosa impossibile dato che si è stabilito, anche se implicitamente, $i = 1$). $M$, la sua rappresentazione intera senza segno, è un numero di $23$ bit ($0\le M \le 2^{23}-1)$ con $2^{23}$ possibili valori. Quindi normalizzando $M$ si ha
\begin{equation}\label{eq:2}m = \frac{M}{2^{23}}\end{equation}
Se $M = 0$ allora $m = 0$. Se invece $M = 2^{23}-1,$ allora $m = 1 - \frac{1}{2^{23}}$. Quindi si può definire, almeno per il tipo float
\begin{equation}\label{eq:3}0\le m \le(1 - \frac{1}{2^{23}})\end{equation}
e la cosa ha anche un senso dato che, come già detto per i numeri a virgola fissa, $2^{-23}$ è la più piccola quantità rappresentabile da una mantissa di $23$ bit e quindi la parte frazionaria non può avvicinarsi ad $1$ per più di questa quantità.
Per quanto riguarda l'esponente $e$, questo è definito come $e = E - 127$. Viene cioè scostato di un certo valore rispetto alla sua rappresentazione intera $E$ ($127$ per float, $1023$ per double). Quindi, per il tipo float, dato che all'esponente sono riservati $8$ bit ($0\le E \le 255$) si ha
$-127\le e \le 128$
L'intervallo di $e$ sembra quindi essere un valore intero compreso tra $[-127, 128]$ ma, come si vedrà a breve, i valori all'estremo $-127$ e $128$ sono riservati ad usi particolari.
La cosa importante da notare per tutti i tipi a virgola mobile così definiti è che la mantissa ha sempre un numero fisso di valori esattamente rappresentabili ($2^{n}$ per mantisse ad $n$ bit) qualunque sia l'esponente $e$. Una volta fissato $e$ però, l'insieme di numeri esattamente rappresentabili con quel dato esponente viene raddoppiato grazie all'esponente $s$, che funziona come una riflessione intorno allo zero. L'esponente $e$, d'altro canto, funziona come un valore che scala l'insieme di valori reali esattamente rappresentabili. In altre parole, fissando gli esponenti $e = k$ ed $s = 0$ i valori esattamente rappresentabili sono sempre gli stessi (i $2^{n}$ della mantissa) per qualunque $-127\le k \le 128$. Cambiando solo $s =1$ si avranno gli stessi $2^{n}$ valori cambiati di segno. Quindi, per un dato esponente $e$ ci saranno $2^{n} \times 2$ valori esattamente rappresentabili. Ora, cambiando l'esponente $e = k+1$ (mantenendo $s = 0$) il numero di valori esattamente rappresentabili resta lo stesso (i $2^{n}$ della mantissa) ma ogni valore viene scalato di $2$ dato che si passa da $2^k$ a $2^{k+1}$ (il cui rapporto è appunto $2$). Questo significa che, finché l'esponente non cambia, i valori reali esattamente rappresentabili sono equidistanti ma aumentando o diminuendo l'esponente cambia di conseguenza anche l'equidistanza tra di essi.
Quindi più grande è un numero e maggiore sarà l'errore massimo di approssimazione per quel numero. Questo è vero in assoluto ma l'errore relativo è costante. In breve, intuitivamente e senza entrare nel dettaglio, se un numero è piccolo un piccolo errore di approssimazione è tollerabile (ad esempio, 1 centimetro su un metro). Man mano che il valore del numero aumenta anche l'errore nell'approssimazione aumenta con esso (1 metro su 100 metri). In entrambi i casi però l'errore relativo resta $\frac{1}{100}$. Alla fine, un errore assoluto maggiore per numeri grandi sembra poter essere accettabile, a patto di prestare maggiore attenzione durante i calcoli (si veda il paragrafo Aritmetica sotto)
Un'altra cosa da notare è che, come detto in precedenza, i valori all'estremo dell'intervallo dell'esponente ($-127$ e $128$) sono riservati quindi il numero reale positivo ($s = 0$) più piccolo ($m=0, \enspace e = -126$) esattamente rappresentabile è
$f_{min} = (-1)^0(1 + 0)\times 2^{-126} = \displaystyle\frac{1}{2^{126}}$
dopodiché, più piccolo di questo c'è solo lo zero mentre più grande di questo c'è ($M\enspace \&\!= 0x1$, bit meno significativo della mantissa settato; vedi \eqref{eq:2})
$(-1)^0(1 + 2^{-23})\times 2^{-126} = 2^{-126} + 2^{-149} = f_{min} + 2^{-149}$
Questo vuol dire che tra $f_{min}$ ed il suo successivo c'è molta meno differenza che tra $f_{min}$ ed il suo precedente (zero). Intorno allo zero c'è praticamente un piccolo vuoto di valori che non sono esattamente rappresentabili.
Usare il valore riservato $e=-127$ per l'esponente significa, di fatto, $e = -126$ con la formula \eqref{eq:1} che diventa
$f = (-1)^s(0 + m)\times 2^e$
(impostando $i = 0$ dato che non serve in questo caso la parte intera; rappresentata dal bit implicito).
La formula \eqref{eq:3} diventa invece
$2^{-23}\le m \le(1 - \frac{1}{2^{23}})$
(dato che lo zero ha già una sua rappresentazione e non ha bisogno di una nuova in questo caso).
In questo modo il numero reale positivo ($s = 0$) più piccolo ($m=2^{-23}, \enspace e = -126$) esattamente rappresentabile è
${f_d}_{min} = (-1)^0(0 + 2^{-23})\times 2^{-126} = \displaystyle\frac{1}{2^{149}}$
I numeri reali rappresentati con $e = -127$ sono detti denormalizzati. Tutti gli altri sono normalizzati.
Infine, l'esponente $e=128$ è riservato per i non-numeri reali speciali quali infinito ($\pm \infty$) o per valori indeterminati o non definiti (radice numero negativo, $\frac{0}{0}$, ecc.)
Aritmetica
Tra le quattro operazioni aritmetiche disponibili per i numeri floating point quelle che presentano maggiori insidie sono l'addizione e, di conseguenza, la sottrazione. Moltiplicazione e divisione non destano particolare preoccupazione (non considerando i classici errori di overflow o di perdita minima di precisione durante i calcoli).
Senza entrare nel dettaglio di come i calcolatori effettuano le operazioni aritmetiche, basta pensare che avendo un numero grande (esponente grande) ed aggiungendo o sottraendo un numero piccolo (esponente piccolo) il risultato possa anche non cambiare dato che, come visto in precedenza, l'errore di approssimazione assoluto aumenta man mano che i valori diventano grandi. Aggiungere un numero molto piccolo ad un numero molto grande può significare che la migliore approssimazione per il risultato sia la stessa usata per rappresentare il numero più grande. Ad esempio, $2.0^{10} + 2.0^{-10}$ non è detto che porti ad un valore diverso dal primo addendo, $2.0^{10}$.
Un altro problema, sempre legato alla addizione o sottrazione, e quella che vede la sottrazione di due numeri simili (stesso esponente, mantisse simili) molto grandi (o la loro addizione se i segni sono diversi). Facendo un esempio concreto, definiamo $A$, $B$ e $\delta$ come valori che hanno esatta rappresentazione sul sistema in uso
$A = 1.0,\quad B = 1.0\times 10^6,\quad \delta = 1.5$
Definiamo quindi
$A' = A + \delta = 2.5,\quad B' = B + \delta = 1000001.5$
$A'$ e $B'$ non è detto che abbiano esatta rappresentazione nel sistema in uso ma è ovvio, per quanto detto sinora, che $A_r$ avrà una rappresentazione più accurata rispetto a $B'$ in quanto è più vicina allo zero (esponente più piccolo equivale a minore equidistanza tra i valori rappresentati esattamente) ma, come detto in precedenza, per valori grandi l'errore relativo resta costante e un errore assoluto di $0.5$ tra $B'$ e $B$ è più che accettabile (come lo è avere 50 centesimi in più o in meno su 1 milione, non fa molta differenza). Definiamo quindi $A_r$ e $B_r$ come le rappresentazioni di $A'$ e $B'$ nel sistema in uso
$A_r = A + \delta = 2.49,\quad B_r = B + \delta = 1000002$
Sottraendo $A' - A$ e $B' - B$ si vorrebbe che il risultato fosse il più possibile aderente a quello di $\delta$ ma
$A' - A = 1.49 \simeq \delta, \quad B' - B = 2.0$
$A' - A$ ha un valore accettabile, $B' - B$ no. Se si hanno due numeri simili abbastanza grandi la loro rappresentazione, per quanto poco accurata, risulta accettabile ma la loro differenza può perdere in precisione fino a valori non accettabili.
In conclusione, è bene prestare attenzione quando si sommano o sottraggono numeri grandi e numeri piccoli così come quando si sottraggono due numeri gradi (o si sommano due numeri grandi di segno diverso). Una soluzione, in entrambi i casi, può essere quella di riformulare le espressioni, se e dove possibile, cercando di evitare tali operazioni.
Confronto
Una conseguenza importante del fatto che un numero in virgola mobile possa non avere esatta rappresentazione è che risulta quasi sempre sbagliato confrontare direttamente due variabili a virgola mobile (a meno che non si assegni esplicitamente ad entrambe la stessa costante letterale e che si acceda ad esse solo in lettura).
Una soluzione può essere quella di valutare il confronto rispetto ad un valore molto piccolo di tolleranza. Se $a$ e $b$ sono valori a virgola mobile ed $\epsilon$ è il valore di tolleranza, invece di avere
$a = b\quad$ e quindi $a - b = 0$
si avrà piuttosto
$a \simeq b\quad$ se $\quad |a - b| \le \epsilon$
La differenza $|a - b|$ può essere vista come l'errore assoluto di approssimazione di un numero $a$ rispetto alla sua rappresentazione esatta $b$ e questo, come visto in precedenza, varia con il variare della grandezza del numero. In questo caso bisognerebbe fixare di volta in volta $\epsilon$ in base alle grandezze di $a$ e $b$ e non è il massimo della comodità. In questo caso conviene considerare l'errore relativo
$\bigg| \displaystyle\frac{a - b}{b}\bigg| \le \epsilon$
$\displaystyle\frac{|a - b|}{|b|} \le \epsilon$
$|a - b| \le |b|\, \epsilon$
Qui sorge un problema. Se $b < 1$, $\enspace \epsilon$ verrà scalato ad un valore più piccolo riducendo così il valore di tolleranza ritenuto più consono. Si può risolvere la cosa considerando che $|a-b|$ è un valore in modulo (quindi $|a-b| = |b-a|$) e che per valori piccoli non è poi così sbagliato considerare l'errore assoluto. La nuova formula quindi considererà l'errore assoluto per valori minori di $1$ e l'errore relativo per valori più grandi
$|a - b| \le max\,(|a|, |b|, 1)\, \epsilon$
Riferimenti:
[1] Essential Mathematics for Games and Interactive Applications - Van Verth, Bishop
[2] Real-Time Collision Detection - Ericson
Nessun commento:
Posta un commento