Aritmetica dei Calcolatoridisi.unitn.it/~sebe/info/08-aritmetica.pdf · Numeri in Virgola Mobile...

Informatica 1 / 34

Aritmetica dei Calcolatori

Operazioni su Bit

❖ Operazioni su Bit

❖ Memorie❖ Codifica deiNumeri Interi❖ Codifica conModulo e Segno

❖ Codifica inComplemento a 1

❖ Somma di Numeriin Complemento a 1

❖ Complemento a 2


❖ Operazioni suNumeri Binari❖ AritmeticaModulare❖ Numeri in VirgolaMobile

❖ Numeri Reali in C

Informatica 2 / 34

Scienza della rappresentazionee dell’elaborazione dell’informazione

● Abbiamo visto come i computer rappresentanol’informazione...

✦ Sequenze di bit (esempio: per i numeri naturali,rappresentazione binaria)

● ...vediamo ora come elaborare tale informazione!

✦ Operazioni su bit o sequenze di bit

Algebra Booleana





❖ Complemento a 2




Informatica 3 / 34

● Tecnicamente, “Algebra di Boole a 2 valori”...

✦ 2 soli possibili valori: 0 e 1

■ Se x e una variabile, x = 1⇔ x 6= 0,x = 0⇔ x 6= 1

✦ 3 operazioni: and (∧), or (∨) e not (¬)✦ 0: elemento neutro per ∨; 1 = ¬0: elemento neutro

per ∧

● Operazioni fondamentali:0 ∨ 0 = 00 ∨ 1 = 11 ∨ 0 = 11 ∨ 1 = 1

0 ∧ 0 = 00 ∧ 1 = 01 ∧ 0 = 01 ∧ 1 = 1

¬0 = 1¬1 = 0

Algebra Booleana: Assiomi





❖ Complemento a 2




Informatica 4 / 34

● Proprieta commutativa: a ∧ b = b ∧ a; a ∨ b = b ∨ a● Elementi neutri: a ∧ 1 = a; a ∨ 0 = a● a ∧ ¬a = 0; a ∨ ¬a = 1● Proprieta distributiva: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c);

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Or in Dettaglio





❖ Complemento a 2




Informatica 5 / 34

A

BC

C = A ∨B

● Il risultato e 1 se almeno uno dei due operandi e 1

✦ Per certi versi simile ad una somma

● Detto anche somma logica

✦ Talvolta indicato col simbolo +

● Estendibile ad n operandi: la somma logica di n variabili e1 se il valore di almeno una variabile e 1

And in Dettaglio





❖ Complemento a 2




Informatica 6 / 34

A

BC

C = A ∧B

● Il risultato e 1 se tutti e due gli operandi sono 1

✦ Per certi versi simile ad un prodotto

● Detto anche prodotto logico

✦ Talvolta indicato col simbolo ·

● Estendibile ad n operandi: il prodotto logico di n variabili e1 se il valore di tutte le variabili e 1

Memorizzazione dei Bit





❖ Complemento a 2




Informatica 7 / 34

Scienza della rappresentazionee dell’elaborazione dell’informazione

● Per poter elaborare l’informazione, deve esserememorizzata!

✦ Dove? Nella memoria principale (RAM: RandomAccess Memory)

■ Vedi slide “Architettura del Calcolatori”

● ...vediamo ora come puo funzionare tale memoria!

✦ Memorizzazione di bit o sequenze di bit✦ Varie possibilita: per esempio Flip-Flop e memorie

dinamiche

Flip Flop SR





❖ Complemento a 2




Informatica 8 / 34

R

S

Q

● Input S (Set) e R (Reset)● S e R mai contemporaneamente a 1● Output: Q — Dipende da se stesso...

Flip Flop SR - Come Funziona





❖ Complemento a 2




Informatica 9 / 34

S R Q precedente Q successivo

0 0 0 01 0 0 10 1 0 00 0 1 11 0 1 10 1 1 0

● S=1: La porta NOR in basso ha output sempre 0✦ Q=not R = 1 (perche se S=1 allora R=0)

● R=1: La porta NOR in alto ha output sempre 0: Q=0● S=R=0: La porta NOR in basso ha output not Q

