Capitolo 1 I NUMERI 1.1 Basi di numerazione

(1)

Capitolo 1 I NUMERI

1.1 Basi di numerazione

Un numero `e una sequenza finita di simboli detti cifre. I simboli utilizzati dipendono dal sistema di numerazione utilizzato.

Il sistema di numerazione usualmente utilizzato `e detto posizionale decimale, dove posizionale indica che il valore di una cifra dipende dalla posizione che essa ha all’interno di un certo numero, e decimale indica che la base utilizzata `e b = 10. I simboli utilizzati in base 10 sono 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9.

Ad esempio, se scriviamo il numero 9102.917 intendiamo esprimere il numero

9 × 10³+ 1 × 10²+ 0 × 10¹+ 2 × 10⁰+ 9 × 10⁻¹+ 1 × 10⁻²+ 7 × 10⁻³

Si noti che la notazione posizionale non `e l’unica esistente. Esistono anche altri sistemi di numerazione, ad esempio la numerazione romana, in cui ogni cifra del numero rappresenta sempre il proprio valore (M = 1000, X = 10, V = 5, I = 1, . . .).

Nulla vieta, per rappresentare un numero reale a ∈ R, di utilizzare basi diverse dalla decimale. Sia dunque b ∈ N una base qualsiasi. Per rappresentare i numeri in base b sono necessari esattamente b simboli.

Se 2 ≤ b ≤ 10 si usano come simboli le prime b cifre della base decimale, ovvero i simboli 0, 1, . . . , b − 1.

Se b > 10, si aggiungono alle 10 cifre decimali le lettere maiuscole dell’alfabeto.

Ad esempio:

1

(2)

b cifre 2 0 1

8 0 1 2 3 4 5 6 7

16 0 1 2 3 4 5 6 7 8 9 A B C D E F

Quindi, generalizzando, un numero a ∈ R pu`o essere espresso in base bnella forma

a = ± (aⁿan−1an−2. . . a1a0. a−1a−2. . .)b= ± Xn i=−∞

aibⁱ

con ai cifre della base b.

La parte che precede il punto di radice viene detta parte intera e quella che segue il punto di radice viene detta parte frazionaria.

Se lavoriamo con una base generica b, è importante indicare in quale base è espresso un numero dato, in quanto il suo valore varia al variare di b. Quando vi possono essere ambiguità nella scrittura, è opportuno indicare come pedice il valore di b.

Ad esempio:

123.110 = 1 × 10²+ 2 × 10¹+ 3 × 10⁰+ 1 × 10⁻¹= 123.110

123.17 = 1 × 7²+ 2 × 7¹+ 3 × 7⁰+ 1 × 7⁻¹= 66.142857142 . . .10

123.14 = 1 × 4²+ 2 × 4¹+ 3 × 4⁰+ 1 × 4⁻¹= 27.2510

E anche evidente che lo stesso numero necessita di un numero di cifre` maggiore o uguale, al diminuire della base b.

Ad esempio:

25310 = FD16

= 3758

= 111111012

1.1.1 Cambiamento di base

Si è visto che lo stesso numero reale può essere rappresentato rispetto a differenti basi. Noi siamo ovviamente abituati ad operare in base 10, ma, ad esempio, i computer lavorano con numeri espressi in base 2 e quindi è importante conoscere le modalità di passaggio da una base all’altra e le problematiche che tali cambiamenti di base possono creare.

E noto che i numeri reali si possono suddividere in due sottoinsiemi: i` numeri razionali (insieme Q) ed i numeri irrazionali (insieme I). A loro volta i numeri razionali possono essere divisi in due categorie: i numeri a parte frazionaria finita ed i numeri periodici (e come tali illimitati).

(3)

1.1. Basi di numerazione 3 Per ambedue le categorie `e possibile trovare la frazione generatrice (cio`e la frazione n

m tale che a = n

m, con n ed m interi, espressi in base b):

Numeri finiti: Dato un numero a, rappresentato in base b, con parte frazionaria finita, la frazione generatrice ha come numeratore tutto il numero (privato del punto di radice e degli zeri davanti alla prima cifra significativa) e, come denominatore, un 1 seguito da tanti zeri quante sono le cifre che formano la parte frazionaria.

Ad esempio calcoliamo la frazione generatrice del numero 73.4568

ed anche la corrispondente frazione generatrice decimale (ottenuta convertendo numeratore e denominatore in base 10):

73.4568= 734568× 8⁻³=µ 73456 1000

¶

8

=µ 30510 512

¶

10

=µ 15255 256

¶

10

Numeri periodici: Dato un numero a, periodico in base b, la frazione generatrice ha per numeratore tutto il numero (privato del punto di radice e degli zeri davanti alla prima cifra significativa) meno il numero ottenuto togliendo le cifre del periodo (e trascurando il punto di radice) e per denominatore il numero formato da tante cifre b − 1 quante sono le cifre del periodo, seguite da tanti zeri quante sono le cifre dell’antiperiodo (che `e la parte che segue il punto di radice e che precede il periodo).

Ad esempio:

Sia b = 16. Calcoliamo le frazioni generatrici dei numeri 0.2D16 e 0.AE16 ed anche le corrispondenti frazioni generatrici decimali:

Primo numero:

0.2D16=µ 2D − 2 F0

¶

16

=µ 2B F0

¶

16

=µ 43 240

¶

10

Secondo numero:

0.AE16=µ AE − A F0

¶

16

=µ A4 F0

¶

16

=µ 41 60

¶

10

Il passaggio da una base b1 ad una base b2 non conserva necessaria- mente la tipologia del numero e questo, come vedremo, far`a parte di una delle caratteristiche da tener presente quando si lavora con i computer.

Vediamo alcune regole da ricordare relativamente al cambiamento di base di un numero:

(4)

• Se un numero `e illimitato non periodico in una certa base, lo `e anche in tutte le altri basi possibili.

• Un numero finito in una certa base, pu`o essere finito oppure periodico in un’altra base.

• Un numero periodico in una certa base, pu`o essere periodico oppure finito in un’altra base.

Dato un numero razionale a espresso in base b1, `e possibile sapere anticipatamente se esso `e, o meno, finito in base b2:

Si calcola la frazione generatrice decimale, ovvero a = n

m con n ed m espressi in base 10. Se m risulta essere una potenza di b2(ovvero m = b^e₂ con e ∈ N) allora in base b2 il numero sar`a finito.

Ad esempio:

Esempio 1

