NUMERI REALI - unibo.it

NUMERI REALI

• Dominio: R

• Un soprainsieme degli interifialcune proprietà degli interi potreb-bero non essere più verificate

• Un numero reale può non essere finita-mente rappresentabile come stringa di simboli

• in nessuna base: numeri irrazionali (p, e, ...)

• in alcune basi: numeri razionali periodici

NUMERI REALI

• La rappresentazione di un numero razio-nale può risultare periodica o meno, a seconda della base adottata

• In particolare, non è mai periodica se si assume come base il denominatore della sua forma fratta

• 1/3 = (0.333333333333...)10 = (0.1)3

• 8/7 = (1.142857142857...)10 = (1.1)7

• ...

NUMERI REALI IN DIVERSE BASI• Se la rappresentazione di un numero razionale in base

B è periodica, è periodica anche la rappresentazione in

base B’ = B/k; il viceversa vale solo se B’ = Bn

• un numero periodico in base 10 è sicuramente: periodico anche in base 2 (perché 10 = 2*5)

• un numero periodico in base 2 può essere o non essere periodico in base 10…

• … ma lo è certamente in base 4, 8, 16, ...

• Intuitivamente: se non bastavano i fattori primi della base B a esprimere il numero in forma finita, la situazione non può certo migliorare avendo meno fattori a disposizione (come accade con B’ = B / k), mentre potrebbe migliorare avendo a disposizione nuovi fattori (come con B” = r * B)

NUMERI REALI: MANTISSA E RESTO

Dato un numero reale V, e fissati:• una base B• un naturale N

è sempre possibile esprimere V come somma di due contributi, di cui il primo costituito da esattamente N cifre:

V ” m * Besp + r * Besp-N

mantissa(n cifre)

esponente(intero)

resto(reale)

NUMERI REALI: MANTISSA E RESTO

• Esistono infinite triple Æm, esp, ræ che

consentono di esprimere, a parità di B e N, lo stesso numero reale V.

• Ad esempio, se V=31.4357, N=4, B=10:

RAPPRESENTAZIONE NORMALIZZATA

• Poiché la rappresentazione deve essere unica, occorre fare una scelta

• Si sceglie la tripla Æm, esp, ræ tale che

1/B £ m < 1, r<1

Rappresentazione normalizzata

RAPPRESENTAZIONE NORMALIZZATA

• Poiché la rappresentazione deve essere unica, occorre fare una scelta

• Si sceglie la tripla Æm, esp, ræ tale che

1/B £ m < 1, r<1

Rappresentazione normalizzata

In pratica, è quella in cui la man-tissa è <1, e la sua prima cifra dopo la virgola è diversa da 0

NUMERI REALI: IL VINCOLO

• Un numero reale ha spesso una rappre-sentazione infinita in una data base, ma rappresentare infinite cifre è impossibile

• Ergo, assumiamo come rappresentazio-ne approssimata del numero reale V il

solo contributo m * Besp

V » m * Besp

• Il resto si trascura fi Errore di troncamento

NUMERI REALI: LE SCELTE OPERATIVE

• In pratica dobbiamo stabilire:

• il numero N di cifre binarie (bit) per la mantissa• il numero P di cifre binarie (bit) per l’esponente• la codifica da adottare per l'esponente• come rappresentare il segno del numero

• Osservazione: nel caso B=2, la mantissa normalizzata è compresa fra 1/2 e 1:

1/2 £ m < 1

fi il primo bit dopo la virgola è sempre 1.

NUMERI REALI: LE SCELTE OPERATIVE

• In pratica dobbiamo stabilire:

• il numero N di cifre binarie (bit) per la mantissa• il numero P di cifre binarie (bit) per l’esponente• la codifica da adottare per l'esponente• come rappresentare il segno del numero

• Osservazione: nel caso B=2, la mantissa normalizzata è compresa fra 1/2 e 1:

1/2 £ m < 1

fi il primo bit dopo la virgola è sempre 1.

Ma allora si può evitare di scriverlo esplicitamente! In effetti, un bit prefissato non porta informazione.

Dunque, N cifre binarie richiedono per la memoriz-zazione soltanto N-1 bit.

NUMERI REALI: LE SPECIFICHE (IEEE-754)

NUMERI REALI: LE SPECIFICHE

Casi speciali (espMAX=255 per i float, 2047 per i double):

• esp=0, m=0 rappresenta 0.0• esp=espMAX m=0 rappresenta – ¥

