Rappresentazione dei numeri ed aritmetica di base · Rappresentazione dei numeri ed aritmetica di...

transcript

Rappresentazione dei numeri ed aritmetica di base

Codifiche dei numeri, agenda

• Codifica “naturale” – Mediante il Sistema di Numerazione Posizionale (S.N.P.), in base 2– Adatto solo per numeri naturali (interi positivi)

• Modulo e Segno– Un bit per il segno, gli altri per il modulo in SNP– Solo interesse teorico

• Complemento a 2– Codifica mediante SNP “non puro”– Ampiamente usata per le proprietà aritmetiche (facilita circuiti di calcolo)

• Virgola mobile– Numeri reali– Standard IEEE 754, ampiamente usato

Calcolatori Elettronici, Beraldi, 19/20

Interi

Naturali

Numeri e numerali

Numero

Numerale Numerale

Rappresentazione

Interpretazione

Trasformazione fra Rappresentazioni

Esempio numerali: “dodici”, 12, XII, 0xC

Entità astratta

Analogia: gatto e cat denotano lo stesso “oggetto” in due lingue differenti

Sistema di Numerazione Posizionale, richiami

• E’ definito da una coppia (A,B) dove:– B>1 è un intero, detto base del sistema, ed A un insieme di simboli

distinti, le cifre , con |A|=B– sistema decimale, B=10, A={0,1,2,3,4,5,6,7,8,9}– sistema binario, B=2, A={0,1}– sistema ottale, B=8, A={0,1,2,3,4,5,6,7}– sistema esadecimale, B=16, A={0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}

• Ogni cifra rappresenta un numero distinto compreso fra 0 e B-1

• 1à “uno”, 2à”due”

• Interpretazione mentale immediata

Sistema Numerazione Posizionale , richiami

• Un valore numerico è rappresento da una sequenza di cifre (allineamento) appartenenti ad A

dk-1..d2d1d0.d-1d-2…d-p …

• PARTE-INTERA.PARTE-FRAZIONARIA

• L’indice associato alla cifra denota la posizione della cifra • La posizione esprime il peso della cifra

– Valore di di= V(di) = di x Bi

Esempio: sistema decimale (base 10)

• 10 cifre, A={0,1,2,3,4,5,6,7,8,9}• Esempio: 743.234

– d2=7, d1=4, d0=3 – V(743) = 7 x 102 + 4 x 10 + 3– V(0.234) = 2 x 10-1 + 3 x 10-2 + 4 x 10-3

103 102 101 100 10-1 10-2 10-3

1000 100 10 1 0.1 0.01 0.001

Notazione

• Per evidenziare la base B del sistema di numerazione si usa la seguente notazione

• (…)B (B in base 10!)

• Negli esempi seguenti, se omessa vale 10• La cifra più a sinistra è detta cifra più significativa, quella a destra cifra

meno significativa– Se B=2 si usano gli acronimi MSB (Most Significant Bit) ed LSB (Least

Significant Bit)

Sistema Binario (base 2)

•Utilizzato dai circuiti elettronici dei calcolatori

•2 cifre (bit) d Î A = {0,1}

V(N) = dk-1 x 2k-1 + dk-2 x 2k-2 +.....+ d1 x 21 + d0 x 20 + d-1 x 2-1 +......+ d-p x 2-p

(1010.101)2 = 1 x 23 + 1 x 21 + 1 x 2-1 + 1 x 2-3 = (10.625)10

23 22 21 20 2-1 2-2 2-3

8 4 2 1 0.5 0.25 0.125Calcolatori Elettronici, Beraldi, 19/20

Potenze di 2 ricorrenti

• 22=4• 23=8• 24=16• 25=32• 26=64• 27=128• 28=256• 29=512• 210=1024 (K) K=Kilo• 220 = 1024K (M) M=Mega• 230 = 1024M (G) G=Giga• 240 = 1024G (T) =Tera• 250 = 1024T (P) =Peta

• 216=65536 = 64 K• 232= 4 G

Altre basi notevoliBasi 8 e 16

• Esempio: – (721)8à 7 x 82 + 2 x 81 + 1 x 80 = 7x64 + 16 + 1 = 448 +17=(465)10

– (0.1)8à 1/8 = (0.125)10

• Esempio: – (721)16 à 7 x 162 + 2 x 161 + 1 x 160 = 7x 256 + 32 + 1 = 1792 + 33 =

(1825)10

– (0.1)16 à 1/16 = (0.0625)10

• Nota: nel caso rappresentazioni esadecimali è prassi anteporre 0x, oppure il suffisso H

– Ex: 0x721, 721H

Conversione da una base ad un’altra

• Problema: dato un valore rappresentato dall’allineamento N in base B1 trovare la rappresentazione N’ in base B2

• (N)B1 ® (N’)B2

• Nel seguito, se chiaro dal contesto, N denota sia il valore che l’allineamento di cifre

• Bisogna convertire separatamente le parti intera (NI) e frazionaria (NF)

– (N)B1=(NI.NF)B1

– (NI)B1 ® (N’I)B2

– (NF)B1 ® (N’F)B2

Conversione

• I metodi dipendono dalla scelta di usare la base di partenza (B1) o quella di arrivo (B2)

• Poiché si ha familiarità con la base B=10 quando una delle due basi è 10, allora si sceglierà il metodo che consente di lavorare in tale base– Casi notevoli

