Aritmetica  dei  computer

L' aritmetica dei computer, almeno quella implementata direttamente dall' hardware, a causa della necessità pratica di avere una rappresentazione standard dei numeri mediante un numero finito e prefissato di bit, gode di caratteristiche e proprietà  diverse da quelle dell' aritmetica degli interi o dei reali della matematica.

Sugli interi la principale differenza proviene dal fatto che,  con  n bit disponibili, è possibile rappresentare solo  2ⁿ  numeri  diversi. Questo comporta l' esistenza di un minimo ed un massimo tra gli interi rappresentabili. La scelta attualmente implementata in moltissimi linguaggi di programmazione è di sfruttare le possibilità dell'hardware per rappresentare gli interi dell' aritmetica modulo  2ⁿ. Le proprietà di questi interi coincidono con quelle dell'aritmetica di Peano purché ci si tenga lontano dai valori limte.

Per i reali, le differenze sono maggiori. Di nuovo, invece di un insieme illimitato (i reali dell' analisi) si deve usare una "rappresentazione" dotata di minimo e di massimo. Ma in più,  sempre per la necessità di lavorare con un numero finito di bit, si perde anche la proprietà di densità dei reali: tra due "reali" del computer ce n'è sempre un numero finito (eventualmente zero). Infine, come vedremo, la spaziatura tra i "reali" del computer non è uniforme e queste proprietà peculiari determinano la principale differenza tra operazioni con i  reali dell' analisi e i "reali" del computer: 
Pur valendo sempre la proprietà commutativa, cessano di avere validità generale la proprietà associativa e distributiva delle operazioni elementari. Pertanto, formule equivalenti secondo l' aritmetica dei reali, divengono inequivalenti sul computer.  Uno dei compiti dell' analisi numerica è  quello di chiarire  la portata quantitativa di queste inequivalenze e gli effetti sugli algoritmi numerici.

Sia la rappresentazione e l' aritmetica degli interi, sia quella dei reali, relativamente all' utilizzo sui computer, sono oggetto di  accordi internazionali per la definizione di standards. I sistemi attualmente più diffusi sono l' aritmetica modulo 2 ⁿ con complemento a due per gli interi  (possibilità  prevista dallo standard IEC 10967 accanto ad un  aritmetica intera superiormente e inferiormente limitata)  e  quello per i numeri floating point definito nello standard appena menzionato e nello IEEE Standard for Binary Floating point Arithmetic (ANSI/IEEE Std 754-1985, ora IEC 60559)  (più brevemente "IEEE 754 " )per i "reali". 
 

Rappresentazione degli interi

Ricordiamo che la notazione decimale posizionale, cui siamo abituati, è quella in cui il significato di uno dei dieci simboli  di  base  (le cifre  0,1,2,3,4,5,6,7,8,9)  dipende dalla posizione di questo all' interno della sequenza di cifre.
P. es. il numero  361 va interpretato come: 3 centinaia + 6 decine + 1 unità . Ovvero:

3 10² + 6 10¹ + 1 10⁰

Se invece di usare le dieci cifre usuali ne usiamo solo due (0,1 rappresentabili in un circuito mediante tensione alta e tensiona bassa) avremo la possibilità di una rappresentazione posizionale  in base due in cui un numero è costituito unicamente da una sequenza di 0 e 1.
P.es.

11010  va interpretato come

1   2⁴ + 1   2³ + 0   2² + 1   2¹ + 0   2⁰

Ovvero, indicando con un sottoscritto  ₁₀  oppure  ₂  la rappresentazione in base 10 o 2 rispettivamente,

11010₂ = 26₁₀

Se l' aritmetica (le operazioni tra interi) viene implementata in modo che esista il successivo del massimo intero (e questo sia il minimo intero) e, viceversa, esista il precedente del minimo (e questo sia il massimo)  l' aritmetica del computer diviene esattamente l' aritmetica modulo 2 ⁿ come definita in algebra.

Questa possibilità è quella "naturale" per un computer perché le operazioni aritmetiche sono svolte su dati rappresentati in registri (speciali circuiti) del processore sotto  forma di un numero fisso di bit.

Facciamo l' esempio di un intero (senza segno) rappresentato in registri a 8 bit. Potrebbe essere:

pari a 254. Se adesso sommiamo 3 (11₂)  a questo numero  dovremmo ottenere 

cioè  257. Però la cella più a sinistra non esiste nel registro del nostro processore. Quindi il bit corrispondente può "perdersi" lasciando come risultato  l' intero contenuto nelle sole otto celle più a destra: 1 che corrisponde a     257 mod 2⁸. Questo schema di base va lievemente modificato per tener conto di interi col segno.

Se abbiamo a disposizione n bit e vogliamo rappresentare interi negativi e positivi (in numero uguale), la soluzione più semplice sarebbe  quella di usare uno dei bit per indicare il segno e gli altri per la rappresentazione in base 2 usuale. In questo caso potremmo rappresentare 2^n-1 interi positivi (da +0 a 2^n-1 - 1 ) e 2^n-1 interi negativi ( da -0 a -2^n-1 + 1 ). Da notare che in tal modo esisterebbero due diverse rappresentazioni dello zero e il range dei positivi sarebbe lo stesso dei negativi.

Tuttavia, questo metodo di rappresentazione non è il più agevole per implementare l' aritmetica modulo 2ⁿ. A questo scopo esistono due diverse rappresentazioni degli interi con segno utilizzate in modo standard nell' aritmetica dei computer contemporanei.

La rappresentazione con bias (distorsione, forse meglio traducibile in questo caso con traslazione)  e quella a complemento a due. L' utilizzo della prima (con lievi modifiche) è limitato alla codifica degli esponenti (interi) dei numeri con virgola (numeri floating point). La seconda è oggi la codifica generalmente usata per la rappresentazione degli interi con segno sfruttando le capacità dell' hardware.
In entrambe, gli interi tra -2^n-1 e 2^n-1-1 hanno un' unica rappresentazione mediante sequenze di n bit consecutive nell' aritmetica modulo 2ⁿ . Quello che cambia tra le due rappresentazioni è solo l' associazione tra sequenze di 0 e 1 ed interi nell' intervallo in questione. Nella rappresentazione con complemento a due lo zero è associato alla sequenza di n zeri, mentre in quella con bias B = 2^n-1-1 il valore binario (senza segno) del bias B nella rappresentazione posizionale diviene la rappresentazione dello zero mentre il numero le cui cifre sono tutte zero rappresenta il valore -B  (vedi tabella più avanti).

La rappresentazione complemento a due è basata sull' utilizzo dell' aritmetica delle conguruenze. In tale aritmetica infatti metà degli elementi sono gli inversi additivi dell' altra metà e pertanto possono essere presi a rappresentanti di un insieme (limitato) di numeri negativi. Per esempio, con 8 bit, 11111111 rappresenterebbe 2⁸-1=255. Essendo però 11111111+00000001 = 00000000 (mod 2⁸), 11111111 può essere considerato rappresentativo di -1. E così via per circa metà degli interi rappresentabili. Ne restarà uno ( 2⁷ ) che, essendo inverso additivo di se stesso nell' aritmetica modulare, dovrà essere assegnato convenzionalmente o al massimo valore positivo o al minimo negativo. In pratica, per ottenere la rappresentazione complemento a due di un numero negativo, basta invertire tutti i bit della rappresentazione binaria del numero positivo (gli zeri diventano uno e gli uno diventano zero) e poi sommare uno al risultato. La spiegazione di questo algoritmo è semplice: con la notazione complemento a due vogliamo sfruttare le proprietà dell' aritmetica modulare (e poter fare la somma tra numeri positivi e negativi esattamente con lo stesso algoritmo (circuiti) che manipola la somma tra numeri positivi). Questo implica che se sommiamo ad un numero positivo il corrispondente negativo dobbiamo trovare zero. Facendo riferimento alla discussione sopra accennata, si vede che se si somma ad un numero positivo la sequenza di bit invertiti si ottiene un numero fatto solo dalle cifre 1. Aggiungendo un ulteriore 1 si ottiene zero (con quel numero di bit). Da cui l' algoritmo del complemento a due.
Un modo complementare di considerare la notazione per i negativi del complemento a due è di interpretare il bit più significativo come coefficiente della corrispondente potenza di due ma cambiata di segno: 10101110 = -2⁷ + 2⁵+2³+2²+2¹.

Come esempio, la tabella seguente mostra quale è l' associazione tra sequenze di 8 bit ed valori interi con segno nelle  rappresentazioni qui descritte (complemento a 2 e con bias = 127 ).
 
 
 

Rappresentazione dei numeri con la virgola - cifre significative.

x.yxwt  10^e  oppure   0.xyxwt  10 ^e+1  (dove x, y, w, t indicano cifre decimali).  Il coefficiente della potenza di 10 viene chiamato mantissa del numero. Nel primo caso la mantissa è  x.yxwt , mentre nel secondo è 0.xyxwt.  La rappresentazione mediante virgola mobile offre due principali vantaggi su altre possibili alternative:  rende più semplice automatizzare le operazioni aritmetiche  e  soprattutto permette di eliminare qualsiasi ambiguità tra zeri significativi e  posizionali.

Per illustrare quest' ultimo punto  cerchiamo di capire come interpretare il valore delle cifre del numero 15000.  Chiaramente, si tratta di un numero in cui ci sono 1 decina di migliaia  e  5 migliaia. Però,  non  è  chiaro se i tre zeri che seguono vadano interpretati come " esattamente zero centinaia, zero decine e zero unità" oppure come indicatori del valore di decine di migliaia e migliaia delle cifre precedenti ma  senza per questo implicare che il numero in questione corrisponda ad una conoscenza esatta anche di centinaia, decine e unità.  Nel primo caso, diremo che si tratta di zeri "significativi"  e che le cifre significative del numero  sono in tutto 5. Nel secondo caso, gli zeri servono solo ad attribuire il giusto valore posizionale a 1 e 5 ma il numero di cifre significative è 2. Con la rappresentazione in virgola mobile si  definiscono significative tutte le cifre  della mantissa di lunghezza finita (zeri inclusi) che siano a destra della prima cifra diversa da zero.

In notazione binaria il concetto di numero a virgola mobile si estende in modo diretto. Inoltre, poiché le cifre possono essere solo  0 oppure 1,  se si opta per la   forma   "normalizzata"  1.xyzt  2^e    , in cui  la mantissa  1.xyzt  inizia sempre per 1, possiamo omettere di indicare l' 1 prima del punto  risparmiando un simbolo  per rappresentare la mantissa ma mantenendo una cifra (binaria) ignificativa in più di quelle esplicitamente scritte.

Per standardizzare la rappresentazione di numeri binari floating point è necessario  decidere quanti bit utilizzare e come ripartirli tra mantissa ed esponente.  Esistono moltissime possibili soluzioni e, in principio, i linguaggi di programmazione dovrebbero essere "neutri" rispetto alle convenzioni di rappresentazione.  Di fatto, fin dalla fine degli anni '80, si è imposto lo standard  IEEE 754  che, nella revisione del 2008, prevede tre rappresentazioni binarie, lasciando ai singoli linguaggi la scelta di quali adottare:
 

1. una "corta" che utilizza 4 bytes, ovvero 32 bit ripartiti in:  1 bit per il segno  della mantissa, 23 bit per la mantissa, senza il primo 1 (bit nascosto), ed 8 bit per l' esponente espresso come intero binario  nella forma con bias 127.
2. una "più lunga" o "a precisione doppia" che utilizza 8 bytes (64 bit) ripartiti in: 1 bit per il segno  della mantissa, 52 bit per la mantissa, senza il primo 1 (bit nascosto), ed 11 bit per l' esponente espresso come intero binario  nella forma con bias 1023.
3. una "a precisione quadrupla" con 16 byte (128 bit) ripartiti in 1 per il segno della mantissa, 112 bit per la mantissa (sempre senza il bit nascosto) e 15 bit per l'esponente, intero nella rappresentazione con bias 16383.

Inoltre, due dei possibili valori dell' esponente sono in realtà riservati per esprimere dei valori speciali risultanti da possibili operazioni aritmetiche mal definite come divisioni per zero o rapporti del tipo 0/0, nonché per rappresentare lo zero e un insieme di numeri "denormalizzati" per cui non vale la convenzione del bit nascosto.

In dettaglio, per numeri a 32 bit la codifica  è la seguente.
Indichiamo con S, M ed E i campi di  1, 23 e 8 bit riservati alla codifica di segno (della mantissa), mantissa ed esponente.

Il campo "esponente", E,   dei floating assume in notazione posizionale valori tra 0 e 255.

1. I valori di E da 1 a 254 permettono di esprimere numeri normalizzati in cui il primo bit (nascosto, cioè non rappresentato esplicitamente) della mantissa è 1 (a sinistra del punto)  e gli esponenti vanno da -126 a +127. In altre parole, il valore del numero rappresentato da S,M ed E sarà  (-1)^S  1.M 2^E-127 . Perciò il più piccolo numero normalizzato è  1.000...000 2 ^-126  che corrisponde approssimativamente a  10 ^-38   , mentre il più grande ( 1.111...111   2 ⁺¹²⁷ )        corrisponde a circa  10 ⁺³⁸ .
2. Se il campo E è zero e M  è zero, si ha lo zero, di cui esiste un valore positivo ed uno negativo a seconda del valore di S (0 o 1). Zero positivo e zero negativo devono essere trattati dai linguaggi di programmazione come perfettamente equivalenti.
   
3. Se il campo E è zero mentre  M è non nullo si tratta di numeri in cui la mantissa va interpretata come 0.M e la potenza di 2 come -126. Questi numeri "denormalizzati" permettono di rappresentare valori  compresi tra   circa  10^-45    e   circa  10^-38 al prezzo di un crescente perdita di precisione (diminuzione delle cifre significative) man mano che ci si avvicina allo zero.
4. Se il campo E è 255 e M è 0  si considera il valore come segnale di  un "overflow" ed il valore viene indicato come + o - infinito a seconda del segno.
5. Infine, se il campo E è 255 ed M è non nullo, si attribuisce a tale sequenza il valore NaN  ( Not a Number ) che solitamente sta a segnalare il risultato di operazioni aritmetiche non definite come per esempio il calcolo del rapporto 0/0.

In modo analogo per floating a 64 o 128 bit. Lo standard non vieta l'esistenza di ulteriori rappresentazioni. Da segnalare in particolare la presenza su processori Intel di una rappresentazione a 10 byte (80 bit), di cui 15 dedicati all' esponente, ma senza bit nascosto, quindi con mantisse di 64 bit totali tutti espliciti.

Da notare che i valori speciali NaN ( o nan ) e +/- infinito dello standard IEEE non sono intesi come elementi dell' insieme dei numeri reali ma come valori speciali  da utilizzare nella programmazione per avviare eventuali procedure di  manipolazione delle condizioni di errore. Talvolta  un compilatore può generare automaticamente codice di gestione delle condizioni di errore  nascondendo al programmatore la possibilità di accedere ai valori speciali dello standard IEEE-754. Tuttavia, normalmente, esistono opzioni del compilatore che permettono di  evitare la gestione automatica.

Infine va aggiunto che  lo standard prevede  quattro diversi tipi di arrotondamento nell'  esecuzione delle operazioni tra numeri a virgola mobile:

• arrotondamento al numero più  vicino (il default)
• arrotondamento verso +Inf
• arrotondamento verso 0
• arrotondamento verso -Inf
  

• una volta determinata il numero di cifre del risultato da tenere;
  
• si incrementa  l' ultima cifra di 1 se la cifra successiva è   >  5 o 5  seguito da almeno una  cifra non nulla;
• si lascia invariata l'  ultima cifra se la successiva è < 5;
• se la cifra successiva all'  ultima è 5  seguito solo da zeri  si incrementa l'  ultima di 1 se è dispari mentre la si lascia invariata se pari. In tal modo , in media, metà degli arrotondamenti saranno per eccesso e metà per difetto.

• una volta determinata il numero di cifre del risultato da tenere;
  
• si incrementa  l' ultima cifra di 1 se la cifra successiva è   1 seguito da almeno una  cifra non nulla;
• si lascia invariata l'  ultima cifra se la successiva è 0;
• se la cifra successiva all'  ultima è 1  seguito da zeri  si incrementa l'  ultima di 1 se è 1 mentre la si lascia invariata se 0.

Conseguenze della rappresentazione dei reali sulle proprietà dell' aritmetica

Le principali caratteristiche della rappresentazione dei reali che influenzano le proprietà dell' aritmetica sul computer sono:

i) il numero finito di cifre significative,
ii) il numero finito di reali,
iii) la loro non uniformità e
iv) la rappresentazione mediante una base diversa da quella usuale ( 2 invece di 10).

