10 milioni per 7 è sempre pari a 70 milioni?

Il calcolo numerico può condurre a sottili e pericolosi errori di arrotondamento. Per evitarli è necessario conoscere il problema e sapere come aggirarlo.

---

Consideriamo il seguente programma, scritto in C:

#include <stdio.h>

int main() {
  float x = 7;
  float S = 0;
  int i;
  for (i = 0; i < 10000000; i++) {
    S += x;
  }
  printf(“%f\n”, S);
}

Il programma aggiunge 7 alla variabile S dieci milioni di volte. Il risultato atteso è quindi di 70 milioni. Ma in effetti, compilando (senza ottimizzazioni) ed eseguendo il programma si ottiene

77603248.000000

che è piú grande di oltre il 10%. Sorpresi? È l’effetto degli errori di arrotondamento causati dal fatto che i numeri, nei computer, si possono rappresentare solo con un numero finito di cifre. Ora, sia 7 che 10 milioni sono perfettamente rappresentabili nella memoria di un computer. Allora, perché il risultato è così cattivo?

La rappresentazione dei numeri nei computer

I numeri, nella memoria di un computer, si rappresentano nel sistema binario. In questo sistema qualsiasi numero è rappresentato in un sistema posizionale in base 2, in modo tale che qualsiasi numero intero composto di m cifre (0 e 1) rappresenta un numero

dove dᵢ è il valore della i-esima cifra (0 o 1). Ad esempio, il numero intero 5 si rappresenta come 00000101 in un computer a 8 bit, essendo 1⨉2²+0⨉2¹+1⨉2⁰=4+0+1=5. Gli zeri iniziali non sono, naturalmente, significativi.

Per rappresentare numeri non interi, come 3.14, in linea di principio si potrebbe usare la stessa notazione, con la sola differenza che il valore iniziale di i è negativo e pari al numero di cifre dopo la virgola. Ad esempio, 3.14 corrisponde a 11.001000111111010101110001 in binario. In effetti,

Osserviamo che il numero preciso risultante dal calcolo di cui sopra è, in effetti, 3.1400003433. I numeri razionali in una base non sono necessariamente numeri razionali in un’altra base (ad esempio, 1/10 è irrazionale in base 2). Una tale rappresentazione è poco pratica per i computer, che hanno bisogno di un numero enorme di cifre per rappresentare, con sufficiente precisione, numeri che, nella notazione decimale, richiedono un numero limitato di cifre. I computer, per questo, utilizzano la notazione standard IEEE754. All’interno di questa notazione, i numeri in virgola mobile, come vengono chiamati, si rappresentano con 32 bit, utilizzando una sorta di notazione scientifica in base 2. Nella notazione scientifica, un numero x si scrive come x=y×10ⁿ, dove, di solito, y∈[1,10) e n è scelto di conseguenza. Ad esempio, la distanza media della Terra dal Sole è di 149 597 870 700 m, che si scrive anche come 1.49 597 870 700⨉10¹¹ m. Analogamente, 3.1400003433, in base 2, si può scrivere come 1.100100011110101110001⨉2¹, cioè, come y×2ⁿ, con y∈[1,2) e n=1. Con questa convenzione, la cifra che precede il punto decimale è sempre 1 e si può omettere. Il numero che moltiplica la potenza di due (1.100100100011111101010101110001) si chiama mantissa e può essere rappresentato, nella cosiddetta forma normale, come 1001000111111010101110001, omettendo il primo 1. Nella notazione IEEEE754, un numero si rappresenta utilizzando il primo bit per il suo segno (0 se positivo), 8 bit per rappresentare l’esponente di 2 (n=1 nell’esempio) nella notazione in eccesso a 127 (cioè come un intero tale che n=m-127; m=128 nel nostro esempio), e 23 bit per rappresentare la sua mantissa nella forma normale. La sequenza di bit necessaria per rappresentare il nostro numero è la seguente: 0 10000000 10010001 11101011 1000100.

Anatomia del problema

Dichiarando x come numero in virgola mobile (float), il compilatore lo rappresenta come 0 10000001 1100000 000000000000 0000000000, cioè come (1+1×2-¹+1×2-²)×2²=7. Infatti, il primo 0 rappresenta il segno +. Il seguente gruppo di 8 bit rappresenta 129 che, a sua volta, corrisponde all’esponente di due 129-127=2. Dei restanti 23 bit, solo i primi due non sono nulli e corrispondono alle potenze -1 e -2. L’1 aggiunto a queste potenze è implicito nella forma normale e non rappresentato esplicitamente.

Il problema sorge quando il programma effettua la somma. Per fare ciò, una CPU deve considerare i due termini della somma come rappresentati utilizzando la stessa potenza di due; in questo modo può utilizzare la proprietà distributiva della moltiplicazione. Quando S=16 777 222, la sua rappresentazione nella memoria del computer è 0 10010111 000000000000 000000000000 0000011. L’esponente di due è 10010111, corrispondente al numero intero 151. L’esponente di 2 nella notazione scientifica è quindi 151-127=24. S, di conseguenza, si esprime come y×2²⁴. Per poter sommare x=7 ad esso, dobbiamo esprimere x come z×2²⁴, in modo che la CPU possa fare la somma di y e z per ottenere il nuovo valore di S. La rappresentazione originale di x era 1,11 seguita da 21 zeri, per 2². Per esprimerla come z×2²⁴, dobbiamo spostare i bit della mantissa di 22 posti a destra. Il risultato è un numero composto da 21 zeri seguiti dalle cifre 111. In un numero a 32 bit non c’è posto per l’ultimo 1, che si perde, e, di fatto, x=6 e S=16 777 228.

Per mitigare gli effetti dell’arrotondamento, le somme si eseguono nella FPU (Floating Point Unit), che utilizza 80 bit per rappresentare i numeri in virgola mobile. Aggiungendo 7 a 16 777 228 si ottiene 16 777 235. Sfortunatamente, quando si copia questo numero nella memoria, la FPU aggiunge un 1 alla mantissa, per recuperare l’errore precedente. Il risultato è S=16 777 236, cioè 16 777 228 + 8. Di fatto, il valore aggiunto alla somma è 8 invece di 7. Lo stesso accade a ogni iterazione successiva e di fatto si aggiunge 8 invece di 7 molte volte. In un caso, il valore aggiunto alla somma effettiva S è in realtà 11!

La lezione

Quando si sommano, con un computer, due valori, S e x, è necessario prestare attenzione ai loro valori relativi. Se log₂(S)-log₂(x) ≪ p, dove p è il numero di bit utilizzati per la mantissa, allora non avrete problemi. Se invece log₂(S)-log₂(x) ≃ p o più grande, allora, molto probabilmente, vi imbatterete in errori di arrotondamento che potrebbero anche essere gravi. Mai sommare ciecamente numeri troppo diversi. Allo stesso modo, dovreste sempre prestare attenzione alla differenza di numeri molto simili. Se i numeri sono troppo vicini, la loro differenza può essere difficile da rappresentare e può essere pari a zero, anche se i due numeri sono diversi.