• esp=espMAX m„0 rappresenta NaN

dove NaN (Not a Number) indica il risultato di operazioniindeterminate o impossibili:

0 / 0 0 * ¥ ¥ - ¥ ¥ / ¥

• esp=0 m„0 rappresenta valori non normalizzati

ciò consente di rappresentare numeri ancora più piccoli, ampliando il range di valori rappresentabili a parità di costo.

NUMERI REALI: CIFRE SIGNIFICATIVE

Cifre significative

• Poiché assumendo V » m * Besp trascuriamo

il resto r * Besp-N, e poiché nella forma nornalizzata r<1, l’errore vale:

Eassoluto £ Besp-N

• Esso non è molto significativo in sé: lo è di più se rapportato al valore del numero

Erelativo £ Besp-N / (m * Besp)

• da cui, poiché 1/B £ m < 1,

Erelativo £ Besp-N / Besp-1 = B1-N

NUMERI REALI: CIFRE SIGNIFICATIVECifre significative

Se dunque Erelativo £ B1-N , le cifre

decimalisignificative risultano:• float

• N=24 Er £ 2-23 = 10-23*log2 = 10-7

• circa 6-7 cifre decimali significative

• double

• N=53 Er £ 2-52 = 10-52*log2 = 10-15

• circa 14-15 cifre decimali significative

NUMERI REALI: ESEMPIO 1

Rappresentazione come float di V = 1.0

• rappr. normalizzata: V = 1.010 = 0.12 * 21

• segno (1 bit): 0• mantissa (24 bit): .10000000 00000000 00000000• esponente (8 bit con eccesso 126)

esp=1 fi 126+1 = 127 fi 01111111

in memoria:



• rappr. normalizzata: V = 101.1112 = .1011112 * 23


esp=3 fi 126+3 = 129 fi 10000001

in memoria:


Rappresentazione come float di V = -29.1875

• rappr. normalizzata: V = - .1110100112 *25


esp=5 fi 126+5 = 131 fi 10000011

in memoria:



• rappr. normalizzata: V =.0(0011)2 periodico!


esp=-3 fi 126-3 = 123 fi 01111011

in memoria:





esp=-3 fi 126-3 = 123 fi 01111011

in memoria:

Errore di troncamentoo si tronca o si arrotonda

di solito si arrotonda





esp=-2 fi 126-2 = 124 fi 01111100

in memoria:


Rappresentazione come float di V = -1/310

• rappr. normalizzata: V = -.(01)2 periodico!


esp=-1 fi 126-1 = 125 fi 01111101

in memoria:

ESPERIMENTI: SPIARE DENTRO JAVA

Come verificare se quanto calcolato è esatto?

• Occorre un modo per "spiare" dentro la macchina virtuale del linguaggio (Java, C, Pascal, …)

• In Java, la classe wrapper Float (risp. Double) fornisce la funzione floatToIntBits (risp. doubleToLongBits)

• Tale funzione "estrae" la rappresentazione di un float (risp. double) bit per bit e la pone in un int (risp. long) pronta per la stampa o altre elaborazioni.

ESEMPIO: SPIARE UN FLOAT in Java

Esempio di codice che "spia" un float f:

System.out.println("Numero float: " + f);

int internalRep = Float.floatToIntBits(f);

// converto l'intero in stringa binaria// tramite una variante di toStringString binaryString = Integer.toBinaryString(internalRep);

// aggiungo '0' davanti fino ad avere 32 bit// dato che toBinaryString non mette zeri inizialiwhile (binaryString.length()<32) binaryString = "0" + binaryString;

// stampo la stringa a videoSystem.out.println(binaryString);

ESPERIMENTI: MIGLIORIE ESTETICHE• La versione precedente stampa un'unica stringa di 32

bit, praticamente illeggibile per noi: 10111110101010101010101010101011

• meglio sarebbe separare le varie parti, ad esempio: 1 01111101 01010101010101010101011

o magari: 1 01111101 0101010 10101010 10101011

Per farlo: System.out.println(binaryString.charAt(0) + " " +binaryString.substring(1,9) + " " +binaryString.substring(9,16) + " " +binaryString.substring(16,24) + " " +binaryString.substring(24,32) );

OPERAZIONI FRA REALI & ERRORI

• Negli interi, si possono creare errori nelle operazioni, ma gli operandi sono comunque rappresentati esattamente (entro il range)

