Cifra di guardia

Una cifra di guardia è una cifra aggiunta nella rappresentazione di un numero in virgola mobile in fase di calcolo, per limitare gli errori di arrotondamento e di cancellazione numerica.

Proprietà

Poiché nella rappresentazione in virgola mobile si impiega un numero fisso di cifre significative possono sorgere problemi di precisione, specialmente nelle operazioni di sottrazione quando si opera su numeri che hanno ordine di grandezza molto differente oppure valori molto prossimi (problema noto come "cancellazione catastrofica"). Quando si effettuano sottrazioni su numeri in virgola mobile in base b con p cifre, l'errore relativo del risultato può essere pari a b - 1. Se si considera infatti la differenza tra 1,0...0 e 0,a...a (dove a = b - 1), il sottraendo viene traslato di una cifra e la differenza calcolata in virgola mobile sarà pari a b^-p+1, mentre il risultato esatto sarebbe b^-p, con un errore relativo pari a

${\frac {b^{-p+1}-b^{-p}}{b^{-p}}}={\frac {b^{-p}(b-1)}{b^{-p}}}=b-1$.

Essendo il numero c di cifre contaminate da un errore relativo di n·ε pari a log_bn, in base 2 si ha che tutte le p cifre del risultato sono potenzialmente contaminate:

$c=\log _{2}{\left(n\cdot \epsilon \right)}=\log _{2}{\frac {1}{\epsilon }}=\log _{2}{2^{p}=p}$.

Ad esempio, il risultato di 10,1 - 9,93 è 0,17, ma eseguendo il calcolo in virgola mobile con 3 cifre si ha 1,01×10¹ - 0,99×10¹ = 0,02×10¹ = 2×10⁻¹, con un errore di 30 ulp e un risultato errato in ogni sua cifra.

Per evitare questo problema, si può effettuare il calcolo usando una cifra supplementare nel calcolo (la cifra di guardia), troncando gli operandi a p + 1 cifre e arrotondando in seguito il risultato a p cifre. Si dimostra che in questo caso l'errore relativo sul risultato è limitato a meno di 2·ε.

Siano infatti x e y due numeri in virgola mobile positivi in base b e con p cifre, sottratti impiegando p + 1 cifre nel calcolo. Senza ledere la generalità si possono scambiare i due valori per avere x > y, e scalare entrambi in modo che x sia nella forma x₀.x₁...x_p-1 × b⁰. Se y è nella stessa forma, allora la differenza risulterà esatta. Se y è nella forma 0.y₁....y_p-1 × b⁰ allora la cifra di guardia garantisce che la differenza sia calcolata esattamente, e il successivo arrotondamento comporta un errore di al più ε. Se in generale y contiene k zeri in posizione più significativa, ovvero è nella forma 0.0...0y_{k + 1}...y_k+p × b⁰, nel calcolo viene troncato a p + 1 cifre al valore y, con un errore assoluto

$y-{\bar {y}}<(b-1)\left(b^{-p-1}+\dots +b^{-p-k}\right)$.

Il successivo arrotondamento dopo la differenza comporta un errore δ è limitato da ε

$\delta \leq \left({\frac {b}{2}}\right)b^{-p}$

per cui l'errore complessivo dell'operazione sarà pari a

$(x-y)-(x-{\bar {y}}+\delta )=y-{\bar {y}}+\delta$.

Si distinguono tre casi:

• se x - y ≥ 1, l'errore relativo è limitato da

  $\left|{\frac {y-{\bar {y}}+\delta }{1}}\right|\leq b^{-p}\left[(b-1)\left(b^{-1}+\dots +b^{-k}\right)+{\frac {b}{2}}\right]\leq b^{-p}\left(1+{\frac {b}{2}}\right)=\left(1+{\frac {2}{b}}\right)\epsilon \leq 2\epsilon$;

• se x - y < 1, si ha δ = 0 e, nel caso peggiore, con x = 1 e le cifre non nulle di y pari a b - 1 la differenza è limitata inferiormente da $(b-1)\left(b^{-1}+\dots +b^{-k}\right)$, con un errore relativo limitato da

  ${\frac {y-{\bar {y}}+\delta }{(b-1)\left(b^{-1}+\dots +b^{-k}\right)}}<{\frac {(b-1)\left(b^{-p-1}+\dots +b^{-p-k}\right)}{(b-1)\left(b^{-1}+\dots +b^{-k}\right)}}=b^{-p}\leq 2\epsilon$;

• se x - y < 1 ma x - y ≥ 1, deve essere x - y = 1 e quindi δ = 0, per cui vale ancora il limite superiore per l'errore relativo trovato nel caso precedente.

Supporto

Le cifre di guardia sono fondamentali nel contenere l'errore in fase di sottrazione tra numeri in virgola mobile, e la loro assenza causa gravi errori di calcolo e limita la portabilità degli algoritmi. Negli anni 1960 i primi mainframe IBM System/360, prodotti dal 1964 al 1967, operavano senza esse, così come i calcolatori HP-80. Nel 1968 IBM ha aggiunto le cifre di guardia nel calcolo in virgola mobile dell'architettura System/360, prima in quello a precisione singola e poi anche a quello in doppia precisione. Non tutti i produttori di calcolatori si sono adeguati celermente, e una notevole eccezione è stata Cray, che ha continuato a produrre fino al 1995 diversi modelli di calcolatore (Cray-1, Cray-2, Cray X-MP, Cray Y-MP, Cray C90) senza cifre di guardia, che soffrivano di errori visibili in alcuni algoritmi in virgola mobile.

Lo standard IEEE 754 richiede che, nelle implementazioni conformi, le operazioni elementari in virgola mobile debbano fornire il medesimo risultato che avrebbero se calcolate con precisione infinita e poi arrotondate in uno dei modi possibili (arrotondamento al numero macchina più prossimo, a ±Inf o troncamento a zero). Un solo bit di guardia non garantisce sempre tale risultato in ogni operazione, che può essere ottenuto tramite l'uso di un secondo bit di guardia e di un terzo bit detto sticky, che assume il valore dell'or logico di tutti i bit rimanenti.

Bibliografia

• Ephraim J. Borowski e Jonathan M. Borwein, cifre di guardia, in A. Stracca (a cura di), Dizionario Collins della matematica, Gremese Editore, 2004, ISBN 9-788-8844-0338-4.
• David Goldberg, What Every Computer Scientist Should Know About Floating-Point Arithmetic, in ACM Computing Surveys, marzo 1991.
• Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2ª ed., SIAM, 2002, ISBN 978-0-8987-1521-7.