Richiami su alcuni aspetti della
rappresentazione dei numeri nei
sistemi di elaborazione e di calcolo
automatico.
Paolo Lepora
Dipartimento di Matematica, Politecnico di Torino
Politecnico di Torino,
Dipartimento di Matematica,
Stampato : 15 maggio 2002
Indice
1 I RAPPRESENTAZIONE DEI NUMERI
1.1
1
Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.1
cenni storici . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Rappresentazione non Posizionale . . . . . . . . . . . . . . .
3
1.3
Rappresentabilitá di un numero . . . . . . . . . . . . . . . . .
5
1.3.1
. . . . . . . . . . . . . . .
5
Rappresentabilià dei numeri, Rappresentazione dei numeri . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3.3
Algoritmo della divisione . . . . . . . . . . . . . . . .
6
1.3.4
Cifre necessarie per un numero . . . . . . . . . . . . .
11
I numeri frazionari . . . . . . . . . . . . . . . . . . . . . . . .
14
1.3.2
1.4
valore r della radice di N
2 Conversioni di Base
2.1
2.2
2.3
15
conversione alla base 10
. . . . . . . . . . . . . . . . . . . .
15
schema di Horner . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.2.1
17
Conversione della parte frazionaria . . . . . . . . . . .
Conversione dalla BASE 10
. . . . . . . . . . . . . . . . . .
18
2.3.1
conversione della parte frazionaria . . . . . . . . . . .
19
2.3.2
osservazioni . . . . . . . . . . . . . . . . . . . . . . . .
20
rk
2.4
Conversioni da base r a
con k intero positivo . . . . . . . .
22
2.5
numeri con Segno . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.5.1
Modulo e segno . . . . . . . . . . . . . . . . . . . . . .
24
2.5.2
Complemento alla base diminuita . . . . . . . . . . . .
25
2.5.3
Rappresentazione in complemento alla base . . . . . .
27
2.5.4
Algoritmi per complementazione . . . . . . . . . . . .
29
2.5.5
Intervallo di rappresentazione . . . . . . . . . . . . . .
30
2.5.6
Raffronto tra i vari metodi (per la base 2) . . . . . . .
31
i
ii
3 Aritmetica FRAZIONARIA
3.1 Virgola Fissa . . . . . . . . . . . . . . .
3.2 Virgola mobile . . . . . . . . . . . . . .
3.2.1 Mantissa normalizzata . . . . . .
3.2.2 tattamento del segno . . . . . . .
3.3 Intervalli di rappresentazione . . . . . .
3.4 ε macchina . . . . . . . . . . . . . . . .
3.4.1 calcolo teorico di ε macchina . .
3.4.2 Algoritmo per ricavare ε . . . . .
3.5 Parametri in un sistema Virgola mobile
3.5.1 polarizzazione . . . . . . . . . . .
3.5.2 Hidden bit . . . . . . . . . . . .
3.5.3 La rappresentazione dello zero .
3.5.4 Segno del numero . . . . . . . . .
3.5.5 Valori attribuiti ai parametri . .
INDICE
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
33
33
34
36
36
36
39
40
41
42
43
44
45
45
45
Capitolo 1
I RAPPRESENTAZIONE
DEI NUMERI
RAPPRESENTAZIONE DEI NUMERI
1.1
1.1.1
Introduzione
cenni storici
Il concetto di numero, per sua natura primitivo ed astratto, viene usualmente
percepito come raggruppamento di entità sensibili: gli oggetti materiali, i
segni, le voci del linguaggio. Le regole, le leggi, le tecniche della numerazione,
mostrano, nella loro origine uno straordinario grado di universalità che ci
consente di vedere come l’atto stesso del numerare sia uno degli attributi
caratteristici e fondanti del pensiero umano.
La notazione di numero intero risale ad una epoca certamente preistorica. Essa fu collegata inizialmente alla definizione di classi di oggetti
indivisibili
• Persone in un gruppo
• Pecore in un gregge
A ciascuna di queste classi, numeri, venne inizialmente attribuita una
rappresentazione fonetica non tramandata e non pervenuta.
In seguito, con la nascita del linguaggio, venne attribuita una rappresentazione grafica. La nascita del linguaggio realizzava l’associazione tra
parola, segno e contenuto quantitativo dei numeri.
1
2
CAPITOLO 1. I RAPPRESENTAZIONE DEI NUMERI
Presso popoli diversi, in epoche diverse l’associazione
Parola - Segno - Contenuto Quantitativo
non fu quasi mai univoca: in lingue diverse, alla stessa entitá ed allo
stesso contenuto quantitativo vennero associate parole e segni diversi.
Se ad uno stesso contenuto quantitativo posso associare nomi e segni
diversi é evidente che occorre distinguere tra le entitá numeri e l’insieme dei
simboli e dei nomi chiamati a rappresentarli.
La relazione tra un numero e la rappresentazione grafica é del tipo
uno a molti, la stessa relazione vale per numero e rappresentazione
fonetica. Sulla base delle osservazioni appena fatte si noti inoltre che un
numero, nella usa forma scritta potrà sempre essere rappresentato in almeno due modi: il simbolo o l’insieme dei simboli grafici che lo individuano
oppure dalla rappresentazione scritta che riporta fedelmente la rappresentazione fonetica. In questo ultimo caso, dei tre elementi numero , rappresentazione grafica e rappresentazione fonetica si potrà prescindere
dall’elemento rappresentazione grafica , riducendo a due gli elementi necessari. Questa soluzione, peraltro attraente dal punto di vista speculativo,
si mostra essere assai scomoda allorquando si renda necessario esprimere in
forma scritta un insieme non piccolissimo di numeri e relazioni tra di essi.
Cosı̀ , ad esempio, operando in aritmetica decimale , la semplissima relazione
:
1234 + 5678 − 9876
diventerebbe sommare mille duecento trenta quattro a cinque mila
sei cento settanta otto e sottrarre nove mila otto cento settanta sei
Uno studio razionale della numerazione deve operare una distinzione
tra numerazione strumentale, numerazione parlata e numerazione
scritta. Poichè questo tipo di approfondimento esula dagli scopi di queste
note ci soffermeremo unicamente su alcune semplici tecniche di numerazione.
1.2.
1.2
RAPPRESENTAZIONE NON POSIZIONALE
3
Rappresentazione non Posizionale
La rappresentazione primitiva usa la tecnica della ripetizione del simbolo ideografico dell’oggetto. Questo tipo di rappresentazione non necessita
alcuna spiegazione ed è immediatamente capita in ogni cultura. Pur non
essendo efficente, essa viena ancora oggi usata. I punti sulle facce dei dadi, i
numeri sulle tavolette del Domino, alcuni tipi di carte da gioco sono esempi
di tali tecniche. Ai primordi della storia della grecia antica si trovano tracce
di sistemi di numerazione che designavano i numeri con tanti tratti di linee
parallele. Un primo miglioramento si realizza con l’attribuzione di speciali
valori numerici ad alcuni simboli. Cosı̀ nella numerazione detta Romani si
usano alcuni simboli ed alcune convenzioni
I, V, X, L, C, D, M
I
1
II
2
III
3
IIII
4 IV
V
5
VI
6
V II
7
V III 8
V IIII 9 IX
X
10
Il rappresentare i primi dieci elementi con tecniche Romane o moderne,
non appare come un sensibile miglioramento!
Un fondamentale miglioramento é dato dal passaggio da una numerazione in cui il valore della entitá numero non dipende dalla posizione
ad una numerazione in cui il valore dipende dalla posizione
Sia N un generico intero non negativo,
Sia dn−1 , dn−2 , dn−3 , ..., d2 , d1 , d0 l’insieme dei simboli grafici usati per la
rappresentazione.
Potremo scrivere:
4
CAPITOLO 1. I RAPPRESENTAZIONE DEI NUMERI
N = dn−1 dn−2 dn−3 ...d2 d1 d0
Questa scrittura suggerisce la possibilità di pensare le singole cifre
dn−1 , dn−2 , ..., di , ...d0
come dipendenti dalla specifica posizione i occupata nella rappresentazione del numero N . Accettando questa ulteriore ipotesi si potrà parlare
di:
N=
dn−1 dn−2 dn−3 ...d2 d1 d0
|
{z
}
RAPPRESENTAZIONEPOSIZIONALE
È ovvio che dalla ultima ipotesi cui si è fatto cenno discende la necessità
di stabilire, per ogni posizione
i
un peso
pi
.
Il valore corrispondente alla rappresentazione
N = dn−1 dn−r ...d3 d2 d1 d0
sará quindi dato dalla
N = dn−1 · pn−1 + dn−2 · pn−2 + ... + d3 · p3 + d2 · p2 + d1 · p1 + d0 ,
ovvero, utilizzando una presentazione più compatta:
N=
n−1
X
di · pi
i=0
La possibilità ora mostrata, ancorchè molto potente, soffre, per cosı̀ dire
di un eccessivo numero di gradi di libertà. Si nota immediatamente che la
rappresentazione di uno stesso numero N , potrebbe essere fatta in infiniti
modi diversi.
Si tratta quindi di limitare nel sistema usato il numero dei gradi di
libertá. Se stabiliamo che i pesi pi , anziché essere arbitrariamente assegnati
siano dati dalla
pi = r i
con i ∈ [0, n − 1]
1.3. RAPPRESENTABILITÁ DI UN NUMERO
5
allora, il valore corrispondente alla rappresentazione sará dato dalla
dn−1 · rn−1 + dn−r · rn−2 + ... + d3 r3 + d2 r2 + d1 r1 + d0 r0
questo sistema di definizione dei pesi é caratterizzato dall’elemento r , che
prende il nome di radice e dal valore dell’esponente attribuito alla radice r,
preso pari alla posizione che la cifra che la cifra occupa nel numero.
1.3
Rappresentabilitá di un numero
L’interesse per quanto visto sino ad ora ci spinge a porci alcune domande:
• Come posso scegliere il valore della radice?
• Una volta scelto il valore di radice, quali numeri posso rappresentare?
• Come faccio a determinare la rappresentazione cercata?
• La rappresentazione trovata, è unica?
Vedremo di dare risposta alle questioni sopra riportate procedendo nello
stesso ordine :
1.3.1
valore r della radice di N
Il primo problema da affrontare é pertanto il seguente: Quali valori sassegnare ad r. Limitando le nostre considerazioni all’insieme dei numeri interi,
si può osservare che non sono emerse sino ad ora limmitazioni ai valori che
si possono assegnare ad r. È doveroso notare però che
1. la scelta di un valore r = 0 non consente alcuna rappresentazione di
N.
2. la scelta di un valore r = 1 riconduce ad un sistema di numerazione
non posizionale.
Sarà pertanto opportuno evitare la scelta dei valori r = 0 e dei valori
r = 1. Ragioni di opportunità ci consentiranno inseguito di suggerire una
limitazione superiore ai valori da attribuire ad r.
6
CAPITOLO 1. I RAPPRESENTAZIONE DEI NUMERI
1.3.2
Rappresentabilià dei numeri, Rappresentazione dei numeri
Il secondo problema che affrontiamo ci permetterà di rispondere in una, alle
seguenti domande:
• Una volta scelto il valore di radice, quali numeri posso rappresentare?
• Come faccio a determinare la rappresentazione cercata?
• La rappresentazione trovata, è unica?
Dimostreremo che: Dato un intero N ed una radice r
•
1. É possibile rappresentare N come
N=
n−1
X
di r 1
i=0
2. La rappresentazione é unica ?
1.3.3
Algoritmo della divisione
Per la dimostrazione del teorema precedentemente enunciato dobbiamo ricorrere al seguente algoritmo, detto algoritmo della divisione.
Teorema 1 Siano m ed n due interi, sia inoltre
m ≥ 0 ed n > 0
Th) esistono e sono unici 2 interi
q
con
q≥0
che chiameremo quoziente e
p
con 0 ≤ p < n
che chiameremo resto, tali che
m = nq + p
Partiamo dalla successione 0, 1, 2, 3, 4... , ordinata e crescente :
0 < 1 < 2 < 3...
s
1.3. RAPPRESENTABILITÁ DI UN NUMERO
7
notiamo che anche la successione
0 < n < 2n < 3n < 4n < 5n...
s0
é ordinata e crescente. Poichè non sappiamo se m coincide con un elemento
della s’, studieremo separatamente i due possibili casi
1. m coincide con un elemento della successione s’
2. m non coincide con un elemento di s’ ed é quindi compreso fra 2
elementi della successione s’
nel 1◦ caso si avrá
m = qn ⇒ p = 0 :
e pertanto
m − qn = 0 = p
nel 2◦ caso si avrá
qn < m < (q + 1)n
da cui, sottraendo il valore qn, si ottiene:
0 < m − qn < n
ponendo p = m − qn avró
0<p<n
infatti
0 < m − qn = p < n
il che dimostra l’esistenza di p e q.
Dimostreremo l’unicitá ammettendo che esistano altri due interi q ∗ e p∗
tali che
m = q ∗ n + p∗
d’altra parte noi sappiamo che
m = qn + p
Inoltre, per ipotesi, deve essere
0≤p<n
e 0 ≤ p∗ < n
8
CAPITOLO 1. I RAPPRESENTAZIONE DEI NUMERI
e quindi
0 ≤ p = m − qn < n
e
0 ≤ p∗ = m − q ∗ n < n
e quindi ancora
qn ≤ m < (q + 1)n
e
q ∗ n ≤ m < (q ∗ + 1)n
Il che significa che m dovrà cadere nell’intervallo qn . . . (q + 1)n e contemporaneamente m dovrà cadere nell’intervallo q ∗ n . . . (q ∗ + 1)n
D’altra parte, m, che é unico, non puó cadere in 2 distinti intervalli della
successione s’. Questa osservazione ci consente di concludere che dovrá
necessariamente essere q = q ∗ ed essendo p = m − qn e p∗ = m − q ∗ n, anche
p = p∗ .
Possiamo ora procedere alla dimostrazione del teorema precedentemente
annunciato.
Teorema 2 Dato un intero N ed una radice R > 1
1. É possibile individuare i coefficienti dn−1 , dn−2 ...d1 , d0 di un polinomio
avente grado n tali che
N = dn−1 · rn−1 + dn−2 · rn−2 + ... + d1 · r + d0 .
con la condizione 0 ≤ di < r
i ∈ [0, n − 1]
2. I coefficienti dn−1 , dn−2 ...d1 , d0 sono unici
DIMOSTRAZIONE
Sulla scorta dei risultati del teorema precedente, Dividiamo N per R.
Otterremo un quoziente N0 ed un resto d0 , con N0 < N e 0 ≤ d0 < R.
Ripetendo l’operazione, otterremo
N = N0 · R + d0
N0 = N1 · R + d1
N1 = N2 · R + d2
1.3. RAPPRESENTABILITÁ DI UN NUMERO
9
N2 = N3 · R + d3
N3 = N4 · R + d4
Sappiamo inoltre che N > N0 > N1 > N2 > . . . >. Gli interi
N, N1 , N − 2, . . . , Ni , . . . formano una successione di interi positivi,
decrescenti. Esisterá quindi un valore n tale che
Nn = 0 · R + dn+1
A questo punto, procedendo a ritroso, con n sostituzioni otterremo:
N = d0 + RN1
N = d0 + R(d1 + RN2 )
N = d0 + R(d1 + R(d2 + RN3 ))
N = d0 + R(d1 + R(d2 + R(d3 + R(d4 + ...
+... + R(dn−2 + R(dn−1 + 0))))))
N = d0 + d1 · R + d2 R2 + d3 R3 + ...+
+... + dn−2 Rn−2 dn−1 · Rn−1
il che prova l’esistenza.
Proveremo l’unicit‘à nel modo seguente:
Ammettiamo che oltre ai coefficienti ora trovati,
d0 , d1 , d2 ...dn−1
esista un secondo insieme di coefficienti
d∗0 , d∗1 , d∗2 ...d∗n−1
Allora potremo scrivere:
N = d∗0 + Rd∗1 + d∗2 R2 + d∗3 R3 + ... + d∗n−2 Rn−2 + d∗n−1 Rn−1
ma anche
N = d0 + Rd1 + d2 R2 + d3 R3 + ... + dn−2 Rn−2 + dn−1 Rn−1
10
CAPITOLO 1. I RAPPRESENTAZIONE DEI NUMERI
Poichè i 2 polinomi hanno lo stesso grado1 , sottraendo membro a
membro avremo:
0 = (d∗0 − d0 ) + (d∗1 − d1 )R + (d∗2 − d2 )R2 + ...+
+... + (d∗n−2 − dn−2 )Rn−2 + (d∗n−1 − dn−1 )Rn−1 )Rn−1
supponiamo ora che d∗0 − d0 = 0, d∗1 − d1 = 0...d∗k − dk = 0 per k ∈
[0, j − 1] allora
−(d∗j − dj ) = (d∗j+1 − dj+1 )R + ... + (d∗n−1 − dn−1 )Rn−1−j
e quindi, d∗j − dj =
h
= R (d∗j+1 − dj+1 ) + ... + (d∗n−1 − dn−1 )Rn−j−2
i
il che significa che d∗j −dj é divisibile esattamente per R e cioé, a meno
del segno
|d∗j − dj | = q · R
conqintero
. Sarà inoltre 0 ≤ d∗j < R e 0 ≤ dj < R e pertanto
|d∗j − dj | < R
− R < d∗j − dj < R
e ancora
−R < q · R < R
Ma allora, avuto riguardo alle 2 relazioni soprariportare, ricordando
che q é intero, si deve concludere che l’unica possibilitá é che q ≡ ∅
Posso dunque affermare che d∗j = dj . Per completare la dimostrazione
basterà ripetere il medesimo ragionamento per un qualunque j
1
(non é restrittivo supporre che i 2 polinomi abbiano lo stesso grado n. Nel caso ciò
non fosse vero,si procederà nel modo seguente: sia n∗ il grado del polinomio avente i coeff.
d∗0 , d∗1 , d∗2 ...d∗n∗ −1
, sia n il grado del polinomio avente i coeff.
d0 , d1 , d2 ...dn−1
, sia inoltre n∗ < n. Sará sufficiente adeguare il polinomio col grado minore al grado del
polinomio di grado maggiore aggiungendo i coefficienti dn∗ +1 = 0, dn∗ +2 = 0, ..., dn−1 = 0
1.3. RAPPRESENTABILITÁ DI UN NUMERO
11
I teoremi precedenti garantiscono la possibilitá di rappresentare un qualsiasi numero N intero, con un polinomio con radice R qualsiasi.
Le radici piú usate sono R = 10 , R = 2, R = 8, R = 16 Nel caso R = 10
i simboli usati sono:
R = 10
di ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Nel caso R = 2 i simboli usati sono:
R=2
di ∈ {0, 1}
Nel caso R = 8 i simboli usati sono:
R=8
di ∈ {0, 1, 2, 3, 4, 5, 6, 7}
Nel caso R = 16 i simboli usati sono:
R = 16
1.3.4
di ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }
Cifre necessarie per un numero
Determineremo ora il numero di cifre necessarie per rappresentare un numero
N in un sistema posizionalea base fissa R. Per raggiungere quasto scopo
risolveremo inizialmente un problema leggermente diverso:
il massimo numero rappresentabile con n cifre.
il massimo numero rappresentabile con n cifre.
Teorema 3 Dato un sistema di rappresentazione con n cifre nella base R,
Th) Il massimo numero rappresentabile Nmax,n vale
Nmax,n = Rn − 1
Dimostrazione
Sia
N=
n−1
X
di r i
i=0
con
0 ≤ di < r
12
CAPITOLO 1. I RAPPRESENTAZIONE DEI NUMERI
Il numero N assumerà il massimo valore rappresentabile con n cifre
allorquando le singole cifre di assumeranno ciascuna il massimo valore
possibile , e cioè quando
di ≡ di,max
∀i ∈ {0, 1, ..., n − 1}
ma per le ipotesi fatte,
di,max ≡ r − 1
∀i ∈ {0, 1, ..., n − 1}
e pertanto, sostituendo,
Nmax,n =
n−1
X
(r − 1)ri
i=0
N
= (r − 1)rn−1 + (r − 1)rn−2 + ...+
+... + (r − 1)r2 + (r − 1) · r + r − 1 =
= rn − rn−1 + rn−1 rn−2 + ... + −r2 + r2 − r + r − 1 =
= rn − 1
Il che ci permette di concludere che
Nmax,n = rn − 1
Numero di cifre necessarie per rappresentare N
La relazione precedentemente trovata, che mette in relazione il valore Nmax,n ,
massimo numero rappresentabile, coi valori n, numero di cifre dedicate alla
rappresentazione del numero e con R, valore della base di rappresentazione
adottata ci permette di risolvere il problema posto inizialmente.
Teorema 4 Sia dato il numero N , rappresentato nella base R.
Th) Il numero di cifre necessarie per rappresentare N è dato dalla seguente
relazione:
n = dlogr (N + 1)e
Dalla relazione ricavata nel precedente teorema,
Nmax,n = rn − 1
1.3. RAPPRESENTABILITÁ DI UN NUMERO
13
si ottiene, passando ai logaritmi:
n = logr (Nmax,n + 1)
se invece di n cifre, si userasero n − 1 cifre, avremmo dal teorema
precedente:
Nmax,n−1 = rn−1 − 1
rn−1 = Nmax,n−1 + 1
e quindi
n − 1 = logr (Nmax,n−1 + 1)
Tutti i numeri compresi fra
Nmax,n−1 < N ≤ Nmax,n
sono rappresentabili con n cifre
rn−1 − 1 < N ≤ rn − 1
rn−1 < N + 1 ≤ rn
n − 1 < logr (N + 1) ≤ n
e quindi
n = dlogr (N + 1)e
avendo indicato con il simbolo d
per eccesso all’intero superiore
e il valore che si ottiene arrotondando
14
1.4
CAPITOLO 1. I RAPPRESENTAZIONE DEI NUMERI
I numeri frazionari
NUMERI FRAZIONARI
In un sistema posizione a base fissa r un numero N frazionario viene
rappresentato da una successione di cifre dj con 0 ≤ dj < r
N = dn−1 dn−2 ...d2 d1 d0 .d−1 d−2 d−3 ...d−m
Questa rappresentazione corrisponde al valore
N = dn−1 · rn−1 + dn−r · rn−2 + ... + d3 r3 + d2 r2 + d1 r1 + d0 r0 +
d−(m−1) d−m
d−1 d2
+
+
...
+
+ m
r1
r2
rm−1
r
ovvero, in notazione più compatta
+
N=
n−1
X
−m
X
di r i +
i=0
N=
dj · rj
j=−1
n−1
X
di r i
i=−m
avendo indicato con n il numero di cifre della parte intera e con m il numero
di cifre della parte Frazionaria
Osservazione: la cifra piú a sinistra dn−1 é associata al peso rn−1 ; la
cifra piú a destra dm é associata al peso r−m .
la cifra a sinistra, avendo il peso maggiore é detta cifra piú significativa
MSD, mentre quella pú a destra ha il peso minore e viene detta cifra meno
significativa LSD.
Capitolo 2
Conversioni di Base
CONVERSIONI DI BASE
Per le conversioni di base esistono due classi di algoritmi, differenziate dal
fatto di operare nella base di partenza oppure nella base di arrivo:
I primi sono utilizzati dagli umani, in generale abituati ad operare nella
base 10, per le conversioni dette da base 10 a base qualunque. Essi sono
anche utilizzati dagli automi per operare conversioni dalla loro base di lavoro
(usualmente la base 2 o la base 8 o la base 16) ad altre basi). Gli algoritmi
che operano nella base di arrivo, come è facile arguire, vengono usati
dagli umani per convertire numeri da una base qualunque a base 10 e
dagli automi per convertire numeri da una base qualunque alla loro base
di lavoro (solitamente 2 o 8 o 16).
2.1
conversione alla base 10
1) Da base qualunque a base 10
Dato N in base R
• Esprimere R in base 10
• Esprimere i coefficienti di nella base 10
• Eseguire le operazioni nella base 10
es.: 325)7 = 3 · 72 + 2 · 71 + 5 · 70 = 147 + 14 + 5 = 166
325.42
= 3 · 49 + 2 · 7 + 5 + 4 · 7−1 + 2 · 7−2 = 166.6122
2
=.
. . . + 74 + 49
15
16
CAPITOLO 2. CONVERSIONI DI BASE
2.2
schema di Horner
Il procedimento indicato ha il vantaggio di essere estremamente semplice.
Esso presenta tuttavia alcuni svantaggi che si manifestano allorquando ci
si proponga di rendere procedurale la conversione. Nel metodo ora visto si
dovranno dapprima calcolare i valori delle potenze della base memorizzandoli
in opportune locazioni di memoria. Si calcoleranno in seguito le somme dei
prodotti tra le singole cifre dk ed i valori memorizzati delle potenze rk , per
k ∈ {n − 1, n − 2, ..., 2, 1, 0}. Se si volesse evitare di utilizzare n locazioni di
memoria per la registrazione dei valori delle potenze della base, si dovrebbe
ricorere al calcolo delle potenze stesse ad ogni passo della procedure e quindi si dovrebberero effettuare molte operazioni in piú di quelle strettamente
necessarie. Lo schema di Horner consente di dedurre un procedimento di
conversione che si presta agevolmente ad essere rappresentato in modo procedurale, non richiede orerazioni ridondanti e non necessita di locazioni di
memoria per la memorizzazione di risultati intermedi del calcolo. Sia
N = dn−1 ...d1 d0
che corrisponde, in modo esplicito a:
N = dn−1 · rn−1 + dn−r · rn−2 + ... + d3 r3 + d2 r2 + d1 r1 + d0 r0
Rifacendoci alle osservazioni fatte per la dimostrazione del teorema di esistenza ed unicità, si vede immediatamente che è possibile scrivere l’espressione precedente nel seguente modo:
N = (...(((dn−1 )r) + dn−2 )r + dn−3 )r...)r + d1 )r + d0 )
Lo schema di Horner consiste nel calcolo del valore di N , utilizzando la
struttura e l’ordine della espressione sopra riportata.
In forma procedurale, si opererà come segue:
1. 0 → N
2. Per k che varia da n − 1 a 0 ripeti:
3.
4. Fine
N · r + dk → N
2.2. SCHEMA DI HORNER
17
A titolo esemplificativo, vediamo la conversione del numero N espresso nella
base 2, nel corrispondente numero espresso nella base 10
11101)2
→
.... )10
i singoli passi saranno:
1. N = 0
2. N = N · r + d4 = 0 · 2 + 1 = 1
3. N = N · r + d3 = 1 · 2 + 1 = 3
4. N = N · r + d2 = 3 · 2 + 1 = 7
5. N = N · r + d1 = 7 · 2 + 0 = 14
6. N = N · r + d0 = 14 · 2 + 1 = 29
7. Fine
2.2.1
Conversione della parte frazionaria
Anche per la conversione della parte frazionaria si procederà allo stesso
modo:
F =
−m
X
dj · rj
j=1
rappresentato come 0.d−1 d−2 . . . d−m 0. . . .
d−1 · r−1 + d−2 · r−2 + d−3 · r−3 + . . . d−m · r−m
r−1 (d−1 + r−1 (d−r + r−1 (d−3 + . . . r−1 (d−m ) . . .))
Ṽm =
Ṽm−1 =
Ṽm−2 =
Ṽk =
..
.
d−m
Ṽm · r−1 + d−(m−1)
Ṽm−1 · r−1 + d−(m−2)
Ṽk+1 · r−1 + d−k
F =
Ṽ1 · r−1
18
CAPITOLO 2. CONVERSIONI DI BASE
CONVERTIRE
0.10101
Ṽ5
Ṽ4
Ṽ3
Ṽ2
Ṽ1
Ṽ0
2.3
=
= 1 · r−1 + 0 = 1/2 + 0 =
=
=
=
=
1
1
2
1
−1 + 1 = 1 + 4 = 5
2 ·r
4
4
5
5
−1 + 0 = 5
·
r
4
8
5
−1 + 1 = 5 + 1 = 21
·
r
8
16
16
21
−1 = 21 = 0.65625
·
r
16
32
Conversione dalla BASE 10
CONVERSIONE DA UN SISTEMA A BASE 10 AD UN SISTEMA
A BASE QUALSIASI
Direttamente dalla dimostrazione della esistenza ed unicitá si ha
N=
n−1
X
i
di · r =
"n−1
X
i=0
e quindi , ponendo N1 =
#
(di · r
i−1
) · r + d0
i=1
"n−1
X
#
(di · r
i−1
) si potrà scrivere
i=1
N = N1 · r + d0
La stessa procedura, ripetuta, conduce alla seguente successione
N=
N1 =
N2 =
..
.
N1 · r + d0
N2 · r + d1
N3 · r + d2
Nj−1 =
Nj · r + dj−1
Nn−1 = Nn · r + dn−1
avendo posto il termine generale

n−(j−1)
Nj−1 = 
X
i=(j−1)

(di · ri−(j−1) )
2.3.
CONVERSIONE DALLA BASE 10
19
È facile vedere che la successione N ; N1 ; N2 ; ...; Nn−1 ; Nn è decrescente
e che Nn = 0. Il calcolo si arresta quindi dopo n passi. Vediamo alcuni
esempi di conversione Convertire
27)10 → xxxx )16
27 : 16 = 1 · 16 + 11 → d0
1 : 16 = 0 · 16 + 1 → d1
)
→ 1B
27)10 → xxxx)2
27 : 2 =
13 : 2 =
6:2=
3:2=
1:2=
2.3.1
13 · 2 + 1
6·2+1
3·2+0
1·2+1
0·2+1
→ d0
→ d1
→ d2 ⇒ 11011
→ d3
→ d4
conversione della parte frazionaria
PER LA PARTE FRAZIONARIA SI HA
−m
X
F =
dj · rj = d−1 · r−1 + d−r · r−r +
j=−1
+d−3 · r−3 + . . . d−m · r−m
moltiplicando per la base r otterremo
r · F = d−1 + d−2 · r−1 + d−3 · r−2 + . . . d−m · r−m+1 = d−1 + Ṽ−1
avendo posto Ṽ−1 =
−m
X
dj · rj+1 la moltiplicazione di F per la base r
j=−2
mette in evidenza una parte intera d−1 ed una parte frazionaria Ṽ−1
Potremo pertanto scrivere
20
CAPITOLO 2. CONVERSIONI DI BASE
br · F c = d−1
Per Ṽ−1 opereremo come per F ed otterremo
br · Ṽ−1 c = d−2
..
.
r · V−j+1 = d−j
2.3.2
osservazioni
Vediamo alcune osservazioni:
(a) Come posso affermare che dopo ogni passo esiste una parte intera
ed una frazionaria?
Al passo k si avrá
rṼ−k = d−(k+1) + Ṽ−k+1)
poiché 0 ≤ d−(k+1) < R ⇒ ∃ parte intera.
Vediamo Ṽ−(k+1)
Ṽ−k+1 = d−(k+1) · r−1 + d−(k+2) · r−2 . . . d−m rk−m
le potenze di r vanno da −1 a −m + k
Ci si deve domandare a questo punto se:
−m
X
dj · rk+j
≥1
j=−(k+1)
Poniamoci nel caso peggiore:k = 0 e dj = r − 1
−m
X
∀j = −1, ..., −m
dj · rj = d−1 · r−1 + d−2 · r−2 + . . . d−m · r−m
j=−1
se dj = r − 1
−m
X
dj · r j
= (r − 1)r−1 + (r − 1)r2 + . . . + (r − 1)r−m
j=−1
= 1 − r−1 + r−1 − r−2 + r−2 + . . . −
= −r−m+1 + r−m+1 − r−m
= 1 − r−m ⇒ < 1
per ogni valore di m.
2.3.
CONVERSIONE DALLA BASE 10
21
(b) Operando con m cifre frazionarie, per moltiplicazione, avremo,
al termine di ogni passo, ancora m cifre significative per la parte
frazionaria. Ciò non ci consente di fare alcuna previsione sul numero di passi da copiere prima che la procedura si arresti. Anzi,
potremo dire che la procedura si arresterà solamente nel caso in
cui V−j+1 = 0. Ci saranno quindi casi in cui la procedura non
si arresta. Viene cosı́ a mancare una delle ipotesi fondamentali
per poter definire la procedura descritta un algoritmo (Un algoritmo deve terminare in un numero finito di passi). Si dovrá
pertanto prevedere l’arresto dopo che si saranno individuate le
cifre frazionarie desiderate. È ovvio che in tutti questi casi, si
dovrà accettare un errore di conversione in quanto il valore dopo
l’arresto della procedura sarà troncato ad un certo numero di cifre
frazionarie,inferiore al numero ci cifre necessarie.
Vediamo alcuni esempi
CONVERTIRE
0.6875)10 → xxxx)2
0.6875 · 2 =
0.3750 · 2 =
0.75 · 2 =
0.5 · 2 =
1.3750
0.75
1.5
1.0










