Come si `e visto, quello che viene rappresentato all’interno di un computer
`e solo un sottoinsieme di R. Vediamo ora cosa accade alle operazio-ni aritmetiche elementari quando gli operandi sono numeri macchina.
Indichiamo le operazioni macchina (per distinguerle dalle operazioni a-ritmetiche) con i simboli ⊕, ª, ⊗, ®.
Anzitutto si ricordi che le operazioni vengono eseguite utilizzando ap-posite zone di memoria della ALU (Arithmetic and Logic Unit), dette accumulatori o registri. Se in memoria centrale vi sono a disposizione t cifre per la mantissa, negli accumulatori di norma ve ne `e un numero su-periore (talvolta anche il doppio) in modo da aumentare la precisione del calcolo. Ma anche questa accortezza, in certe condizioni, non pu`o evitare che nel calcolo si producono degli errori, talvolta anche grossolani.
Supponiamo di dover eseguire, utilizzando il computer, l’operazione x+y che indichiamo con x⊕y. Anzitutto quello che sar`a memorizzato, per quanto riguarda gli operandi, `e una loro approssimazione, ovvero fl(x) e fl(y). Inoltre, il risultato della somma tra fl(x) e fl(y) verr`a ulteriormente approssimato in quanto nella restituzione del risultato, si ritorner`a ad avere t cifre per la mantissa. Pertanto:
2.4. Operazioni aritmetiche floating-point 27
x ⊕ y = fl(fl(x) + fl(y)) = (fl(x) + fl(y))(1 + ε1)
con |ε1| ≤ eps. Questo significa che, oltre agli errori di assegnazione, ad ogni addizione macchina si introduce un ulteriore errore. Ci`o `e vero anche per le altre operazioni, ovvero si ha
x ª y = fl(fl(x) − fl(y)) = (fl(x) − fl(y))(1 + ε2) x ⊗ y = fl(fl(x) × fl(y)) = (fl(x) × fl(y))(1 + ε3) x ® y = fl(fl(x)/fl(y)) = (fl(x) / fl(y))(1 + ε4) con |ε2|, |ε3|, |ε4| ≤ eps.
2.4.1 Propriet`a
Le operazioni su F non godono di tutte le propriet`a delle corrispondenti operazioni su R.
L’unica propriet`a che resta valida `e la propriet`a commutativa ovvero x ⊕ y = y ⊕ x
x ⊗ y = y ⊗ x
La propriet`a associativa e la distributiva non sono pi`u valide! Si ha infatti x ⊕ (y ⊕ z) 6= (x ⊕ y) ⊕ z
x ⊗ (y ⊗ z) 6= (x ⊗ y) ⊗ z x ⊗ (y ⊕ z) 6= (x ⊗ y) ⊕ (x ⊗ z) x ⊗ (y ª z) 6= (x ⊗ y) ª (x ⊗ z) Anche altre propriet`a risultano non pi`u valide
(x ⊗ y) ® y 6= x (x ® y) ⊗ y 6= x
(x ⊗ y) ® z 6= (x ® z) ⊗ y
Relazione anomala. Un’altra violazione importante `e data dalla cosid-detta relazione anomala che sancisce la non unicit`a dell’elemento neutro dell’addizione e della sottrazione (ovvero dello zero). Tale relazione pu`o essere cos`ı espressa:
Se |fl(y)|
|fl(x)| < eps, allora x ⊕ y = fl(x) x ª y = fl(x).
Ci`o accade quando x ed y hanno ordini di grandezza molto diversi.
13 13.5 14 14.5 15 15.5 16 16.5 0
0.5 1 1.5 2
q
((x+y)−x)/y
Figura 2.2: Effetti dell’aritmetica del computer
Vediamo un esempio: consideriamo la seguente espressione algebrica (x + y) − x
y (2.2)
che nell’insieme R fornisce 1.0 come risultato, qualsiasi sia y 6= 0. Se prendiamo x = 1.0 ed y < eps, utilizzando un computer otterremo 0, a causa della relazione anomala. Se applichiamo in (2.2) la propriet`a commutativa prima e l’associativa poi, otteniamo la seguente espressione (anch’essa matematicamente uguale ad 1.0)
y + (x − x)
y ,
e con il computer otterremo, con gli stessi valori di x e di y, il risultato esatto 1.
Ma il fenomeno `e ben pi`u complicato. Infatti, diamo a y dei valori vicini alla precisione macchina (supponendo di lavorare con 8 byte), e precisamente y = 10−q con q = 13.0 + k × 0.01 per k = 0, . . . , 350. Si ottengono per l’espressione (2.2) i risultati della figura 2.2. Si vede che,
2.4. Operazioni aritmetiche floating-point 29 a seconda del valore di q, il risultato dell’espressione varia nell’intervallo [0, 2]. I valori di y sono decrescenti e, a partire da quando si realizza la relazione anomala, si ottiene sempre zero.
La non validit`a della propriet`a associativa assume particolare rilevanza quando si opera con numeri vicini ad amin oppure a amax. Vediamo, ad esempio, cosa accade alle seguenti espressioni algebriche equivalenti quando assegnamo ad x, y e a z, valori elevati come ordine di grandezza (utilizzando 4 byte e quindi con amax dell’ordine di 1038):
x ×y
z = x × y z
Sia x ' 1030, y ' 1030, z ' 1025. Con la prima formula otteniamo un risultato numerico dell’ordine di 1035, mentre con la seconda abbiamo una condizione di overflow ed otteniamo Inf.
Analogamente assegnamo dei valori aventi ordine di grandezza molto piccolo (amin`e dell’ordine di 10−38). Sia x ' 10−30, y ' 10−30, z ' 10−25. Con la prima formula otteniamo un risultato numerico dell’ordine di 10−35, mentre con la seconda abbiamo una condizione di underflow ed otteniamo 0.
2.4.2 Errori
Consideriamo ora l’errore relativo, e cambiamo leggermente notazione.
Indichiamo
εr(x) = |x − fl(x)|
|x|
per ogni x ∈ R.
Sia
ε⊕r(x, y) = |(x + y) − (x ⊕ y)|
|x + y| , con x, y ∈ R,
l’errore commesso nel calcolo della somma di due numeri. In modo simi-lare si possono definire εªr(x, y), ε⊗r(x, y), ε®r(x, y).
E possibile dimostrare che solamente le operazioni macchina ⊗ e ® sono` stabili rispetto agli errori di arrotondamento, ovvero se εr(x) e εr(y) sono piccoli, allora lo sono anche ε⊗r(x, y) ed ε®r(x, y). Un’operazione macchina si dice stabile quando
∃ c > 0, tale che ε¯r(x, y) ≤ c (εr(x) + εr(y)) , ∀x, y ∈ R dove ¯ rappresenta una qualsiasi operazione macchina.
Vediamo cosa accade quando deve essere eseguita una moltiplicazione (o una divisione). Si debba eseguire z = x × y (oppure z = x / y), con x, y, z ∈ R. Anzitutto i due valori reali a seguito dell’assegnazione in memoria, divengono fl(x) e fl(y). Poi il computer trasferisce dalla memoria agli accumulatori i due valori fl(x) ed fl(y) senza modificare la normalizzazione ma solamente aggiungendo degli zeri alla destra per completare i bit addizionali a disposizione degli accumulatori. Successiva-mente viene effettuata l’operazione tra le mantisse e separataSuccessiva-mente viene calcolato l’esponente del risultato. Il risultato viene poi trasferito nuo-vamente in memoria, effettuando la normalizzazione e l’arrotondamento necessari per ricondursi a t cifre di mantissa.
Di seguito riportiamo alcuni esempi, supponendo di lavorare (solo a scopo esplicativo) in un sistema a base decimale (con la base binaria il discorso sar`a analogo), con t = 8 cifre decimali a disposizione per la mantissa in memoria e 2t = 16 cifre decimali a disposizione per la mantissa negli accumulatori.
Esempio 1
Sia x = 0.27531012 × 10−2 ed y = 0.35720021 × 104.
Memoria Accumulatore
fl(x) = 0.27531012 × 10−2 → 0.2753101200000000 × 10−2 × fl(y) = 0.35720021 × 104 → 0.3572002100000000 × 104 fl(z) = 0.98340833 × 101 ← 0.0983408326791252 × 102
Con tali valori si ha x = fl(x) ed y = fl(y). Nel caso di una molti-plicazione, il prodotto di due mantisse di lunghezza massima t fornisce un risultato di lunghezza al massimo 2t. Pertanto il risultato `e esatto nell’accumulatore. L’unico errore che viene commesso `e quello di asse-gnazione durante la restituzione in memoria quando il risultato viene normalizzato e ridotto a t cifre di mantissa.
Esempio 2
Sia x = 0.57203146 × 10−1 ed y = 0.27001052 × 102.
Memoria Accumulatore
fl(x) = 0.57203146 × 10−1 → 0.5720314600000000 × 10−1 / fl(y) = 0.27001052 × 102 → 0.2700105200000000 × 102 fl(z) = 0.21185525 × 10−2 ← 2.118552491954754 × 10−3
2.4. Operazioni aritmetiche floating-point 31 Anche in questo esempio non vi `e errore di assegnazione, ovvero x = fl(x) ed y = fl(y). Nel caso della divisione, il risultato nell’accumulatore non
`e sempre esatto (in quanto possono prodursi pi`u di 2t cifre). Vi `e quindi un errore nel risultato dell’accumulatore in quanto sar`a arrotondato a 2t cifre. Nella restituzione in memoria l’errore di assegnazione sar`a almeno nella t-esima cifra, a causa dell’arrotondamento e della normalizzazione.
Errore di cancellazione. Gli esempi mostrano che le moltiplicazioni e le divisioni macchina non producono errori molto elevati. Purtroppo ci`o non `e sempre vero per le operazioni macchina ⊕ e ª. In talune condizioni si pu`o realizzare uno degli errori pi`u deleteri, chiamato l’errore di cancellazione. Esso si verifica quando si sommano tra loro numeri quasi uguali in modulo (ma di segno diverso) oppure quando si sottraggono numeri quasi uguali tra loro.
E possibile infatti dimostrare che`
ε⊕r(x, y) ≤ eps + (1 + eps) µ
εr(x) |x|
|x + y|+ εr(y) |y|
|x + y|
¶
con x, y ∈ R. Pertanto, quando y ' −x, il termine a destra (la maggio-razione) pu`o essere anche molto grande e pu`o permettere ad ε⊕r(x, y) di essere molto elevato. Un discorso analogo vale per la sottrazione ª.
Cerchiamo ora di descrivere cosa accade quando deve essere eseguita una somma (o una differenza) tra due numeri in modo da capire perch`e tale operazione pu`o essere cos`ı imprecisa. Si debba eseguire z = x + y.
Il computer trasferisce dalla memoria agli accumulatori i due valori fl(x) ed fl(y) senza modificare quello tra i due operandi che risulta essere il maggiore in valore assoluto, e modificando l’altro operando in modo che abbia lo stesso esponente di quello maggiore in valore assoluto (vengono quindi eventualmente aggiunti degli zeri davanti alla prima cifra a1).
Anche in tal caso, in tale trasferimento, vengono aggiunti degli zeri alla destra per completare i bit addizionali a disposizione degli accumula-tori. Successivamente viene effettuata l’operazione ed il risultato viene poi trasferito nuovamente in memoria, effettuando la normalizzazione e l’arrotondamento necessari per ricondursi a t cifre di mantissa.
Riportiamo alcuni esempi supponendo ancora di lavorare in un sistema a base decimale, con t = 8 cifre decimali per la mantissa in memoria e 2t = 16 cifre decimali per la mantissa negli accumulatori. Per un sistema di questo tipo, utilizzando la formula (2.1), si ha eps = 0.5 × 10−7.
Esempio 1
Sia x = 0.23487757 × 103 ed y = 0.56799442.
Memoria Accumulatore
fl(x) = 0.23487757 × 103 → 0.2348775700000000 × 103 + fl(y) = 0.56799442 × 100 → 0.0005679944200000 × 103 fl(z) = 0.23544556 × 103 ← 0.2354455644200000 × 103
Abbiamo x = fl(x) ed y = fl(y). Per quanto riguarda l’addizione, essa viene eseguita nell’accumulatore in modo esatto (ovvero conservando esattamente i valori fl(x) ed fl(y)) e l’unico errore introdotto risulta essere quello di assegnazione durante la restituzione del risultato in memoria (poich`e dobbiamo conservare solo t = 8 cifre della mantissa).
Esempio 2
Sia x = 0.56543451 × 106 ed y = 0.21554623 × 10−4.
Memoria Accumulatore
fl(x) = 0.56543451 × 106 → 0.5654345100000000 × 106 + fl(y) = 0.21554623 × 10−4 → 0.0000000000215546 × 106 fl(z) = 0.56543451 × 106 ← 0.5654345100215546 × 106
In questo esempio, poich`e la grandezza dei due operandi `e abbastanza diversa (sono distanti tra loro) il trasferimento di fl(y) nell’accumulatore produce un errore (si perdono due cifre). Pertanto la somma calcolata nell’accumulatore non sar`a esatta (ovvero non verr`a calcolato esatta-mente fl(x) + fl(y)). Inoltre, restituendo il risultato in memoria (poich`e dobbiamo conservare solo t = 8 cifre della mantissa) si ottiene fl(z) = fl(x), ovvero si realizza la relazione anomala. Infatti |fl(y)| / |fl(x)| `e dell’ordine di 10−10 e quindi minore di eps.
Esempio 3
Sia x = 1.0 ed y = 0.5 × 10−7.
Memoria Accumulatore
fl(x) = 0.10000000 × 101 → 0.1000000000000000 × 101 + fl(y) = 0.50000000 × 10−7 → 0.0000000050000000 × 101 fl(z) = 0.10000001 × 101 ← 0.1000000050000000 × 101
In questo esempio abbiamo x = fl(x) = 1 e y = fl(y) = eps. Si vede che la somma viene eseguita correttamente negli accumulatori e, nella
resti-2.4. Operazioni aritmetiche floating-point 33 tuzione del risultato in memoria, a causa dell’arrotondamento si ottiene fl(z) = 1.0000001. Se avessimo utilizzato per y il valore 0.4 × 10−7 si sarebbe realizzata la relazione anomala. Dunque eps `e effettivamente il pi`u piccolo valore per il quale fl(1 + eps) > 1.
Esempio 4
Sia x = 0.5654328749876 ed y = −0.5654328510104.
Memoria Accumulatore
fl(x) = 0.56543287 × 100 → 0.5654328700000000 × 100 + fl(y) = −0.56543285 × 100 → −0.5654328500000000 × 100 fl(z) = 0.20000000 × 10−7 ← 0.0000000200000000 × 100
In questo esempio, abbiamo espressamente inserito del valori x 6= fl(x) ed y 6= fl(y), per enfatizzare quanto accade. L’addizione negli accumulatori viene eseguita in modo esatto (ovvero conservando esattamente i valori fl(x) ed fl(y)). Tuttavia, nella restituzione del risultato in memoria, gli zeri che seguono la cifra 2 non hanno alcun significato! Essi provengono solo dal fatto che negli accumulatori abbiamo aggiunto degli zeri alla destra della mantissa. Gli zeri del risultato non hanno significato come non ne avrebbe avuto qualsiasi altra cifra decimale che avessimo messo al loro posto. Infatti, la somma x + y darebbe 0.239772 × 10−7 e quindi l’errore relativo (approssimato a 3 cifre decimali) `e εr(z) = 0.166, che
`e elevato. Nei calcoli successivi, utilizzando fl(z) (anzich`e z) `e come se lavorassimo con solo 1 cifra decimale esatta. `E l’errore di cancellazione.
Regola per l’errore di cancellazione. Siano mxed my le mantisse di due numeri x ed y aventi lo stesso segno (rispettivamente segno opposto) che hanno coincidenti le prime r cifre. La differenza (rispettivamente la somma) tra questi due numeri ha solamente le prime (t − r) cifre del risultato che possono considerarsi significative (t rappresenta il numero di cifre significative che possono essere rappresentate in memoria). Tutte le altre cifre non hanno alcun significato.
Diamo ora alcuni esempi utilizzando la semplice e la doppia precisione per mettere in luce come i calcoli in semplice precisione siano affetti da errori anche rilevanti. Questi risultati sono stati ottenuti su di un com-puter, mentre gli esempi precedenti, svolti a mano, servivano unicamente a mostrare come vengono effettuate le operazioni.
semplice precisione
x y xª y x⊕ y
123456789.0 123456788.0 8.0 246913568.0 123456789.0 123456790.0 0.0 246913584.0 0.56543451×106 0.21554623×10−4 565434.5 565434.5 1.0 0.5 × 10−6 0.999999523 1.00000048 0.5654328749876 0.5654328510104 0.0 1.13086569 0.3333333333 0.1111111111 0.222222239 0.444444448
doppia precisione
x y xª y x⊕ y
123456789.0 123456788.0 1.0 246913577.0
123456789.0 123456790.0 −1.0 246913579.0
0.56543451×106 0.21554623×10−4 565434.509978 565434.510022
1.0 0.5 × 10−6 0.9999995 1.0000005
0.5654328749876 0.5654328510104 0.239772000032×10−7 1.130865726 0.3333333333 0.1111111111 0.2222222222 0.4444444444
2.4.3 Esempi sull’errore di cancellazione
Talvolta `e possibile modificare le proprie espressioni in modo da caute-larsi nei confronti di un possibile errore di cancellazione. Semplici trasfor-mazioni di tipo algebrico o modifiche nell’algoritmo possono aiutarci ad evitare tale errore.
Vediamo alcuni esempi.
Calcolo delle radici di un polinomio di secondo grado
A tutti `e noto che le radici del polinomio ax2+ bx + c = 0 sono date da x1 = −b −√
b2− 4ac 2a x2 = −b +√
b2− 4ac
2a .
(2.3)
Se |4ac| << b2 una delle due soluzioni sar`a mal calcolata, in quanto
√b2− 4ac ' |b| e quindi si verificher`a un errore di cancellazione a causa della differenza di due numeri quasi uguali.
Ad esempio, se a = 10−3, b = 0.8 et c = −1.2 × 10−5, le soluzioni esatte sono
x1 = −800 x2 = 1.5 × 10−5.
2.4. Operazioni aritmetiche floating-point 35 La prima soluzione, fl(x1), su di un computer, `e ben calcolata mentre per la seconda si ha fl(x2) = 2.980232 × 10−5, con εr(x2) ' 0.9868. Per evitare tale errore, utilizziamo il fatto che, data una soluzione x1 della nostra equazione, la seconda soluzione pu`o essere calcolata come
x2= c ax1
. (2.4)
Pertanto, sapendo che la soluzione ben calcolata `e quella che evita l’e-ventuale errore di cancellazione, ovvero `e sempre data da
x1= −b − sign(b)√
b2− 4ac
2a (2.5)
dove sign(b) rappresenta il segno del numero b, anzich`e utilizzare le for-mule (2.3), sar`a meglio usare le forfor-mule (2.4) e (2.5).
Vediamo nella figura 2.3 i risultati ottenuti per la soluzione x2 (quella che pu`o essere mal calcolata) con le formule (2.3) (linea continua) e quelli ottenuti con le formule (2.4, 2.5) (linea tratteggiata) nel caso in cui si abbia a = 10−3, b = 0.8 et c = −(1 + k × 0.05) × 10−5per k = 0, . . . , 100.
0 1 2 3 4 5 6 7 8 9
x10-5
-6 -5.5 -5 -4.5 -4 -3.5 -3 -2.5 -2 -1.5 -1
x10-5 valore di c
x_2
Figura 2.3: Calcolo degli zeri di ax2+ bx + c
Formule alternative
Vediamo ora alcuni esempi di espressioni che potenzialmente potrebbero essere affette dall’errore di cancellazione. Semplici modifiche di tipo alge-brico, ci permettono di considerare delle espressioni equivalenti che non presentano tale problema.
Esempio 1 Sia |δ| << |x|.
√x + δ −√
x = δ
√x + δ +√ x Esempio 2
Sia |δ| << |x|.
cos(x + δ) − cos(x) = −2 sinδ 2sin
µ x + δ