✦ Q=Q● Utile per memorizzare un bit!!!

Memoria Dinamica





❖ Complemento a 2




Informatica 10 / 34

● Grosso numero di condensatori collegati a circuitielettronici

● Ogni condensatore puo essere in 2 stati:

✦ Condensatore carico: memorizza il bit 1✦ Condensatore scarico: memorizza il bit 0

● Ogni condensatore tende naturalmente a scaricarsi

✦ Lo stato di carica deve essere periodicamenteripristinato (refresh)

✦ Per questo si parla di memoria dinamica

● La memoria si cancella quando il computer viene spento(come per i Flip-Flop)

Locazioni di Memoria





❖ Complemento a 2




Informatica 11 / 34

● Flip-Flop, condensatori o altri elementi di memoria sonoraggruppati in gruppi di 8

✦ 8 bit = 1 byte

● Ogni gruppo di 8 elementi (byte) e chiamato cella (olocazione) di memoria

● Ogni locazione di memoria e identificata da un numero,chiamato Indirizzo di Memoria

● L’intera memoria e una sequenza di locazioni (celle)accessibili tramite il loro indirizzo

● 1024(= 210) byte = 1KB, 1024KB(= 220 byte) = 1MB,1024MB(= 230 byte) = 1GB, etc...

Codifica dei Numeri Interi





❖ Complemento a 2




Informatica 12 / 34

● k bit→ codificano 2k simboli/valori/numeri...

✦ Si usa la base 2 per codificare i numeri✦ Numeri naturali n ∈ N : valori da 0 a 2k − 1

● Come codificare numeri interi z ∈ Z?

✦ Problema: numeri negativi z < 0⇒ z /∈ N✦ Si codificano sempre 2k valori...✦ ... Ma quali???

● Varie possibilita: modulo e segno, complemento a 1,complemento a 2, ...

Codifica con Modulo e Segno





❖ Complemento a 2




Informatica 13 / 34

● Idea semplice: si usano k − 1 bit per rappresentare ilvalore assoluto (modulo) del numero...

● ...Ed un bit per codificare il segno!

✦ bit piu significativo a 0: numero positivo✦ bit piu significativo a 1: numero negativo

● Valori codificati: da −2k−1 + 1 a 2k−1 − 1

✦ 2k − 1 valori???✦ Come mai??? Due diverse sequenze di bit per

codificare lo 0? (+0 e −0???)

■ 1

k−1︷︸︸︷

000 . . . 0 vs 0

k−1︷︸︸︷

000 . . . 0

Codifica in Complemento a 1





❖ Complemento a 2




Informatica 14 / 34

● Altra idea semplice: i numeri negativi si rappresentanofacendo il complemento ad 1 del valore assoluto

✦ Numero positivo: rappresento il valore assoluto✦ Numero negativo: cambio 0 in 1 e viceversa

(complemento a 1 di x:

k︷︸︸︷

1 . . . 1−x = (2k − 1)− x)✦ Numeri positivi: ancora, bit piu significativo a 0

● Ancora, due rappresentazioni dello 0 (+0 e −0)?

k︷︸︸︷

111 . . . 1

vs

k︷︸︸︷

000 . . . 0● Modulo e segno→ Non facile da sommare...● Complemento a 1→ a volte le cose vanno meglio (se il bit

piu significativo non da’ riporto, OK)

Somma di Numeri in Complemento a 1





❖ Complemento a 2




Informatica 15 / 34

● Somma di numeri interi codificati in complemento a 1:

1. Sommare le rappresentazioni dei due numeri2. Riporto sul bit piu significativo→ sommarlo al

risultato3. Se i riporti delle due cifre piu significative della nuova

somma sono uguali, il risultato e attendibile4. Altrimenti, il risultato non e rappresentabile su k bit

● Esempio: 6 +−3 (codifica su k = 5 bit)

✦ 6 = 00110; −3 = 00011 = 11100

1 1 10 0 1 1 01 1 1 0 00 0 0 1 0

✦ 00010 + 1 = 00011 (= 3)

Complemento a 2





❖ Complemento a 2




Informatica 16 / 34