• B1¹10 e B2=10 (già visto)• B1=10 , B2¹10• B2=B1k

Conversione da base 10 a B, N>0 ed intero

• Usiamo la seguente osservazione: in generale possiamo affermare che per ogni intero B (1<B£N):

N = Q x B + R [1]

• Dove Q (Q<N) è il quoziente della divisione fra interi (divisione Euclidea) ed R (0£R<B) il resto

• Notazione– Q = N/B (quoziente)– R = N mod B (resto)

• Sia V(N) = dk-1Bk-1 + .. + d1B + d0

• D’altra parte: dk-1Bk-1 + .. + d1B + d0 = B(dk-1Bk-2 + .. + d1) + d0e quindi (vedi [1]): d0=N mod B, e dk-1Bk-2 + .. + d1 = N / B

N intero da convertire, B base di arrivo

iß0;while N<>0 do

1. diß N mod B2. NßN/B3. ißi+1

endwhile

Esempio: (25)10 = (??)2

(25)10 = (11001)2

Algoritmo di Conversione da base 10 a B, N>0 ed intero

N N / 2 N mod 2 Cifra

25 12 1 d0=112 6 0 d1=0

6 3 0 d2=0

3 1 1 d3=1

1 0 1 d4=1

N N / 16 R mod 16 Cifra

30 1 14 d0=E

1 0 1 d1=1

(30)10 = (??)16

(30)10 = (1E)16 =0x1E

Altro esempio

N N/2 R mod 2 Cifra

30 15 0 d0=0

15 7 1 d1=1

7 3 1 d2=1

3 1 1 d3=1

1 0 1 d4=1

(30)10 = (11110)2

Notaà 0xE=(1110)2

Metodo “diretto” di conversione da base 10 a B

• Dato N individuare direttamente le potenze nella base B

Esempio: • rappresentare 27 in base B=2:

– 16+8+2+1 => (11011)2

• Osservazione: • LSB=0 ó pari; LSB=1 ó dispari • Valore massimo = 111….1 = 2K-1 (K bit pari ad 1)

Relazione fra le basi 2/8/16

(E54)16

(1110 0101 0100)2

(621)8

(110 010 001)2

(E54)16 (1110 0101 0100)2 (111 001 010 100)2 (7124)8

Da base 16(2) a 2(16)

Da base 8(2) a 2(8)

Da base 16(8) a 8(16) Calcolatori Elettronici, Beraldi, 19/20

Conversione da base 10 a B, N<1

N=d-1B-1 + d-2B-2+. + d-mB-m+ .. + …NB= d-1B0+ d-2B-1 .. + d-mB-m+1 + … + … = d-1+ (d-2B-1 +.. + d-mB-m+1+ ..+ ..) =I + N’ (I=intero, N’<1)

Quindi per isolare la prima cifra:

d-1 = parte intera di NB (=trunc(NB) )

N’ = NB - d-1 = (d-2B-1 .. + d-mB-m+1+ ..+ ..)

• Siamo nel caso iniziale… Le altre cifre si isolano in modo analogo:• d-2 = parte intera di N’B• …• Finché precisione voluta oppure N=0

N<1 valore frazionario da convertire, B base di arrivo, m cifre (precisione)

iß1;while N>0 and i£m do

1. d-i ß trunc (NB);2. NßNB - d-i; 3. Ißi+1

endwhile

Algoritmo di conversione da base 10 a B, N<1

(0.8125)10 = (0.1101)2

d-3=000.50.25

d-2=111.250.625

d-4=111.00. 5

d-1=111.6250.8125

CifraTrunc(2N)2NN

Esempio: (0.8125)10 = (??)2

Esempio: (12.25)10 ® (..)2

• 12/2 = 6 resto 0 ® d0=0• 6/2 = 3 resto 0 ® d1=0• 3/2 = 1 resto 1 ® d2=1• 1/2 = 0 resto 1 ® d3=1

• 0.25 x 2 = 0.50, parte intera 0 ® d-1=0• 0.50 x 2 = 1.0, parte intera 1 ® d-2=1

(12.25)10 ® (1100.01)2

N 2N Trunc(2N) Cifra

0.2 0.4 0 d-1=0

0.4 0.8 0 d-2 =0

0.8 1.6 1 d-3 =1

0.6 1.2 1 d-4 =1

Esempio: (0.2)10 = (??)2

(0.2)10 = (0.0011)2

Esempionumeri periodici

Esercizio

• Esprimere in base 10 il numero periodico (0,10)2

Riepilogo

10 B¹10

prodotti successivi (N<1)

sviluppo del polinomio

divisioni successive (N intero )

16Calcolatori Elettronici, Beraldi, 19/20

Codifica naturale

• Esprime il numero mediante il sistema posizionale usando una stringa di bit…

• Un bit b rappresenta una cifra binaria– Il bit b=1 rappresenta la cifra binaria 1 e b=0 la cifra 0–

Numeri interi, Modulo e segno

• E’ il più immediato da comprendere – Si dedica un bit al segno ed i rimanenti al modulo – Di regola 1 denota il segno -

• Esempio

– -15 à |15| = (1111)2 à -15 = (11111)2

– 15 à (01111)2

• Con k bit l’intervallo di dei valori rappresentabili è S=[-2k-1-1,..,2k-1-1] – Doppia rappresentazione di 0

Complemento a 2

