Marco Tarini -Università dell'InsubriaA.A. 2017/18Architettura degli elaboratori -Rappresentazione dell'informazione nei calcolatori -31

(1)

Aritmetica binaria

Architettura degli elaboratori - 79 -

numeri razionali

(«con la virgola, e sviluppo finito oppure periodico»)

Numeri binari non interi

Come si esprime un numero non intero in binario?

Esattamente come in base dieci:

235.13

10

=

2x10

²

+ 3x10

¹

+ 5x10

⁰

+ 1x10

^-1

+ 3x10

^-2

2 centinaia + 3 decine + 5 unità + 1 decimi + 3 centesimi .

Esempio in base 2:

101.1001

2

=

1x2

²

+ 0x2

¹

+ 1x2

⁰

+ 1x2

^-1

+ 0x2

^-2

+ 0x2

^-4

+ 1x2

^-8

= 4 + 1 + 1/2 + 1/8

= 5.625₁₀

(2)

Aritmetica binaria

Numeri binari non interi

oppure: cosi come, in base 10:

nello stesso modo, in base 2:

101.1001

2

=

101

₂

unità + 1001

₂

/ 2

⁴

= 5 + 9/16 235.13

=

235 unità + 13centesimi (/10²)

(perché sono 2 cifre dopo la virgola)

235.138 =

235 unità + 138millesimi (/10³)

(perché sono 3 cifre dopo la virgola)

Conversione da decimale a binario di numeri frazionari: esempio

0.748

₁₀

= 0.101111110…

₂

0.748 1.496 0.992 1.984 1.968 1.936 1.872 1.744 1.488 0.976

raddoppio della parte frazionaria (quella dopo la virgola)

(3)

Aritmetica binaria

Conversione da decimale a binario di numeri frazionari: esempio

0.15

₁₀

= 0.001001100…

₂

0.15 0.30 0.60 1.20 0.40 0.80 1.60 1.20 0.40 0.80

raddoppio della parte frazionaria (quella dopo la virgola)

Conversione da decimale a binario di numeri frazionari: algoritmo

Implementazione dell’algoritmo in C