● Complemento a 2 di un numero binario:

✦ Scorrere i bit a partire dalla destra✦ Fino al primo bit che vale 1 (compreso), invariato✦ A partire dal bit successivo, fare il complemento a 1

● Equivalente a fare il complemento a 1 e poi sommare 1

✦ Complemento in base 2 di x: 2k − x = 1

k︷︸︸︷

0 . . . 0−x

● Esempio: complemento in base 2 di 87 (= 10101112)

✦ 1 piu a destra invariato, poi inverto : 0101001✦ 272 − 10101112 = 100000002 − 10101112 = 101001✦ Complemento a 1 +1: 0101000 + 1 = 101001

Codifica in Complemento a 2





❖ Complemento a 2




Informatica 17 / 34

● Numeri positivi: rappresentare il valore assoluto● Numeri negativi: rappresentati usando il complemento a 2

del valore assoluto

✦ Ancora, il bit piu significativo indica il segno✦ Stavolta, la codifica dello 0 e unica✦ Codifica i numeri da −2k−1 a 2k−1 − 1

● E stavolta, la somma e semplice...

✦ x+ (−y) = x+ (2k − y) = 2k + x− y...✦ ...Su k bit, questo e equivalente a x− y

Esempi di Codifica





❖ Complemento a 2




Informatica 18 / 34

decimale modulo complemento complementoe segno a 1 a 2

-4 100-3 111 100 101-2 110 101 110-1 101 110 1110 100 / 000 111 / 000 0001 001 001 0012 010 010 0103 011 011 011

Somme e Sottrazioni in Base 2





❖ Complemento a 2




Informatica 19 / 34

● Come normalmente in base 10 (numeri in colonna,riporto, etc...)

● Se si usa complemento a 2, funziona anche con numerinegativi

✦ Ma occhio agli overflow!!!✦ Overflow? Numeri su k bit, ma risultato non

rappresentabile su k bit✦ Matematica “dell’orologio”...

● Esempi: k = 6, 5 + 12

1 10 0 0 1 0 10 0 1 1 0 00 1 0 0 0 1

● k = 7, 5− 8; k = 7,−5 + 8; k = 7,−64− 8; k = 7, 63 + 1;

Esempi Senza Overflow





❖ Complemento a 2




Informatica 20 / 34

● k = 7, 5− 8

✦ 5 = 00001012;−8 = 00010002 + 12 = 11101112 + 12 = 11110002

0 0 0 0 1 0 11 1 1 1 0 0 01 1 1 1 1 0 1

✦ 11111012 =... −(11111012 + 12) = −00000112 = −3

● k = 7,−5 + 8

✦ −5 = 00001012 + 1 = 11110102 + 12 = 1111011;

8 = 00010002

1 1 1 1 0 0 0 01 1 1 1 0 1 10 0 0 1 0 0 00 0 0 0 0 1 1

✦ 00000112 = 3

Esempio di Overflow





❖ Complemento a 2




Informatica 21 / 34

● k = 7,−64− 8

✦ 64 = 10000002;−64 = 10000002 + 12 = 01111112 + 12 = 10000002

✦ 8 = 00010002;−8 = 00010002 + 12 = 11101112 + 12 = 111100021

1 0 0 0 0 0 01 1 1 1 0 0 00 1 1 1 0 0 0

✦ 01110002 = 56... WTH??? Sommando 2 numerinegativi si ottiene un numero positivo???

● −64− 8 = −72...

✦ Numeri rappresentabili: −26 = −64→ 26 − 1 = 63...

Esempio di Overflow





❖ Complemento a 2




Informatica 22 / 34

● k = 7, 63 + 1

✦ 63 = 01111112✦ 1 = 000000012

1 1 1 1 1 10 1 1 1 1 1 10 0 0 0 0 0 11 0 0 0 0 0 0

✦ 10000002 = −(10000002 + 1) = −(01111112 + 12) =−1000000 = −64... WTH??? Sommando 2 numeripositivi si ottiene un numero negativo???

● Ancora, il risultato corretto (63 + 1 = 64) non sarebberappresentabile...

Esempi ed Esercizi





❖ Complemento a 2




