Date post: | 19-Jun-2015 |
Category: |
Technology |
Upload: | majong-devjfu |
View: | 7,441 times |
Download: | 1 times |
NumeriNumeri didimacchinamacchina
Luca Zanni , Marco Prato
Calcolo NumericoCorsi di Laurea in Matematica e Informatica
RappresentazioneRappresentazione internainterna deidei numerinumeri
A causa della limitata lunghezza della locazione di memoriadisponibile per rappresentare i numeri, si possonorappresentare solo un intervallo limitato di numeri interi e uninsieme finito di numeri reali
I numeri rappresentabili esattamente sul calcolatore sonodetti numeri finiti o numeri di macchina
NumeriNumeri interiinteri
Sia M il numero di bits riservati per la rappresentazione di unnumero in un elaboratore
Interi positivi
Sono caratterizzati da una rappresentazione binaria con il primobit uguale a 0bit uguale a 0
Ad esempio, n = 109 su 16 bit (M = 16) ha una rappresentazioneinterna
00000000 01101101
(109)10 = (1101101)2
NumeriNumeri interiinteri
Il massimo numero intero positivo rappresentabile esattamentecon M bits è dato da
Nmax = 2(M-1)-1
011……………1
Esempi:
M = 16Nmax = 215-1 = 32767
M = 32Nmax = 231-1 = 2147483647
NumeriNumeri interiinteri
Interi negativi
Per unificare le operazioni di addizione e sottrazione si usarappresentare i numeri interi negativi nella forma complemento adue. Sia –n il numero intero negativo da rappresentare con Mbits:
- si considera la rappresentazione di n su M bits
- si invertono logicamente tutte le M cifre
- si somma 1 al risultato dell’inversione logica
NumeriNumeri interiinteri
Esempio: rappresentazione interna di n = -5 su M = 16 bits
- Si considera la rappresentazione di 5 su 16 bits
00000000 00000101
- Si esegue l’inversione logica delle 16 cifre
11111111 11111010
- Si somma 1 al risultato dell’inversione logica
11111111 11111011
NumeriNumeri interiinteri
Il minimo numero intero negativo rappresentabile esattamentecon M bits è dato da
Nmin = -2(M-1)
100……………0Esempi:Esempi:
M = 16Nmin = -215 = -32768
M = 32Nmin = -231 = -2147483648
Quando si cerca di rappresentare un numero n > Nmax o n < Nmin siparla di overflow
NumeriNumeri interiinteri
I numeri interi rappresentabili con M bits sono quindi
2(M-1) – 1 + 2(M-1) + 1 = 2M
Esempio: M = 4 bits
positivi negativi lo zero
Esempio: M = 4 bits
0 111 7 1 111 -10 110 6 1 110 -20 101 5 1 101 -30 100 4 1 100 -40 011 3 1 011 -50 010 2 1 010 -60 001 1 1 001 -70 000 0 1 000 -8
NumeriNumeri realireali
Sia x ≠ 0 il numero reale che si vuole rappresentare.Consideriamo il numero scritto in rappresentazione binaria, connotazione posizionale e con la prima cifra significativa (che èsempre 1) a sinistra del punto radice1:
x = (-1)s · 1.a1a2a3… · 2p
Si devono memorizzare:- s (0 se x > 0, 1 se x < 0) � 1 bit- le cifre a1a2a3… della mantissa � t bits- la caratteristica p (Emin ≤ p ≤ Emax) � l bits (la rappresentazionedi p è traslata: si rappresenta p + bias)
1: rappresentazione nel formato IEEE (Institute of Electrical and ElectronicsEngineers) standard for binary floating-point arithmetic, documento 754dell’ANSI
NumeriNumeri realireali
I bit riservati per la memorizzazione in precisione semplice (32bit) e in precisione doppia (64 bit) di un numero reali sono cosìdistribuiti:
precisione semplice
precisione doppiasemplice doppia
n. bitstl
biasEminEmax
32 (4 bytes)1238127-126127
64 (8 bytes)15211
1023-10221023
NumeriNumeri realireali
Precisione semplice
s p mantissa
32 bits
8 bits 23 bits
Precisione doppia
s p mantissa
8 bits 23 bits
64 bits
11 bits 52 bits
EsempioEsempio
Rappresentazione interna di x = (4.25)10 in precisione semplice
x = (100.01)2 = 1.0001 · 22
- s = 0 (x > 0)- le cifre della mantissa da memorizzare sono 0001- l’esponente è 2 ma si deve memorizzare in forma traslata (p +- l’esponente è 2 ma si deve memorizzare in forma traslata (p +bias)
01000000 10001000 00000000 00000000
caratteristica mantissa
p 0 0 0 0 0 0 1 0
bias (127) 0 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
segno
NumeriNumeri realireali
Numero positivo più piccolo rappresentabile in precisione semplice:
xmin = 1.00…0 · 2-126 ~ 1.17 · 10-38
00000000 10000000 00000000 00000000
Numero positivo più grande rappresentabile in precisione semplice:Numero positivo più grande rappresentabile in precisione semplice:
xmax = 1.11…1 · 2127 ~ 3.40 · 1038
01111111 01111111 11111111 11111111
Precisione doppia:
xmin = 1.00…0 · 2-1022 ~ 2.22 · 10-308 , xmax = 1.11…1 · 21023 ~ 1.7 · 10308
OsservazioneOsservazione
Il valore di p corrispondente alla configurazione degli l bit inprecisione semplice è il seguente:
configurazione degli 8 bit p00000000 (*)00000001 -126 (Emin)00000010 -125
mantissa con tutti bit nulli:rappresentazione di 0
mantissa con bit non nulli:rappresentazione dei00000010 -125
011111110 -1011111111 010000000 110000001 2
11111110 127 (Emax)11111111 (**)
rappresentazione deinumeri denormalizzati
mantissa con tutti bit nulli:rappresentazione di Inf
mantissa con bit non nulli:rappresentazione di Nan
ErroreErrore didi rappresentazionerappresentazione
Rappresentando un numero reale x = ±m·βp su un calcolatore (con tbit a disposizione per la mantissa), si presenta uno dei seguentiquattro casi:
1. x può essere rappresentato in modo esatto (numero dimacchina)
2. x è, in valore assoluto, più piccolo del più piccolo numero2. x è, in valore assoluto, più piccolo del più piccolo numeropositivo rappresentabile (p < Emin). In questo caso si verifica ununderflow e generalmente si assume 0 come valoreapprossimato di x (con eventuale segnalazione di warning)
3. x è, in valore assoluto, più grande del più grande numeropositivo rappresentabile (p > Emax). In questo caso si verifica unoverflow, x viene approssimato con ±∞ a seconda del segno e ilsistema arresta il calcolo
ErroreErrore didi rappresentazionerappresentazione
Rappresentando un numero reale x = ±m·βp su un calcolatore (con tbit a disposizione per la mantissa), si presenta uno dei seguentiquattro casi:
4. la caratteristica è rappresentabile in modo esatto (Emin ≤ p ≤Emax), ma la mantissa m di x non è rappresentabile con t cifre.In questo caso il numero x = ±a1a2a3…·βp viene approssimato conIn questo caso il numero x = ±a1a2a3…·βp viene approssimato conil numero di macchina x’ = ±m’·βp , con
<
≥+
=
=
+
+
−
βaa
βaβa
aaaa
aaa
m
tt
t
t
t
tt
t
2
1 se
2
1 se
....0
....0
'
1
1
21
21
arrotondamento
troncamento
EsempiEsempi
- β = 10, t = 4tr(x) = 0.3478·103
x = 0.347821·103
rd(x) = 0.3478·103
tr(x) = 0.3478·103
x = 0.347891·103
rd(x) = 0.3479·103rd(x) = 0.3479·103
- β = 2, t = 4tr(x) = 0.1011·210
x = 0.101101·210
rd(x) = 0.1011·210
tr(x) = 0.1011·210
x = 0.101110·210
rd(x) = 0.1100·210
PrecisionePrecisione didi macchinamacchina
TeoremaTeorema
Siano x un numero reale non nullo, x’ approssimazione di macchinadi x. L’errore relativo che si commette approssimando x con x’ è
=≤
−
≡−
−
t
t
xβ
β
epsepsx
xxε
1
1
1 ,'
arrotondamento
troncamento
−tβx 1
2arrotondamento
La quantità eps è detta precisione di macchina ed è definita comeil più piccolo numero di macchina che sommato a 1 restituisce comenumero di macchina un numero maggiore di 1
Su calcolatore la precisione di macchina è data da:
21-(23+1) = 2-23 ~ 1.19·10-7 (32 bit)eps =
21-(52+1) = 2-52 ~ 2.22·10-16 (64 bit)
N.B.: il +1 corrisponde allacifra a sinistra del puntoradice che, essendo sempre 1,non viene memorizzata
OperazioniOperazioni tratra interiinteri didi macchinamacchina
Addizione tra interi di macchina
Siano x’ e y’ due numeri interi rappresentabili su M bit. Si possonoavere due casi:
1. la somma z = x’ + y’ richiede M cifre � la sua rappresentazionedi macchina z’ coincide con zdi macchina z’ coincide con z
Esempio: M = 5, x’ = 10101, y’ = 00111 � z = 11100 � z’ = z
2. la somma z = x’ + y’ richiede M+1 cifre � la suarappresentazione di macchina z’ coincide con un numero congruo az modulo 2M (ovvero, z - z’ = k · 2M, con k numero intero). In questocaso si dice che l’addizione ha provocato un traboccamento
Esempio: M = 5, x’ = 10101, y’ = 01101 � z = 100010� z’ = 00010
OperazioniOperazioni tratra interiinteri didi macchinamacchina
Sottrazione tra interi di macchina
Siano x’ e y’ due numeri interi rappresentabili su M bit.L’operazione z = x’ - y’ viene eseguita come la somma di x’ con ilcomplemento a due di y’
Esempi:
- M = 4, x’ = 0010, y’ = 0011 � z = 0010 – 0011 = 0010 + 1101 = 1111
� z’ = z
- M = 4, x’ = 0101, y’ = 0011 � z = 0101 – 0011 = 0101 + 1101 = 10010
� z’ = 0010
OperazioniOperazioni tratra interiinteri didi macchinamacchina
Moltiplicazione tra interi di macchina
Siano x’ e y’ due numeri interi rappresentabili su M bit.L’operazione z = x’ * y’ può essere ricondotta ad una sequenza diaddizioni e di spostamenti a destra della stringa delle cifre
Per il calcolo si utilizzano due accumulatori A e B; l’accumulatore APer il calcolo si utilizzano due accumulatori A e B; l’accumulatore Aè formato da M bit mentre l’accumulatore B è composto da dueparti, la prima di M+1 bit (che chiameremo R) e la seconda di M bit.Il numero di macchina x’ viene memorizzato in A mentre y’ nellaseconda parte di B. In R si memorizza il numero r inizializzato a 0
Seguiamo il procedimento con un esempio pratico
OperazioniOperazioni tratra interiinteri didi macchinamacchina
Moltiplicazione tra interi di macchina
Esempio: M = 6, x’ = 000011, y’ = 000101
A 000011 B 0000000 000101
Si calcola 1*x’+r (1 è la cifra di y’ associata a 20) e il risultato lo si memorizza in R
A 000011 B 0000011 000101
R
A 000011 B 0000011 000101
Si esegue uno spostamento di un bit verso destra in B
A 000011 B 0000001 100010
Si calcola 0*x’+r (0 è la cifra di y’ associata a 21) e il risultato lo si memorizza in R
A 000011 B 0000001 100010
Si esegue uno spostamento di un bit verso destra in B
A 000011 B 0000000 110001
passopasso 11
passopasso 22
OperazioniOperazioni tratra interiinteri didi macchinamacchina
Moltiplicazione tra interi di macchina
A 000011 B 0000000 110001
Ripetendo i passi precedenti si ottiene
A 000011 B 0000011 110001 1*x’ + r
A 000011 B 0000001 111000 spostamento a destra
R
passopasso 33
passopasso 66
passopasso 55
passopasso 44A 000011 B 0000001 111000 0*x’ + r
A 000011 B 0000000 111100 spostamento a destra
A 000011 B 0000000 111100 0*x’ + r
A 000011 B 0000000 011110 spostamento a destra
A 000011 B 0000000 011110 0*x’ + r
A 000011 B 0000000 001111 spostamento a destra
Dopo M passi, in B è memorizzato z = x’ * y’ e nella seconda parte di B la sua rappresentazione di macchina z’
passopasso 11
OperazioniOperazioni tratra interiinteri didi macchinamacchina
Moltiplicazione tra interi di macchina
Esempio: M = 3 , β = 10, x’ = 215, y’ = 162
A 215 B 0000 162
A 215 B 0430 162 2*x’ + r
passopasso 33
passopasso 22
A 215 B 0043 016 spostamento a destra
A 215 B 1333 016 6*x’ + r
A 215 B 0133 301 spostamento a destra
A 215 B 0348 301 1*x’ + r
A 215 B 0034 830 spostamento a destra
OperazioniOperazioni tratra interiinteri didi macchinamacchina
Divisione tra interi di macchina
Siano x’ e y’ due numeri interi rappresentabili su M bit.L’operazione z = x’ / y’ può essere ricondotta ad una sequenza disottrazioni e di spostamenti a sinistra della stringa delle cifre
Per il calcolo si utilizzano due accumulatori A e B; l’accumulatore APer il calcolo si utilizzano due accumulatori A e B; l’accumulatore Aè formato da M bit mentre l’accumulatore B è composto da dueparti, entrambe di M bit (che chiameremo R e Q). Il numero dimacchina y’ viene memorizzato in A mentre x’ in R. In Q simemorizza il numero q inizializzato a 0
Anche in questo caso seguiamo il procedimento con un esempiopratico
OperazioniOperazioni tratra interiinteri didi macchinamacchina
Divisione tra interi di macchina
Esempio: M = 6, x’ = 010000, y’ = 000101
Inizialmente si eseguono s spostamenti verso destra nell’accumulatore B, fino aquando in R c’è un numero r tale che y’ ≤ r < βy’.La divisione sarà composta da s + 1 passi
A 000101 B 010000 000000
R Q
A 000101 B 010000 000000
s = 1 (y’ = 000101, βy’ = 001010)
A 000101 B 001000 000000
Si calcola il numero intero q tale che qy’ ≤ r < (q+1)y’ e r = r – qy’. Al primo passo siha q = 1 e r = 000011
A 000101 B 000011 000001
Si esegue lo spostamento di un bit verso sinistra in B
A 000101 B 000110 000010 passopasso 11
OperazioniOperazioni tratra interiinteri didi macchinamacchina
Divisione tra interi di macchina
Esempio: M = 6, x’ = 010000, y’ = 000101
A 000101 B 000110 000010
Si calcola il numero intero q tale che qy’ ≤ r < (q+1)y’ e r = r – qy’. Al secondo e
R Q
Si calcola il numero intero q tale che qy’ ≤ r < (q+1)y’ e r = r – qy’. Al secondo eultimo passo (s + 1 = 2) si ha q = 1 e r = 000001
A 000101 B 000001 000011
Alla fine del procedimento, in Q è memorizzato il quoziente della divisione (q =000011) e in R rimane memorizzato il resto (r = 000001)
passopasso 22
OperazioniOperazioni tratra interiinteri didi macchinamacchina
Divisione tra interi di macchina
Esempio: M = 4, β = 10, x’ = 3151, y’ = 0012
A 0012 B 3151 0000
A 0012 B 0031 5100 spostamento a destra (s = 2)
passopasso 33
passopasso 22
passopasso 11A 0012 B 0007 5102 q = 2, r = 7
A 0012 B 0075 1020 spostamento a sinistra
A 0012 B 0003 1026 q = 6, r = 3
A 0012 B 0031 0260 spostamento a sinistra
A 0012 B 0007 0262 q = 2, r = 7
quozienteresto
OperazioniOperazioni tratra realireali didi macchinamacchina
Addizione e sottrazione tra reali di macchina
Siano
x’ = ±m’x·βp = (0.x1x2…xt) (x1 ≠ 0) , y’ = ±m’y·βq = (0.y1y2…yt) (y1 ≠ 0)
due numeri reali di macchina rappresentati in base β con t cifredue numeri reali di macchina rappresentati in base β con t cifredella mantissa. Si vuole calcolare z’ = ±m’z·βs, approssimazione dimacchina di z = x’ ± y’. Si eseguono i seguenti tre passi:
1. Confronto degli esponenti:- se p = q, si va al passo 2 con m’y = m’y = 0.y1y2…yt- se p ≠ q (ad es. p > q), si divide m’y per βp-q e si costruiscem’y = 0.00…0y1y2…yt
p-q
OperazioniOperazioni tratra realireali didi macchinamacchina
Addizione e sottrazione tra reali di macchina
2. Somma delle mantisse: si esegue mz = m’x ± m’y- se mz = 0, allora z’ = 0- se la somma ha provocato traboccamento, si divide mz per β,si sceglie come m’z il troncamento (arrotondamento) alla t-esima cifra del risultato di tale divisione e si pone s = p + 1esima cifra del risultato di tale divisione e si pone s = p + 1- se la somma non ha provocato traboccamento e le prime r ≥ 0cifre di mz sono nulle, si moltiplica mz per βr, si sceglie come m’zil troncamento (arrotondamento) alla t-esima cifra delrisultato di tale moltiplicazione e si pone s = p – r
3. Controllo della caratteristica: si esamina se Emin ≤ s ≤ Emax(intervallo di rappresentazione della caratteristica)
OperazioniOperazioni tratra realireali didi macchinamacchina
Esempio: sommare i numeri di macchina
x’ = 0.12345678·102, y’ = 0.23456789·10-1 (β=10, t=8)
Seguendo il procedimento descritto si hanno p = 2 e q = -1, dunque
m’y = 0.00023456789m’y = 0.00023456789
Si sommano le mantisse:
mz = 0.12345678 + 0.00023456789 = 0.12369134789
La somma non ha provocato traboccamento, r = 0, s = p - r = 2 em’z = 0.12369134. Quindi
z’ = 0.12369134·102
p-q=3
OperazioniOperazioni tratra realireali didi macchinamacchina
Esempio: sommare i numeri di macchina
x’ = 0.75869978·102, y’ = 0.98151815·102 (β=10, t=8)
Seguendo il procedimento descritto si hanno p = 2 e q = 2, dunque
m’y = 0.98151815m’y = 0.98151815
Si sommano le mantisse:
mz = 0.75869978 + 0.98151815 = 1.74021793
La somma ha provocato traboccamento: si divide mz per 10 (mz =0.174021793), si definisce m’z = 0.17402179 e si pone s = p + 1 = 3.Quindi
z’ = 0.17402179·103
OperazioniOperazioni tratra realireali didi macchinamacchina
Esempio: sommare i numeri di macchina
x’ = 0.75869978·102, y’ = -0.75868863·102 (β=10, t=8)
Seguendo il procedimento descritto si hanno p = 2 e q = 2, dunque
m’y = 0.75868863m’y = 0.75868863
Si sottraggono le mantisse:
mz = 0.75869978 - 0.75868863 = 0.00001115
La somma non ha provocato traboccamento: si moltiplica mz per 104
(mz = 0.1115), si definisce m’z = 0.11150000 e si pone s = p - r = -2.Quindi
z’ = 0.11150000·10-2
r=4
OperazioniOperazioni tratra realireali didi macchinamacchina
Moltiplicazione tra reali di macchina
Siano
x’ = ±m’x·βp = (0.x1x2…xt) (x1 ≠ 0) , y’ = ±m’y·βq = (0.y1y2…yt) (y1 ≠ 0)
due numeri reali di macchina rappresentati in base β con t cifredue numeri reali di macchina rappresentati in base β con t cifredella mantissa. Si vuole calcolare z’ = ±m’z·βs, approssimazione dimacchina di z = x’ * y’. Si eseguono i seguenti due passi:
1. Moltiplicazione delle mantisse: si calcola mz = m’x * m’y (mz ha 2tcifre)- se la prima cifra di mz è 0, si moltiplica mz per β e si pone r = 1- se la prima cifra di mz è diversa da 0, si pone r = 0La mantissa m’z di z’ è il troncamento (arrotondamento) alla t-esimacifra di mz
OperazioniOperazioni tratra realireali didi macchinamacchina
Moltiplicazione tra reali di macchina
2. Controllo della caratteristica: si pone s = p + q – r e si esaminase Emin≤ s ≤Emax (intervallo di rappresentazione della caratteristica)
Esempio: moltiplicare i numeri di macchina
x’ = 0.11111·101, y’ = 0.33333·103 (β=10, t=5)x’ = 0.11111·101, y’ = 0.33333·103 (β=10, t=5)
Moltiplicando le mantisse si ottiene
mz = 0.11111 * 0.33333 = 0.0370362963
Essendo la prima cifra di mz nulla, si moltiplica mz per 10 (mz =0.370362963), si definisce m’z = 0.37036 e si pone s = p + q - r = 3.Quindi
z’ = 0.37036·103
OperazioniOperazioni tratra realireali didi macchinamacchina
Divisione tra reali di macchina
Siano
x’ = ±m’x·βp = (0.x1x2…xt) (x1 ≠ 0) , y’ = ±m’y·βq = (0.y1y2…yt) (y1 ≠ 0)
due numeri reali di macchina rappresentati in base β con t cifredue numeri reali di macchina rappresentati in base β con t cifredella mantissa. Si vuole calcolare z’ = ±m’z·βs, approssimazione dimacchina di z = x’ / y’. Si eseguono i seguenti tre passi:
1. Confronto delle mantisse- se m’x ≥ m’y , si definisce m’x come la divisione di m’x per β e si pone
r = 1- se m’x ≥ m’y , si definisce m’x = m’x e si pone r = 0
OperazioniOperazioni tratra realireali didi macchinamacchina
Divisione tra reali di macchina
2. Divisione delle mantisse: si calcola mz = m’x / m’y . La mantissa m’zdi z’ è il troncamento (arrotondamento) alla t-esima cifra di mz
3. Controllo della caratteristica: si pone s = p - q + r e si esaminase Emin≤ s ≤Emax (intervallo di rappresentazione della caratteristica)
Esempio: dividere i numeri di macchina
x’ = 0.30200·10-2, y’ = 0.15000·103 (β=10, t=5)
La mantissa di x’ è maggiore di quella di y’, dunque m’x = 0.030200 er = 1. Quindi
mz = 0.030200 / 0.15000 = 0.2013333
Si ha s = p – q + r = -4,z’ = 0.20133·10-4
ConsiderazioniConsiderazioni sull’aritmeticasull’aritmeticadidi macchinamacchina
In aritmetica di macchina non valgono le seguenti (*):
- proprietà associativa per prodotto e somma: può accadere che
fl(fl(x’+y’)+z’) ≠ fl(x’+fl(y’+z’)) ≠ fl(fl(x’+z’)+y’)fl(fl(x’*y’)*z’) ≠ fl(x’*fl(y’*z’)) ≠ fl(fl(x’*z’)*y’)
- proprietà distributiva del prodotto rispetto alla somma: può- proprietà distributiva del prodotto rispetto alla somma: puòaccadere che
fl(fl(x’+y’)*z’) ≠ fl(fl(x’*z’)+fl(y’*z’))
- legge dell’annullamento del prodotto (fl(x’*y’) = 0 non implica cheuno tra x’ e y’ sia necessariamente uguale a 0)
- unicità dell’elemento neutro rispetto alla somma: può accadereche fl(x’+y’) = x’ con y’ ≠ 0
(*) si indichi con x’ o con fl(x) il numero di macchina che approssima il numero reale x
ConsiderazioniConsiderazioni sull’aritmeticasull’aritmeticadidi macchinamacchina
Esempio: non validità delle proprietà associativa della somma
Supponiamo di avere i tre numeri
a = 0.1234567, b = 6666.325, c = -6666.325
e di utilizzare l’aritmetica di macchina con β = 10 e t = 7. Si ha
a’ = 0.1234567·100, b’ = 0.6666325·104, c’ = -0.6666325·104a’ = 0.1234567·100, b’ = 0.6666325·104, c’ = -0.6666325·104
Eseguiamo la somma dei tre numeri in due modi diversi:
1. z = b’ + c’ � calcolo di z’ � s = z’ + a’ � calcolo di s’Si ottiene: z = 0; z’ = 0; s = 0.1234567·100; s’ = s
2. z = a’ + b’ � calcolo di z’ � s = z’ + c’ � calcolo di s’Si ottiene: z = 0.1234567·100 + 0.6666325·104 = 0.66664484567·104
z’ = 0.6666448·104; s = 0.0000123·104; s’ = 0.1230000·100
ConsiderazioniConsiderazioni sull’aritmeticasull’aritmeticadidi macchinamacchina
Esempio: non unicità dell’elemento neutro per la somma
Sianox’ = 0.62379·107, y’ = 0.32881·101
due numeri di macchina rappresentati in base β = 10 con t = 5 cifreper la mantissa. Si haper la mantissa. Si ha
z = x’ + y’ = (0.62379 + 0.00000032881)·107 = 0.62379032881·107
z’ = 0.62379·107 = x’
ConsiderazioniConsiderazioni sull’aritmeticasull’aritmeticadidi macchinamacchina
Esempio: il prodotto di macchina tra due numeri di macchina puòessere nullo anche se entrambi i numeri sono non nulli
Sianox’ = 1.0·10-30, y’ = 1.0·10-20
due numeri di macchina rappresentati in base β = 2 in precisionedue numeri di macchina rappresentati in base β = 2 in precisionesemplice (t = 32 cifre per la mantissa). Il prodotto tra x’ e y’ è
z = x’ * y’ = 1.0·10-50
che il calcolatore arrotonda a 0 (underflow)
ErroreErrore sullesulle operazionioperazioni didi macchinamacchina
Se x è un numero reale e x’ è la sua approssimazione di macchina,valgono le formule equivalenti
x
xx
εηepsη
xx
epsεεxx
−=≤=
≤+=
, ,'
),1('
Indichiamo con il simbolo # una generica operazione aritmetica.Il risultato z di un’operazione tra due numeri di macchina x’, y’ puònon essere un numero di macchina: la sua approssimazione z’ è
oppure
x
xxx
x εηepsη
ηx
+
=≤
+
=
1 , ,
1'
epsηη
yx
η
zz
epsεεyxεzz
≤
+
=
+
=
≤+=+=
,1
'#'
1'
),1)('#'()1('
ErroreErrore sullesulle operazionioperazioni didi macchinamacchina
Tenendo conto delle espressioni di x’ e y’
epsεεyxεzz ≤+=+= ),1)('#'()1('
epsεεεyyεxx yxyx ≤+=+= , ),1(' ),1('
si ha
Vediamo ora come si comportano le singole operazioni elementarinel dettaglio
epsεεεεεyεxz yxyx ≤+++= ,, ),1))(1()#1(('
ErroreErrore sullesulle operazionioperazioni didi macchinamacchinaSomma
Sia S = x + y la somma algebrica di due numeri reali x e y; la sommacalcolata risulta essere
L’errore relativo che si commette, trascurando i termini quadraticidell’errore (simbolo =), risulta
epsεεεεεyεxS yxyx ≤++++= ,, ),1))(1()1(('
·dell’errore (simbolo =), risulta
In dettaglio e passando ai valori assoluti
εεyx
yε
yx
x
S
SSε yxS +
+
+
+
=−
=' ·
·
)(1 2
epsOepsyx
y
yx
x
εεyx
yεε
yx
xεε
yx
yε
yx
xε yxyxS
+
+
+
+
+
≤
+
+
+
++
+
+
+
=
N.B.: si dice che f(x) ≤ O(g(x))
se esiste C > 0 t.c. |f(x)| ≤ C · |g(x)|
CancellazioneCancellazione didi cifrecifre
Consideriamo i numeri reali x = 0.12345789, y = -0.12343211. Sianox’ = 0.12345·100, y’ = -0.12343·100 le loro approssimazioni dimacchina in base β = 10 con t = 5 cifre per la mantissa.La somma esatta risulta S = 0.2578·10-4 mentre la somma calcolataS’ = 0.00002·100 = 0.20000·10-4.L’errore relativo che si commette è
Poiché i due numeri risultavano essere quasi uguali in valoreassoluto ma di segno opposto, la somma delle mantisse ha causatozeri dopo il punto radice e, dovendo normalizzare il risultato, sonoentrate da destra delle cifre nulle (quelle in rosso). Questapatologia prende il nome di fenomeno della cancellazione di cifre
1102.2...22420.0
'−
⋅≈=−
=
S
SSεS
ErroreErrore sullesulle operazionioperazioni didi macchinamacchinaMoltiplicazione
Sia P = x * y il prodotto algebrico tra due numeri reali x e y; ilprodotto calcolato risulta essere
L’errore relativo che si commette, trascurando i termini quadraticie cubici dell’errore, risulta
epsεεεεεyεxP yxyx ≤+++= ,, ),1))(1(*)1(('
e cubici dell’errore, risulta
In dettaglio e passando ai valori assoluti
εεεP
PPε yxP ++=
−=
' ·
)(3 2
epsOeps
εεεεεεεεεεεεε yxyxyxyxS
+≤
++++++=
ErroreErrore sullesulle operazionioperazioni didi macchinamacchinaDivisione
Sia Q = x / y la divisione algebrica tra due numeri reali x e y; ladivisione calcolata risulta essere
Moltiplicando numeratore e denominatore per (1-εy) e trascurando
epsεεεεεy
εxQ yx
y
x≤+
+
+= ,, ),1(
)1(
)1('
Moltiplicando numeratore e denominatore per (1-εy) e trascurandotermini quadratici e cubici, l’errore relativo commesso risulta
In dettaglio e passando ai valori assoluti
εεεQ
QQε yxQ +−=
−=
' ·
)(3 2
epsOeps
εεεεεεεεεεεεε yxyxyxyxQ
+≤
−−−++−=
ErroreErrore inerenteinerente e e erroreerrore algoritmicoalgoritmico
In generale, l’errore relativo commesso durante il calcolo diun’espressione razionale φ(x) a partire da un dato x si compone didue parti: l’errore inerente e l’errore algoritmico
L’errore inerente dipende dal problema ed è dovuto al fatto che ildato x non è rappresentato in maniera esatta ma attraverso lacorrispondente approssimazione di macchina x’corrispondente approssimazione di macchina x’
Dati Risultati
x
x’φ(x)
φ(x’)
aritmetica esatta
ErroreErrore inerenteinerente
Se εdati è grande rispetto a εx, allora il problema si dice malcondizionato. Quello che succede è che a piccole variazioni sui dati
x
xxεx
'−
=
)(
)'()(
xφ
xφxφεdati
−
=
Errore relativo sui dati Errore relativo sui risultati
condizionato. Quello che succede è che a piccole variazioni sui daticorrispondono grandi variazioni sui risultati
Il condizionamento è una caratteristica inerente al problema chesi sta affrontando ed esprime quanto esso sia sensibile ad unavariazione dei dati
CondizionamentoCondizionamento
Le operazioni di moltiplicazione e di divisione tra due numeri realisono problemi ben condizionati
L’operazione di somma tra due numeri reali è un problema ben
)(3 , )(3 22
epsOepsεepsOepsε QP +≤+≤
L’operazione di somma tra due numeri reali è un problema bencondizionato a meno che non abbiano valore assoluto molto simile esegno opposto. In tal caso, l’errore relativo può essere grande e,come abbiamo visto, si ha il fenomeno della cancellazione di cifre
)(12
epsOepsyx
y
yx
xεS +
+
+
+
+
≤
ErroreErrore inerenteinerente e e erroreerrore algoritmicoalgoritmico
L’errore relativo commesso durante il calcolo di un’espressionerazionale φ(x) a partire da un dato x si compone di due parti:l’errore inerente e l’errore algoritmico
L’errore algoritmico non dipende intrinsecamente dal problema madipende dall’algoritmo usato per risolvere il problema stesso
Dati Risultati
x φ(x)
fl(φ(x’))
aritmetica esatta
ErroreErrore algoritmicoalgoritmico e e stabilitàstabilità
Un algoritmo si dice stabile se l’errore relativo generato εalg èpiccolo, ovvero se l’algoritmo non è troppo sensibile agli errori
)(
))(()(
xφ
xφflxφε lga
−
=
Errore relativo sui risultati
piccolo, ovvero se l’algoritmo non è troppo sensibile agli erroriintrodotti con le operazioni di macchina richieste dell’algoritmostesso
Al contrario del condizionamento, la stabilità è una proprietàdell’algoritmo e non del problema
ErroreErrore totaletotale
L’errore totale deve tener conto sia della presenza di datiapprossimati sia degli errori introdotti ad ogni operazioneelementare dall’algoritmo usato per risolvere il problema
In prima approssimazione, l’errore totale è dunque la sommadell’errore inerente e dell’errore algoritmico
Dati Risultati
x φ(x)
fl(φ(x’))
aritmetica esatta
x’
SommaSomma didi tretre numerinumeriEsempio: siano a, b, c numeri reali di cui si vuole calcolare la sommas = a + b + c
Errore inerente (dati perturbati, aritmetica esatta)
dati:
algoritmo:
epsεεεεccεbbεaa cbacba ≤+=+=+= ,, ),1('),1('),1('
'~ 2. ''~ .1 czvbaz +=+=
errore:
Errore algoritmico (dati esatti, aritmetica di macchina)
dati:
algoritmo:
errore:
cbadati εcba
cε
cba
bε
cba
a
s
vsε
++
+
++
+
++
=−
=·
ccbbaa === ',','
21εε
cba
ba
s
wsε lga +
++
+=
−=
epsεεεczwεbaz ≤++=++=2121
, ),1)(ˆ( 2. )1)((ˆ .1
·
SommaSomma didi tretre numerinumeriEsempio: siano a, b, c numeri reali di cui si vuole calcolare la sommas = a + b + c
Errore totale (dati perturbati, aritmetica di macchina)
dati:
algoritmo:
epsεεεεccεbbεaa cbacba ≤+=+=+= ,, ),1('),1('),1('
epsεεεczsεbaz ≤++=++=2121
, ),1)(''(' 2. )1)(''(' .1
errore:
21
'εε
cba
baε
cba
cε
cba
bε
cba
a
s
ssε cbatot +
++
++
++
+
++
+
++
=−
=·
2121
errore inerente errore algoritmico