Aritmetica  dei  computers

L' aritmetica dei computers, 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.  E' inoltre alla base della possibilita' di implementare in modo semplice l' aritmetica modulo  2ⁿ.
Se l' aritmetica intera (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 un'  implementazione dell' aritmetica modulo 2 ⁿ come definita in algebra (si ricorda che l'  aritmetica modulo p corrisponde all'  adattamento dell'  aritmetica usuale agli insiemi  i cui elementi siano classi di equivalenza di numeri interi rispetto alla relazione di equivalenza costituita dalla proprietà "avere lo stesso resto nella divisione per p").

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 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 definito 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 possibilita' è 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. Pero' la cella grigia non esiste nel registro del nostro processore. Quindi il bit corrispondente "si perde" lasciando come risultato  l' intero contenuto nelle sole celle bianche: 1 che corrisponde a     257 mod 2⁸.

Se abbiamo a disposizione n bit e vogliamo rappresentare interi negativi e positivi (in numero uguale), la soluzione più semplice è quella di usare uno dei bit per indicare il segno e gli altri per la rappresentazione in base 2 usuale. In questo caso potremo 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.
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.

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 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 tre rappresentazioni qui descritte (con bias = 127 ).
 
 
 

Rappresentazione dei numeri con la virgola - cifre significative.

x.yxwt  10^e  oppure   0.xyxwt  10 ^e+1 .  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 ambiguita' 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  (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.

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 dagli ultimi '80  anni, si è imposto lo standard  IEEE 754  che prevede almeno due rappresentazioni:
 

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.

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 valori tra 0 e 255.

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 . Percio' 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 ⁺³⁸ .

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.

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   10^-37 al prezzo di un crescente perdita di precisione (diminuzione delle cifre significative) man mano che ci si avvicina allo zero.

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.

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. In questo caso il campo esponente è di 11 bit  (e la rappresentazione è  mediante interi con bias 1023)  mentre quello mantissa diviene di 52 bit  (con in più   il bit nascosto per i numeri normalizzati).

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 da zeri  si incrementa l'  ultima di 1 se è dispari mentre la si lascia invariata se pari.

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 il caso a 64 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 B sia più piccolo di A in valore assoluto per più di un fattore 2^-23 perché sommare A a B divenga equivalente a sommare 0 ad A.

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 rappresenati 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, mentre se si  arriva a valori inferiori al più piccolo valore denormalizzato diverso da zero, si parla di underflow e il risultato viene considerato esattamente uguale a 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 puo' 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.

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 (a rigore, nel caso di aritmetica con arrotondamento, l' errore relativo è maggiorato da epsilon/2 a meno di correzioni in epsilon², tuttavia, se siamo interessati all' ordine di grandezza dell' errore, la differenza tra epsilon ed epsilon/2 è inessenziale sia per la rappresentazione a 32, sia per quella a 64 bit). Quindi in generale potremo scrivere:
x_comp=x(1+e_x) dove |e_x|<epsilon dipende da x.