• Fissato un numero k>1 di cifre binarie, il complemento a 2 su k bit di un intero N, N Î S={-2K-1 ,..2K-1 –1} , è

N 0£ N £2K-1 –1C(k,N)=

2k-|N| -2K-1£ N £–1

•Una definizione alternativa è C(k,N) = (N + 2k) mod 2k

Algoritmo di conversione…

• Sia N il negato di N ed N’ il complemento su k bit..• N’+N=2k

• N + N + 1 = 2k

• Pertanto, N’ = N +1

Un “regolo” per i calcoli in complemento

2 - 3 ® (2+5) mod 8 = 7 mod 8 = 7 ® -13 – 2 ® (3+6) mod 8 = 9 mod 8 = 1 ® 1-1 - 3 ® (7 + 5) mod 8 à 12 mod 8 = 4 ® -4

0 01 12 23 3-4 4-3 5-2 6-1 7

N C (3,N)

complemento

valore rappresento

|N| + C(3,N)=8

TELEDIDATTICA

Attenzione

• Questa videolezione sostitutiva della didattica frontale è registrata econservata tramite strumenti digitali.

• La registrazione è riutilizzabile solo alle condizioni previste dalla normativavigente sul riuso dei dati pubblici (direttiva comunitaria 2003/98/CE e d. lgs.36/2006 di recepimento della stessa), in termini compatibili con gli scopi per iquali è stata raccolta e registrata, ovvero esclusivamente a fini didattici, e nelrispetto della normativa in materia di protezione dei dati personali.

• Gli studenti possono usare le registrazioni ai soli fini didattici esi impegnano a non distribuire le registrazioni all'esterno etanto meno di utilizzarle a fini commerciali.

Riassunto argomenti

• Numeri interi e frazionari (positivi)• Conversione Binario à Decimale • 101010.11 à ?

• Conversione Decimale à Binario • 25 à ?

• Usiamo un foglio excel per queste operazioni di conversione...

Complemento a 2

Algoritmi per il calcolo del complemento di –N

• Primo metodo: – Rappresentare il valore assoluto di N in base 2– Invertire tutti i bit ed aggiungere 1

• Esempio: rappresentare N=–25 in complemento su k=8 bit. |-25| = 25 = 16+8+1

00011001 (25)

11100110 + (Inverto i bit)1 = (sommo 1)

11100111 (231)

• Secondo: – Rappresentare il valore assoluto di N in base 2 – Partendo da destra, lasciare invariati tutti i bit fino al primo bit 1, poi invertire gli altri

Valore expresso da un un numero binario complemento a 2

Esempio

= 4+1 = 5=-8+4+1= -3 = 1 più piccolo positivo=4+2+1 = 7 più grande positivo

=-8+4+2+1=-1 più piccolo negativo=-8 più grande negativo

Esempio: k = 4 bit -23 22 21 20ßPeso-8 4 2 1

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

1 1 1 11 0 0 0