Vediamo più da vicino come questi fattori intervengono nel caso della rappresentazione mediante 32 bit. Le modifiche per i casi con numero diverso di bit sono ovvie e lasciate come esercizio.

La proprietà i) implica che, dato un numero rappresentato sul computer esiste più di un numero B ( non solo B=0 ) che soddisfa l' equazione

A + B = A

è sufficiente che il rapporto tra B sia ed A sia più piccolo di 2^-24 perché sommare A a B divenga equivalente a sommare 0 ad A (con arrotondamento al numero più vicino). Supponiamo, per esempio di voler effettuare la somma:

1.0 2⁴⁶ + 1.0 2²⁰

con reali a 32 bit. Il primo numero ha mantissa

1.00000000000000000000000 (23 zeri) ed esponente 46;

il secondo ha la stessa mantissa ed esponente 20.

Per poter sommare i numeri, uno dei due (il minore) viene trasformato mediante divisioni della mantissa e conseguenti variazioni dell' esponente della potenza di 2, in modo da avaere lo stesso esponente del maggiore e mantissa non più normalizzata:
1.00000000000000000000000 (23 zeri) ed esponente 20 = 0.00000000000000000000000001 (26 zeri a sinistra di 1) ed esponente 46.

A questo punto si possono sommare le mantisse per ottenere la nuova mantissa: 1.00000000000000000000000001 (tra i due 1 ci sono 25 zeri). L' esponente del risultato resta 46. Ed infine, essendo  la nuova mantissa già normalizzata, si scrivono le prime 23 cifre a destra del punto nel campo mantissa del risultato per ottenere  la rappresentazione standardizzata di  2⁴⁶. Quindi
1.0 2⁴⁶ + 1.0 2²⁰ = 1.0 2⁴⁶ .

