Calcolo Numerico - 2 - Rappresentazione Dei Numeri

36
Rappresentazione Rappresentazione dei dei numeri numeri Luca Zanni , Marco Prato Calcolo Numerico Corsi di Laurea in Matematica e Informatica

Transcript of Calcolo Numerico - 2 - Rappresentazione Dei Numeri

Page 1: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

RappresentazioneRappresentazionedeidei numerinumeri

Luca Zanni , Marco Prato

Calcolo NumericoCorsi di Laurea in Matematica e Informatica

Page 2: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

CalcoloCalcolo numericonumerico

Di cosa si occupa il calcolo numerico?

• “trovare gli algoritmi che risolvono un problema matematiconel minor tempo e con la massima accuratezza”nel minor tempo e con la massima accuratezza”

• “dare una risposta numerica ad un problema matematicomediante un calcolatore”

(V. Comincioli, Analisi Numerica: Metodi, Modelli, Applicazioni)

Page 3: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

OsservazioneOsservazione

L’utilizzo di uno strumento come il calcolatore impone dei limitidi tempo e di spazio

Esempio: studiare un algoritmo al calcolatore per determinarele radici di un’equazione di secondo grado ax2 + bx +c = 0 eapplicarlo al caso a = 1, b = (104+10-13), c = 10-9

Metodo 1: formula di risoluzione

L’output del programma implementato al calcolatore è

In particolare, , ovvero, la proprietà del

prodotto delle radici non è verificata

a

acbbx

2

42

2,1

−±−=

a

cxx =≠=⋅

−9

21100

0 ,102

4

1=−= xx

Page 4: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

OsservazioneOsservazione

L’utilizzo di uno strumento come il calcolatore impone dei limitidi tempo e di spazio

Esempio: studiare un algoritmo al calcolatore per determinarele radici di un’equazione di secondo grado ax2 + bx +c = 0 eapplicarlo al caso a = 1, b = (104+10-13), c = 10-9

Metodo 2: calcolare una delle due radici e ricavare la secondamediante la proprietà del prodotto delle radici

13

1

2

4

110 ,10

−−==−=

ax

cxx

Page 5: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

OsservazioneOsservazione

Applicando due algoritmi diversi, in teoria equivalenti, abbiamoottenuto risultati diversi

Durante il corso vedremo alcuni criteri

- per capire quali sono i casi critici di algoritmi e problemi:- per capire quali sono i casi critici di algoritmi e problemi:parleremo di stabilità e condizionamento

- per misurare l’efficienza degli algoritmi: parleremo dicomplessità computazionale (numero di operazioni svoltedall’algoritmo)

Page 6: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

Dov’èDov’è l’errorel’errore??

Il calcolatore è in grado di rappresentare solo un numero finitodi cifre

si rappresenta solo un sottoinsieme finito dell’insieme deisi rappresenta solo un sottoinsieme finito dell’insieme deinumeri reali e un intervallo limitato di numeri interi

Ne segue che sia i dati iniziali che i risultati delle operazioni diun algoritmo non sono rappresentabili esattamente

creazione e propagazione di errori durante l’esecuzione deglialgoritmi

Page 7: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

PrimiPrimi passipassi

Preliminarmente, quindi, si devono considerare:

- la rappresentazione dei numeri interi e reali sul calcolatore

- come vengono eseguite le operazioni dal calcolatore

- quali sono gli effetti dell’aritmetica finita sugli algoritmi

Page 8: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

La La rappresentazionerappresentazione deidei numerinumeri

Rappresentazione posizionale dei numeri

In base 10 abbiamo i simboli:

0,1,2,3,4,5,6,7,8,9

Page 9: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

La La rappresentazionerappresentazione deidei numerinumeri

Il numero “287” si può rappresentare in basi diverse:

- base 2 (simboli 0,1)

(100011111)2 = 1·28 + 0·27 + 0·26 + 0·25 + 1·24 + 1·23 + 1·22 + 1·21 + 1·20