• 0a à (0000 1010) (• 0• 1• 2• ..• 9• A (10)10

Disassembly of section .text:main:; int main() {

0: 08 d0 4d e2 sub sp, sp, #8

4: 00 00 a0 e3 mov r0, #08: 04 00 8d e5 str r0, [sp,

#4]; unsigned short x = 123;

c: 7b 10 a0 e3 mov r1, #12310: b2 10 cd e1 strh r1, [sp,

#2]; unsigned short y = 124;

14: 7c 10 a0 e3 mov r1, #12418: b0 10 cd e1 strh r1, [sp]

; return 0;1c: 08 d0 8d e2 add sp, sp,

#820: 1e ff 2f e1 bx lr

clang esempio2.c -target arm-none-eabi -c -g

int main() {unsigned short x = 123;unsigned short y = 124;return 0;}

Operazioni aritmetiche fra interi

• Addizione • Sottrazione • Moltiplicazione • Divisione

Addizione binaria

• BASE B=2• 0+0=0• 0+1=1• 1+0=1• 1+1=10 =(2)10

• 1+1+1=11 =(3)10 1 1 1 0 0 0 + (56)100 1 1 1 0 1 = (29)10

----------------------(85)10

Riporto (carry)

64+16+4+ 1 = 85

La somma di due numeri a k bit e’ rappresentabile al piu’ con k+1 bitSe abbiamo a disposizione k bit ed il risultato richiede k+1 bit si ha overflow

Regole per l’addizione

Somma di tre bit: A B e Cin

Cout Cin +A +B =

------------S

Cin A B Cout S

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

In generale:Cin e’ il il riporto (carry) generato dalla somma dei bit in posizione precedenteCout è il riporto generato

la coppia di valori (Cout,Si) indica il numero di “uno”, espresso in base 2

Schema di un addizionatore k bit

b0b1bK-1a0a1a2aK-1 b2

sK-1 s2 s1 s0

c1c2cK-1

Cin A B Cout S

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

http://www.edutecnica.it/sistemi/sommatori/sommatori.htm

Proprietà della rappresentazione in complemento • Perché usare la rappresentazione in complemento?

• Semplifica le operazioni aritmetiche

• La somma algebrica X+Y può essere calcolata mediante la somma aritmetica dei complementi: C(X+Y)=[C(X)+C(Y)] mod 2k

• Semplificazione dei circuiti elettronici che eseguono le operazioni – Il calcolo del complemento non richiede l’esecuzione di alcuna differenza

Sottrattore/Addizionatore

SOMMATORE

0/1(A/S)

0à 11à0A BaK-1 a0 bK-1 b0

Esempio

• -5 + 2 (su K=8 bit)• Troviamo la rappresentazione di -5 in complemento• |-5|=5=4+1®

0000 0101 ®1111 1011

1111 1011 (-5)0000 0010 (+2)1111 1101 (-3)

• Verifica: 1111 1101 ® -128 + 64 +32+16+8+4+1 = -3

Altro esempio

• K=4à 24=16, valori rappresentabili={-8..7}

• X=-1, Y=-3• C(-1)=16-1=15 à 11112• C(-3)=16-3=13 à 11012

1111 + (15)1101 = (13)11100 - (28)10000 = (16)1100 Per eliminare il contributo 24, tralascia MSB

Rappresenta -8+4 = -4 (corretto)

Moltiplicazione numero A per 2k

• Il prodotto di A per 2k si ottiene postando di k posizioni le cifre a sinistra ed inserendo k bit pari a zero in LSB ()

• Esermpio (k=1): A=1101 à 11010• (8+4+1) à (16+8+2) • 13 à 26

• Domanda= Dimostrare la regola

Prodotto AxB (qualuque B)

• Osservazione: Un numero intero è pari alla somma di potenze di 2

• Esempio: B=(1101)2 à 8+4+1 à 23+22+20

• Sfruttando la proprietà distributiva del prodotto rispetto alla somma, AxB è pari a

• A (23+22+20) = A23+A22+A

Esempio (18 x 10)

1 0 0 1 0 (18)1 0 1 0 (10)

---------------------

=> 27+ 25 + 24 + 22 = 128 + 32 + 16 + 4 = 180

0 0 0 0 01 0 0 1 0

0 0 0 0 01 0 0 1 0----------------------

1 0 1 1 0 1 0 0

Regole del prodotto fra due bit

• A B = P• 0 0 = 0• 0 1 = 0• 1 0 = 0• 1 1 = 1

• Questa regola si chiama and e si indica in uno dei seguenti modi:

• A and B • A ∙ B• A & B

Esercizio: Algoritmo di moltiplicazione (in C)

• Scrivere l’agoritmo del prodotto in C usando somme parziali• Operazioni richieste:• Prodotto: x2 Arithmetic Shift Left (<<) • Estrarre MSB: Arithmetic Shift Right (>>) più AND

• Conosciamo meglio questi operatori

Arithmetic Shift Left (ASL)

linguaggio C:B=A<<1

linguaggio assembly (x86):ASL

ASL Esempi

• 011001010 à 110010100 (domanda: è sempre corretto ASL= x2 ?)

• (per i numeri negativi no)

Arithmetic Shift Right (ASR)

linguaggio C:B=A>>1

linguaggio assembly (x86):ASR

Bitwise AND

0 1 1 1 1 0 1 1

1 0 0 1 0 1 0 1

0 0 0 1 0 0 0 1

A and B

Prevelare il bit meno significativo (LSB) di A

• A & 1

• Perchè ?

Esercizio: Algoritmo di moltiplicazione

A=..B=..R ß 0...0repeat K times {

b ß B & 1if b = 1{

RßR+A}SHL R //Left shiftSHR B //Right shift

Esercizio: Algoritmo di moltiplicazione

unsigned char A = 18;unsigned char B = 12;unsigned char P=0;printf("%d %d ",A,B);for (int i=0;i<8;i++){

(B&1)&&(P+=A);A<<=1;B>>=1;

}printf("%d\n",P);}

Divisione di un numero A per 2

• La divisione per si ottiene spostando le cifre a sinistra di 1 posizione e copiando il MSB

Esempio: -128 / 2= -64 (2=21, shift 1 posizione)1000 0000 à1100 0000 à (-64)

Esempio

• La divisione di N per 2k si ottiene postando di k posizioni le cifre a destra ed inserendo k bit pari al valore di MSB

• Esempio : -128/8 = -16 (8=23)

1000 0000 à (3 posizioni a destra)

1111 0000 = (-16)10

• Esempio : -128/8 = -16 (8=23)

• Esercizio: verificare tale regola

Divisione per 2 di numeri dispari

• 10001001 (-128 + 8 + 1 = -119)

• 11000100 (-128+64+4 = -60 )

• Divisione per 2 con arrotondamento verso i negativi... (-119/2 = -60)

• 11111111 (-1) • 11111111 (-1) (-1/2 = -1)

Divisione euclidea numeri >0 (Quoziente e resto)

• A = Q x D + R • A = Divisiore • D=Dividendo• Q=Quoziente • R=Resto

Algoritmo di divisione

• A = Q x D + R• A = Dividendo• D = Divisore• Q=Quoziente (incognita)• R=Resto (incognita)

DividendoDivisiore

Quoziente

Esempio divisione fra interi: 29/3 (11101/11)2

11101 1111000 100101

29 – 3 x 23 = 29-3x8 = 29 – 24 = 5 à b3 = 1

00101 111100 10<0

5 – 3 x 22 = 5-3x4 = 5 – 12 = -7 à b2 = 0

00101 11110 100

<05 – 3 x 21 = 5-3x2 = 5 – 6 = -1 à b1 = 0

Esempio divisione fra interi: 29/3 (11101/11)2

0101 1111 100110

5 – 3 x 20 = 5-3 = 2 à b0 = 1

Esempio divisione fra interi: 29/3

• Supponiamo i = 3

• 29 – 3 x 23 = 29-3x8 = 29 – 24 = 5 à b3 = 1• 5 – 3 x 22 = 5-3x4 = 5 – 12 = -7 à b2 = 0• 5 – 3 x 21 = 5-3x2 = 5 – 6 = -1 à b1 = 0• 5 – 3 x 20 = 5-3 = 5 – 3 = 2 à b0 = 1

• RESTO R = 2, Q = (1001)2 = 9

• Se fossimo partiti da qualunque i>3, avremmo trovato bi = 0 e quindi il risultato sarebbe stato lo stesso..

Divisione come successione di sottrazioni (idea)

• Eseguire iterativamente:

R(i) = R(i+1) – D bi 2i

• Dove i = indice iterazione, R = Resto, bi = cifra incognita• Osservazione: si parte da un valore i e si ‘scende’• Quale deve essere il valore iniziale di i?

Algoritmo divisione interi (A/D) (restore division)

A=..D=..Q=0 R ß Ai ß sizeof (A)repeat until i==0 {

SHL Q //Q=2QRßR-2iDif R<0 {

Q+=0RßR+2iD //Restore data

}else{

Q+=1 }i-=1}

R(i) = R(i+1) – D bi 2i

Divisione fra interi

• Operazioni richieste:• Shift • Confronto fra numeri• Differenza

Esempi di istruzioni aritmetiche assembly

• add , somma • sub , sottrazione

• div , divisione fra interi senza segno• mul , moltiplicazione fra interi senza segno

• idiv , divisione fra interi con segno • imul , moltiplicazione fra interi con segno

Estensione del segno

• Problema:– Sia dato un intero N, rappresentato in complemento mediante k bit– Rappresentare N usando k+q bit (q>0)

• Soluzione:– Fare q copie di MSB

• Dimostrazione (banale per N positivo)– Sia N<0 (N=1bb…b , dove b è una cifra binaria) – Per induzione: Sia Nq la stringa con estensione di q bit

• q=1: Poiché –2K–1=–2K +2K–1, allora V(N)=V(N1). • q>1: estendere di un bit la stringa ottenuta da N con estensione di q-1 bit à

V(Nq)=V(Nq-1)• Esempio

– -2 = (110)2 con 3 bit diventa (111110)2 su 6 bit

Overflow

• Esprimere gli operandi in complemento alla base– La rappresentazione in complemento differisce solo per i valori negativi

• Eseguire la somma• Trascurare l’eventuale riporto• Se non si è verificato overflow, allora la somma rappresenta il risultato

espresso in complemento• Si verifica overflow quando gli operandi hanno lo stesso segno ed il

risultato ha segno opposto

Overflow, esempio

• Eseguire su k=4 bit la differenza: –3-6 |-3| ® 2+1 ®0011 ®1101

|-6| ® 4+2 ®0110 ®1010

1101 + (-3)1010 = (-6)

1000 (riporti)

(1)0111 (7!)

Rilevazione overflow

Si e’ verificato OVERFLOW se:1) i due operandi hanno lo stesso segno 2) Il risultato ha il segno diverso dagli operandi