• Nei reali, invece, già gli stessi operandi pos-sono essere già affetti da errore a causa dell’impossibilità di rappresentare le infinite cifre dei numeri periodici e irrazionali: è l’errore di troncamento.

• Errore di troncamento = ogni qual volta il numero di cifre disponibili è insufficiente.

ERRORE DI TRONCAMENTO• Si manifesta quando

• il numero è periodico

• il numero non è periodico ma ha troppe cifre

• il risultato di un’operazione, a causa un riporto, richiede troppe cifre

• Esempi (mantissa di 8 bit, per semplicità)

• 15.810 = .1111110011001100... * 24 (è 15.75)

• 300.510 = .10010110012 * 29 (è 300)

• 15110 + 16010 =

= .10010111 * 28 + .10100000 * 28 =

= .100110111 * 29 (è 310)

OPERAZIONI FRA REALI & ERRORI

Vi sono poi altre due sorgenti di errore:• l’errore di incolonnamento

• è causato dalla necessità di incolonnare i numeri per poterli sommare o sottrarre

• l’errore di cancellazione• è la conseguenza finale della presenza, a

monte, di errori di troncamento, che possono far sì che alcune cifre del risultato non siano affidabili, ovvero siano “virtualmente cancellate”

• si manifesta sottraendo numeri simili fra loro.

ERRORE DI INCOLONNAMENTO

L’errore di incolonnamento è causato dalla necessità di incolonnare i numeri per poterli sommare o sottrarre

• per incolonnare due numeri che, in forma normalizzata, hanno esponente diverso bisogna per forza“de-normalizzarne” uno

• si allinea quello di valore assoluto minore a quello di valore assoluto maggiore

• ciò causa una perdita di cifre significative nel numero che viene “de-normalizzato”.


Esempio: 96.5 + 1.75• Ipotesi: mantissa di 8 bit (per semplicità)

• 96.510 =.110000012 * 27 (senza errore)

• 1.7510 =.111000002 * 21 (senza errore)

Somma:

.110000012 * 27 + .110000012 * 27 +

.111000002 * 21 = .000000112 * 27 =

.110001002 * 27


Esempio: 96.5 + 1.75• Ipotesi: mantissa di 8 bit (per semplicità)

• 96.510 =.110000012 * 27 (senza errore)

• 1.7510 =.111000002 * 21 (senza errore)

Somma:

.110000012 * 27 + .110000012 * 27 +

.111000002 * 21 = .000000112 * 27 =

.110001002 * 27

cifre perse:è l’errore di

incolonnamento È 98, non 98.25 come doveva!

ERRORE DI INCOLONNAMENTO: ESPERIMENTO

public static void test() {

double val1 = 12345.0;

double val2 = 1e-16; // proprio al limite…

// errore di incolonnamento: // val1 + val2 COINCIDE con val1 !

if (val1 + val2 == val1) System.out.println("val1 + val2 == val1 !!");

}

---Java Run---val1 + val2 == val1 !!

ERRORI: ESPERIMENTO

public static void test1() {

double val1 = 0.1; // sembra 0.1 .. ma non lo è !double val2 = 0.3; // sembra 0.3 .. ma non lo è !

System.out.println(val1); // stampa 0.1 .. ma è un'illusione !System.out.println(val2); // stampa 0.3 .. ma è un'illusione !

// … e infatti, il triplo di val1 non è val2 !!!

double d = val1 + val1 + val1; // non è il triplo di val1!

if (d != val2) { System.out.print("ERRORE di "); System.out.println(d - val2);} // differenza di 5.5E-17

}val1 = 0.1val2 = 0.3

ERRORE di 5.551115123125783E-17

ERRORE DI CANCELLAZIONE

L’errore di cancellazione può presentarsi quando si sottraggono due numeri molto simili fra loro

• accade solo se in almeno uno dei due operandi, all’inizio, vi è stato errore di troncamento

• consiste nel fatto che si introducono zeri da destra per normalizzare il risultato, ma quegli zeri non sono significativi

• se ci fossero state le cifre perse all’inizio a causa del troncamento, il risultato sarebbe stato diverso.


Esempio: 15.8 - 15.5• Ipotesi: mantissa di 8 bit (per semplicità)

• 15.810 =.111111002 * 24 (con errore tronc.)

• 15.510 =.111110002 * 24 (senza errore)

Differenza:

.111111002 * 24 -