Controlliamo se il numero decimale finito 872.4310 `e finito anche in base 2.

872.4310=µ 87243 100

¶

10

=µ 87243 2²· 5²

¶

10

e poichè tale frazione è irriducibile, il numero finito in base decimale non lo è certamente in base binaria.

Esempio 2

Calcoliamo in quale/i base/i il numero decimale periodico 0.¯410 `e finito.

0.410 =µ 4 9

¶

10

=µ 4 3²

¶

10

pertanto il numero `e finito in base 3 ed in base 9 e si ha 0.410= 0.113= 0.49

Vediamo ora come convertire un numero reale da una base b1 ad una base b2. Vi sono differenti modalit`a per effettuare la conversione a seconda dei valori assunti da b1 e da b2.

Caso b₂ = 10

Numero finito: Vi sono due possibili algoritmi per calcolare il valore decimale (che potrebbe non essere finito) di un numero reale (finito) espresso in base qualsiasi b1:

(5)

1.1. Basi di numerazione 5 1. Utilizzo della notazione posizionale: si calcola il valore utilizzando

la definizione

a = ± (anan−1an−2. . . a1a0.a−1a−2. . . a−m)b= ± Xn i=−m

aibⁱ

Vediamo alcuni esempi:

Esempio 1

2401.23145= 2 × 5³+ 4 × 5²+ 1 + 2 5+ 3

5² + 1 5³ + 4

5⁴ = 351.534410

Esempio 2

110110.1012= 1 × 2⁵+ 1 × 2⁴+ 1 × 2²+ 1 × 2 +1 2+ 1

2³ = 54.62510

Esempio 3

21.213= 2 × 3 + 1 +2 3 + 1

3² = 7.710

2. Utilizzo dell’Algoritmo di Horner: si considerano separatamente la parte intera e la parte frazionaria del numero e poi si procede come segue:

Parte intera: Partendo dalla prima cifra significativa alla sinistra, verso destra, si moltiplica il valore per la base b1 e si aggiunge la cifra successiva. Il risultato si moltiplica per la base b1e si aggiunge la cifra successiva, e cos`ı via sino all’esaurimento delle cifre. Ovvero

(anan−1an−2. . . a1a0)b=

((· · · ((aⁿ×b1+an−1)×b1+an−2)×b1+· · · )×b1+a1)×b1+a0

Parte frazionaria: Partendo dalla prima cifra significativa alla destra della parte frazionaria, verso sinistra, fino al punto di radice si divide il valore per la base b1 e si aggiunge la cifra precedente.

Il risultato si divide per la base b1 e si aggiunge la cifra precedente e cos`ı via sino all’esaurimento delle cifre, terminando con una divisione per b1. Ovvero

(0.a−1a−2a−3. . . a−m+1a−m)b =

((· · · ((a−m: b1+a−m+1) : b1+a−m+2) : b1+· · · ): b1+a−1) : b1

(6)

Vediamo un esempio:

110110.0012 =

parte intera → ((((1×2 +1)× 2 +0)× 2 +1)× 2 +1)× 2 + 0

→ 5410

parte frazionaria → ((1 : 2 + 0) : 2 + 0) : 2

→ 0.12510

= 54.12510

Numero periodico: Supponiamo ora che il numero espresso in base b₁ abbia parte frazionaria periodica. Come possiamo procedere per calcolare la parte frazionaria decimale, visto che essendo illimitata la parte frazionaria in base b1, non possiamo utilizzare n`e la notazione posizionale n`e l’algoritmo di Horner? Possiamo far uso della regola di determinazione della frazione generatrice decimale di un numero periodico in base qualsiasi precedentemente indicata.

Vediamo qualche esempio:

Esempio 1

Convertiamo il numero 0.14 in base b2 = 10:

0.14=µ 1 3

¶

4

=µ 1 3

¶

10

=µ 3 9

¶

10

= 0.310

Esempio 2

Convertiamo il numero 0.2D16 in base b2= 10:

0.2D16=µ 2D − 2 F0

¶

16

=µ 2B F0

¶

16

=µ 43 240

¶

10

= 0.1791610

Esempio 3

Convertiamo il numero 4.315 in base b2= 10:

4.315=µ 431 − 43 40

¶

5

=µ 333 40

¶

5

=µ 93 20

¶

10

= 4.6510

Caso b₁ = 10

Numero finito: Sia dato un numero decimale finito che si vuole convertire in base b2 (e in tale base potrebbe essere non finito). Bisogna anzitutto distinguere la parte intera dalla parte frazionaria ed operare in modo differente:

(7)

1.1. Basi di numerazione 7 Parte intera: L’algoritmo di conversione ha sempre termine e consiste nell’effettuare iterativamente delle divisioni per la nuova base b2, fermandosi solo quando si ottiene un quoziente nullo. I resti delle divisioni effettuate, presi in ordine inverso a quello con cui sono stati calcolati, formano la parte intera del numero convertito. Ov- viamente i resti ottenuti sono dei numeri decimali il cui valore `e

< b2. Se b2 > 10, per formare il numero nella nuova base, ai resti decimali vanno sostituiti (se necessario) i corrispondenti simboli della nuova base di numerazione.

Parte frazionaria: Si moltiplica ripetutamente per la base b2 e si tol- gono le parti intere che, prese nell’ordine, formeranno la parte frazionaria del numero espresso nella nuova base b2. Anche in tal caso le parti intere ottenute sono dei numeri decimali il cui valore `e

< b2 e, quando b2 > 10, per formare il numero nella nuova base ad essi vanno sostituiti (se necessario) i corrispondenti simboli della nuova base di numerazione.

Come è facilmente intuibile, non è assolutamente certo che tale procedura termini dopo un numero finito di passi. Vi sono infatti due possibilità:

1. Ad un certo passo si ottiene come valore del prodotto un numero con parte frazionaria nulla. In questo caso il procedimento si arresta ed il numero nella nuova base sar`a finito.

2. Ad un certo passo si ottiene come valore del prodotto un numero con parte frazionaria precedentemente gi`a trovata durante i passi precedenti. In questo caso si `e individuato il periodo della parte frazionaria del numero espresso nella nuova base b2.

Vediamo ora alcuni esempi, utilizzando le seguenti convenzioni grafiche:

Nella procedura di divisione per la parte intera del numero da convertire, con una freccia ascendente si indica che i resti ottenuti devono essere considerati in ordine inverso. Nella procedura di moltiplicazione per la parte frazionaria, con una freccia discendente si indica che le parti intere dedotte dai risultati delle moltiplicazioni devono essere considerate nell’ordine con il quale esse sono state ottenute; tali parti intere risultano evidenziate nel prodotto tramite una sottolineatura delle stesse e vengono ovviamente sottratte dal prodotto prima di effettuare la successiva moltiplicazione; i caratteri ? posti a fianco di un certo numero di parti intere

(8)

contigue indicano che tali cifre formeranno il periodo del numero convertito; l’eventuale periodo viene individuato quando si trova un valore da moltiplicare che sia gi`a stato considerato e i due valori coincidenti vengono indicati da un simbolo ◦ che li precede.