ma……. 1000

-3 + 1101-6 = 1010

------- => ------------9 10111 => 7

0100+5 + 0101+6 = 0110

------- => -----------+11 01011 => -5

……il verificarsi dell’overflow implica la disuguaglianza del riporto in ingresso e quello in uscita dalla posizione MSB (Cin<>Cout)

L’overflow si può rilevare testando la condizione “Cin<>Cout” di MSB

Esercizi di riepilogo

• Eseguire le seguenti conversioni• (-16)10 = (??)2 [complemento a 2, minimo numero di cifre ]• (-16)10 = (??) 2 [complemento a 2, k=10 cifre binarie ]• (-126)10 = (??) 2 [complemento a 2, minimo numero di cifre ]• (27)10 =(??)2

• (1/3)10 = (??)3• (128)10 = (??)16 = (??)8 = (??)2• (11.111)2 = (??)10

Esercizi di riepilogo

• Eseguire le operazioni• 16 - 23, in complemento (k=7 bit) • 16 + 23 in complemento (k=7 bit, k=6 bit) • -16 - 23 in complemento (k=7 bit e k=6 bit) • 11101 x 11• 10101011 / 10

Operazioni e range (esempio)

. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .

unsigned a + b

Risultato corretto

Risultato errato

Range nel linguaggio C

• short int [-128 , +127] 1 byte.• int [-32769 ,+32767], 2 byte in memoria.• long int [2147483648 , +2147483647] 4 byte.

• char [-127,128]

Range di valori in Python

• Gli interi in Python 3 non sono limitati; • Python assegna automaticamente memoria addizionale quanto è

necessario quando i numeri diventano grandi.

Codifica ‘ASCII’

• Lab

Esempio

int main(){unsigned char a = 10;unsigned char b = 15;unsigned char c ;c = a+b;return 0;}

Registri (piccolo predulio)

• Nella CPU gli operandi delle operazioni aritmetiche sono (di norma) contenuti nei ‘registri’

• Un registro è una memoria ad altissima velocità• In assembly, i registri sono indicati simbolicamente

• Ad esempio, l’architettura x86 ha 8 registri da 32 bit: A,B,C,D,DI,SI

• Si può riferire un byte, 2 bytes, o 4 bytes del registro:

• eax (4 bytes), ax (2 bytes), ah (byte 1), ai (byte 0)

eax ax

Prime istruzioni assembly (x86)

• movb //copia un byte• movzbl //copia un byte, occupando un long estendi con zeri • addl //addiziona due long

Esempio

…; unsigned char a = 10;

d: c6 45 fb 0a movb $10, -5(%rbp); unsigned char b = 15;

11: c6 45 fa 0f movb $15, -6(%rbp); c = a+b;

15: 0f b6 4d fb movzbl -5(%rbp), %ecx19: 0f b6 55 fa movzbl -6(%rbp), %edx1d: 01 d1 addl %edx, %ecx1f: 40 88 ce movb %cl, %sil22: 40 88 75 f9 movb %sil, -7(%rbp)

Esempio (target ARM)

• clang test.c -target arm-none-eabi -S

Numeri reali

Sistema in virgola mobile (floating point)

• Notazione scientifica

X = f x 10E

• dove, f è detta mantissa, E esponente

X = 0,314 x 101

• Fissato il valore X, la sua rappresentazione varia con l’esponente (virgola si sposta a sinistra se E aumenta e a dx se diminuisce)

– X = 3,14 x 100 = 0,314 x 101 =0,0314 x 102

• Usare questa notazione avendo a disposizone uno spazio finito

Caratteristiche

• Ammettiamo di disporre di p = 3 cifre decimali per esprimere f e k=2 per E. Inoltre usiamo i segni + e –– |f| Î [0.1, 0.101,… …0.999];– |E| Î [0..99]

Calcolatori Elettronici, Beraldi, aa 03/04

ApprossimazioneErrore assoluto

• In generale è impossibile rappresentare con esattezza tutti i valori reali disponendo di un numero finito di cifre ed impiegando il sistema posizionale – Numeri irrazionali (p)– Periodici (1/3 = 0,33..)

• Indichiamo con X il valore esatto e con x il valore approssimato – X = 1/3 à x =0,33

• Si definisce errore assoluto, EA, la differenza fra x ed X

• EA = X-x (|EA|=|X-x|)

• E’ una prima misura della bontà dell’approssimazione

ApprossimazioneErrore relativo

• Si definisce errore relativo il rapporto• ER = (X-x)/x = EA/x, con x¹0.

– Si impiega x al denominatore perché di solito si dispone del valore approssimato

– X = x(1+ER)• Perché è utile introdurre tale misura?

• Un errore di 1 cm su una misurazione di 10 m è diverso che un errore di 1 cm su una misura di 10000 Km !

• E’ legato alla nozione intuitiva di precisione

Errore relativo e precisione

• Calcoliamo l’errore assoluto massimo – Consideriamo due valori consecutivi (assumiamo esponente invariato)

• x1= 1.F x 2E

• x2 = (1.F +2-p)x 2E

– Fissato E, l’errore massimo si commette quando X cade a metà fra x1 ed x2.• max{EA}=(x2-x1)/2 =(0,5x2-p) x 2E

• Il valore minino di x vale – min{x}= 1.0 x 2E

• L’errore relativo vale al più – ERmax = (0,5x2-p) x 2E / 2E = 2-1 x 2-p = 2-p-1

• L’errore relativo e quindi la precisione della rappresentazione è stabilita dal numero di cifre della mantissa

Caratteristiche della rappresentazione

• L’insieme S dei valori rappresentabili in virgola mobile ha le seguenti proprietà– E’ simmetrico rispetto allo 0– Esiste un valore minimo, xmin diverso da 0 – Il tentativo di esprimere un valore |X|>0, ma minore di xmin produce

underflow– Esiste un valore massimo, xmax

• Il tentativo di esprimere un valore |X|> xmax produce overflow

• Perdita della proprietà del continuo– " x,y Î R à (x+y)/2 Î R– Ciò non è vero in S (approssimazione)

Calcolatori Elettronici, Beraldi, aa 03/04

IEEE Floating Point 754 Nozioni di base

• Standard IEEE 754– Introdotto nel 1985 come standard per aritmetica in virgola mobile per

consentire portabilità dei programmi– Praticamente supportato da tutte le CPU

• Necessità per calcoli numerici– Standard per rounding, overflow, underflow

• Formato base – Precisione singola (32 bit)– Precisione doppia (64 bit)

• Formato esteso – Precisione singola estesa (³44 bit)– Precisione doppia estesa (³80 bit)

IEEE Floating Point 754 Formati numerici

• Esistono due forme: forma normalizzata e forma denormalizzata• Forma normalizzata: (-1)s x 1.F x 2EXP-Bias

– s è il bit di segno – Il primo bit della mantissa è sempre 1, e non è rappresentato (bit implicito)– Il valore 1.F è detto anche significando– L’esponente E è dato in forma polarizzata, ossia si memorizza EXP=E+Bias

(Bias è la costante di polarizzazione)

• Forma denormalizzata: (-1)s x 0.F x 2Emin

• Un numero è quindi espresso mediante la tripla di valori <S,F,EXP>– Un valore di EXP=0 indica che il numero è in forma denormalizzata

Configurazioni

F x 2Emin

(1.F) x 2EXP-Bias

± ¥�

Alcuni parametri

Elemento Singola Precisione Doppia Precisione

Numero bit di segno 1 1

Numero bit esponente 8 11

Numero bit della frazione F 23 52

Numero di bit, totale 32 64