.111110002 * 24 =

.000001002 * 24 = . 100000002 * 2-1


Esempio: 15.8 - 15.5• Ipotesi: mantissa di 8 bit (per semplicità)

• 15.810 =.111111002 * 24 (con errore tronc.)

• 15.510 =.111110002 * 24 (senza errore)

Differenza:

.111111002 * 24 -

.111110002 * 24 =

.000001002 * 24 = . 100000002 * 2-1

cifre cancellate:è l’errore di

cancellazione

Sono 0 solo perché abbiamo troncato 15.8 all’inizio: avrebbero dovuto essere 11001

ERRORI: CONSEGUENZE

• A causa di questi errori, la proprietà associativa può non essere più verificata

• Esempio (mantissa di 8 bit, per semplicità)

• X = 0,75 fi .11000000 * 20 (senza errori)

• Y = 65,6 fi .10000011 * 27 (err. troncamento)

• Z = 64,0 fi .10000000 * 27 (senza errori)

• ORRORE!(X + Y) - Z è diverso da X + (Y - Z)

ERRORI: CONSEGUENZE

(X + Y) - Z è diverso da X + (Y - Z)

R = .10000000 * 22 R = .10010000 * 22

ACCUMULAZIONE DI ERRORI

• La presenza di errori che si accumulano può portare a risultati totalmente assurdi

• Esempio: Calcolo di p con l’algoritmo di Euclide

Una circonferenza di raggio 1 è lunga 2p,che può essere approssimata:

• dall’esterno, dal perimetro del poligono regolare di n lati circoscritto

• dall’interno, dal perimetro del poligono regolare di n lati inscritto

ACCUMULAZIONE DI ERRORI

Valgono le relazioni:

• ln = lato del poligono di n lati inscritto

• Ln = lato del poligono di n lati circoscritto

= 2 l / Ö (4 – l 2)

L'ALGORITMO IN JAVA (1/2)import java.io.*;

public class PigrecoEuclide {

public static void main(String[] args) {

System.out.println("Calcolo di pigreco con FLOAT."); System.out.print("Precisione [1e-8] ? ");

float eps = 1E-8F; // inizializz. richiesta da eccezione

try{

BufferedReader kbd = new BufferedReader( new InputStreamReader(System.in));

eps = Float.parseFloat(kbd.readLine());}catch(IOException e){

System.err.println("Errore di input - Program exit");System.exit(1);

}...

L'ALGORITMO IN JAVA (2/2) ... // algoritmo

float nlati = 4.0F, ln = (float) Math.sqrt(2.0);float smpinf, smpsup;

do {float OC2 = (float) Math.sqrt(4.0 - ln * ln); nlati *= 2.0;ln = (float) Math.sqrt(2.0F - OC2);smpinf = ln * nlati / 2.0F;smpsup = ln * nlati / OC2;System.out.println("nl=" + nlati + " d2=" + OC2 +

" piInf=" + smpinf + " piSup=" + smpsup);} while ((smpsup-smpinf >= eps) && (nlati < 1e+19));

}}

L'OUTPUTCalcolo di pigreco con FLOAT.Precisione (suggerito 1e-8)? 1e-8

nl=8.0 d2=1.4142137 piInf=3.0614672 piSup=4.329568nl=16.0 d2=1.8477591 piInf=3.1214445 piSup=3.378627nl=32.0 d2=1.9615706 piInf=3.1365461 piSup=3.1979947nl=64.0 d2=1.9903694 piInf=3.1403334 piSup=3.155528nl=128.0 d2=1.9975909 piInf=3.1412857 piSup=3.1450741nl=256.0 d2=1.9993976 piInf=3.1415188 piSup=3.1424654nl=512.0 d2=1.9998494 piInf=3.1412080 piSup=3.1414444nl=1024.0 d2=1.9999623 piInf=3.1424513 piSup=3.1425104nl=2048.0 d2=1.9999906 piInf=3.1424513 piSup=3.142466nl=4096.0 d2=1.9999976 piInf=3.1622777 piSup=3.1622815nl=8192.0 d2=1.9999994 piInf=3.1622777 piSup=3.1622787nl=16384.0 d2=1.9999999 piInf=2.8284270 piSup=2.8284273nl=32768.0 d2=2.0 piInf=0.0 piSup=0.0

NUMERI REALI - unibo.it

Documents

Transcript of NUMERI REALI - unibo.it