Nei linguaggi di programmazione

(1)

Aritmetica binaria

Architettura degli elaboratori - 61 -

Nei linguaggi di programmazione

Alcuni linguaggi come il C permettono al programmatore di stabilire:

Su quanti bit deve essere rappresentato un intero short, long, ...

Specificare se:

il numero deve essere interpretato come intero (con segno, in complemento a due)

valori ∈ [ –2^(n-1) .. 2^(n-1)– 1 ], oppure se:

il numero deve essere interpretato come naturale (senza segno, in binario)

valori ∈ [0 .. 2ⁿ-1].

Nei linguaggi di programmazione

Rappresentazioni più usate

8 bit : “byte” (o “char”) 16 bit (2 bytes) : “short int” o “short”

32 bit (4 bytes) : “integer” o “int”

(o “word”, in un sistema a 32-bit) 64 bit (8 bytes) : “long int” o “long”

(o “word”, in un sistema a 64-bit) Di default, in complemento a due.

Se numeri naturali: specificare “unsigned” (“senza segno”) es: “unsigned char”, (8 bit senza segno)

“unsigned int” (32 bit senza segno)

Valori massimi e minimi esprimibili?

(2)

Una scomoda ambiguità

«Endedness»!

Aritmetica binaria

0A0B0C0D

0D 0C 0B 0A

integer a 32 bit

a:

a+1:

a+2:

a+3:

……

Memoria

Little-endian

0A0B0C0D

0A 0B 0C 0D

integer a 32 bit

a:

a+1:

a+2:

a+3:

……

Memoria

Big-endian

Rappresentazione in codice eccesso N con N = 2

^k-1

Variante della rappresentazione in complemento a 2

In questa rappresentazione il numero N da rappresentare viene prima sommato ad una base prefissata («offset»),

qui pari a 2^k-1(dove k è il numero di bit a disposizione),

in questo modo il valore risultante è sempre positivo o nullo questo valore viene codificato come un intero privo di segno.

nota: l’offset è il valore associato al bit più significativo Es: su tre bit (k = 3, offset = 2²= 4) «codice eccesso 4»

per rappresentare -1 codifico (-1)+4= 3 in binario, cioè 011 110 codifica… 6 –4cioè 2

Si può anche vedere come una rappresentazione in complemento a 2 in cui il MSB (quello del segno) viene invertito

(3)

Aritmetica binaria

Notazione in codice eccesso 2

^k-1

: proprietà

Intervallo di valori rappresentabili: stessa del CP2 ! Van

Notazione in codice eccesso N, con N = 2

^k-1

(k=3)

N N+2^3-1 Codifica

-4 (-4 +4) 000

-3 (-3 +4) 001

-2 (-2 +4) 010

-1 (-1 +4) 011

0 (0 +4) 100

1 (1 +4) 101

2 (2 +4) 110

3 (3 +4) 111

Il primo bit rappresenta il segno, ma a differenza del complemento a 2 i numeri negativi hanno il bit del segno a 0 ed i positivi, zero incluso, hanno il bit del segno a 1.

Vantaggio: i numeri sono tutti ordinati in ordine crescente Svantaggio: il numero zero NON è più rappresentato da tutti 0

(4)

Paragone delle rappresentazioni di interi (su tre bit)

Aritmetica binaria

codifica (i tre bits)

interpretato come nautrale

interpretato come intero

in CP2

interpretato in codice eccesso 4

000 0 0 -4

001 1 1 -3

010 2 2 -2

011 3 3 -1

100 4 -4 0

101 5 -3 1

110 6 -2 2

111 7 -1 3

Paragone delle rappresentazioni di interi (su tre bit). Osservazioni

In CP2

lo 0 è rappresentato da tutti 0 (comodo!) (e il -1 è sempre rappresentato da tutti 1) In codice di eccesso N,con N = 2^k-1

tutti 0 rappresenta il minore dei numeri rappresentabili tutti 1 rappresenta il maggiore dei numeri rappresentabili l’ordinamento è lo stesso dei numeri naturali!

(cioè è immediato identificare il maggiore dei due numeri dati) rispetto al CP2, il bit di segno (MSB) è invertito (0 = -, 1 = + o zero) il resto dei bit coincide

Usi tipici: (motivazioni: vedi scritte in verde) Il codice di eccesso è usato per l’esponente dei numeri in virgola mobile (vedi poi).

CP2 si usa praticamente in tutti gli altri casi (codifica numeri +/- )

(5)

Aritmetica binaria

Numeri binari frazionari

Come si esprime un numero frazionario in binario?

Esattamente come in base dieci:

235.13

₁₀

=

2x10

²

+ 3x10

¹

+ 5x10

⁰

+ 1x10

^-1