Rappr. Esponente Eccesso 127 Eccesso 1023

Intervallo esponente -126 … +127 -1022 … +1023

https://float.exposed/0x80000000

https://float.exposed

Esempio

• Calcolare il valore massimo, Xmax , esprimibile in SP (normalizzato)– EXP=254

• il valore 255=(11111111)2 è riservato– F=(111…1)2, (23 bit)– Xmax = (1.11…1)2 x 2254-127 = (2-2-23) x 2127 » 2128 »3.4 x 1038

• Calcolare il valore minimo Xmin che può essere espresso in SP– EXP=1 (il valore 0 è riservato)– F=0…0– Xmin = (1.00…00)2 x 21-127 = 2-126 » 1.2 x 10-38

Range dei valori (normalizzati)

Singola precisione 32 bit: 1 Segno, 8 Esponente, p=23 per F

0-(2 – 2-23) x 2127 -1 x 2-126 » 2128

» 3.4x1038» 1.2 x 10-38

0-(2 – 2-52) x 21023 -1 x 2-1022 » 21024

» 1.7x10308

2-1022

Doppia precisione 64 bit: 1 Segno, 11 Esponente, p=52 per F

» 2.2 x 10-308

Esempio

• Calcolare il valore massimo, Xmax , esprimibile in SP (denormalizzato)– EXP=0 (NON USATO)– F=(111…1)2, (23 bit)– 2-126 (111…1)2 = (1-2-23) x 2-126 » 1.4 10−45

• Calcolare il valore minimo Xmin che può essere espresso in SP– EXP=0 (NON USATO)– F=0…1 = 2-23

– Xmin = 2-23 x 2-127 = 2-149 » 3.3 10-38

Range dei valori (de-normalizzati)

Singola precisione 32 bit: 1 Segno, No Esponente, p=23 per F

0-2-126 1…111 = (1-2-23) 2-126 -1 x 2-126 » 2128

» 3.38x1038» 1.2 x 10-38

Distribuzione dei valori FP

Range dei valori FP

Floating Point Range

Denormalized Normalized Approximate Decimal

Single Precision

± 2−149 to (1−2−23)×2−126

± 2−126 to (2−2−23)×2127

± ≈10−44.85 to ≈1038.53

Double Precision

± 2−1074 to (1−2−52)×2−1022

± 2−1022 to (2−2−52)×21023

± ≈10−323.3 to ≈10308.3

Esempio

• #include <stdio.h>• int main(){• float a = 1;• int i=0;• while (a>0)• printf ("%d %0.50f\n",i++, a/=2.0 );• return 0;• }

Esempio

• Rappresentare in singola precisione il valore X=28,125• Parte Intera

– 28 = 16+8+4 à 11100 • Parte Frazionaria

– 0,125 = 1/8 à 0,001

• X=11100,001

• Trasformiamolo in formato IEEE 754 SP– Segno = 0– X = 1,1100001 x 24

– F = 1100001– EXP=127+4 = 131 =128+2+1 à 10000011– X = 0 10000011 1100001 0000000000000000 = 0x41E10000

Esempio

La stringa esadecimale 0x56700000 e’ un numero in formato IEEE.754. Calcolarne il valore.

5 à 01016 à 01107à 0111

0 101 0110 0 111 0000 0000 0000 0000 000

Bit segno = 0 à numero positivoEsponente = bit (30:23)-127=(10101100)2 - 127 = 172 – 127 = 45Mantissa = 1.bit(22:0) = (1.111)2 = 1.875

Risultato = + 1.875 x 245

Esempio

La stringa esadecimale 0x80880000 e’ un numero in formato IEEE.754. Calcolarne il valore.

Segno = bit (31) = 1 = -Esponente= bit(30:23) -127 = 000000012 - 127 = 1 – 127 = -126Mantissa = 1. bit(22:0) = 1.00012

Risultato = -1.0625 x 2-126 (= -1.24896….. x 10-38)

Esempio

• Rappresentare il valore 1 in singola precisione IEEE 745– 23 bit mantissa (parte frazionaria F), – 1 segno (S)– 8 esponente (EXP)– Forma normalizzata: 1.0 20 => s=1, F=0, EXP-127=0 (EXP=127)– s=0, EXP=127=(0111111)2, F=0 = (000..0)2,

s exp F

0 01111111 00000000000000000000000

0x 3 F 8 0 0 0 0 0

3F/80/00/00

Aritmetica: addizione/sottrazione

• x = 1.Fx 2Ex

• y = 1.Fy 2Ey

• x+y = 1.F’x 2a + 1.F’y 2a = (1.F’x + 1.F’y) 2a

1. Se necessario, rendere gli esponenti uguali incrementando il minore2. Addizionare le mantisse3. Normalizzare il risultato

Esempio

Moltiplicazione/Divisione

• x = 1.Fx 2Ex

• y = 1.Fy 2Ey

• x/y = 1.Fx 2a / 1.Fy 2b = (1.F’x / 1.F’y) 2a-b

Esempio di istruzioni assembly FP (x87)

Altri esempi

Esempio <math.h> (/usr/include/)

Calcolo di funzioni trigonometriche mediante algoritmo CORDIC[argomento facoltativo]

(x’,y’)

https://en.wikipedia.org/wiki/CORDIC

CORDIC

(x’,y’)

Ricordiamo la definizione di seno/coseno

(cos(f),sen(f))