In generale, rapportando i valori alla più usuale base 10, possiamo considerare che una mantissa di 24 cifre binarie significative (incluso il bit nascosto) corrisponde approssimativamente a 7 cifre decimali significative. Se sommiamo due numeri decimali rappresentati con sole con 7 cifre significative che differiscono per più di 7 ordini di grandezza, il risultato (entro le sette cifre significative) è indistinguibile dal maggiore tra i due addendi.

La proprietà ii) è all' origine della possibilità di uscire al di fuori dell' intervallo dei valori rappresentabili mediante le operazioni aritmetiche. Se lo "sfondamento" è nella direzione di andare al di là del massimo  valore assoluto possibile, si parla di overflow, e il risultato sarà  uno dei due valori eccezionali +Inf e -Inf. Mentre, se si  arriva a valori inferiori invalore assoluto al più piccolo valore denormalizzato diverso da zero, si parla di underflow e il risultato viene considerato esattamente uguale a zero.
Es. con 32 bit  (10^-45)² vale esattamente zero.

La proprietà iii) discende anch' essa dalla precisione finita:
La minima distanza non nulla tra due reali è  dell' ordine di 10 ^-45 attorno allo zero mentre diviene dell' ordine di 10 ³¹ in prossimità dell' estremo superiore dell' insieme.