- base 4 (simboli 0,1,2,3)

(10133)4 = 1·44 + 0·43 + 1·42 + 3·41 + 3·40

- base 16 (simboli 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F)

(11F)16 = 1·162 + 1·161 + 15·160

Page 10: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

La La rappresentazionerappresentazione deidei numerinumeri

In generale, fissata una base β > 1, ogni numero naturale N sipuò rappresentare come una stringa di simboli

Il valore del numero si ottiene daIl valore del numero si ottiene da

dove ord(di) è il valore numerico dell’i-esimo simbolo di

Se usiamo come simboli le cifre arabiche e se β ≤ 10, alloraord(di) = di

Page 11: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

SceltaScelta delladella basebase

La scelta della base influisce su:

- numero dei simboli

- lunghezza delle stringhe

- complessità dell’aritmetica (le tabelline)- complessità dell’aritmetica (le tabelline)

In generale, se la base è piccola si avranno:

- pochi simboli

- stringhe lunghe

- aritmetica semplice

Page 12: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

TabellineTabelline delladella sommasomma

Page 13: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

SommaSomma in base 2in base 2

La somma di due cifre conriporto fornisce il risultato e ilsuccessivo riporto. Il numerodelle possibili combinazioni degliimpulsi in entrata è basso

Page 14: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ProdottoProdotto in base 2in base 2

Page 15: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

SceltaScelta delladella basebase

In conclusione, la scelta della base 2 (rappresentazione binaria)comporta la manipolazione di lunghe stringhe di numeri ma lacomplessità dell’aritmetica è bassa

Le operazioni possono essere realizzate con semplici circuitielettrici

Finora si è parlato solo di numeri naturali, vediamo ora come sipossono rappresentare in base 2 (in generale, in una genericabase β) anche i numeri reali

Page 16: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

RappresentazioneRappresentazione deidei numerinumeri realireali

TeoremaTeorema

Fissata una base β > 1, ogni numero reale x si può rappresentareunivocamente come

dove- s è il segno di x

pββaβaβasx ⋅+++⋅=−−−

