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
Reali
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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)
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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)
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
0
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
0.2
Esempio: (0.2)10 = (??)2
(0.2)10 = (0.0011)2
Esempionumeri periodici
Calcolatori Elettronici, Beraldi, 19/20
Esercizio
• Esprimere in base 10 il numero periodico (0,10)2
Calcolatori Elettronici, Beraldi, 19/20
Riepilogo
10 B¹10
prodotti successivi (N<1)
sviluppo del polinomio
divisioni successive (N intero )
2 8
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
•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
Calcolatori Elettronici, Beraldi, 19/20
_
_
_
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
7
0
1
2
4
5
6
3
01
2
3-4
-1
-2
-3
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
Valore expresso da un un numero binario complemento a 2
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
• 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
Calcolatori Elettronici, Beraldi, 19/20
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)
1
0
01
00
0
1
1
1
0
1
1
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
0
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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)
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
A
B
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
B
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)
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Resto
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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!)
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
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
Calcolatori Elettronici, Beraldi, 19/20
Operazioni e range (esempio)
. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .
unsigned a + b
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
ah al
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)
10
SP
15
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
± 0
± ¥�
NaN
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
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-126
» 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
2-126
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’)
(x,y)
https://en.wikipedia.org/wiki/CORDIC
CORDIC
(x,y)
(x’,y’)
Ricordiamo la definizione di seno/coseno
(cos(f),sen(f))
R=1
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
x
y
b0 = f
CORDIC (idea di base)
• Per calcolare cos(f), applicare iterativamente rotazioni di ampiezza g ad un vettore unitario finchè il suo angolo coincide con f,
• Le rotazioni g sono decrescenti
• B è la differenza fra questo vettore e quello iniziale
x
y
b0 = fb1 = b0 - g1
g1b1
CORDIC (idea di base)
• Per calcolare cos(f), applicare iterativamente rotazioni di ampiezza g ad un vettore unitario finchè il suo angolo coincide con f,
• Le rotazioni g sono decrescenti
• bi è la differenza fra questo vettore e quello iniziale
x
y
b0 = fb1 = b0 - g1b2 = b1 + g2
..
g2b1
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,2
0
0,2
0,4
0,6
0,8
1
1,2
1,4
1,6
0 5 10 15 20
Angolo g
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
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
B
A
64-bit ALU
Shift Left
Shift Right
WriteControl
32 bits
64 bits
64 bits
Divisione come successione di sottrazioni (idea) A = Q x D + R
111100 100
111100 –100000
R D
ß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
Q
01)
2)
(aggiunto 3 zeri)
011100 10000 013)
111100 100000 0
111100 –100
R-23D
Divisione come successione di sottrazioni (idea) A = Q x D + R
101100 110
101100 –110000
R D
ß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 a dxQ ed aggiungi 0
1. Se R<D finito, altrimentisposta a dx D, e vai alpasso 1
Q
01)
2)
(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
R D
R-23D
1. Poniamo inizialmente R = A
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
Q
01)
2)
23D (aggiunto 3 zeri)
011100 10000 013)
011100 –010000
R-22D4)
22D
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 = ------
Algoritmo Divisione lunga
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
Algoritmo Divisione lunga
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
Algoritmo Divisione lunga
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]