CORDIC (idea di base)

• Per calcolare cos(f), applicare iterativamente rotazioni di ampiezza g ad un vettore unitario v = (1,0), finchè il suo angolo coincide con f,

• Le rotazioni g sono decrescenti

• b è la differenza fra questo vettore e quello iniziale

b0 = f

• Per calcolare cos(f), applicare iterativamente rotazioni di ampiezza g ad un vettore unitario finchè il suo angolo coincide con f,

• B è la differenza fra questo vettore e quello iniziale

b0 = fb1 = b0 - g1

• Per calcolare cos(f), applicare iterativamente rotazioni di ampiezza g ad un vettore unitario finchè il suo angolo coincide con f,

• bi è la differenza fra questo vettore e quello iniziale

b0 = fb1 = b0 - g1b2 = b1 + g2

Usare solo incrementi che siano potenza di 2

tan(g) g (deg) g (rad). 1.0000000000 0.785398163 0.4500000000.5000000000 0.463647609 0.2656505120.2500000000 0.244978663 0.1403624350.1250000000 0.124354995 0.0712501630.0625000000 0.062418810 0.0357633440.0312500000 0.031239833 0.0178991060.0156250000 0.015623729 0.0089517370.0078125000 0.007812341 0.0044761420.0039062500 0.003906230 0.0022381050.0019531250 0.001953123 0.0011190570.0009765625 0.000976562 0.000559529..

Usare solo incrementi potenza di 2

• Applicando iterativamente questa equazione si deternina il valore richiesto

Un esempio: cos (78.9)

0 5 10 15 20

Angolo g

0 5 10 15 20 25 30

coseno

Pseudorotazioni

• Si può evitare di moltiplicare per . Il vettore finale avrà una lunghezza>1

• Tuttavia si può normalizzare dividendo per K = P cos(fi)

• Per calcolare sen,cos, etc. sono necessarie solo operazioni di addizione, shift e lookup di una tabella (per gi)

Algoritmo di moltiplicazione in HW

Product

64-bit ALU

Shift Left

Shift Right

WriteControl

32 bits

64 bits

Divisione come successione di sottrazioni (idea) A = Q x D + R

111100 100

111100 –100000

ßEquivalenteà

1. Poniamo inizialmente R = A

2. Abbassare le prime tre cifreequivale a far allineare Dcon R, ossia spostare a sx Dfino a far coincidere gli MSBe poi eseguire la differenza.Questo perchè siaggiungono zeri a dx. Se ladifferenza è >=0, sposta adx Q ed aggiungi 1,altrimenti (vedi dopo).

3. Se R<D finito, altrimentisposta a dx D, e vai alpasso 1

(aggiunto 3 zeri)

011100 10000 013)

111100 100000 0

111100 –100

Divisione come successione di sottrazioni (idea) A = Q x D + R

101100 110

101100 –110000

ßEquivalenteà

2. Abbassare le prime tre cifreequivale a far allineare Dcon R, ossia spostare a sx Dfino a far coincidere gli MSBe poi eseguire la differenza.Questo perchè siaggiungono zeri a dx. Se ladifferenza è <0, sposta a dxQ ed aggiungi 0

1. Se R<D finito, altrimentisposta a dx D, e vai alpasso 1

(aggiunto 3 zeri)

011100 11000 003)

101100 110000 0

101100 –110

Divisione come successione di sottrazioni A = Q x D + R

111100 100

111100 –100000

2. Abbassare le prime tre cifre equivale a far allineare D con R, ossia spostare a sx D fino a far coincidere gli MSB e poi eseguire la differenza

3. Sposta a sx Q, se la differenza è >=0 aggiungi 1

4. Se R<D finite, altrimenti vai al passo 1

23D (aggiunto 3 zeri)

011100 10000 013)

011100 –010000

R-22D4)

001100 100 011

111100 100000 0

Algoritmo Divisione lunga

• 1) A partire da sinistra si seleziona nel dividendo un numero di bit pari al numero di bit del divisore; la sequenza di bit così ottenuta rappresenta il resto parziale della divisione.

1110 / 101 = ------

2) Se è possibile sottrarre il divisore dal resto parziale senza chiedere un prestito, si aggiunge un bit di valore 1 alla destra del quoziente parziale; il risultato della sottrazione rappresenta il nuovo resto parziale.

1110 / 101 = 101 ---------- 1100

2) Se, invece, non è possibile sottrarre il divisore dal resto parziale senza chiedere un prestito, si aggiunge un bit di valore 0 alla destra del quoziente parziale.

1110 / 101 = 101 ---------- 10100 000

3) Se è possibile, si aggiunge alla destra del resto parziale un nuovo bit del dividendo e si ricomincia dal punto 2; se, invece, non ci sono altri bit del dividendo da aggiungere al resto parziale, la divisione è terminata con quoziente finale pari all'ultimo quoziente parziale e resto finale pari all'ultimo resto parziale.

1110 / 101 = 101 ---------- 10 100 000 ----100

1 0 0 1 0 = A1 0 1 0 = B

---------------------R= 0 0 0 0 0

1 0 0 1 00 0 0 0 0

1 0 0 1 0----------------------

1 0 1 1 0 1 0 0

R= [00000] R= [100100]R =[1001000]R =[10110100]

Rappresentazione dei numeri ed aritmetica di base · Rappresentazione dei numeri ed aritmetica di...

Documents