Esempio 1

Divisioni Quozienti Resti 967 ÷ 16 60 710 = 716

60 ÷ 16 3 1210= C16

3 ÷ 16 0 310 = 316

6

Moltiplicazione Parti intere 0.78125 ×16 = 12.5 1210 = C16

0.5 ×16 = 8.0 810= 816

0.0 ^?

Quindi

967.7812510= 3C7.C816= 3.C7C816× 16² Esempio 2

Divisioni Quozienti Resti

93 ÷ 2 46 1

46 ÷ 2 23 0

23 ÷ 2 11 1

11 ÷ 2 5 1

5 ÷ 2 2 1

2 ÷ 2 1 0

1 ÷ 2 0 1

6

Moltiplicazione Parti intere

0.625 ×2 = 1.25 1

0.25 ×2 = 0.5 0

0.5 ×2 = 1.0 1

0.0

? Quindi si ottiene

93.62510 = 1011101.1012 = 0.10111011012× 2⁷

(9)

1.1. Basi di numerazione 9 Esempio 3

20 ÷ 2 10 0

10 ÷ 2 5 0

5 ÷ 2 2 1

2 ÷ 2 1 0

1 ÷ 2 0 1

6

0.025 ×2 = 0.05 0

0.05 ×2 = 0.1 0

0.1 ×2 = 0.2 0

◦ 0.2 ×2 = 0.4 0 ?

0.4 ×2 = 0.8 0 ?

0.8 ×2 = 1.6 1 ?

0.6 ×2 = 1.2 1 ?

◦ 0.2 ^?

Avendo trovato un valore frazionario da moltiplicare, precedentemente gi`a considerato (il valore 0.2), la parte frazionaria finita del numero dato risulta essere periodica in base 2.

Si ottiene quindi

20.02510= 10100.00000112

Esempio 4

7 ÷ 7 1 0

1 ÷ 7 0 1

6

◦ 0.76 ×7 = 5.32 5 ?

0.32 ×7 = 2.24 2 ?

0.24 ×7 = 1.68 1 ?

0.68 ×7 = 4.76 4 ?

◦ 0.76 ^?

(10)

Avendo trovato un valore frazionario considerato in precedenza (il valore 0.76), la parte frazionaria finita del numero dato risulta essere periodica in base 7.

Quindi si ottiene

7.7610= 10.52147

Numero periodico: Supponiamo ora che il numero decimale abbia parte frazionaria periodica. Per la parte intera possiamo procedere come nel caso del numero finito. Ma come possiamo procedere per calcolare la parte frazionaria nella nuova base b2? Possiamo ancora usare il precedente algoritmo di moltiplicazione, ma lavorando con i cosiddetti numeri misti (intero+frazione propria).

Vediamo qualche esempio:

Esempio 1

◦ 1

3 ×2 = 2

3 = 0 + 2

3 0 ?

2

3 ×2 = 4

3 = 1 + 1

3 1 ?

◦ 1 3

?

ottenendo

0.310= 0.012

Esempio 2

◦ 2

3 ×2 = 4

3 = 1 + 1

3 1 ?

1

3 ×2 = 2

3 = 0 + 2

3 0 ?

◦ 2 3

?

ottenendo

0.610= 0.102

(11)

1.1. Basi di numerazione 11 Caso generale

Non vi sono algoritmi particolari qualora b1 o b2 non siano uguali a 10.

In tale caso la conversione deve essere fatta in due tappe, passando at- traverso la base 10 (ovvero b1 → 10 → b²).

La base 2 e le sue potenze sono molto utilizzate in informatica. Nel caso in cui si debba passare dalla base 2 alla base 2^k (o viceversa) esiste una procedura pressoch`e immediata (senza dover passare per la base 10).

Quando la base considerata `e 2^k, per rappresentare le sue 2^k−1 cifre sono necessarie, in base 2, delle k-uple di cifre binarie. Ad esempio se b = 4 = 2² le cifre 0, 1, 2, 3 in tale base sono rappresentabili dalle 4 coppie binarie (00)2, (01)2, (10)2e (11)2. Se b = 16 = 2⁴le cifre in tale base sono rappresentabili dalle 16 quaterne binarie (0000)2, (0001)2, (0010)2, . . . , (1110)2e (1111)2.

Dato quindi un numero in base 2, per trasformarlo in base 2^k `e sufficiente, a partire dal punto di radice, verso sinistra per la parte intera e verso destra per la parte frazionaria (aggiungendo eventualmente gli zeri necessari), raggruppare delle k-uple di cifre binarie e poi sostituire ad esse la corrispondente cifra nella nuova base.

Ad esempio:

Convertiamo il numero 10001.1101110112 in base b2 = 16 = 2⁴: 0001| {z } 0001

| {z } . 1101

| {z } 1101

| {z } 1000

| {z }

↓ ↓ ↓ ↓ ↓

1 1 . D D 8

e si ha

10001.1101110112= 11.DD816= 0.11DD816× 16²

Il procedimento inverso di passaggio da una base 2^k alla base 2 `e simi- lare, ma in tal caso si costruiscono, a partire dalle cifre della base 2^k, le k-uple di cifre binarie.

Ad esempio:

2 1 . 6 7 3

↓ ↓ ↓ ↓ ↓

z}|{010 z}|{

001 . z}|{

110 z}|{

111 z}|{

011 e si ottiene

21.6738= 10001.1101110112= 0.10001110111011 × 2⁵

(12)

Naturalmente tale procedimento pu`o essere utilizzato anche per passare da una base b1= 2^k¹ ad una base b2 = 2^k², con due passi: prima di passa dalla base b1 alla base 2 e poi dalla base 2 alla base b2.

Un altro vantaggio di tale conversione pressochè immediata si nota in presenza di numeri con parte frazionaria periodica in quanto, in tal caso, anche nella nuova base il numero sarà periodico ed il suo periodo è facilmente identificabile.