Infine occorre aver coscienza anche del punto iv) per poter comprendere come mai conti fatti a partire da costanti numeriche descrivibili esattamente con un numero finito di cifre significative in notazione decimale possano corrispondere a calcoli approssimati in corrispondenza di  valori per cui non esiste una conversione binaria dotata di un numero finito di cifre significative.

Anche qui un esempio può aiutare a capire. Consideriamo il risultato della divisione 1/10.

In base 10  è esprimibile con un numero finito di  cifre decimali diverse da zero  ( 1/10 = 0.100000...₁₀ ).  Pertanto la rappresentazione finita ottenuta troncando gli zeri finali non introduce nessuna inesattezza nella rappresentazione decimale.

In base 2 lo stesso numero è rappresentato da  0.000110011001100110011... ₂ cioè corrisponde ad una rappresentazione  periodica di periodo 0011 ( e antiperiodo 0). Se abbiamo solo n bit per rappresentare questo numero dovremo necessariamente approssimarlo (troncando o arrotondando).  Una conseguenza pratica importante è che, mentre  in aritmetica decimale con un numer finito di cifre i prodotti   n*0.1 (n=1,2,3,....) assumono periodicamente valori in cui la parte decimale è tutta nulla, in aritmetica binaria con un numero  finito di cifre questo non è più vero  e potremmo scoprire che su alcuni sistemi 0.1*20.0 non è  uguale a 2.0 !

Da questa peculiarità della rappresentazione dei reali si ricava che possiamo considerare un numero con virgola del computer come un' approssimazione del valore vero a meno di un errore relativo, dipendente dal numero, maggiorato dalla precisione macchina ε_M. Quindi in generale potremo scrivere:
x_comp=x(1+ε_x) dove |ε_x|< ε_M dipende da x.

N.B. La precisione macchina definita come sopra dipende dal tipo di arrotondamento utilizzato. La funzione o costante epsilon messa a disposizione da linguaggi di programmazione di alto livello come C, C++, Fortran differisce dalla precisione macchina per un fattore 2, quando, come di solito avviene, si utilizza ' arrotondamento al numero rappresentabile più vicino.  Pertanto, epsilon(1.0) del Fortran è due volte la precisione macchina per il tipo real di default. Tuttavia in molti casi si è interessati solo all' ordine di grandezza decimale della precisione macchina e si può ignorare l' eventuale fattore 2.