y
1 + 0.3750
0 + 0.75
1 + 0.5
1+0
e quindi
0.6875)10 ⇒ 0.1011
CONVERTIRE
0.1)10 → xxxx)2
d−1
d−2
d−3
d−4
22
CAPITOLO 2. CONVERSIONI DI BASE
0.1 · 2 =
0.2 · 2 =
0.4 · 2 =
0.8 · 2 =
0.6 · 2 =
0.2 · 2 =
0.4 · 2 =
0.8 · 2 =
0.6 · 2 =
0.2 · 2 =
0.4 · 2 =
0.8 · 2 =
0.2
0.4
0.8
1.6
1.2
0.4
0.8
1.6
1.2
0.4
0.8
1.6































y
0 + 0.2
0 + 0.4
0 + 0.8
1 + 0.6
1 + 0.2
0 + 0.4
0 + 0.8
1 + 0.6
1 + 0.2
0 + 0.4
0 + 0.8
1 + 0.6
⇒ d−1
⇒ d−2
⇒ d−3
⇒ d−4
⇒ d−5
⇒ d−6
⇒ d−7
⇒ d−8
⇒ d−9
⇒ d−10
⇒ d−11
⇒ d−12
e quindi
0.1)10 ⇒ 0.0001100110011001100110011001100110011...
2.4 Conversioni da base r a rk con k intero
positivo
Nel caso particolare in cui sia richiesta la conversione da base r a rk
si possono individuare tecniche di conversione molto interessanti dal
punto di vista della semplicitá.
Il numero N , nella base R = rk sará :
dn−1 dn−2 . . . dj . . . d2 d1 d0 )R0
o, piú esattamente,
dn−1 · R0
n−1
+ dn−2 · R0
n−2
1
+ . . . d1 · R0 + d0 · R0
0
0 ≤ di < R 0
Avendo posto R = rk , potremo sostituire al valore R il valore rk
dn−1 · (rk )n−1 dn−2 (rk )n−2 + di (k )i + d1 rk + d0
2.4. CONVERSIONI DA BASE R A RK CON K INTERO POSITIVO23
se esprimiamo di come un polinomio in base r avremo
di = Ci,k−1 · rk−1 + Ci,k−2 rk−2 . . . Ci,1 r + Ci,0
sostituendo avremo.
³
³
³
³
´
Cn−1,k−1 rk−1 + Cn−1,k−2 rk−2 + . . . Cn−1,1 r + Cn−1,0 (rk )n−1 +
´
Cn−2,k−1 rk−1 + Cn−2,k−2 rk−2 + . . . Cn−2,1 r + Cn−2,0 (rk )n−2 +
´
C1,k−1 rk−1 + C1,k−2 rk−2 + . . . C1,1 r + C1,0 (rk )1 +
´
C0,k−1 rk−1 + C0,k−2 rk−2 + . . . C0,1 r + C0,0 (rk )0 =
Cn−1,k−1 rkn−k+k−1 + Cn−1,k−2 rkn−k+k−2 + Cn−1,0 rkn−k +
Cn−2,k−1 rkn−2k+k−1 + Cn−2,k−2 rkn−2k+k−2 + Cn−2,0 rkn−2k +
C1,k−1 rk+k−1 + C1,k−2 rk+k−2 + C1,0 rk +
Cn−1,k−1 rkn−1 + Cn−1,k−2 rkn−2 +
. . . C0,k−1 rk−1 + C0,k−2 rk−2 + . . . C0,0 r0
Allora si puó concludere che la rappresentazione di N vale:
Cn−1,k−1 Cn−1,k−2 Cn−1 , . . . Cn−1,0 Cn−2,k−1 . . . Cn−2,0 , . . .
C1,k−1 C1,k−2 . . . C1,1 , C1,0 C0,k−1 C0,k−2 . . . C0,1 , C0,0
La cosa é interessante specialmente per il modo in cui abbiamo generato i coefficienti: Ci,j é dato dalla jesima cifra ottenuta nella rappresentazione di di infatti
di =
k−1
X
Ci,j · rj
j=0
e quindi si puo concludere che nelle conversioni da base rk a base r e
viceversa sará sufficiente saper convertire le singole cifre espresse in
base rk nella corrispondente rappresentazione in base r.
Per il caso inverso occorrerá saper convertire gruppi di cifre del numero in base r, presi a gruppo di k cifre a partire da LSB, nelle corrispodenti cifre della base rk . Non é restrittivo supporre che le cifre di
N nella base r siano un multiplo itero di k. Se cosı́ non fosse, basterá
aggiungere da sinistra un tante cifre dn+2 = 0, dn+1 = 0 , dn = 0 in
modo da esprimere N con un numero di cifre multiplo di k.
24
CAPITOLO 2. CONVERSIONI DI BASE
2.5
numeri con Segno
Rappresentazione dei numeri con Segno
2.5.1
Modulo e segno
I tutti i sistemi di numerazione, Il modo piú semplice per rappresentare
numeri con segno consiste nell’anteporre o nel postporre alla rappresentazione N del numero, 2 simboli speciali che indichino se il valore
da attribuire alla rappresentazione sia > o < di ∅
La rappresentazione cui siamo abituati usa normalmente i simboli
+e−
anche se non é difficile incontrare simboli diversi. Basterá ricordare i
simboli CR DB spesso usati in ambito bancario oppure la tecnica di
porre tra i simboli ( e ) il numero N quando sia n < 0.
NB1: In questo caso + e − sono simboli unari e non hanno nulla a
vedere coi simboli + e − visti come operatori binari per somma
e sottrazione
NB2: Per i calcolatori sarebbe scomodo dover fare ricorso a 2 segni
speciali oltre ai 2 giá usati 0 e 1
Si conviene pertanto che
(a) La prima cifra (M SD) rappresenti il segno del numero
(b) Il valore 0 della prima cifra indicherá N > 0 mentre il valore
(R − 1) indicherá numeri N < 0
(c) Le restanti cifre rappresentano il modulo del numero
Se N > 0 allora la rappresentazione é:
0|N | = 0dn−2 . . . d1 d0
se N < 0 allora
(R − 1)|N | = (R − 1)dn−2 dn−3 . . . d1 d0
Questa rappresentazione é detta:
2.5. NUMERI CON SEGNO
25
MODULO E SEGNO
2.5.2
Complemento alla base diminuita
SiaNmax il massimo numero che riesco ad esprimere utilizzando n cifre
per la parte intera ed m cifre per la parte frazionaria
Nmax =
n−1
X
i=0
di · r i +
−m
X
dj · r j
j=−1
Nmax = (r − 1)rn−1 + . . . r − 1+
+(r − 1)r−1 + (r − 1)r−2 + . . . (r − 1)r−m
= rn − rn−1 + rn−1 x + . . . + r − 1 + 1 − r−1 +
+ . . . + r−m+1 r−m =
= rn − r−m
Definisco come complemento alla base diminuita
N̄(r) = Nmax − N = rn − r−m − N(r)
Dove n indica il numero di cifre destinate alla rappresentazione della
parte intera e m il numero di cifre destinate alla rappresentazione della
parte frazionaria
É immediato verificare che se si fa riferimento a numeri interi N̄R
sará
N̄R = rn − 1 − NR
Applicando la definizione n = 3 m = 0 R = 0
N = 27 N̄ = 103 − 1 − 27 = 999 − 27 = 972
N̄ = 972
n = 3 m = 2 R = 10
N = 27.22 N̄ = 103 − 10−2 − 27.22 = 999.99 − 27 − 22
n=5m=0R=2
N = 00101 N̄ = 2| 5{z
− 1} −00101 =
N̄ = 11111 −00101 = 11010
N̄ = 972.77
26
CAPITOLO 2. CONVERSIONI DI BASE
N̄ = 11010
La prima cifra rappresenta ancora il segno ma le cifre n − 2 . . . 0 non
rappresentano il modulo del numero!
Valore vero
N = −dn−1 (2n−1 − 1) +
n−2
X
di · 2i
i=0
se dn−1 = 0 ci si ritrova nello schema ben noto;
se invece dn−1 6= 0 allora si dovrá operare con la tecnica sopra indicata.
L’operazione che trasforma un numero positivo in un numero negativo
é assai semplice:
Sia +N =
n−1
X
di ri con dn−1 = 0 allora −N sará
i=0
−N =
n−1
X
ki r i
i=0
con kn−1 = r − 1 ki = d¯i {n − 2, n − 3, . . . 2, 1, 0} e d¯i = (r − 1) −
di . Ricordando peró che dn−1 = 0 allora léstressione soprariportata
diventa: dn−1 = r − 1
Pertanto sará
−N =
n−1
X
d¯i ri
i=0
infatti, dalla definizione
N̄
= Nmax − N = rn − 1 − N
=
=
n−1
X
n−1
X
i=0
n−1
X
i=0
(r − 1) · ri −
(r − 1 − di )ri
i=0
ponendo (r − 1 − di ) = d¯i ⇒
N̄ =
n−1
X
i=0
d¯i · ri
di · ri
2.5. NUMERI CON SEGNO
27
Osservazioni
⇒ La semplicitá operativa circuitale
⇒ Doppia rappresentaione dello zero!
⇒ Per il caso R = 2 il valore vero si ottiene dalla
N = −dn−1 · (2n−1 +
n−2
X
di 2i )
i=0
se dn−1 = 0 ci si ritrova nel caso normale, se invece dn−1 6= 0, per
R = 2 dn−1 = 1 e quindi
N = −2
n−1
+
n−2
X
di · 2 i
i=0
2.5.3
Rappresentazione in complemento alla base
¯ come complemento di N alla base R la sequenza di cifre
Definiamo N̄
¯ = rk − N con k uguale al numero di cifre dedicato
ottenuta dalla N̄
alle rappresentazioni di N
N = 027, R = 10 K = 3
¯ = 103 − 027 = 973
N̄
N = 00101 R = 2 K = 5
¯ = 25 − 00101 = 100000 − 00101 = 11011
N̄
N = 127 R = 10 K = 3
¯ = 103 − 127 = 873 → Valore ERRATO poiché , per K = 3, non é
N̄
possibile rappresentare 127.
¯ = rn − N si puó dedurre
Infatti dalla N̄
28
CAPITOLO 2. CONVERSIONI DI BASE
¯
N̄
=
rn
−
n−1
X
i=0
=
=
=
=
rn
−1−
n−1
X
i=0
n−1
X
i=0
n−1
X
di r i =
n−1
X
di r i + 1 =
i=0
i
(r − 1) · r −
n−1
X
di ri + 1 =
i=0
(r − 1 − di ) · ri + 1 =
d¯i ri + 1
i=0
per R = 2 n = 5
N = 00011 N̄ = 11100
¯ = N̄ + 1
N̄
= 11100 +
1
======
11101
Ci si deve occupare, anche per le rappresentazioni in complemento alla
base della rappresentazione dello zero. Sia N = 000000, sia n = 6 e
sia infine N̄ = 111111, allora
¯ =
N̄
111111 +
1
∗1 000000
| {z }
n=6
Ricordando che la scelta di operare con i numeri con n cifre implica
che vengano tralasciate le cifre da n + 1 in poi (Piú correttamente si
dirá che si opera in aritmetica modulo (2n ), ci consente di concludere
che in questo caso non si ha la doppia rappresentazione dello zero.
Possiamo infine, a questo proposito, esaminare, vuoi per il complemento alla base diminuita, vuoi per il complemento alla base l’operazione di sottrazione tra 2 numeri D = N − M Vediamo dapprima il
caso del complemento alla base
2.5. NUMERI CON SEGNO
29
L’operazione D = N − M puó essere vista come
N − M + rn − rn
= N + (rn − M ) − rn =
¯ − rn = N + M̄
¯
= N + M̄
¯
N − M = N + M̄
Operando invece in complemento alla base diminuita, si avrá:
N −M
= N − M + rn − 1 − (rn − 1) =
= N + (rm − 1 − M ) − rn + 1 =
= N + M̄ + 1
In entrambe le situazioni é facile vedere come la tecnica della complementazione sia particolarmente utile per le operazioni aritmetiche di
somma e sottrazione.
2.5.4
Algoritmi per complementazione
Si riportano due algoritmi: il primo deriva direttamente dalla definizione,
il secondo é molto semplice da usare.
A ⇒ Dalla definizione: si trova il complemento as 1 e si somma 1
B ⇒ Partendo da LSB, procediamo verso M SB
B.1 Lasciare inalterate le cifre fino al primo 1
B.2 Complemento le cifre successivo fino a M SG
Esempio algoritmo A
N = 01001001110001000
N̄ = 10110110001110111 +
1
¯
N̄
10110110001111000
Algoritmo B
N = 01001001110001000
¯ = 10110110001111000
N̄
30
CAPITOLO 2. CONVERSIONI DI BASE
2.5.5
Intervallo di rappresentazione
Sulla scorta delle precedenti osservazioni, siamo ora in grado di fissare
con precisione gli intervalli di rappresentazione.
Interi senza segno 0 ` − − − a 2n − 1
N ≤ 2n − 1]
2n N ∈ [0, 2n − 1] [0 ≤
Modulo e segno
−2n−1 − 1 ` − − − a 2n−1 − 1
Complemento a 1
−2n−1 − 1 ` − − − a 2n−1 − 1
Complemento a 2
−2n−1 ` − − − a 2n−1 − 1
2.5. NUMERI CON SEGNO
2.5.6
31
Raffronto tra i vari metodi (per la base 2)
Numero
decimale
Modulo
e segno
Complem.
alla
base
dimunita
Complem.
alla
base
+7
+6
+5
+4
+3
+2
+1
+0
-0
-1
-2
-3
-4
-5
-6
-7
-8
0011
0110
0101
0100
0011
0010
0001
0000
1000
1001
1010
1011
1100
1101
1110
1111
–
0111
0110
0101
0100
0011
0010
0001
0000
1111
1110
1101
1100
1011
1010
1001
1000
–
0111
0111
0101
0100
0011
0010
0001
0000
–
1111
1110
1101
1100
1011
1010
1001
1000
32
CAPITOLO 2. CONVERSIONI DI BASE
Capitolo 3
Aritmetica
FRAZIONARIA
ARITMETICA FRAZIONARIA
L’abituale tecnica di utilizzare un apposito simbolo ( normalmente il
carattere <, > o il carattere < . > per rappresentare la suddivisione tra
parte intera e parte frazionaria di un numero, non puó essere adottata
nei nei registri di un sistema di elaborazione. Si sono dunque elaborate altre tecniche per la rappresentazione di numeri in aritmetica
frazionaria.
3.1
Virgola Fissa
Virgola Fissa
Si conviene di rappresentare il numero come:
a) un intero N ∗
b) un fattore di scala P
Per il fattore di scala si adottano le seguenti convenzioni:
c) il fattore di scala non viene memorizzato
d) il fattore di scala é pari ad una potenza della base
33
34
CAPITOLO 3. ARITMETICA FRAZIONARIA
e) il fattore di scala non cambia mai durante i calcoli
una qualsiasi sequenza assume significati differenti in base al valore
del fattore di scala utilizzato.
Come si é visto, nella aritmetica intera i numeri rappresentabili su n
posizioni sono Rn .
Nel caso di interi positivi si ha
[0, Rn − 1]
nel caso di interi relativi, in complemento alla base si ha
[−Rn−1 , Rn−1 − 1]
l’uso di un fattore di scala consente, senza mutare il numero degli elementi rappresentabili dal sistema, di operare in aritmetica frazionaria.
Purtroppo il fattore di scala, non essendo registrato (memorizzato),
non muta e quindi il programmatore, altre a dovrá tener conto della la
posizione del punto decimale, dovrá tener conto della possibilitá, tuttaltro che remota, superare, durante l’esecuzione dei calcoli, dei limiti
del sistema di numerazione adottato e del fattore di scala prescelto.
L’uso della virgola fissa é assai limitativo, complicato per il programmatore e fonte di numerosi errori. Queste ragioni rendono il sistema
ora descritto assai poco utilizzato.
É necessario poter operare con un fattore di scala variabile
3.2
Virgola mobile
Il numero N , sin qui rappresentato da
N=
n−1
X
di r i
i=0
viene rappresentato nel modo seguente:
a) il segno del numero.
b) una quantitá M chiamata mantissa del numero.
3.2. VIRGOLA MOBILE
35
c) un fattore di scala costituito da una base R e da un esponente E
N = ±M · RE
P
X
=±
−m
X
dj · r∗j
di ri · Rj=0
i=−1
Per di e dj valgono le ipotesi 0 ≤ di < r e 0 ≤ dj < r∗ R = base del
numero r = base della mantissa r∗ = base dell’esponente
M = mantissa
E = esponente
Come avviene nell’aritmetica intera M é rappresentata dalla successione di cifre
M = d−1 d−2 d−3 . . . d−m
E = dp−1 dp−2 . . . d1 d0
Sulla scorta delle ipotesi precedenti, la coppia (M, E) unitamente al
segno di M ed al segno di E, rappresentano N
Osservazioni:
a) nella
nE
X
N =±
−n
Xm
dj · r∗j
d − iri · Rj=1
i=−1
a) I valori r ,R ed r∗ possono assumere valori diversi
b) Nel caso in cui r, R ed r∗ siano coincidenti si puó fare in modo che
la prima cifra delle mantisse sia 6= 0.
Ogni spostamento della virgola della M verso destra richiede la diminuzione di una unitá del valore E, inversamente, uno spostamento verso
sinistra richiede che il valore di E sia aumentato di una unitá.
Ad esempio
esempio con r 6= R 6= r∗
36
CAPITOLO 3. ARITMETICA FRAZIONARIA
0.7432 · 1013
0.007432 · 1015
0.07432 · 1014
3.2.1
Mantissa normalizzata
se la prima cifra della mantisa é 6= 0 e cioé d−1 6= 0 si dice che la
mantissa é normalizzata Le limitazioni ai valori assunti dalla mantissa
saranno quindi:
0 ≤ M < 1 non normalizzata
≤M <1
normalizzata
r−1
3.2.2
tattamento del segno
La coppia M ed E é vista come numero con segno.
Il segno del numero
Per quanto riguarda il segno del numero ci connverrá fare riferimento
a quanto detto nei paragrafi precedenti per i numeri interi. Tra i 3
possibili metodi utilizzabili, il piú comune, é il metodo detto Modulo e
segno.
Il segno dell’esponente
Per quanto riguarda il segno dell’esponete si usa una tecnica diversa
da quelle sin qui esaminate. Tale tecnica, detta di Polarizzazione verrá
esaminata in seguito.
3.3
Intervalli di rappresentazione
Max valore mantissa 1 − r−nm
Min valore mantissa r−nm (non normalizzata)
Min valore mantissa r−1 (normalizzata)
3.3. INTERVALLI DI RAPPRESENTAZIONE
37
Max valore esponente > 0 rn−E − 1
Min valore esponente < 0 −(rnE − 1)∗ dipende dalla scelta fatta per
E<0
Allora possiamo indicare quali sono gli intervalli che sono utilizzabili
coi numeri cosı́ organizzati:
10 caso
mantissa normalizzata
N GP
N GN
N LP
N LN
= (1 − r−nm ) · Rr
= −N GP
= r−1 · R
= −N LP
nE −1
20 caso
mantissa non normalizzata
GP
GN
LP
LN
n
= (1 − r−nm ) · Rr E −1
= −GP
m
= r−nm · R(r E −1)
= −LP
38
CAPITOLO 3. ARITMETICA FRAZIONARIA
Vediamo alcune particolaritá di questa classe di numeri.
Non esistono numeri tra N LN e N LP oppure tra LN e LP
Ve ne sono invece rnm nell’intervallo N LP ` −−− −−− a R·N LP
ma anche nell’intervallo R · N LP ` − − − − −− a R2 · N LP ve
ne sono esattamente rnm .
Ma questo intervallo é di R volte piú grande del precedente. Questi
numeri non solo non sono equispaziati nell’intervallo di esistenza, non
sono nemmeno spaziati con progressione lineare: si ha una spaziatura a
scatti. Si puó idealmente suddividere l’intervallo N LP N GP in rnE
intervalli più piccoli aventi ampiezza che cresce secondo la successione:
{R R2 R3 · · · Ri · · · R(r
nm −1)
}
I numeri macchina ricoprono in modo discreto lo spazio dei numeri
reali. La loro caratteristica é quella di diradarsi progressivamente coll’aumentare del modulo del numero. All’interno ci ciascuno degli intervalli delimitati dalla successione sopra riportata, i numeri macchina sono equispaziati. In ogni intervallo della successione, vi sono
esattamente rnm numeri macchina.
Esempio: Ipotesi R = 2 M normalizzata nm = 4 nE = 2 numeri
positivi
0.1000
0.1001
0.1010
0.1011
0.1100
0.1101
0.1110
0.1111
00
01
10
11
1/2
1/2+1/16
1/2+1/8
1/2+1/8+1/16
1/2+1/4
1/2+1/4+1/16
1/2+1/4+1/8
1/2+1/4+1/8+1/16
1
1+1/8
1+1/4
1+3/8
1+1/2
1+5/8
1+3/4
1+7/8
2
2+1/4
2+1/2
2+3/4
3
3+1/4
3+1/2
3+3/4
4
4+1/2
4+1
5+1/2
6
6+1/2
7
7+1/2
3.4. ε MACCHINA
3.4
39
ε macchina
Quanto visto nella sezione precedente ci permette di fare alcune ulteriori osservazioni. In ogni intervallo della successione:
{R, R2 , R3 , · · · Ri , · · · R(r
nm −1)
}
vi sono esattamente rnm numeri macchina. Se invece di studiare il
diradamento dei numeri macchina in assoluto studiamo la distanza
tra 2 numeri riferita al valore assoluto di uno dei due, troveremo una
quantità che non dipende più dall’intervallo considerato.
Teorema 5 Nell’intervallo di esistenza dei numeri macchina:
N GN ≤ n ≤ N LN ; 0; N LP ≤ n ≤ N GP
oppure
GN ≤ n ≤ LN ; 0; LP ≤ n ≤ GP
il rapporto della distanza tra due numeri macchina consecutivi e l’estremo
inferiore dell’intervallo della successione
{R R2 R3 · · · Ri · · · R(r
nm −1)
}
cui i 2 numeri appartengono è costante in tutto l’intervallo di esistenza. Siano N1 e N2 i due numeri macchina consecutivi, presi
nell’intervallo
r(j−1) < N1 < N2 < rj
L’ampiezza dell’intervallo sarà
χj = rj − r(j−1) = r(j−1) (r − 1)
In questo intervallo cadranno esattamente rnm numeri e pertanto la
distanza tra un numero ed il successivo sarà data da:
ψx =
r(j−1) (r − 1)
r nm
e quindi, il rapporto tra questo valore ed il valore r(j−1) che rappresenta
l’estremo inferiore dell’intervallo considerato, risulta essere:
E=
r(j−1) ·(r−1)
rnm
(j−1)
r
40
CAPITOLO 3. ARITMETICA FRAZIONARIA
e pertanto:
E = rnm (r − 1)
Come è facile vedere, tale valore non dipende dal particolare intervallo
utilizzato per il calcolo. Tale valore dipende unicamente dai parametri
caratteristici della rappresentazione in Floating point adottati.
L’elemento ora individuato costituisce una caratteristica fondamentale
dei sitemi di numerazione utilizzati e prende il nome di precisione di
macchina o ε macchina.
definizione
ε é definito come: ampiezza dell’intervallo tra 1 ed il numero macchina immediatamente > 1. Conoscendo i parametri caratteristici del
sistema adottato si puó facilmente ricavare il valore di ε.
3.4.1
calcolo teorico di ε macchina
Teorema 6 Sia r la base di rappresentazione, sia nm il numero di
cifre destinate alla rappresentazione della mantissa del numero.
Th) Il valore di ε macchina è dato dalla:
ε = r(−nm +1)
Dimostrazione Partendo dalla definizione, esprimiamo il valore di 1
e del numero macchina immediatamente > 1; sottrarremo quindi
il secondo valore dal primo ottenendo cosı̀ il risultato cercato.
Il valore 1 é dato da
0
N1 = r−1 · rr = 1
Il valore immediatamente maggiore sará
N1+ = (r−1 + r−nm ) · rr
0
Sottraendo si ottiena:
(r−1 + r−nm ) · r1 − r−1 · r1 = 1 + r−nm +1 − 1 = r(1−nm )
e quindi:
ε = r(−nm +1)
3.4. ε MACCHINA
3.4.2
41
Algoritmo per ricavare ε
Nel caso invece non sia possibile conoscere il valore di ε in modo
analitico, (caso assai comune), é possibile determinare il suo valore
ricorrendo ad un semplice algoritmo: Si parte da un valore di tentativo tent, molto grande. In un ciclo, con divisioni successive, si dimezza, ad ogni passo, il valore di tentativo; si arresterà il ciclo quando
il valore di tent trovato sarà cosı̀ piccolo da non raggiungere, se sommato al valore 1, il primo numero macchina immediatamente > 1. A
questo punto tent è certamente inferiore al valore ε cercato. Se ne
prende il doppio 2 · tent, ben sapendo che in questo caso il valore sarà
certamente approssimato per eccesso. Per uscire dal dilemma: valore
approssimato per difetto, valore approssimato per eccesso si ricorre
ad un arificio apparentemente inutile in un contesto analitico puro:
si somma il valore approssimato per eccesso ad 1 e quindi si sottrae
nuovamente 1
a = tent + 1
e quindi
tent = a − 1
In realtà, però, non ci si trova ad operare in un contesto analitico
puro ma si lavora coi numeri macchina che, per quanto detto in precedenza, non sono densi nell’intervallo. L’operazione tent + 1 potrà
soltanto condurre ad un numero macchina, in particolare, al numero
macchina approssimato per difetto al valore vero tent + 1. È ovvio
che tale numero macchina non potrà che essere il numero macchina
immediatamente > 1. Ne discende immediatamente che la successiva
sottrazione di 1 dal numero ora trovato, condurrà immediatamente al
valore cercato di ε.
Procedendo in termini più schematici si ha:
(a) Inizio
(b) Assegnare ad ε un valore di tentativo (grande)
(c) CICLO : ripeti
i. Dividere il valore di ε per 2
ii. Sommare al valore trovato il valore 1
42
CAPITOLO 3. ARITMETICA FRAZIONARIA
iii. Se il risultato della somma é 6= 1 allora ripeti
(d) Raddoppiare il valore di ε
(e) Sommare al valore trovato 1
(f ) Sottrarre 1 al valore trovato
(g) Fine
EP := 10.
↓
→ →
EP := EP/2.
↑
↓
← f also se (1 + EP = 1)
↓
vero
↓
↓
EP := EP ∗ 2.
EX := 1.0 + EP
EP := EX − 1.0
3.5
Parametri in un sistema Virgola mobile
Vi sono molte scelte possibili tra i parametri che caratterizzano un
sistema in virgola mobile:
(a) La base R
i. la base del numero
ii. la base della mantissa
iii. la base dell’esponente
(b) La Mantissa
3.5. PARAMETRI IN UN SISTEMA VIRGOLA MOBILE
43
i. numero di cifre destinate alla mantissa
ii. normalizzazione
iii. metodo adottato per il segno della mantissa
(c) L’esponente
i. numero di cifre destinate all’esponente
ii. metodo adottato per il segno dell’esponente
(d) Convenzioni per
i. il numero 0
ii. il più piccolo numero neq0
iii. il più grande numero rappresentabile
Prima di poterci addentrare nelle possibili scelte dei parametri sopra
richiamati converrà soffermarci su alcuni aspetti essenziali ad una
piena comprensione dei numeri in virgola mobile
3.5.1
polarizzazione
Tecnica della polarizzazione.
Non abbiamo sino ad ora affrontato esplicitamente il problema della
rappresentazione del segno dell’esponente in un sistema virgola mobile. Sebbene le tecniche classiche di rapppresentazione possano essere utilmente applicate, si preferisce, di solito, fare ricorso ad una
strategia differente. Anzichè rappresentare esponenti con segno, si
preferisce sommare al valore dell’esponente una quantità P tale da
avere come effetto la traslazione della rappresentazione dell’esponente
in un intervallo 0 ≤ x ≤ EspM ax
P prende il nome di fattore di polarizzazione.
44
CAPITOLO 3. ARITMETICA FRAZIONARIA
Sia Ev l’esponente vero
Sia Ep l’esponente come viene rappresentato: esponente polarizzato
Sia P il fattore di polarizzazione
allora
Ep = Ev + P
La scelta del valore da assegnare a P non è particolarmente complessa
Poichè si ha −(rnE −1 − 1) < Ev < +(rnE −1 − 1), dovendo necessariamente essere 0 ≤ Ep si deduce immediatamente che P non potrà
assumere valori minori di −(rnE −1 − 1); d’altra parte, Ep non potrà
assumere valori maggiori di rnE − 1 e quindi, per questa limitazione,
P non assumerà valori maggori di
rnE − 1 − (rnE −1 − 1) = (rnE −1 )(r − 1)
Il vantaggio di questa tecnica consiste nel utilizzare esponenti che assumono valori proporzionali al valore assoluto del numero consentendo quindi di effettuare confronti tra 2 numeri dimenticando che si sta
operando con numeri FP.
Nel caso di N LP con Ev = min si ottiene Ep = 0.
3.5.2
Hidden bit
Nel caso si usino mantisse normalizzate, con R = 2, si potrà fare in
modo che il primo bit (MSB) della mantissa sia 6= 0 e quindi d1 = 1
in tal caso é possibile evitare di memorizzare questa cifra ottenendo
un miglioramento nella precisione:
la rappresentazione é tale da presentare una mantissa con un bit in +,
tale tecnica viene chiamata del bit nascosto - Hidden hit.
Sulla base di quanto sopra, si possono fare immediatamente le seguenti
considerazioni:
→ Hidden-bit, non muta il range
→ Hidden-bit, muta εps
→ Hidden-bit, richiede l’uso di registri con un numero di bit superiore
al numero di bit usati per la memorizzazione.
3.5. PARAMETRI IN UN SISTEMA VIRGOLA MOBILE
3.5.3
45
La rappresentazione dello zero
Abbiamo sinora evitato di parlare della rappresentazione del numero
ZERO Da un punto di vista astratto, appare immediatamente che M =
0 è condizione necessaria e suff. perchè N = 0
M =0→N =0
. L’esponente non ha alcuna importanza ai fini della rappresentazione
dello zero. Le osservazioni appena fatte, ci suggeriscono alcune considerazioni:
Visto che l’esponente non ha alcun ruolo nella rappresentazione dello
zero, ci suggerisce la possibilità di assegnare valori 6= 0 all’esponente per scopi speciali
Mentre per un numero intero con o senza segno il valore 0 implica
che tutti i bit a 0:
di = 0
∀i = 0, n − 1
per un numero FP N = 0 non richiede che tutti i bit siano zero, essi tuttavia possono esserlo. Si può pretanto parlare di zero
sporco e di zero pulito.
3.5.4
Segno del numero
Il segno di un numero dipende ovviamente dal segno della mantissa. Sarà sufficente fare riferimento alle considerazioni precedentemente svolte per i numeri interi applicandole alla mantissa.
È tuttavia opportuno ricordare che si sta affermando come uno
standard di fatto la scelta di fare ricorso alla rappresentazione in
Modulo e segno.
3.5.5
Valori attribuiti ai parametri
La rappresentazione
nm
X
X=
nm
X
i=1
−i
di rM
· Rj=0
j
cj · rE
46
CAPITOLO 3. ARITMETICA FRAZIONARIA
non è completamente definita se non vengono assegnati opportuni
valori a tutti i paramentri del sistema
Vediamo insieme alcune scelte progettuali legate ad alcuni dei più
famosi sistemi di elaborazione di dati.
Tipo di
elab.
n. tot.
di bit
nE
nm
rM
rE
R
mant.
Ibm - 7090
CDC 6600
CDC 6/7000
PDP11 sing.
VAX11 sing.
VAX11 doub.
VAX11 quad.
IBM 370 long
Univac 1100
HP 21 MX
36
58
60
32
32
64
128
64
32
48
8
10
11
8
8
8
15
7
11
8
27
47
48
23
23
55
112
56
20
39
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
16
2
2
2
2
2
2
16
2
2
HP 15 TASC.
56
16
39
10
10
10
MS
MS
MS
MS
MS
MS
MS
MS
Cpl-1
Pol7
Cpl-2
Bcd
3.5. PARAMETRI IN UN SISTEMA VIRGOLA MOBILE
47
Elab.
Num.
di bit
totale
Numero
bit
esp.
Radice
Rappr.
della
manti.
PDP11
(single)
VAX11
double
VAX11
quad.
IBM 370
long.
Univac1100
double
HP 21 MX
extended
AMD 9511
single
HP 15
tascab.
CDC
6/7000
32
8
p=27
8
p = 27
15
p = 215
7
p = 26
11
2
2
MS
MS
MS
2
MS
16
MS
2
2
cpl.
a1
cpl.
a2
cpl.
10
MS
2
cpl.
a1
2
MS
80x87 Intel
short
64
128
64
32
48
48
56
60
32
8
p = 27
8
p = 27 − 1
16
compl. a 10
11
Ev + 21 0 se ≥ 0
Ev + 21 0 − 1 se < 0
8
p = 27 − 1
2
48
CAPITOLO 3. ARITMETICA FRAZIONARIA
Esaminiamo ora, con maggior dettaglio il sistema VAX11 . Questa famiglia di sistemi, prodotti dalla Digital (Casa ormai scomparsa, acquistata da Compaq... a sua volta ormai scomparsa, acquistata da Hewelett-Packard) é strutturata per operare in virgola
mobile con 4 tipi differenti di formato:
F f ormat 4Byte nE = 8 nm = 23
Df ormat 8Byte nE = 8 nm = 55
Gf ormat 8Byte nE = 11 nm = 52
Hf ormat 16Byte nE = 15 nm = 112
↓
(nE −1)
)
N = (−1)s · 0.1M · 2(E−2
NGP
NLP
NGN
NLN
ε
F
D
G
H
≡ 1.7 · 1038
0.29 · 10−38
≡ 0.9 · 1038
0.29 · 10−38
0.610308
0.610−308
0.6104932
0.610−4932
2−23 10−7
2−55 10−16
2−52 10−15
2−122 = 10−33
I gradi di libertá del sistema FP, come si evince con facilitá sia
dalla trattazione teorica, sia dalle tabelle precedenti, non solo
sono realmente moltissimi, ma sono stati usati dai vari produttori
di Hardware, come un metodo di contro-standardizzazione.
Sarebbe quindi estremamente auspicabile una definizione, internazionalmente accettata di alcuni valori e/o parametri standard.
3.5. PARAMETRI IN UN SISTEMA VIRGOLA MOBILE
3.5.6
49
Formato IEEE
L’Institut of Electrical and Electronic Engineering (IEEE) ha
proposto nel 1982 una normativa. Due formati base:
singolaprecisione
doppiaprecisione
(32
(64
bit)
bit)
Due formati opzionali:
single
double
S
E8
precision
precision
extended
extended
M23
Double ext. s, 15, 64
S
E11
M52
tnt
nm
nE
εps
SEMPLICE
32
23∗
8
−23
2
DOPPIA
64
52∗
11
2−52
ESTESA
80
64∗
15
2−63
∗23 + 1 (hidden hit)
∗ ∗ 52 + 1 (hidden hit)
∗ ∗ ∗64 (no hidden hit)
MAX POS
MIN POS
2128
2126
21024
21022
216384
216383
50
CAPITOLO 3. ARITMETICA FRAZIONARIA
Lo standard IEEE-754 prevede:
(a) Mantissa normalizzata nel modo seguente: 1 ≤ M < 2
(b) Esponente polarizzato P = 2nE −1 − 1
N = (−1)1 1.M · 2(Ep −P )
Sulla base delle precedenti ipotesi, si deduce facilmente che
• L’esponente polarizzato teorico sará compreso nel seguente
intervallo: 0
≤ Ep ≤ 2nE − 1
• : L’esponente vero teorico, tenendo conto del valore dell’esponente polarizzato, sará: 0 − (2nE −1 − 1) ≤ Ev ≤ 2nE − 1 −
(2nE −1 − 1)
Lo standard IEEE-754 prevede inoltre che, per motivi speciali
vengano esclusi i valori agli estremi e pertanto
• L’esponente vero potrá assumere pertanto, i seguenti valori:
³
´
2nE −1 − 1 + 1 ≤ Ev ≤ 2nE − 2nE −1 − 1
L’intervallo di rappresentazione diventa di conseguenza
Mmin · 2(2
)≤N <M
(2nE −1 −1)
max · 2
nE −1 −1
e quindi
nE −1 −1
) ≤ N < 2 · 2(2nE −1 −1)
1 · 2(2
Casi speciali
Ricordando che per i numeri positivi si ha : N = (−1)2 · M · RE ,
si potrá affermare che se M = 0 ⇒ N = 0. La cosa é vera sia che
E = 0 sia per E 6= 0. Nel secondo caso, tuttavia si dirá che si é in
presenza di uno Zero sporco. Esaminiamo quindi compiutamente
le possibili configurazioni alla luce della precedente osservazione
e tenendo conto della esclusione dei valori estremi dell’intervallo
operata dallo standard IEEE-754.
Si possono riconoscere i seguenti casi:
3.5. PARAMETRI IN UN SISTEMA VIRGOLA MOBILE
M
E
S
0
0
6 0
=
6= 0
0
6= 0
6= 0
0
0
6 0
=
6= 0
N
2 E −1
2NE − 1
0
0
1
0
1
−
−
51
ZERO +
ZERO −
N >0
N <0
+∞
N AN
NON NORMALIZZATO
rM = 2, rE = 2, ed r = 2
Mantisse sono normalizzate.
Hidden hit
Esponente in forma polarizzata con costante di polarizzazione
P = 2nE −1 − 1
il valore del numero N nella rappresentazione IEEE 754 é dato
dalla
N = (−1)2 · 1.M · 2(E−p)
mentre nel caso classico si avrebbe:
N = (−1)1 · 0.M · 2(E−p)
(equivale a compiere uno shift a sinsitra di 1 bit)
52
CAPITOLO 3. ARITMETICA FRAZIONARIA
3.6
Operazioni tra due numeri
3.6.1
Somma tra due numeri interi
N1
N1 =
n−1
X
N2
d1,i · ri
i=0
Interi
N2 =
m−1
X
d2,i · ri
i=0
Non é limitativo supporre m = n. Se cosi non fosse, si dovrenno
esaminare i 2 casi seguenti:
se m > n basterá porre d1,i = 0
∀ n − 1 < i < m. In questo
caso anche N1 sará costituito da m cifre.
se m < n si porrá d2,i = 0
∀ m − 1 < i < n ed in questo caso
anche N2 sará costituito da n cifre.
N1 = d1,n−1 rn−1 + . . . d1,2 · r2 + d1,1 r1 + d1,0
N2 = d2,n−1 rn−1 + . . . d2,2 · r2 + d2,1 r1 + d2,0
N1 +N2 = (d1,n−1 + d2,n−1 ) rn−1 +. . .+(d1,1 + d2,1 )·r +d1,0 +d2,0
Se potessimo garantire
0 ≤ d1,i + d2,i < r − 1
Allora potremmo concludere facilmente
N1 + N2 = (d1,n−1 + d2,n−1 ) (d1,n−2 + d2,n−2 ) + . . . + (d1,0 + d2,0 )
Purtroppo, per quanto riguarda d1,i + d2,i le cose non stanno cosı́
ricordano infatti che
0 ≤ d1,i ≤ r − 1
e 0 ≤ d2,i ≤ r − 1
si puó solo concludere che
0 ≤ d1,i + d2,1 ≤ 2(r − 1)
esaminiamo i due casi
3.6.
OPERAZIONI TRA DUE NUMERI
53
A) 0 ≤ d1,i + d2,i ≤ (r − 1) ed in questo caso, ovviamente non vi
sono problemi.
B) r ≤ d1,i + d2,i ≤ 2(r − 1)
in tal caso pongo d1,i + d2,1 = (r + d∗i )
per cui
0 ≤ d∗ i ≤ r − 1
in tal caso
+ . . . + (d1,i+1 + d2,1+1 ) ri+1 + (d1,i + d2,1 ) ri =
. . . (d1,i+1 + d2,1+1 ) ri+1 + (r + d∗i ) · ri + . . .
(d1,i+1 + d2,1+1 ) ri+1 + d∗i · ri + . . .
L’aver posto
d1,i + d2,i . . . = (r + d∗i )
permettere di assicurare che, in ogni caso, 0 ≤ d∗ i ≤ r − 1 come
richiesto. Ci si dovrá pero ricordare che il valore della cifra di
posto i + 1 dovrá essere incrementato di una unitá.
La cifra che viene sommata alla cifra di posto i+1 prende il nome
di riporto.
La discussione si puó dire conclusa salvo l’esame del caso con
riporto
d1,i + d2,i + 1
anche in questo caso si avrá
0 < d1,i + d2,i + 1 ≤ 2r − 1
e quindi si ricade nel caso giá esaminato.
3.6.2
Differenza tra due numeri interi
Per quanto riguarda la differenza, senza ripetere quanto giá osservato, si puó dire
N1 =
n−1
X
i=0
d1,i ri
N2 =
n−1
X
i=0
d2,i ri
54
CAPITOLO 3. ARITMETICA FRAZIONARIA
N1 − N2 =
N1 =
d1,n−1 rn−1 + d1,n−2 rn−2 + . . . + d1,1 r + d1,0
N2 =
d2,n−1 rn−1 + d2,n−2 rn−2 + . . . + d2,1 r + d2,0
N1 − N2 = (d1,n−1 + d2,n−1 ) rn−1 +
. . . + (d1,0 − d2,0 )
¢
Pn−1 ¡
i
=
i=0 d1,i − d2,i ·
N1 − N2 =
n−1
X
(d1,i − d2,i ) · ri
i=0
Anche in questo caso, é necessario mostrare che
0 ≤ d1,i − d2,i ≤ r − 1
Nel caso in cui d1,i ≥ d2,i la condizione soprariportata é dimostrata.
Nel caso invece d1,i < d2,i si opera nel modo seguente
+ . . . + (d1,i+1 − d2,1+1 ) ri+1 + (d1,i − d2,1 ) ri + . . . +
. . . (d1,i+1 − d2,1+1 ) + (r + d1,i − d2,i ) ri + . . . +
in tal caso, é vero che d1,i < d2,i ma é pure vero che
r + d1,i > d2,i
e pertanto la δ é determinata.
Il resto della dimostrazione continua in perfetta analogia alla
precedente.
Resta da verificare per completezza che
δ∗
0 ≤ d1,i − d2,i − 1 ≤ r − 1
Basterá osservare che la
r + d1,i > d2,1 + 1
in quanto 0 ≤ d2,i ≤ r − i
e pertanto 0 ≤ r + d1,i − d2,i − 1 ≤ r − 1che é quanto ?? .
3.6.
OPERAZIONI TRA DUE NUMERI
3.6.3
55
Carry (riporto) e Borrow (prestito)
L’operazione di spostamento di una quantitá pari a R dalla cifra
di posto i verso la cifra di posto i + 1 viene detta Carry
L’operazione di spostamento di una quantitá pari a R dalla cifra
di posto i + 1 verso la cifra di posto i viene detta Borrow
in entrambe le situazioni si opera da LSD verso M SD
Purtroppo la tecnica non é esente da complicazioni: per trattare
correttamente i casi con complicazioni é necessario operare qualche
distinzione
operazioni su interi senza segno
operazioni su interi con segno
É opportuno ricordare che si opera in aritmetica modulo n, su
registri con n cifre
n=4
R=8
N1 = 4451
N 2 = 4127
Se calcolo la somma N1 + N2 avró
4
1
3
2
1
0
4
4
4
1
5
2
1
7
0
6
0
0
+
cé stato carry nelle colonne: 0, 1, 3 ció ha generato una somma
di 1 nelle colonne 1, 2, 4. Purtroppo peró la colonna 4 non esiste:
il risultato supera la capacitá dei registri
In tale situazione si ha una situazione detta di Overflow o Tracimazione
56
CAPITOLO 3. ARITMETICA FRAZIONARIA
Al termine di una operazione di somma é opportuno verificare se
l’operazione sulla cifra di posto n−1 ha generato carry in tal caso
il risultato non é corretto.
Per la sottrazione ci si ritrova in una situazione analoga.
Nel caso ci sia stata una operazione di borrow per la cifra di posto
n − 1.
Se, con le regole viste per l’algebra booleana cerchiamo di definire
la somma diremo, posto A = B1 + B2
B1 =
n−1
X
d1,i 2i
B2 =
i=0
n−1
X
d2,i 2i
i=0
per quanto riguarda il bit i si avrá
b1,i + b2,i ⇒ ai = b1,i + b2,i
bi
1
bi
2
0
0
1
1
0
1
0
1
carry
0
1
1
0
0
0
0
1
oltre alla ai = b1,i + b2,i si avrá
carry = b1,i · b2,i
per la somma, quindi, si deve tenere conto anche del bit di carry
che proviene dalla posizione i − 1.
La tabella vista precedentemente diventa
3.6.
OPERAZIONI TRA DUE NUMERI
b1,i
b2,i
carry,i−1
ai
carry,i
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
0
0
1
0
1
1
1
57
e quindi
ai = b1,i + b2,i + carryi−1
Carryi = b1,i · b2,i + carryi−1 · (b1,i + b2,i )
3.6.4
Moltiplicazione tra due numeri
Sono stati sviluppati diversi algoritmi
Vediamo l’algoritmo detto della somma e scorrimento. Sia:
N1 =
n−1
X
di r i
i=0
e
N2 =
m−1
X
ej rj
i=0
P
m−1
j
N1 · N2 =
j=0 ej · r · X =
=
em−1 · rm−1 · X + em−2 · rm−2 · X+
+
e2 · r2 · X + e1 · r1 · X + e0 · r0 · X
58
CAPITOLO 3. ARITMETICA FRAZIONARIA
es.128 · 53 =
128·
53
384 ← e0 · 1 · X
6400 ← e1 · 10 · X
6784
L’algoritmo trasforma una moltiplicazione in:
A) Moltiplicazioni piú semplici
B) Scorrimento verso sinistra
C) Somma
si noti ancora che A) puó essere vista come una serie di somme.
c0 r0 · X = equivale a sommare per c0 volte X
ei ri : ci · X ⇒ somma ei volte x ri · [ei x] ⇒ scorrimento di i posti
a sinistra. Shift-left.
Che cosa accade se si opera con la somma/sottrazione su 2 numeri
relativi.
A Modulo e sogno. Chiamo s il segno di N1 + N2 chiamo S1 il
segno di N1 ed s2 il segno di N2
N1 − N2
1 se
S1
s2
s
N1 + N2
0
1
0
0
1
1
1
0
0
1
0
1
1
0
|N1 | + |N2 |
|N1 | + |N2 |
|N1 | − |N2 |
|N2 | − |N1 |
|N1 | − |N2 |
|N2 | − |N1 |
|N1 | > |N2 |
|N2 | > |N1 |
|N1 | > |N2 |
|N2 | > |N1 |
Le operazioni avvengono solo tra numeri ≥ 0 e quindi valgono le
regole giá viste.
3.6.
OPERAZIONI TRA DUE NUMERI
59
B) Complemento alla base
N = N1 − N2 = N1 + N2
com’é ovvio operazioni di somma o di sottrazione possono, anche
in questo caso dare risultati che non appartengono ai numeri rappresentati con n cifre. In questi casi ci si trova in una situazione
di overflow.
La struttura di questi numeri utilizza la posizioni n − 1 (la nesima cifra) per il segno: se N1 > 0 e N2 > 0 la loro somma
puó dare luogo ad un valore 1 nella posizione n − 1 e non da mai
carry ma 1 in posizione n − 1 indica che N1 + N2 < 0 il che é
impossibile. Per contro, se N1 < 0 e N2 < 0 N1 + N2 puó dare
luogo ad un valore 0 nella posizione n − 1 e da sempre, comunque
il carri, ma, in relatá non sempre N1 + N2 da trasformazioni.
Si puó solamente concludere che il carry non e sufficiente a dare
indicazioni circa lo stato di tracimazione. I casi sono i seguenti:
Somma
N1
N2
CARRY
OVERFLOW
>0
<0
>0
<0
MAI
SEMPRE
dipende
dipende
<0
>0
>0
<0
dipende
dipende
MAI
MAI
Le sole informazioni contenute nella tabella precedente non ci
consentono di definire tutti i possibili casi. É necessario studiare
il carry non solo nella posizione n − 1 ma anche nella posizione
n−2
60
CAPITOLO 3. ARITMETICA FRAZIONARIA
CARRYn−1
CARRYn−2
OVERFLOW
0
0
1
1
0
1
0
1
NO
SI
SI
NO
Possiamo quindi cooncludere che la situazione di Overflow corrisponde a quei casi in cui il carry di posizione n − 1 é diverso
dal valore del carry di posizione n − 2 e cioé Cn−1 6= Cn−2
3.6.5
Operazioni di somma e sottrazione
Ci occupiamo ora delle operazioni di somma con numeri rappresentati in virgola mobile. Sia:
N1 = M1 · RE1
e
N2 = M2 · RE2
vogliamo studiare N1 + N2 =
N = M1 · RE1 + M2 · RE2
Il metodo consiste nel modificare M fino a rendere gli esponenti
E1 ed E2 uguali, a questo punto si puó operare la somma delle
mantisse.
Si danno alcuni casi:
1) E1 > E2 allora si incrementerá E2 del valore (E1 − E2 ) e
contemporaneamente si fará scorrere la virgola a sinistra di (E1 −
E2 ) posti per M2
N = M1 · RE1 + M2 · R−(E1 −E2 ) · RE2 · R+(E1 +E2 ) =
=
M · RE1 + M2 · R−(Ei 1 −E2 ) · RE2 · RE1 · R−E2 ) =
h 1
=
M1 + M2 R−(E1 −E2 ) · RE1
Spostare la virgola a sinistra di E1 − E2 posti per M2
3.6.
OPERAZIONI TRA DUE NUMERI
61
2) E2 > E1
allora
N = M1 · RE1 · R−(E2 −E1 ) · RE2 · R+(E2 −E1 ) + M2 · RE2
1
=
M1 · RE³1 · R−(E2 −E1 ) · RE2 · R−E
´
+
M2 RE2 M1 · R−(E2 −E1 ) + M2 RE2
equivale a spostare la virgola a sinistra di E2 − E1 posti per M2
L’operazione di spostamento del punto decimale verso sinistra
consiste, nella aritmetica modulo n a far scorrere verso destra
tutte le cifre della mantissa. Lo spostamento di k posti a sinistra della virgola significa lo scorrimento a destra di k cifre. Le
cifre d0 , d1 , d2 . . . dk−1 scompariranno ed il loro posto sará occupato rispettivamente dalle dk , dk+1 , dk+2 . . . inoltre, k cifre = 0
andranno ad occupare lw posizioni dn−1 , dn−2 , dn−k .
Si osserva immediatamente che per ogni operazione di somma
che usi 2 numeri con esponenti diversi, si ha una perdita di
informazione. Tale perdita inoltre é proporzionale al |E1 − E2 |.
62
3.6.6
CAPITOLO 3. ARITMETICA FRAZIONARIA
interruttore parallelo
—–
3.6.7
—–
decoder
3.6.
3.6.8
OPERAZIONI TRA DUE NUMERI
Flip-Flop RS
—-
3.6.9
—-
Flip-Flop JK
63
64
3.6.10
CAPITOLO 3. ARITMETICA FRAZIONARIA
Rugistro
—-
3.6.11
Half Adder
Un circuito sommatore puó essere schematizzato nel seguente modo
3.6.
OPERAZIONI TRA DUE NUMERI
65
Purtroppo, un sommatore a 2 ingressi non é sufficiente in quanto é
necessario tener conto del carry
3.6.12
Full Adder
—–
3.6.13
—–
Sommatore Parallelo
66
3.6.14
—-
CAPITOLO 3. ARITMETICA FRAZIONARIA
Sommatore Seriale