...)( 3

3

2

2

1

1

dove- s è il segno di x- gli ai sono numeri interi (detti cifre) tali che0 ≤ ai ≤ β-1 per ogni i=1,2,3,… e a1 ≠ 0

- p è un numero intero (detto caratteristica di x)- può esistere un intero k per cui ai = 0 per ogni i ≥ k- non può esistere un intero k per cui ai = β-1 per ogni i ≥ k

Esempio: 0.75 = 3/4 = 1/2 + 1/4 = 1·2-1 + 1·2-2

(β = 2, p = 0, s = 1, a1 = 1, a2 = 1, ai = 0 per ogni i ≥ 3)

Page 17: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

NotazioneNotazione scientificascientifica

Se

la sua rappresentazione in notazione scientifica è

Tale rappresentazione è anche chiamata in virgola mobilenormalizzata

pββaβaβasx ⋅+++⋅=−−−

...)( 3

3

2

2

1

1

pβaaax .... 321

±=

normalizzata

Esempio: 0.75 = .11·20

= .011·21

= .0011·22

rappresentazionescientificanormalizzata

rappresentazionescientifica

non normalizzata

punto radice

Page 18: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

NotazioneNotazione scientificascientifica

Si ha

p

p

i

i

i

p

βms

ββas

ββaβaβasx

⋅⋅=

⋅⋅=

⋅+++⋅=

∑∞

=

−−−

)(

...)(

1

3

3

2

2

1

1

N.B.: la somma degli infiniti termini a β-1

dove- è la mantissa

- βp è la parte esponente

Le cifre della mantissa senza gli zeri iniziali sono dette cifreessenziali (o più significative)

βms ⋅⋅=

∑∞

=

−=

1

)( i

i

iβam

infiniti termini aiβ-1

converge a un numero m perché β > 1

Page 19: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ConversioneConversione didi basebase

Conversione di un numero intero positivo da base 10 a base β > 1

0101

2

1

1

01

1

1

011

)...(

...

)...(

aβαaβaβaβa

aβaβaβa

aaaax

p

p

p

p

p

p

p

p

βpp

+=++++=

++++=

=

01011)...( aβαaβaβaβa pp +=++++=

pp

ppp

aβα

aβαα

+=

+==−−

0

... 11

1212

3

1

2

1)...( aβαaβaβaβaα p

p

p

p +=++++=−

Page 20: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

AlgoritmoAlgoritmo delledelle divisionidivisioni successivesuccessiveIl procedimento eseguito si chiama algoritmo delle divisionisuccessive. I resti ottenuti nelle varie divisioni considerati dalprimo all’ultimo e convertiti nei simboli della nuova baseesprimono l’intero x nella nuova base

Esempio:

(1972)10 = (1 1 1 1 0 1 1 0 1 0 0)2

N.B.: l‘algoritmo si arresta quando trova un quoziente nullo

Page 21: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

AlgoritmoAlgoritmo delledelle divisionidivisioni successivesuccessive

Altri esempi

Page 22: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

AlgoritmoAlgoritmo delledelle divisionidivisioni successivesuccessivePseudo-codice

Dato l’insieme di simboli (d0, d1, …, dβ-1)q xs (‘ ‘)while q ≠ 0

r resto(q/β) )...( aaaax =r resto(q/β)q parte intera(q/β)s concatena(dr,s)

stampa s 0101

2

1

1

01

1

1

011

)...(

...

)...(

aβαaβaβaβa

aβaβaβa

aaaax

p

p

p

p

p

p

p

p

βpp

+=++++=

++++=

=

pp

ppp

aβα

aβαα

+=

+==−−

0

... 11

1212

3

1

2

1)...( aβαaβaβaβaα p

p

p

p +=++++=−

Page 23: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ConversioneConversione didi basebase

Conversione di un numero reale positivo < 1 da base 10 a base β > 1

α

... ...

...

2

3

1

21

2

3

1

21

3

3

2

2

1

1

++=−⇒+++=

+++=

−−

−−

βaβaaβxβaβaaβx

βaβaβax

... ... 2

4

1

321

2

4

1

321++=−⇒+++=

−−

−−βaβaaβαβaβaaβα

Il procedimento seguito si chiama algoritmo delle moltiplicazionisuccessive

Page 24: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

AlgoritmoAlgoritmo delledelle moltiplicazionimoltiplicazionisuccessivesuccessive

Conversione di un numero reale positivo < 1 da base 10 a base β > 1

Esempi:

(0.980712890625)10 = (0.FB1)16(0.75)10 = (0 . 1 1)2

è la parte frazionaria del quoziente

precedente (1.5 – 1)

0.980712890625 x 16 = 15.691406250.69140625 x 16 = 11.06250.0625 x 16 = 1

0.75 x 2 = 1.5 p. int. 10.5 x 2 = 1.0 p. int. 1

B

F

1

Page 25: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

AlgoritmoAlgoritmo delledelle moltiplicazionimoltiplicazionisuccessivesuccessive

Anche se è possibile rappresentare un numero reale < 1 con unnumero finito di cifre in una certa base, non è detto che,cambiando base, si ottenga ancora una rappresentazione finita

Esempi:

(0.1)10 = (0.00011)2 (0.1)10 = (0.02)5(0.1)10 = (0.00011)2

0.1 x 2 = 0.2 p. int. 00.2 x 2 = 0.4 p. int. 00.4 x 2 = 0.8 p. int. 00.8 x 2 = 1.6 p. int. 10.6 x 2 = 1.2 p. int. 10.2 x 2 = 0.4 p. int. 0

(0.1)10 = (0.02)5

0.1 x 5 = 0.5 p. int. 00.5 x 5 = 2.5 p. int. 20.5 x 5 = 2.5 p. int. 2

Page 26: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

AlgoritmoAlgoritmo delledelle moltiplicazionimoltiplicazionisuccessivesuccessivePseudo-codice

Dato l’insieme di simboli (d0, d1, …, dβ-1) e il numero massimo dicifre N

p x

... ...

...

2

3

1

21

2

3

1

21

3

3

2

2

1

1

++=−⇒+++=

+++=

−−

−−

βaβaaβxβaβaaβx

βaβaβax

p xi 0s ‘0.‘while p ≠ 0 and i < N

r parte intera(p*β)p p*β - parte intera(p*β)s concatena(s,dr)i i + 1

stampa s

... ... 2

4

1

321

2

4

1

321 ++=−⇒+++=−

−−

−−βaβaaβαβaβaaβα

Page 27: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ConversioneConversione didi basebaseConversione di un numero reale x da base 10 a base β > 1

Se x = 0, la sua rappresentazione è 0 in qualunque base.Se x ≠ 0, si procede nel modo seguente:

1. si considerano:- |x| (valore assoluto di x)- |x| (valore assoluto di x)- INT(|x|) (parte intera di x)- |x| - INT(|x|) (parte frazionaria di x)

2. si converte INT(|x|) con l’algoritmo delle divisioni successive3. si converte |x| - INT(|x|) con l’algoritmo delle moltiplicazioni

successive4. si scrivono nell’ordine il segno, le cifre della rappresentazione

di INT(|x|), il punto radice e le cifre della rappresentazionedi |x| - INT(|x|)

Page 28: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ConversioneConversione didi basebaseEsempio: convertire in base 2 il numero x = (-25.375)10

1. |x| = 25.375, s = ‘-’INT(|x|) = 25INT(|x|) - |x| = 0.375

2. (25)10 = (11001)22. (25)10 = (11001)2

3. (0.375)10 = (.011)2

4. x = (-11001.011)2

Page 29: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ConversioneConversione didi basebaseConversione di un numero reale x da base β > 1 a base 10

Data la rappresentazione di x in base β, conviene convertire ognisimbolo al valore decimale e usare la rappresentazione posizionaledel numero, utilizzando l’aritmetica in base 10

βrpp aaaaax ).......( 121 +

±=

1. valutare l’espressione polinomiale

in t = β

2. valutare l’espressione polinomiale

in t = β

3. la rappresentazione in base 10 di x sarà data da ± (f(t) + g(t))

pp

ppatatatatf ++++=

−−

1

2

2

1

1... )(

1

1

1

1... )(

+

+−

−+++= tatatatg p

rp

r

rp

r

Page 30: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ConversioneConversione didi basebaseEsempio: convertire in base 10 il numero x = (-11001.011)2

1. 1·24 + 1·23 + 0·22 + 0·21 + 1·20 =(25)10

2. 1·(1/2)3 + 1·(1/2)2 + 0·(1/2)1 = (0.375)10

3. x = (-25.375)103. x = (-25.375)10

N.B.: dal punto di vista del costo computazionale (numero dioperazioni richieste), l’algoritmo usato per la valutazione deipolinomi nell’esempio non è ottimale

Page 31: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ConversioneConversione didi basebaseConversione di un numero reale x da base β > 1 a base γ > 1

Metodo 1: passare attraverso la base intermedia 10.

1. Convertire il numero da base β a base 10 (utilizzandol’espressione polinomiale del numero)

2. Convertire il numero ottenuto da base 10 a base γ (utilizzandogli algoritmi delle divisioni e/o moltiplicazioni successive)

Esempio: convertire in base 2 il numero x = (1221)7

x = 1·73 + 2·72 + 2·71 + 1·70 = (456)10x = (111001000)2

(456)10 = (111001000)2

Page 32: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ConversioneConversione didi basebaseConversione di un numero reale x da base β > 1 a base γ > 1

Metodo 2: applicare direttamente l’algoritmo delle divisioni e/omoltiplicazioni successive (si deve usare l’aritmetica in base β edesprimere le cifre ottenute nella conversione nei simboli dellabase γ)

Metodo 3: supponiamo γ = βk, con k intero > 1

1. Si scompone la rappresentazione di x in base β in gruppi di kelementi a partire dal punto radice verso sinistra per la parteintera e verso destra per la parte frazionaria. Il primo el’ultimo gruppo, se necessario, vengono completati con deglizeri.

2. Ogni gruppo è convertito nel simbolo corrispondente dellabase γ.

Page 33: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ConversioneConversione didi basebaseEsempio: convertire il numero (-1101110.01)2 in base 8

In questo caso si ha β = 2, γ = 8, k = 3.

(- 001 101 110 . 010)2 = (-156.2)81 5 6 2

Esempio: convertire il numero (-1101110.01)2 in base 16

In questo caso si ha β = 2, γ = 16, k = 4.

(-0110 1110 . 0100)2 = (-6E.4)16

6 E 4

Page 34: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

ConversioneConversione didi basebaseConversione di un numero reale x da base β > 1 a base γ > 1

Metodo 4: supponiamo γk = β con k intero > 1

Si sostituisce ogni cifra della rappresentazione di x in base β conun gruppo di k cifre della base γ rappresentanti la conversionedella cifra di base β in base γ.della cifra di base β in base γ.

Esempio: convertire il numero (37.47)9 in base 3

In questo caso si ha β = 9, γ = 3, k = 2.

(3 7 . 4 7)9 = (1021.1121)3

10 21 11 21

Page 35: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

BasiBasi utilizzateutilizzateLe basi più utili per le applicazioni agli elaboratori elettronicisono 2, 8 e 16. Per facilitare la conversione tra queste basi èopportuno costruire tabelle che associano ai simboli di una base β= γk stringhe di k elementi contenenti le conversioni dei simboli0,1,…,β-1 nella base γ

β = 8, γ = 2, k = 3 β = 16, γ = 2, k = 4β = 8, γ = 2, k = 3 β = 16, γ = 2, k = 4

(000)2 = 08 (0000)2 = 016 (1000)2 = 816(001)2 = 18 (0001)2 = 116 (1001)2 = 916(010)2 = 28 (0010)2 = 216 (1010)2 = A16

(011)2 = 38 (0011)2 = 316 (1011)2 = B16(100)2 = 48 (0100)2 = 416 (1100)2 = C16(101)2 = 58 (0101)2 = 516 (1101)2 = D16

(110)2 = 68 (0110)2 = 616 (1110)2 = E16(111)2 = 78 (0111)2 = 716 (1111)2 = F16

Page 36: Calcolo Numerico - 2 - Rappresentazione Dei Numeri

EserciziEsercizi1. Trasformare il numero 921.53 da base 10 a base 16.

[R.: 399.87AD147AD…]2. Trasformare il numero ABCDEF.2B3 da base 16 a base 10.

[R.: 11259375.168701…]3. Trasformare il numero 92A.5B da base 16 a base 8 passando

attraverso la base intermedia 10.[R.: (2346.3554687…)10 = (4452.266)8]

4. Trasformare il numero AF.4C da base 16 a base 2, 4 e 8 applicandola regola diretta della conversione separata di opportuni gruppi di

4. Trasformare il numero AF.4C da base 16 a base 2, 4 e 8 applicandola regola diretta della conversione separata di opportuni gruppi dicifre (iniziare dalla base 2).

[R.: (10101111.01001100)2 = (2233.1030)4 = (257.23)8]5. Trasformare il numero 92A.5B da base 16 a base 8 passando

attraverso la base intermedia 2.[R.: (100100101010.01011011)2 = (4452.266)8]

6. Trasformare il numero 12112.121 da base 3 a base 9.[R.: (175.53)9]

7. Trasformare il numero 321123.123 da base 4 a base 8 passandoattraverso la base intermedia 2.

[R.: (111001011011.011011)2 = (7133.33)8]