Ad esempio:

1 6 3 2 . 6 3 1 4

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

z}|{001 z}|{

110 z}|{

011 z}|{

010 . z}|{

110 z}|{

011 z}|{

001 z}|{

100 e quindi

1632.63148= 1110011010.11002= 0.111001101011002× 2¹⁰ 1.1.2 Normalizzazione ed approssimazione

Un numero a ∈ R, rappresentato in base b, non ha una rappresentazione unica. Infatti, ricordiamo che quando si sposta il punto di radice a destra di una posizione, il numero risulta moltiplicato per la base, e che quando si sposta il punto di radice a sinistra di una posizione, il numero risulta diviso per la base.

Ad esempio, per uno stesso numero espresso in base b ≥ 8, si hanno le seguenti rappresentazioni:

1234.57^b× b⁵ = 0.123457^b× b⁹= 123457^b× b³= 1.23457^b× b⁸

= 123457000b× b⁰= 0.00123457b× b¹¹= · · · E possibile decidere che tutti i numeri vengano rappresentati in una` stessa forma (ovvero in forma normalizzata). Ad esempio si pu`o decidere di adottare la convenzione che il numero debba essere rappresentato sempre con prima cifra significativa (ovvero cifra non nulla) alla destra del punto di radice ovvero nella forma

a = ±(0.a1a2a3. . .)b× b^e= ± (0.m)^b× b^e con a16= 0.

e viene detto esponente o caratteristica ed m viene detta mantissa.

(13)

1.1. Basi di numerazione 13 Con questa normalizzazione `e possibile rappresentare tutti i numeri reali, eccettuato lo 0.

La normalizzazione non modifica la natura del numero reale. Pertanto i numeri scritti in forma normalizzata possono avere mantissa finita, oppure periodica, oppure illimitata (ad esempio a = π).

Prima di proseguire, si desidera sottolineare quanto segue: consideriamo un certo numero a ∈ Q espresso, ad esempio, in base 10. La sua rappresentazione, anche se si fissa la normalizzazione, pu`o non essere univoca. Vediamo questo esempio:

Sia dato il numero 0.11910. Apparentemente `e un numero periodico con parte frazionaria illimitata (0.119999999 . . .). Calcoliamo la sua frazione generatrice.

0.11910=µ 119 − 11 900

¶

10

=µ 108 900

¶

10

= 0.1210

Questo significa che 0.11910 e 0.1210 sono due rappresentazioni, con la medesima normalizzazione, dello stesso numero.

Esiste una regola generale per tale fenomeno: la rappresentazione normalizzata non `e unica per tutti i numeri reali decimali il cui periodo sia 9 e, se i numeri sono espressi in base b, per tutti i numeri reali il cui periodo sia uguale a b − 1. In tutti gli altri casi, la normalizzazione determina univocamente m ed e.

Supponiamo ora di poter conservare solo un numero t di cifre significative della mantissa di a (escludendo il punto di radice e lo zero che lo precede) e quindi di considerare una approssimazione di a del tipo:

a^∗= ±(0.a1a2a3. . . at)b× bê= ± (0.m^∗)b× bê= ± m^∗b× bê−t dove m è un intero formato dalle t cifre a1a2a3. . . at.

Vi sono due modi per approssimare un numero conservando solo t cifre di mantissa:

Troncamento: Vengono banalmente trascurate nella mantissa m, tutte le cifre successive ad at.

Ad esempio:

a t a^∗

(0.4567894251 . . .)₁₀ 3 0.45610

6 0.45678910

8 0.4567894210

(14)

Arrotondamento: Si usa la seguente regola:

a^∗= ±(0.a1a2a3. . . at)b·b^e dove at =

½ at se at+1< b/2 at+ 1 se at+1≥ b/2 at+1`e ovviamente la cifra che segue at, ovvero la prima cifra trascu- rata della mantissa.

Ad esempio:

a t a^∗

(0.4567894251 . . .)₁₀ 3 0.45710

6 0.45678910

8 0.4567894310

1.1.3 Errore assoluto e relativo

Dato un numero reale decimale a ed una sua approssimazione a^∗ si definisce

Errore assoluto: la quantit`a

εa= |a − a^∗| Errore relativo: la quantit`a

εr = |a − a^∗|

|a| , con a 6= 0

In generale, l’errore relativo fornisce un’indicazione pi`u realistica di

“quanto si sbaglia” considerando a^∗ al posto di a, in quanto esso non viene influenzato dall’ordine di grandezza dei numeri che si stanno considerando ed `e legato unicamente al numero di cifre di a^∗, a partire dalla prima, che coincidono con quelle di a.

Per conoscere quante cifre significative decimali in comune vi sono tra un numero a ed una sua approssimazione a^∗, `e sufficiente calcolare il valore

− log10εr.

Consideriamo il seguente esempio (errori e logaritmo decimale sono approssimati a 3 cifre significative):

a a^∗ εa εr −log10εr

0.456789425 × 10⁻³⁰ 0.4567895 × 10⁻³⁰ 7.5 × 10⁻³⁸ 1.64 × 10⁻⁷ 6.79 0.456789425 × 10⁻³⁰ 0.6 × 10⁻³⁰ 1.43 × 10⁻³¹ 3.14 × 10⁻¹ 0.5

(15)

1.2. Algoritmi 15 I valori di a e di a^∗sono molto piccoli. Nel secondo caso l’approssimazione a^∗ non ha nessuna cifra significativa in comune con a, ma guardando l’errore assoluto esso sembrerebbe essere piccolo (dell’ordine di 10⁻³¹).

L’errore relativo mette giustamente in luce la scarsa accuratezza dell’approssimazione.

Si consideri ora l’esempio seguente

a a^∗ ε_a ε_r −log10ε_r

0.456789425 × 10⁺³⁰ 0.4567895 × 10⁺³⁰ 7.5 × 10⁺²² 1.64 × 10⁻⁷ 6.79 0.456789425 × 10⁺³⁰ 0.6 × 10⁺³⁰ 1.43 × 10⁺²⁹ 3.14 × 10⁻¹ 0.5 Sia a che a^∗ sono valori molto grandi. Guardando gli errori assoluti (che sono grandi), sembrerebbe che entrambe le approssimazioni non fossero buone. L’errore relativo (ed il logaritmo), invece, mostrano come la prima approssimazione sia accettabile. Si noti anche che gli errori relativi di questo esempio coincidono esattamente con quelli dell’esempio precedente.

Se consideriamo come approssimazione a^∗ il valore ottenuto per troncamento o arrotondamento a t cifre della mantissa normalizzata si hanno le seguenti relazioni

Errore assoluto:

εa = |a − a^∗| ≤ c × b^e−t Errore relativo:

εr = |a − a^∗|

|a| ≤ c × b^1−t

con c = 1

2 se si lavora per arrotondamento e c = 1 se si lavora per troncamento.

1.2 Algoritmi

1.2.1 Conversione da base 10 a base b di un numero intero Siano dati a ∈ Z (in base 10) e b ≥ 2. Si desidera convertire in base b il valore assoluto di a. Applichiamo il procedimento delle divisioni ripetute ad |a| ed otteniamo il seguente algoritmo.

(16)

read a ∈ Z read b≥ 2 a = |a|

while a 6= 0 do q = j a

b k r = a − q × b print r a = q end while dove ¹ x

y º

indica la parte intera della divisione tra x ed y. I resti interi stampati, presi nell’ordine inverso (sostituendo eventualmente il corrispondente simbolo per le basi b > 10), danno le cifre del numero convertito in base b.

1.2.2 Conversione da base b a base 10 di un numero intero, con l’algoritmo di Horner

Siano dati a ∈ Z, con |a| = (anan−1. . . a0)b(rappresentato con n + 1 cifre della base b). Si desidera calcolare il valore decimale del numero dato, utilizzando l’algoritmo di Horner.

read a ∈ Z read n ∈ N read b≥ 2 x = an

for i = n − 1, . . . , 0 step −1 x = x × b + aⁱ

end for print sign(a)x

dove sign(a) rappresenta il segno di a. Le varie cifre del numero a vanno fornite, per le basi b > 10, sostituendo eventualmente il corrispondente valore decimale delle cifre non numeriche. Il valore sign(a)x corrisponde al numero convertito in base decimale.

1.2.3 Calcolo del valore di un polinomio in un punto

Sia dato un polinomio P di grado al pi`u n (P ∈ Pⁿ) scritto nella forma P (x) = α0xⁿ+ α1xⁿ⁻¹+ · · · + αn−1x + αn, (1.1)

(17)

1.3. Esercizi 17 ed un punto ¯x. Si vuole valutare P (¯x) ovvero il valore del polinomio nel punto ¯x.

Possiamo applicare l’espressione (1.1) ovvero calcolare P (¯x) =

Xn i=0

αix¯ⁿ⁻ⁱ

effettuando j − 1 moltiplicazioni per ogni potenza x^j (j = 1, . . . , n), n moltiplicazioni per i prodotti relativi ai coefficienti ed infine n addizioni, ovvero, in totale, n²+ n/2 moltiplicazioni ed n addizioni.

In alternativa possiamo utilizzare il seguente schema iterativo

½ β0 = α0

βi = ¯x βi−1+ αi, i = 1, . . . , n

ottenendo βn = P (¯x). Con tale procedimento vengono eseguite solamente n moltiplicazioni ed n addizioni.

Tale algoritmo corrisponde esattamente alla regola di Ruffini per trovare il polinomio quoziente Q(x) ed il resto r della divisione di P (x) per (x−¯x), con P (x) = Q(x)(x− ¯x)+r, Q(x) = β⁰xⁿ⁻¹+β1xⁿ⁻²+· · ·+βⁿ⁻²x+βn−1, r = P (¯x) ed anche all’algoritmo di Horner gi`a illustrato nelle conversioni della parte intera da base b a base 10. Si ha quindi

read n

read αi, i = 0, . . . , n read x¯

β = α0

for i = 1, . . . , n β = ¯x × β + αi

end for print β

1.3 Esercizi

Esercizio 1.1 Si scriva un algoritmo per la conversione da base 10 a base b della parte frazionaria di un numero.

Esercizio 1.2 Si scriva un algoritmo per la conversione da base b a base 10 della parte frazionaria di un numero, con l’algoritmo di Horner.

Esercizio 1.3 Sapendo che se P (x) = Q(x)(x − ¯x) + r, allora P⁰(x) = Q⁰(x)(x − ¯x) + Q(x) e quindi P⁰(¯x) = Q(¯x) si scriva un algoritmo che calcoli il valore della derivata prima del polinomio P (x) nel punto ¯x.

(18)

(19)

Capitolo 2

ARITMETICA DEL COMPUTER

2.1 Rappresentazione ed aritmetica dei numeri in- teri

In questo contesto non ci interessa dare una trattazione completa delle varie forme di rappresentazione degli interi nel computer. Ci limitiamo a dare alcune indicazioni che valgono per la quasi totalit`a dei computer attuali.

In un computer i numeri interi vengono memorizzati come numeri bi- nari in rappresentazione complemento a due. Per tale memorizzazione sono a disposizione un certo numero finito k di cifre binarie (bit = binary digit), compreso il bit per rappresentare il segno del numero intero. Non tutti i numeri interi sono quindi rappresentabili, ma solo quelli compresi tra nmin = −2^k−1 e nmax = 2^k−1− 1.

Gruppi di 8 bit vengono chiamati byte. Una word (o parola) può essere di 16 bit (2 byte) o di 32 bit (4 byte), e la sua lunghezza dipende dall’architettura del computer. La maggior parte dei computer è in grado di utilizzare k = 16 bit oppure k = 32 bit per memorizzare i numeri interi, qualsiasi sia la lunghezza della word. Con taluni linguaggi è possibile richiedere altri valori per k (ad esempio k = 8 o k = 64).

Gli interi che appartengono all’intervallo [nmin, nmax] sono rappresentati esattamente (nessun errore). Se si cerca erroneamente di memorizzare un numero n < nmin (n > nmax) si ha la cosiddetta situazione di underflow (rispettivamente overflow).

Gli intervalli di interi rappresentabili per k = 16 e k = 32, con una rappresentazione complemento a due, sono:

19

(20)

byte bit nmin nmax

2 16 −2¹⁵= −32 768 2¹⁵− 1 = 32 767

4 32 −2³¹= −2 147 483 648 2³¹− 1 = 2 147 483 647 Per quanto riguarda le operazioni aritmetiche tra interi (addizione, sottrazione, moltiplicazione e divisione intera) esse danno sempre luogo ad un risultato esatto. L’unico caso di errore pu`o avvenire qualora il risultato dell’operazione sia un numero esterno all’intervallo [nmin, nmax], con impossibilit`a di rappresentare tale risultato e quindi con situazione di underflow o di overflow.

2.2 Rappresentazione dei numeri reali

Come vedremo, l’utilizzo dei numeri reali su di un computer pu`o essere, a differenza dei numeri interi, causa di numerosi problemi.

Usualmente i computer utilizzano per i numeri reali una rappresentazione normalizzata in base binaria (b = 2). Talvolta viene usata una normalizzazione in base esadecimale (b = 16), anche se poi la mantissa viene memorizzata sul computer trasformando in binario le rispettive cifre esadecimali.

Sia fissata una certa normalizzazione ed una certa base b per il numero reale a, ad esempio

a = ± (0.a1a2a3. . .)b× b^e= ± (0.m)^b× b^e

(la normalizzazione pu`o comunque variare da un computer ad un altro).

Il numero di bit che sono a disposizione in un computer per rappresentare un numero reale `e sempre finito. Esso viene suddiviso logica- mente in tre parti in cui vengono rappresentati, rispettivamente, il segno del numero (sempre un solo bit che viene posto uguale a zero, per i numeri positivi, ed uguale a uno, per i numeri negativi), l’esponente e la mantissa:

± esponente mantissa

Il numero di cifre a disposizione per la mantissa e per l’esponente intero non possono superare un certo limite prefissato. Questo porta a due importanti conseguenze:

1. Poich`e il numero di cifre della mantissa m del numero a pu`o essere illimitato, oppure finito ma superiore al numero di cifre t messe a

(21)

2.2. Rappresentazione dei numeri reali 21 disposizione nella rappresentazione del computer, solo un numero finito di numeri reali a possono essere esattamente rappresentati esattamente all’interno del computer. Tutti gli altri verranno rappresentati con una loro approssimazione a^∗.

Il numero massimo t di cifre binarie, disponibile per la mantissa m, definisce la precisione del numero.

2. Il rango dei numeri reali normalizzati rappresentabili, presi in valore assoluto, è compreso tra un valore minimo amin = b^L−1ed un valore massimo amax = bÛ(1 − b^−t), dove L < 0 è il minimo esponente rappresentabile e U > 0 è il massimo esponente rappresentabile.

Quindi i numeri con |a| < a^min non sono rappresentabili in forma normalizzata e si ha una condizione di underflow; il numero a in tal caso viene trattato come zero oppure, se possibile, memorizzato come numero denormalizzato (anche detto subnormalizzato) ed in tal caso si parla di gradual underflow. I numeri con |a| > amax

danno luogo al cosiddetto overflow; il numero a in tal caso assume il valore della rappresentazione al calcolatore dell’infinito (+Inf oppure -Inf).

Pertanto solo un sottoinsieme dell’insieme R dei reali pu`o essere rappresentato in un computer. Tale sottoinsieme viene chiamato insieme dei numeri floating point (o numeri macchina, o numeri in virgola mobile) e, con la nostra ipotesi di normalizzazione, pu`o essere definito in questo modo:

F= {0}∪

(

a^∗∈R : a^∗= ±(0.a1a₂a₃. . . at)b×b^e= ±b^e Xt

i=1

aib⁻ⁱ= ± m^∗^b×b^e−t )

con b ≥ 2, 0 ≤ ai≤ b − 1, a16= 0, L ≤ e ≤ U ed m^∗b= a1a2a3. . . at. Quindi all’interno di un computer noi memorizziamo solamente i numeri

± e m^∗b

con e a r cifre binarie e m^∗b a t cifre binarie.

Per memorizzare i numeri floating point, si usano usualmente 4 byte (semplice precisione) oppure 8 byte (doppia precisione). Su taluni computer e con certi linguaggi si possono chiedere anche 10 o 16 byte (precisione estesa) oppure 6 byte. Il numero di bit dedicati alle due parti (esponente e mantissa) possono variare ed anche il tipo di rappresentazione binaria dell’esponente intero relativo e.

(22)

Con 4 byte (qualsiasi sia l’architettura del computer) si riescono a rappresentare almeno 7 cifre decimali significative. Con 8 byte, tale numero viene elevato a circa 16 cifre decimali.

Gli intervalli [−amax, −amin] e [amin, amax] della retta reale possono essere molto grandi (se vi sono molte cifre binarie a disposizione per l’esponente e), ma i numeri di F (in valore assoluto) sono molto densi vicino ad amin e pi`u radi verso amax.

Ad esempio, con 4 byte, vi sono circa 8 388 607 numeri floating point tra 1.0 e 2.0 e solo circa 8 191 tra 1023.0 e 1024.0.

Si veda nella figura 2.1 una schematizzazione della cosiddetta floating point real line.

− amin a_min a_max

max 0

rango utilizzabile rango utilizzabile

zoom denormalizzati

− a overflow

flow flow

overflow under

under

Figura 2.1: Floating point real line

Utilizzando una notazione abituale che si ritrova in molti testi, dato un numero a ∈ R, indichiamo con fl(a) ∈ F la sua approssimazione che viene rappresentata all’interno del computer.

E importante, a fronte di tale approssimazione, riuscire a dare una` limitazione superiore all’errore commesso (che in tal caso prende in nome di errore di assegnazione). Utilizzando le relazioni viste nel capitolo precedente, e tenuto presente che oramai la quasi totalit`a dei computer lavora con l’arrotondamento, avremo:

Errore assoluto:

εa = |a − fl(a)| ≤ 1

2 × b^e−t. Si ha quindi

fl(a) = a + ε1

con |ε1| = ε^a.

(23)

2.2. Rappresentazione dei numeri reali 23 Errore relativo:

εr = |a − fl(a)|

|a| ≤ 1

2 × b^1−t= eps. (2.1) La quantità eps che, come si vede, dipende unicamente dalla base b e dal numero di cifre t (e quindi non dal numero che si vuole rappresentare) viene chiamata precisione di macchina ed è una caratteristica dell’architettura del computer su cui si sta lavorando. Dipende naturalmente anche dal numero di byte utilizzati nella rappresentazione dei numeri macchina, in quanto tale valore influisce sul valore di t. Se la base utilizzata è 2, si ha eps = fl(2^−t). Il valore eps rappresenta il più piccolo numero macchina positivo tale che

fl(1 + eps) > 1 Si ha anche

fl(a) = a (1 + ε2) con |ε2| = εr ≤ eps.

Vediamo alcuni esempi di un programma dove viene letto un valore reale a, usando la semplice precisione, e poi viene immediatamente stam- pato a^∗= fl(a). I valori di εa ed εr vengono calcolati con un programma che usa la doppia precisione, utilizzando i valori a ed a^∗ della tabella.

a a^∗ εa εr

123456789.0 123456792.0 3.0 2.43 × 10⁻⁸

1.23456789 × 10¹³ 1.2345679 × 10¹³ 1.0 × 10⁵ 8.1 × 10⁻⁹ 3.34567891 3.34567881 1.0 × 10⁻⁷ 2.99 × 10⁻⁸ 3.34567891 × 10¹⁰ 3.34567895 × 10¹⁰ 4.0 × 10² 1.2 × 10⁻⁸

0.1 0.100000001 1.0 × 10⁻⁹ 1.0 × 10⁻⁸

0.01 0.00999999978 2.2 × 10⁻¹⁰ 2.2 × 10⁻⁸ 0.001 0.00100000005 5.0 × 10⁻¹¹ 5.0 × 10⁻⁸ Dai risultati si evince che, sia la conversione in binario del numero decimale, sia il numero limitato t di cifre della mantissa binaria che si possono memorizzare, gi`a in fase di assegnazione, non ci permettono di lavorare con l’esatto valore a, ma con una sua approssimazione che pu`o presentare un elevato errore assoluto. Resta comunque valida, per εr, la relazione (2.1) (eps nel caso della semplice precisione vale all’incirca 1.2 × 10⁻⁷).

(24)

La singola precisione può in molti casi essere insufficiente a garantire una sufficiente affidabilità dei calcoli (soprattutto nelle operazioni aritmetiche floating-point, come vedremo in seguito). In tal caso è sempre opportuno utilizzare almeno la doppia precisione, anche se ciò provoca un allungamento dei tempi di calcolo e comunque non ci garantisce com- pletamente dell’esattezza dei calcoli (si veda la sezione 2.7).

2.3 Rappresentazione IEEE 754

Lo standard IEEE 754 per il calcolo in virgola mobile (per esteso, IEEE Standard for Binary Floating-Point Arithmetic, ANSI/IEEE Std 754- 1985) è il più diffuso. Il formato di rappresentazione dei numeri floating point è più complesso di quanto è stato descritto nella sezione precedente. Inoltre, con tale standard, possono essere rappresentati sia lo zero positivo che lo zero negativo ed anche i seguenti valori speciali: infinito positivo (Inf o +Inf), infinito negativo (-Inf), ±NaN (Not a Number).

Il NaN viene utilizzato per rappresentare un valore che non `e un numero reale. Esso viene assegnato, ad esempio, come risultato di operazioni indeterminate quali ±0/± 0, ±∞/± ∞, ∞ − ∞ e ±∞ · ±0.

La base per l’esponente `e b = 2 e la normalizzazione viene fatta considerando un valore compreso tra 1 e 2, ovvero i numeri normalizzati hanno la forma

a^∗= ±(1.a1a2a3. . . at)2× 2ê= ±(1 + 0.a1a2a3. . . at)2× 2ê. La cifra 1 a sinistra del punto di radice non viene rappresentata (hidden bit, o bit nascosto, o bit implicito) e la mantissa corrisponde al numero binario m^∗ = a1a2a3. . . at (t numero di bit disponibili). L’esponente intero relativo e viene rappresentato eccesso 2^r−1− 1, dove r è il numero di bit disponibili per l’esponente, al fine di non dover utilizzare un bit per memorizzare il segno dell’esponente. Viene quindi memorizzato il valore intero binario positivo e^∗= e + 2^r−1− 1, ovvero si ha

± e^∗ m^∗

con a^∗= ±(1.m^∗)2× 2^e^∗⁻⁽²^r⁻¹⁻¹⁾.

Per quanto riguarda il rango dei numeri reali normalizzati, presi in valore assoluto, rappresentabili con tale standard, esso è compreso tra un minimo amin = 2^L ed un massimo amax = 2Û(2 − 2^−t), dove L < 0 è

(25)

2.3. Rappresentazione IEEE 754 25 il minimo esponente rappresentabile e U > 0 `e il massimo esponente rappresentabile.

Il numero di bit dedicati alle varie parti (segno, esponente e mantissa) per la semplice e la doppia precisione sono i seguenti

byte bit segno esponente mantissa

4 32 1 r = 8 t = 23

8 64 1 r = 11 t = 52

Il minimo esponente e = e^∗− (2^r−1− 1) corrisponderebbe ad una rappresentazione in eccesso con tutti gli r bit uguali allo zero, ovvero e = 0 − (2^r−1− 1) (in semplice precisione 0 − 127 = −127, ed in doppia precisione 0 − 1023 = −1023) ed il massimo esponente corrisponderebbe ad una rappresentazione in eccesso con tutti gli r bit uguali ad uno, ovvero e = 2^r − 1 − (2^r−1− 1) (in semplice precisione 255 − 127 = 128, ed in doppia precisione 2047 − 1023 = 1024). In realt`a tali particolari confi- gurazioni assunte dall’esponente e^∗ (tutti i bit uguali a zero oppure tutti i bit uguali ad uno) vengono riservate per indicare dei valori particolari (zero, Inf, NaN ed anche i numeri denormalizzati).

Quindi, riassumendo, per i numeri normalizzati si ha

byte bit L U

4 32 −126 127

8 64 −1022 1023

byte bit amin amax

4 32 1.17549435 × 10⁻³⁸ 3.40282347 × 10³⁸

8 64 2.2250738585072014 × 10⁻³⁰⁸ 1.7976931348623157 × 10³⁰⁸ e, per i valori particolari,

±0 ± tutti i bit uguali ad 0 tutti i bit uguali a 0

±Inf ± tutti i bit uguali ad 1 tutti i bit uguali a 0

±Nan ± tutti i bit uguali ad 1 almeno un bit diverso da 0 Restano da definire i numeri denormalizzati che corrispondono ad una rappresentazione del tipo

± tutti i bit uguali ad 0 m^∗ qualsiasi non nullo

(26)

Tali rappresentazioni corrispondono a dei numeri reali per i quali il bit implicito alla sinistra è uguale a zero (anzichè ad uno), e l’esponente è sempre L, ovvero ai numeri

a^∗= ±(0.m^∗)2× 2^L che sono, in valore assoluto, minori di amin.

Il numero reale denormalizzato pi`u piccolo rappresentabile in valore assoluto diventa quindi 2^L−t (in semplice precisione 1.40129846 × 10⁻⁴⁵ ed, in doppia precisione, 4.9406564584124654 × 10⁻³²⁴). Si veda ancora la figura 2.1.

Relativamente alla precisione di macchina si ha byte bit eps

4 32 fl(2⁻²³) ' 1.19209290 × 10⁻⁷

8 64 fl(2⁻⁵²) ' 2.2204460492503131 × 10⁻¹⁶

Nell’agosto del 2008 `e stata pubblicata una revisione dello standard IEEE 754-1985, chiamata IEEE 754-2008, che estende, completa e sosti- tuisce la precedente versione.

2.4 Operazioni aritmetiche floating-point

Come si `e visto, quello che viene rappresentato all’interno di un computer

`e solo un sottoinsieme di R. Vediamo ora cosa accade alle operazioni 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 superiore (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à memorizzato, per quanto riguarda gli operandi, è una loro approssimazione, ovvero fl(x) e fl(y). Inoltre, il risultato della somma tra fl(x) e fl(y) verrà ulteriormente approssimato in quanto nella restituzione del risultato, si ritornerà ad avere t cifre per la mantissa. Pertanto:

(27)

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 + ε³) x ® y = fl(fl(x)/fl(y)) = (fl(x) / fl(y))(1 + ε4) con |ε²|, |ε³|, |ε⁴| ≤ 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à che resta valida è la proprietà 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 è data dalla cosiddetta relazione anomala che sancisce la non unicità dell’elemento neutro dell’addizione e della sottrazione (ovvero dello zero). Tale relazione può 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.

(28)

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,

(29)

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 10³⁸):

x ×y

z = x × y z

Sia x ' 10³⁰, y ' 10³⁰, z ' 10²⁵. Con la prima formula otteniamo un risultato numerico dell’ordine di 10³⁵, 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⁻³⁸). Sia x ' 10⁻³⁰, y ' 10⁻³⁰, z ' 10⁻²⁵. Con la prima formula otteniamo un risultato numerico dell’ordine di 10⁻³⁵, 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.

(30)

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 separatamente viene calcolato l’esponente del risultato. Il risultato viene poi trasferito nuovamente 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⁻² ed y = 0.35720021 × 10⁴.

Memoria Accumulatore

fl(x) = 0.27531012 × 10⁻² → 0.2753101200000000 × 10⁻² × fl(y) = 0.35720021 × 10⁴ → 0.3572002100000000 × 10⁴ fl(z) = 0.98340833 × 10¹ ← 0.0983408326791252 × 10²

Con tali valori si ha x = fl(x) ed y = fl(y). Nel caso di una moltiplicazione, 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 assegnazione durante la restituzione in memoria quando il risultato viene normalizzato e ridotto a t cifre di mantissa.

Esempio 2

Sia x = 0.57203146 × 10⁻¹ ed y = 0.27001052 × 10².

fl(x) = 0.57203146 × 10⁻¹ → 0.5720314600000000 × 10⁻¹ / fl(y) = 0.27001052 × 10² → 0.2700105200000000 × 10² fl(z) = 0.21185525 × 10⁻² ← 2.118552491954754 × 10⁻³

(31)

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

è sempre esatto (in quanto possono prodursi più di 2t cifre). Vi è quindi un errore nel risultato dell’accumulatore in quanto sarà arrotondato a 2t cifre. Nella restituzione in memoria l’errore di assegnazione sarà 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ò non è sempre vero per le operazioni macchina ⊕ e ª. In talune condizioni si può realizzare uno degli errori più 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 accumulatori. 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⁻⁷.

(32)

Esempio 1

Sia x = 0.23487757 × 10³ ed y = 0.56799442.

fl(x) = 0.23487757 × 10³ → 0.2348775700000000 × 10³ + fl(y) = 0.56799442 × 10⁰ → 0.0005679944200000 × 10³ fl(z) = 0.23544556 × 10³ ← 0.2354455644200000 × 10³

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 × 10⁶ ed y = 0.21554623 × 10⁻⁴.

fl(x) = 0.56543451 × 10⁶ → 0.5654345100000000 × 10⁶ + fl(y) = 0.21554623 × 10⁻⁴ → 0.0000000000215546 × 10⁶ fl(z) = 0.56543451 × 10⁶ ← 0.5654345100215546 × 10⁶

In questo esempio, poichè la grandezza dei due operandi è 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à esatta (ovvero non verrà calcolato esattamente fl(x) + fl(y)). Inoltre, restituendo il risultato in memoria (poichè 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)| è dell’ordine di 10⁻¹⁰ e quindi minore di eps.

Esempio 3

Sia x = 1.0 ed y = 0.5 × 10⁻⁷.

fl(x) = 0.10000000 × 10¹ → 0.1000000000000000 × 10¹ + fl(y) = 0.50000000 × 10⁻⁷ → 0.0000000050000000 × 10¹ fl(z) = 0.10000001 × 10¹ ← 0.1000000050000000 × 10¹

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-

(33)

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⁻⁷ 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.

fl(x) = 0.56543287 × 10⁰ → 0.5654328700000000 × 10⁰ + fl(y) = −0.56543285 × 10⁰ → −0.5654328500000000 × 10⁰ fl(z) = 0.20000000 × 10⁻⁷ ← 0.0000000200000000 × 10⁰

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⁻⁷ e quindi l’errore relativo (approssimato a 3 cifre decimali) `e εr(z) = 0.166, che

è elevato. Nei calcoli successivi, utilizzando fl(z) (anzichè z) è come se lavorassimo con solo 1 cifra decimale esatta. È 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 computer, mentre gli esempi precedenti, svolti a mano, servivano unicamente a mostrare come vengono effettuate le operazioni.

(34)

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×10⁶ 0.21554623×10⁻⁴ 565434.5 565434.5 1.0 0.5 × 10⁻⁶ 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×10⁶ 0.21554623×10⁻⁴ 565434.509978 565434.510022

1.0 0.5 × 10⁻⁶ 0.9999995 1.0000005

0.5654328749876 0.5654328510104 0.239772000032×10⁻⁷ 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 ax²+ bx + c = 0 sono date da x1 = −b −√

b²− 4ac 2a x2 = −b +√

b²− 4ac

2a .

(2.3)

Se |4ac| << b² una delle due soluzioni sar`a mal calcolata, in quanto

√b²− 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⁻³, b = 0.8 et c = −1.2 × 10⁻⁵, le soluzioni esatte sono

x1 = −800 x2 = 1.5 × 10⁻⁵.