+ 3x10

^-2

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

Es in base 2:

101.1001

2

=

1x2

²

+ 0x2

¹

+ 1x2

⁰

+ 1x2

^-1

+ 0x2

^-2

+ 0x2

^-3

+ 1x2

^-4

= 4 + 1 + 1/2 + 1/16

= 5.562510

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)

(6)

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--;

}

(7)

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

(8)

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»: 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.

La rappresntaz in virgola fissa non viene quasi mai usata Vediamo una rappresentazione più potente ed espressiva…

(9)

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

Virgola mobile

Corrisponde alla notazione scientifica (usata nelle discipline tecniche e scientifiche):

v = f × 10e

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 Si riferisce a numeri espressi nella forma: X.YYY × 10^w

X: parte intera Y: parte frazionaria W: esponente

(10)

Aritmetica binaria

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)

Virgola mobile: forma normalizzata

La forma normalizzata prevede che la mantissa sia un valore compreso tra 0 incluso ed 1 escluso: 0 ≤ M < 1

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

3.14159 = 0.314159 × 101 0.00001 = 0.1 × 10-4

1958 = 0.1958 × 104

(11)

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 π 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.

(12)

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 π 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 eccesso 2⁷o 2¹⁰ 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.

(13)

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 frazione binaria in un modo

leggermente diverso da quello visto prima (solo per i numeri normalizzati)

(14)

Aritmetica binaria

Lo standard IEEE 754

Comprende la rappresentazione normalizzata e altre quattro rappresentazioni.

+/- 0 < esp < Max qualsiasi combinazione

Normalizzato Denormalizzato +/- Zero

+/- Infinito Not A Number

+/- 0 qualsiasi combinazione ≠0

+/- 0 0

+/- 111…111 0

+/- 111…111 qualsiasi combinazione ≠0

esponente mantissa

Numeri denormalizzati

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 denormalizzatiper rappresentare numeri più piccoli (vicini allo zero).

Per i numeri non normalizzati non vale la regola

«assumiamo la mantissa cominci con un 1 implicito»

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

0 000000001 0000000 segno mantissa esponente

(il minimo)

(15)

Aritmetica binaria

Numeri denormalizzati

Per i numeri denormalizzati non vale la regola che il bit: sono frazioni pure con uno zero a sinistra della virgola.

Il numero denormalizzato più grande ha esponente 0 e tutti uni nella mantissa, e vale circa 0.9999999 × 2^-127, quindi quasi come il più piccolo normalizzato.

0.9999999 è dato dalla mantissa, il fattore 2^-127è convenzionale.

È però possibile comporre numeri denormalizzati progressivamente più piccoli azzarando i bit a sinistra della mantissa.

Il più piccolo numero denormalizzato ha la mantissa composta di zeri, con il solo LSB pari a uno (0000...001). Il suo valore è 2^-150.

2^-23dato dalla mantissa e 2^-127convenzionale

Numeri denormalizzati

In pratica i numeri denormalizzati permettono una “transizione morbida” verso i valori che causano l’underflow.

Lo zero è rappresentato esplicitamente da una configurazione apposita.

Si può rappresentare il valore “infinito”

Che consente operazioni del tipo infinito + costante = infinito Se si fanno operazioni del tipo infinito / infinito si ottiene la codifica di qualcosa che non è un numero (NAN = not a number).

(16)

Aritmetica binaria

I numeri reali nei linguaggi di programmazione

In linguaggi come il C si possono dichiarare variabili in singola o doppia precisione

Singola precisione: float x;

Doppia precisione: double y;

I letterali frazionari sono double per default: 0.5 viene rappresentato come numero in doppia precisione.

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 moltiplica o si dividono le mantisse in modo consueto si sommano o si sottraggono gli esponenti

si normalizza

(17)

Aritmetica binaria

Operazioni in virgola mobile

I significati speciali sono gestiti correttamente dalle op. Es:

+10.3 / +zero +infinity -1.1 / +zero -infinity

zero / zero NaN  indefinito! (non conta il segno degli 0) +infinity + 12.0 +infinity

+zero * -200.0 -zero

infinity – infinity NaN  indefinito!

sqrt( -10 ) NaN  radice quadrata di neg 14.0 / +infinity +zero

15.1 / -infinity -zero -16.2 / +infinity -zero 12.001 + -zero 12.001

infinity / infinity NaN  indefinito!

NaN + 12 NaN  il NaN si progaga in tutte le op -zero < +zero true

zero > 0.0001 false

NaN == NaN false  il NaN da sempre false, persino qui

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 )

(18)

Aritmetica binaria

Operazioni in virgola mobile

>> 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 «pura»: spesso espressa in FLOPS FLoating-pontOPeration per Second

(op 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)