Informatica 23 / 34

● Numeri su k = 7 bit, codificati in complemento a 2● Verificare se c’e overflow

✦ 0110110 + 0000011

■ Somma di due numeri positivi: mi aspetto risultatopositivo...

✦ 1001010 + 1111101

■ Somma di due numeri negativi: mi aspettorisultato negativo...

✦ 1001010 + 1100000

■ Somma di due numeri negativi: mi aspettorisultato negativo...

✦ 0100000 + 1111010; 1100000 + 0000110

Ancora su Overflow





❖ Complemento a 2




Informatica 24 / 34

● Abbiamo visto overflow in somme (/ sottrazioni) fra interi

✦ Se a+ b > 2k−1 − 1, overflow!✦ Se a+ b < −2k−1, overflow!

● Nota: −2k−1 ≤ a ≤ 2k−1 − 1 e −2k−1 ≤ b ≤ 2k−1 − 1

✦ Overflow solo se a e b hanno lo stesso segno!!!

● Puo esserci overflow anche in caso di numeri naturali

✦ Esempio: k = 7, 100 + 100 (100 = 11001002)1 1 1

1 1 0 0 1 0 01 1 0 0 1 0 01 0 0 1 0 0 0

✦ 10010002 = 64 + 8 = 72: 100 + 100 = 72???

La Matematica dell’Orologio





❖ Complemento a 2




Informatica 25 / 34

● Aritmetica modulare: considero solo n numeri interi

✦ Numeri da 0 a n− 1...✦ ...O numeri da −n/2 a n/2− 1...

● Arrivato al numero piu grande, riparto dal piu piccolo

✦ Se i numeri vanno da 0 a n− 1, (n− 1) + 1 = 0(contando dopo n− 1 riparto da 0)

✦ Se i numeri vanno da −n/2 a n/2− 1,n/2− 1 + 1 = −n/2

✦ Numeri sul quadrante di un orologio!

● Definizione piu formale: classi di equivalenza modulo n

✦ Relazione di equivalenza: a ≡ b⇔ a%n = b%n

Cosa Succede in Caso di Overflow?





❖ Complemento a 2




Informatica 26 / 34

● Operazioni su numeri di k bit→ aritmetica modulo 2k

✦ Calcolando a+ b si ottiene in realta (a+ b)%2k...✦ ...Se il risultato della somma e < 2k, allora

(a+ b)%2k = a+ b← no overflow!✦ Altrimenti, risultato “strano”...

● Usando rappresentazione in complemento a 2 dei numeriinteri, il discorso e analogo:

✦ Se a+ b e compreso fra −2k−1 e 2k−1 − 1, allora nooverflow (risultato corretto)!

✦ Se a+ b < −2k−1, ottengo a+ b+ 2k. Positivo!!!Overflow!

✦ Se a+ b > 2k−1 − 1, ottengo a+ b− 2k. Negativo!!Overflow!

Rappresentazione dei Numeri Reali





❖ Complemento a 2




Informatica 27 / 34

● Rappresentare esattamente un numero reale x ∈ R non epossibile...

✦ Numero reale: numero infinito di cifre decimali nonperiodiche...

✦ ...Non rappresentabile con un numero finito di bit!

● Rappresentiamo un’approssimazione di numeri reali!!!

✦ Alcuni numeri sono rappresentabili correttamente...✦ ...Altri no

● Rappresentazione in virgola mobile

✦ Numero fisso di cifre significative, ma numerovariabile di cifre dopo la virgola

Virgola Fissa e Mobile





❖ Complemento a 2




Informatica 28 / 34

● Numero reale su k cifre: si possono dedicare k − f cifrealla parte intera e f cifre alla parte frazionaria:

k︷︸︸︷ck−1ck−2 · · · cf︸︷︷︸

k−f

. cf−1 · · · c0︸︷︷︸

f

✦ xB =∑k

i=0 ciBi−f =

∑ki=0 ciB

i/Bf =∑k

i=0 ciBi ·B−f

✦ Convertiamo il numero in base 10 come se nonavesse virgola e poi moltiplichiamo per B−f : Virgolafissa!

● Virgola mobile: f non e fisso...