int convert (int d[], float v, int k) { i = k-1;

while (i>=0) { if (2v >= 1)

d[i] = 1;

else d[i]=0;

v = 2v-d[i];

i--;

}

(4)

Note matematiche sullo sviluppo di numeri con la virgola

Tutti (e soli) i numeri razionali ( ∈

ℚ

, le frazioni) hanno sempre sviluppi che sono o finitio periodici:

finiti: es. ½ = 0.5, ¼ = 0.25

periodici: es 1/3 = 0.33333333…. 1/9 = 0.1111111…..

I numeri non razionali ( ∉

ℚ

) hanno sviluppi infiniti e NON periodici es: sqrt(2) = 1.41421356237…. pi = 3.14159265359….

Questo vale a prescindere dalla base ma una stessa frazione puo’ avere uno

sviluppoperiodicoin una base e finitoin un’altra es: 1/5 = 0.2 in base 10,

1/5 = 0.001100110011001100110011…. in base 2

Aritmetica binaria

Troncamento e arrotondamento

I numeri frazionari possono avere un numero infinito di cifre.

Ne scriveremo solo un numero finito k.

Troncamento= ignoro tutte le cifre dopo k (quindi, arrotondo sempre per difetto) Arrotondamento= idem, ma prima

arrotondo per eccesso o per difetto, per minimizzare l’errore dipende solo dellaprima cifra che scarto(la (k+1)-esima) in base 10: 0,1,2,3,4  per difetto. 5,6,7,8,9  per eccesso in base 2: 0  per difetto 1  per eccesso Es, k = 3, in base 10:

arrotondamento di 1.1213….= 1.121 arrotondamento di 1.3487….= 1.349 Es, k = 3, in base 2:

arrotondamento di 0.1010…= 0.101

arrotondamento di 0.1011…= 0.101 + 0.001 = 0.110

(5)

Rappresentazione di numeri frazionari

«in virgola fissa»

Idea: per rappresentare un numero frazionale:

converto in base 2

memorizzo la parte intera in k bits, la parte dopo la virgola in h bit (totale bits usati = k + h)

arrotondo a h cifre la parte decimale con h e k decisi una volta per tutte Esempio. Su un byte (8 bit), k = 4 e h = 4:

6.125₁₀= 110.001₂

Aritmetica binaria

1 1 0

0 0 0 1 0

posizione della virgola (implicita e prefissata)

rappresentazione di 6.125₁₀

(su 4+4 bits)

Rappresentazione di numeri frazionari

«in virgola fissa»: supporto

i numeri in virgola fissa si rappresentano semplicemente come numeri interi

dal punto di vista di un’architettura, non fa differenza!

i numeri in virgola fissa sono numeri interi l’unica differenza sta in come vengono interpretati

per esempio, 342 memorizzato come intero puo’ rappresentare:

342 metri 342 euro

342 pecore, patate, persone, formiche, etc…

oppure anche…

342 cm = 342 centesimi di metro = 3.42metri 342 eurocent = 3.42euro

342 mm = 0.342metri, etc

se un numero rappresenta 1/256 (256-esimi) di unità, allora sto usando numeri in virgola fissa con 8 cifre binarie frazionarie (2^8 = 256)

(6)

Rappresentazione di numeri frazionari

«in virgola fissa»: proprietá

nota: arrotondo = commetto un errore (precisione numerica limitata)

Limiti:

Max numero esprimibile: 2^k- 1 + (quasi) 1 = (quasi) 2^k Min numero esprimibile > 0 : 2^-h ( la «precisione»!) (i numeri più piccoli sono arrotondati a 0 !)

Questi limiti sono molto stretti.

Vorremmo poter rappresentare numeri sia MOLTO più grandi che MOLTO più vicini a zero.

Vediamo una rappresentazione più potente ed espressiva…

Aritmetica binaria

Rappresentazione dei numeri reali

I numeri reali sono nell’intervallo (- +

Nella pratica ci interessa un intervallo magari non infinito ma molto esteso, per es:

dalla massa dell’elettrone 9.1 x 10^-28grammi alla massa del sole: 1.9 x 10³³grammi

Nota: anche se questi numeri cadono in un intervallo di circa 60 ordini di grandezza, nessuno in pratica usa mai numeri di 60 cifre.

Il motivo è che la precisione richiesta è bassa

ad es. nessuno sa quale sia la cifra giusta corrispondente alle tonnellate quando si esprime la massa del sole.

Ne consegue che di solito si adotta la notazione scientifica quella usata anche qui sopra:

es: 1.9 x 10³³

scrivibile anche come: 1.9e33

(7)

Aritmetica binaria

Notazione scientifica

o esponenziale (in base 10)

v = f  10e Usata nelle discipline tecniche e scientifiche:

Soddisfa alla necessità di manipolare numeri di ordini di grandezza diversi

Il nome “virgola mobile” (o floating point) indica che la presenza dell’esponente “sposta” la posizione della virgola.

v = f  10e = 0.1*f  10e+1 = 10*f  10e-1 Esempi:

3.454 102 = 34.54  101 = 345.4  100 = 3454  10-1 I numeri sono espressi nella forma: XXX.YYY  10^EEE

XXX: parte intera (qualsiasi numero di cifre) YYY: parte frazionaria (qualsiasi numero di cifre) XXX.YYY: mantissa

EEE: esponente

Notazione scientifica:

forma normalizzata (in base 10)

La forma normalizzata prevede che la mantissa sia un valore

compreso tra 0 e 10 esclusi: 0< M < 10 (eccetto che per in numero 0) (o in generale fra 0 e B esclusi, quando uso la base B)

Cioè la parte intera della mantissa è una cifra sola, ma non 0 L’esponente lo chiamiamo allora «ordine di grandezza»

Esempi di valori in forma normalizzata (in base 10) sono:

3.14159 = 3.14159  100 0.00005 = 5  10-5

1958 = 1.958  103

In forma normalizzata è più facile paragonare fra loro i numeri Es: qual’è maggiore fra: 3451 106, 3.2  109 , 0.052  1011

?

Se li riscrivo in forma normalizzata, diviene evidente:

3.451 109 > 3.2 109 > 5.2 108 (è maggiore quello di ordine di grandezza maggiore; a parità, conta la mantissa)

(8)

Aritmetica binaria

Notazione scientifica:

forma normalizzata (in base 2)

In base 2, B=2, la prima cifra è fra 0 e 2 esclusi è per forza 1!

Cioè i numeri in forma normalizzata (eccetto lo 0) sono sempre

±1.XXX  2 ±YYY

Dove XXX e YYY sono sequenze di 0 e 1

Virgola mobile

Terminologia:

N = M * B^E M: mantissa B: base E: esponente

Sia la mantissa che l’esponente hanno un segno es: numeri negativi di valore assoluto grande (mantissa negativa ed esponente positivo) es: numeri positivi vicini allo zero

(mantissa positiva ed esponente negativo)

(9)

Aritmetica binaria

Virgola mobile

capacità di rappresentazione

Una considerazione fondamentale (per quanto ovvia) è che i numeri reali sono infiniti, mentre sappiamo che utilizzando k bit possiamo rappresentare solo 2^kvalori.

Ne consegue che dobbiamo rassegnarci a priori a una rappresentazione approssimata e limitata dei numeri reali.

Ad esempio, esisterà una configurazione corrispondente ad un numero M più grande di quelli rappresentati dalle altri

configurazioni: i numeri ancora più grandi di M non saranno rappresentabili

Alcuni numeri reali (come p o 2^1/2o 1/3) non sono rappresentabili con un numero finito di cifre. Saranno approssimati.

Del resto tra due reali qualunque ce ne sono infiniti altri, mentre tra due configurazioni no.

NB: bastano i razionali a mettere in difficoltà la precisione di rappresentazione con un numero finito di bit

Virgola mobile

limiti di rappresentazione

Per capire meglio le limitazioni, pensiamo ad una rappresentazione decimale normalizzata con mantissa di tre cifre (più segno) ed esponente di due cifre (più segno).

Possiamo rappresentare numeri come 0.467  10^-19

Limitazioni: non possiamo rappresentare numeri aventi le seguenti caratteristiche

Troppo grandi (> 0.999  10⁹⁹) o troppo piccoli (< -0.999  10⁹⁹) Troppo piccoli in valore assoluto (positivi < 0.001  10^-⁹⁹o negativi

> -0.001  10^-⁹⁹)

NB: questi numeri non possono proprio essere rappresentati: un tentativo in tal senso porterebbe ad un overflow.

(10)

Aritmetica binaria

Virgola mobile

limiti di rappresentazione

Possono essere rappresentati, ma con limitazioni, i numeri appartenenti agli intervalli citati.

Per questi numeri, i limiti sono dati dalla precisione con cui possiamo rappresentarli.

Il valore 1/3 verrà rappresentato come 0.333  10⁰. Naturalmente 0.333 è solo un arrotondamento di 1/3.

Il valore p verrà rappresentato come 0.314  10¹. Di nuovo, un arrotondamento.

In generale questo genere di arrotondamenti non causano grossi problemi (soprattutto se si dispone di più cifre per la mantissa).

Però bisogna tenerne conto:

1/3  3 = 1,

ma (0.333  10⁰)  (0.3  10¹) = 0.999  10⁰ che è diverso da 1.

Virgola mobile

Nei calcolatori si usa la forma normalizzata (0  M < 1) perché consente una migliore precisione (non si sprecano bit della mantissa) ed è più facilmente gestibile.

L’esponente è espresso generalmente in offset

Nota: l’esponente è interpretato come potenza di 2, non di 10 per facilitare la normalizzazione: spostare la virgola equivale a decrementare o incrementare l’esponente

XX.YY * 2ê= X.XYY * 2ê+1= XXY.Y * 2ê-1 La mantissa è espressa in modulo e segno.

(11)

Aritmetica binaria

Lo standard IEEE 754

È lo standard (quasi) universalmente adottato per la rappresentazione di numeri in virgola mobile (floating point)

Definisce alcuni formati, fra cui i più usati:

Singola precisione (32 bit) --- spesso detti float Doppia precisione (64 bit) --- speso detti double

segno esponente mantissa

1 bit 8 bit 23 bit

1 bit 11 bit 52 bit

1 bit 8 bit 23 bit

1 bit 11 bit 52 bit

Singola precisione

Doppia precisione

Lo standard IEEE 754

Include numeri in virgola mobile

a 32 bits («singola precisione») e a 64 bits («doppia precisione») Il bit di segno è 0per i positivi e 1per i negativi

L’esponente…

singola precisione: 8 bit, in «eccesso 127»

doppia precisione: 11 bit, in «eccesso 1023»

Le configurazioni degli esponenti fatte di tutti 0 e tutti 1 hanno significati speciali:

+/- infinito, +/- zero, NAN (not a number), numero-non-normalizzato La mantissa è espressa come una sequenza di cifre binare dopo 1.0 Per esprimere la mantissa 1.XXXXX scrivo solo XXXXX

la parte «1» prima della virgola è un bit sottointeso)

eccetto che per i numeri non-normalizzati detti «subnormali»

(vedere, chi a voglia)

(12)

Aritmetica binaria

Lo standard IEEE 754

Comprende la rappresentazione normalizzata e altre quattro rappresentazioni.

+/- 0 < esp < Max qualsiasi combinazione

Normalizzato Subnormale +/- Zero +/- Infinito Not A Number

+/- 0 qualsiasi combinazione 0

+/- 0 0

+/- 111…111 0

+/- 111…111 qualsiasi combinazione 0

esponente mantissa

Numeri denormalizzati (o subnormali)

Quando un calcolo dà un risultato inferiore al più piccolo (in valore assoluto) numero rappresentabile, prima dello standard IEEE 754 c’erano due possibilità:

Azzerare il risultato (un numero molto piccolo è quasi 0) Causare un’eccezione di «underflow»

Entrambi gli approcci sono poco soddisfacenti: lo standard IEEE 754 introduce i numeri denormalizzati(o subnormali) per rappresentare numeri più piccoli (vicini allo zero).

Per i numeri denormalizzati non vale la regola

«assumiamo la mantissa cominci con un 1 implicito»

(scriviamo solo gli bit della mantissa esplicitamente) Serve a poter rappresentare numeri molto piccoli, per es

0 000000001 0000000 segno mantissa esponente

(il minimo)

(13)

Paragonare numeri in virgola mobile fra loro

Disequazioni: tutto ok, funziona bene maggiorea>b

minorea<b

maggiore o ugualea>=b minore o ugualea<=b

Ugualianze secche: a==b

non ha molto senso: due numeri in floating-point possono essere diversi solo come conseguenza di minuscole approssimazioni Molto piu’ robusto testare se la differenza fra i due sia QUASI zero:

-epsilon < (a-b) < epsilon, con un epsilonpiccolo es:

( -1e-10 < a-b ) AND ( a-b < 1e-10 )

Aritmetica binaria

Operazioni in virgola mobile

Somma e sottrazione:

si uguagliano gli esponenti le mantisse vengono sommate rinormalizzazione della mantissa (con aggiustamento dell’esponente)

Moltiplicazione e divisione:

si moltiplicano o si dividono le mantisse in modo consueto si sommano o si sottraggono gli esponenti

si normalizza (si riporta in forma normale)

(14)

Aritmetica binaria

Configurazioni speciali

Alcuni valori speciali sono rappresentati da configurazione apposita.

Sono cinque:

0+ («zero positivo», o «+0», o semplicemente «0», «ZERO») rappresenta: lo 0 esatto

oppure un valore positivo molto piccolo (non altrimenti rappresentabile) 0- («zero negativo», o «-0»)

rappresenta: un valore negativo molto piccolo (non altrim. rappresent.) +INF («più infinito»)

rappresenta: infinito,

oppure un valore positivo molto grande (non altr. rappr.) -INF («meno infinito»)

rappresenta: meno infinito

oppure un valore negativo molto grande in modulo NAN(o «NaN», o «Not-A-Number»

è risultato di una operazione illecita o dal risultato non determinabile

Configurazioni speciali:

ZERO+, ZERO-, +INF, -INF,

+INF e –INF sono il risultato di operazioni che generano overflow +0 e -0 possono essere il risultato di operazioni che generano underflow (nota: il segno viene calcolato correttamente!)

Quando vengono usati nelle operazioni matematiche o nei confronti, ci si aspetta che questi valori si comportino in modo sensato per es:

0+ + 5.3  5.3 +INF ==+INF VERO 3.1 /0+ +INF 3.1 /0- -INF 3.2 /+INF 0+

+INF + 5.3 +INF 0+ ==0- VERO(nota!)

400.2 <+INF VERO 0-<0+ VERO

+INF ++INF +INF +INF x 2.0 +INF -3.1 /0+ -INF -3.1 /0- +INF 3.2 –3.2 0+

4.2 +0- 4.2 300.0 /-INF 0- -INF <+INF VERO 0.000001 <0+ FALSO

(15)

Aritmetica binaria

Configurazioni speciali: NAN (Not-A-Number)

E’ il risutato di una operazione illecita oppure intederminata, esempi:

sqrt( -5.0 ) NAN (radice quadrata di meno 5) +INF +-INF NAN

0+ /0+ NAN +INF -+INF NAN

Le operazioni numeriche che coinvolgo NAN fanno sempre NAN NAN+ 5.3  NAN

NAN x 0  NAN 3.1 /NAN NAN NAN-NAN NAN

Le condizioni booleane (vero, falso) che coinvolgo NAN fanno FALSO NAN< 5.3  FALSO

NAN >= 0  FALSO 3.1 ==NAN FALSO

NAN==NAN FALSO (nota! vale solo per x=NAN che x non sia uguale a x)

“NAN si propaga senza fine in tutti i conti”

“qualunque espressione che includa un NAN vale NAN”

0+ /0- NAN +INF /+INF NAN

I numeri reali nei linguaggi di programmazione

In molti linguaggi (C, Java…)

si possono dichiarare variabili in singola o doppia precisione Singola precisione (tipicamente FLOAT-32): float x;

Doppia precisione (tipicamente FLOAT-64): double x;

I letterali frazionari sono double per default:

0.5 literal in doppia precisione.

Per indicare che un literal è a singola precisione (float) si appone una f:

0.5f literal in precisione singola.

(16)

Aritmetica binaria

Operazioni in virgola mobile

assai più complesse delle op sui numeri interi (con o senza segno) spesso anche più ottimizzate

in molti contesti, sono le op più utili e comuni dell’elaborazione

Potenza di calcolo matematica: spesso espressa in FLOPS FLoating-pontOPeration per Second

(operazioni in virgola mobile al secondo)

K-FLOPS (kilo-flops) : migliaia di op al sec (anni 50) M-FLOPS (mega-flops): milioni di op al sec (anni 60-70) G-FLOPS (giga-flops): miliardi di op al sec (anni 80-90)

T-FLOPS (tera-flops): migliaia di miliardi di op al sec (anni 2000) P-FLOPS (peta-flops): milioni di miliardi di op al sec (anni 2010)