✦ x = M ·BE

✦ M : mantissa; E: esponente

Virgola Mobile





❖ Complemento a 2




Informatica 29 / 34

● Numero x e rappresentato in virgola mobile su k bit

✦ x = M ·BE

✦ m bit per la mantissa M ...✦ ...e e = k −m bit per l’esponente E

● L’esponente e quello che fa “muovere la virgola”● Nei computer, B = 2 (rappresentazione binaria)● Mantissa ed esponente: positivi o negativi

✦ Segno mantissa: segno di x✦ Esponente negativo: x piccolo; esponente positivo x

grande

● Rappresentati in complemento a 2 o con altre tecniche...

Virgola Fissa vs Mobile





❖ Complemento a 2




Informatica 30 / 34

● Virgola Fissa:

✦ Operazioni semplici da implementare: e sufficienteeffettuare somme, sottrazioni, moltiplicazioni come sefossimo tra interi e riscalare il risultato

✦ Questo semplifica i requisiti per realizzare una CPU✦ Inoltre se i risultati sono rappresentabili, le operazioni

non introducono errori di approssimazione

● Virgola Mobile:

✦ Permette di trattare nella stessa applicazione sianumeri grandi che numeri piccoli

✦ Applicazioni che abbracciano piu ordini di grandezza

Numeri Reali in C





❖ Complemento a 2




Informatica 31 / 34

● Standard IEEE (IEEE 754)● Mantissa M : modulo e segno (bit di segno s!)● Mantissa “normalizzata”: 1.M● Esponente −2e−1 + 1 < E ≤ 2e−1 − 1 rappresentato come

E′ = E + 2e−1 − 1. Notare che (E′ > 0)● E′ = 0 ha un significato speciale: E = −(2e−1 − 2) e

mantissa 0.M . Anche E′ = 2e − 1 ha un significatospeciale

E′ > 0 : x =

{

1.M · 2E′−(2e−1

−1) Se s = 0

−1.M · 2E′−(2e−1

−1) Se s = 1

E′ = 0 : x =

{

0.M · 2−(2e−1−2) Se s = 0

−0.M · 2−(2e−1−2) Se s = 1

Tipi Floating Point in C





❖ Complemento a 2




Informatica 32 / 34

● float: precisione singola

✦ k = 32✦ e = 8, m = 23

● double: precisione doppia

✦ k = 64✦ e = 11, m = 52

● long double: precisione estesa o quadrupla

✦ k = 80 o k = 128✦ e = 15, m = 64 o m = 112

Esempio: Precisione Singola





❖ Complemento a 2




Informatica 33 / 34

● Approssimazioni di numeri reali rappresentate su 32 bit● Esponente rappresentato su 8 bit

✦ Se E′ 6= 0, si sottrae 27 − 1 = 127✦ Se E′ = 0, esponente −27 − 2 = −126

● Mantissa rappresentata su 23 bit● Bit s di segno

E′ 6= 0⇒ x = (−1)s · 1.M · 2E′−127

E′ = 0⇒ x = (−1)s · 0.M · 2−126

Precisione Singola - Valori Massimo eMinimo





❖ Complemento a 2




Informatica 34 / 34

● Massimo valore rappresentabile:

✦ Massima mantissa: M =

23︷︸︸︷

1 · · · 1✦ Massimo esponente: E = 254− 127 = 127

✦ x = 1.

23︷︸︸︷

1 · · · 1 ·2127 = (2− 2−23) · 2127 ≃ 3.4 · 1038

● Minimo valore rappresentabile: ≃ −3.4 · 1038

● Minimo valore positivo rappresentabile:

✦ Minima mantissa: M = 1✦ Esponente: E′ = 0⇒ E = −126

✦ x = 0.

23︷︸︸︷

0 · · · 1 ·2−126 = 2−232−126 ≃ 1.4 · 10−45

Aritmetica dei Calcolatoridisi.unitn.it/~sebe/info/08-aritmetica.pdf · Numeri in Virgola Mobile...

Documents

Transcript of Aritmetica dei Calcolatoridisi.unitn.it/~sebe/info/08-aritmetica.pdf · Numeri in Virgola Mobile...