Cors

odiCalc

olo

Num

eric

oIe

Labora

torio

Anno

Acc

adem

ico

2006

-200

7C.d

.L.in

Mat

emat

ica

Doce

nte

:D

ott.ss

aFed

eric

aT

inti

e-m

ail:

tntf

rc@

unife.

itH

ome

pag

e:htt

p:/

/dm

.unife.

it/∼

tinti

Calc

olo

Num

eric

o

IlCal

colo

Num

eric

osi

occ

upa

dipr

oget

tare

edan

aliz

zare

met

odinum

eric

iper

lariso

luzi

one

dipr

oble

midel

mon

do

real

e,sf

rutt

ando

alm

eglio

leriso

rse

diun

sist

ema

dica

lcol

o.

L’u

sodiuna

stru

men

todica

lcol

opr

esuppon

elim

itaz

ionich

erigu

ardan

o:

TEM

PO

Anal

isidel

laCom

ple

ssità

Com

puta

zion

ale:

num

ero

diop

eraz

ioninec

essa

rie

SPA

ZIO

Mem

oria

limitat

a:an

alisidel

laquan

tità

dim

emor

ia,

num

erifinitie

anal

isidel

l’er

rore

La

mag

gior

par

tedei

prob

lem

ipuò

esse

redec

ompos

tain

sott

opro

ble

mi

rico

nduci

bili

all’in

siem

edei

prob

lem

ifo

ndam

enta

lidel

Cal

colo

Sci

entifico

.

Inum

erie

lara

ppre

senta

zione

posizi

onale

NU

MERO

↙↘

EN

TIT

A’A

ST

RAT

TA

RA

PPRESEN

TA

ZIO

NE

”set

te”

(7,V

II,111

2,...)

univ

oca

men

tedet

erm

inat

am

olte

plic

ea

seco

nda

dei

criter

idira

ppr

esen

tazi

one

adot

tati.

•RA

PPRESEN

TA

ZIO

NE

PO

SIZ

ION

ALE

Se

legg

iam

ola

stringa

287,

noi

inre

altà

stia

mo

usa

ndo

una

conve

nzi

one

per

inte

nder

ele

segu

enti

oper

azio

ni:

(287) 1

0=

2·1

02+

8·1

01+

7·1

00

Abbia

mo

cioè

una

bas

eβ

=10

che

det

erm

ina

ilpes

odel

lapos

izio

ne

occ

upat

ae

un

insiem

edi

β−

1sim

bol

i:dat

idal

leci

fre

arab

e0,1,2,3,4,5,6,7,8,9.

Con

lost

esso

prin

cipio

pos

siam

orica

vare

altr

era

ppr

esen

tazi

onisc

eglie

ndo

una

div

ersa

bas

e:

(101110100) 2

=1·2

8+

0·2

7+

0·2

6+

1·2

5+

+1·2

4+

1·2

3+

1·2

2+

1·2

1+

1·2

0

bas

e=

2,sim

bol

i0,

1 (10133) 4

=1·4

4+

0·4

3+

1·4

2+

3·4

1+

3·4

0

bas

e=

4,sim

bol

i0,

1,2,

3

(11F

) 16

=1·1

63+

1·1

62+

15·1

60

bas

e=

16,sim

bol

i0,

1,2,

...,9,

A,B

,C,D

,E,F

Inge

ner

ale,

inun

sist

ema

dinum

eraz

ione

inbas

eβ

>1,

ogni

nat

ura

leN

sira

ppr

esen

taco

me:

N=

(dnd

n−

1..

.d0) β

=or

d(d

n)β

n+

ord(d

n−

1)β

n−

1+

...+

ord(d

1)β

1+

ord(d

0)β

0

ove

ord(d

i)è

ilva

lore

del

l’i–

esim

onat

ura

le;se

siusa

no

com

e

sim

bol

ile

cifre

arab

iche

ese

β≤

10,or

d(d

i)=

di.

(dnd

n−

1...d

0) β

èla

form

asinte

tica

diN

inbas

eβ.

SCELT

AD

ELLA

BA

SE

•num

ero

dei

sim

bol

i

•lungh

ezza

del

lest

ringh

e

•com

ple

ssità

del

l’ar

itm

etic

a

BA

SE

pic

cola−→

poch

isim

bol

i

stringh

elu

ngh

e

aritm

etic

ase

mplic

e

OPERA

ZIO

NIA

RIT

MET

ICH

EN

ELLE

DIF

FEREN

TIB

ASI

Val

gono

lest

esse

rego

lee

prop

riet

àfo

rmal

idel

l’ar

itm

etic

adec

imal

e,m

asi

dev

ono

usa

reta

vole

div

erse

da

quel

lepitag

oric

he

per

addiz

ione

em

oltiplic

azio

ne.

La

som

ma

può

dar

eun

ripor

to1;

ilpr

odot

topuò

dar

eun

ripor

toco

mpr

eso

tra

1e

β−

2.B

ase

2

+0

10

01

11

10

·0

10

00

10

1

Bas

e8

+0

12

34

56

7

00

12

34

56

71

12

34

56

710

22

34

56

710

113

34

56

710

1112

44

56

710

1112

135

56

710

1112

1314

66

710

1112

1314

157

710

1112

1314

1516

·0

12

34

56

7

00

00

00

00

01

01

23

45

67

20

24

610

1214

163

03

611

1417

2225

40

410

1420

2430

345

05

1217

2431

3643

60

614

2230

3644

527

07

1625

3443

5261

CA

SO

BIN

ARIO

L’a

ritm

etic

abin

aria

èpar

tico

larm

ente

sem

plic

e.

Som

ma:

(25) 1

0+

(19) 1

0=

(44) 1

0.

11

00

1+

10

01

1=

Rip

orto

11

1

10

11

00

Diff

eren

za:(2

4) 1

0−

(13) 1

0=

(11) 1

0.

11

00

0-

01

10

1=

01

01

1

Pro

dot

to:(1

3) 1

0·(

14) 1

0=

(182) 1

0.

11

01

·1

11

0=

00

00

11

01

11

01

11

01

10

11

01

10

Quoz

iente

:(2

8) 1

0:(9

) 10=

(3) 1

0co

nre

sto

1.

11

10

01

00

1

10

01

11

01

01

0

10

01

00

01

Quoz

iente

epr

odot

toso

no

ripor

tati

adiff

eren

zeo

som

me

etr

asla

zion

idinum

eri.

La

scel

tadel

la

bas

e2

com

por

tala

man

ipol

azio

ne

dilu

ngh

est

ringh

edinum

erim

ala

com

ple

ssità

del

l’ar

itm

etic

aè

bas

sa.

Le

oper

azio

nipos

sono

esse

rere

aliz

zate

con

sem

plic

ici

rcuitiel

ettr

onic

i.

ESEM

PIO

La

som

ma

didue

cifre

con

ripor

tofo

rnisce

ilrisu

ltat

oe

ilsu

cces

sivo

ripor

to.

Ilnum

ero

del

le

pos

sibili

com

bin

azio

nideg

liim

pulsiin

entr

ata

èbas

so.

c1

c0

ripor

tos

ripor

to

00

00

0

00

11

0

01

01

0

01

10

1

10

01

0

10

10

1

11

00

1

11

11

1

Teo

rem

adira

ppre

senta

zione

dei

num

erire

ali

Teo

rem

a.

Sia

α∈R

,α6=

0;fiss

ato

un

inte

roβ

>1,α

sira

ppr

esen

tain

modo

unic

oco

me:

α=

segn

o(α)(

a1β−

1+

a2β−

2+

a3β−

3+

...)

βp

=se

gno(

α)

∞ ∑ i=1

(aiβ−

i )β

p

=se

gno(

α)

mβ

p

ove

segn

o(α)

=±

1(a

seco

nda

che

α>

,<

0),

0≤

ai≤

β−

1,co

na

iin

teri

ea

16=

0e

pè

un

inte

ro;può

esiste

reun

indic

ek

tale

che

ai=

0,k≤

i(r

appr

esen

tazi

one

deg

liin

teri

odei

razi

onal

ifiniti),m

anon

esiste

un

indic

ek

tale

che

ai=

β−

1,k≤

i.

•Il

num

ero

real

e0

sira

ppr

esen

taco

n0.

•Poi

chè

β>

1,la

serie

∑∞ i=

1(a

iβ−

i )è

conve

rgen

te.

•m

sidic

em

antiss

ae

vale

che

1 β≤

m<

1.

•β

psi

dic

epar

tees

ponen

te;p

sidic

ees

ponen

teo

cara

tter

istica

.

•·s

idic

epunto

radic

e,+

o−

sidic

ese

gno

del

num

ero

epuò

esse

reom

esso

seil

num

ero

è

pos

itiv

o.

Un

num

ero

real

eα6=

0si

espr

ime

innot

azio

ne

pos

izio

nal

ein

bas

eβ

>1

info

rma

scie

ntifica

nel

segu

ente

modo:

α=±

.a1a

2..

.βp;

sidic

enor

mal

izza

tase

a16=

0.

Inbas

e2

,in

form

anor

mal

izza

ta,a

1=

1.

ESEM

PI.

.372

10

3nor

mal

izza

ta

.0372

10

4sc

ientifica

.3141592

10

1nor

mal

izza

ta

.3243F

...16

1nor

mal

izza

ta

Alg

oritm

idico

nve

rsio

ne

dibase

Con

vers

ione

diun

inte

ropos

itiv

oα

da

bas

e10

abas

eβ

>1.

MET

OD

OD

ELLE

DIV

ISIO

NISU

CCESSIV

E:

α=

(am

am−

1...a

0) β

=a

mβ

m+

am−

1β

m−

1+

...+

a1β

+a0

=

=(a

mβ

m−

1+

am−

1β

m−

2+

...+

a1)β

+a0

=γ1β

+a0

a0,os

sia

laci

fra

men

osign

ifica

tiva

del

lara

ppr

esen

tazi

one

cerc

ata,

èil

rest

odel

ladiv

isio

ne

inte

radiα

per

β.

γ1

=(a

mβ

m−

2+

am−

1β

m−

3+

...+

a3β

+a

2)β

+a

1=

γ2β

+a

1

γ2

=(a

mβ

m−

3+

am−

1β

m−

4+

...+

a4β

+a

3)β

+a

2=

γ3β

+a

2

...

γm−

1=

am

β+

am−

1=

γm

β+

am−

1

γm

=0β

+a

m

m+

1=

num

ero

del

lediv

isio

nies

eguite

fino

adav

ere

un

quoz

iente

0.

Dat

ol’in

siem

edisim

bol

i(d

0,d

1,.

..d

β−

1)

q←

α;

s←

(’’)

;w

hile

q6=

0

r←

rest

o(q/

β);

q←

par

tein

tera

(q/β

);s←

conca

tena(

dr,s

);st

ampa

s;

ESEM

PIO

.(1

972)

10

bas

e2

1972

:2=

986

rest

o0

986

:2=

493

rest

o0

493

:2=

246

rest

o1

246

:2=

123

rest

o0

123

:2=

61re

sto

161

:2=

30re

sto

130

:2=

15re

sto

015

:2=

7re

sto

17

:2=

3re

sto

13

:2=

1re

sto

11

:2=

0re

sto

1

(197

2)10

=(1

1110

1101

00) 2

bas

e8

1972

:8=

264

rest

o4

246

:8=

30re

sto

630

:8=

3re

sto

63

:8=

0re

sto

3(1

972)

10

=(3

664)

8

bas

e16

1972

:16

=12

3re

sto

412

3:1

6=

7re

sto

11=

B7

:16

=0

rest

o7

(197

2)10

=(7

B4)

16

Conve

rsio

ne

diun

reale

positivo

α<

1da

base

10

abase

β>

1.

MET

OD

OD

ELLE

MO

LTIP

LIC

AZIO

NISU

CCESSIV

E:

α=

(.a1a2a3...)

β=

=a1β−

1+

a2β−

2+

a3β−

3...

•αβ

=a1+

a2β−

1+

a3β−

2+

a4β−

3...=

a1+

n1

a1

èla

par

tein

tera

del

risu

ltat

oe

n1

lapar

tefraz

ionar

ia.

n1

=a2β−

1+

a3β−

2+

...

•n

1β

=a2+

a3β−

1+

a4β−2

+...=

a2+

n2

•n

2β

=a3+

a4β−

1+

a5β−

2+

...=

a3+

n3

•.......

Quan

do

cife

rmia

mo?

Oss

erva

zion

e:Se

lara

ppr

esen

tazi

one

inbas

e10

diun

num

ero

finita,

non

èdet

toch

ela

rappr

esen

tazi

one

del

lost

esso

num

ero

inun’a

ltra

bas

eβ

sia

finita.

Sipuò

dim

ostr

are

che:

un

num

ero

α>

0ha

rappr

esen

tazi

one

finita

inbas

eβ⇔

esisto

no

inte

ripos

itiv

im

,nta

lich

eα

=m βn.

Altrim

enti

ilnum

ero

nel

lanuov

abas

eha

rappr

esen

tazi

one

per

iodic

a.

⇓

Cife

rmia

mo

quan

do

lapar

tefraz

ionar

iadiv

enta

nulla

oppure

quan

do

abbia

mo

ragg

iunto

un

num

ero

dici

fre

suffi

cien

ti.

Dat

ol’in

siem

edisim

bol

i(d

0,d

1,.

..d

β−

1)

eil

num

ero

mas

sim

odici

fre

Nm

ax

p←

α;

s←

’0.’

i←

0;w

hile

s6=

0an

di<

Nm

ax

r←

par

tein

tera

(s∗β

);p←

p∗β

−par

tein

tera

(p∗β

);s←

conca

tena(

s,d

r)

i←

i+

1;st

ampa

(s);

ESEM

PIO

.(0

.1) 1

0

bas

e2

0.1×

2=

0.2

p.

inte

ra0

0.2×

2=

0.4

p.

inte

ra0

0.4×

2=

0.8

p.

inte

ra0

0.8×

2=

1.6

p.

inte

ra1

0.6×

2=

1.2

p.

inte

ra1

0.2×

2=

0.4

p.

inte

ra0

...

(0.1

) 10

=(0

.000

1100

) 2bas

e5

0.1×

5=

0.5

p.

inte

ra0

0.5×

5=

2.5

p.

inte

ra2

0.5×

5=

2.5

p.

inte

ra2

...

(0.1

) 10

=(0

.02)

5

bas

e7

0.1×

7=

0.7

p.

inte

ra0

0.7×

7=

4.9

p.

inte

ra4

0.9×

7=

6.3

p.

inte

ra6

0.3×

7=

2.1

p.

inte

ra2

0.1×

7=

0.7

p.

inte

ra0

...

(0.1

) 10

=(0

.046

2)7

Alg

oritm

odico

nve

rsio

ne

diun

reale

αda

base

10

abase

β>

1.

1.D

eter

min

are|α|,

rico

rdan

do

ilse

gno.

2.D

eter

min

are

[|α|]

ees

eguire

laco

nve

rsio

ne

con

l’al

goritm

odel

lediv

isio

nisu

cces

sive

.

3.D

eter

min

are|α|−

[|α|]

ees

eguire

laco

nve

rsio

ne

con

l’al

goritm

odel

lem

oltiplic

azio

ni

succ

essive

.

4.Scr

iver

eil

segn

o,la

conve

rsio

ne

del

lapar

tein

tera

,il

punto

radic

e,la

conve

rsio

ne

del

lapar

te

fraz

ionar

ia.

ESEM

PIO

.α

=(−

25.3

75) 1

0.

Con

vert

ire

inbas

e2.

1.|α|=

25.3

75;se

gno=

’-’.

2.[|α|]

=25;(2

5) 1

0=

(11001) 2

.

3.|α|−

[|α|]

=.3

75;(.

375) 1

0=

(.011) 2

.

4.α

=(−

11001.0

11) 2

.

Con

vers

ione

diun

real

eda

bas

eβ

>1

abas

e10

.

α=

±(a

1a

2..

..a

p.a

p+

1a

p+

2..

.aq) β

Sfrutt

ando

lara

ppr

esen

tazi

one

pos

izio

nal

eab

bia

mo

che

α=±

(a1β

p−

1+

a2β

p−

2+

...+

apβ

0+

ap+

1β−

1+

ap+

2β−

2+

...+

aqβ

p−

q)

⇓Val

uta

zion

edidue

pol

inom

i:

f(x

)=

a1x

p−

1+

a2x

p−

2+

...+

ap

inx

=β

,

g(x

)=

aqx−

p+

q+

aq−

1x−

p+

q−

1+

...+

ap+

1x

inx

=1/β

.

(α) 1

0=±

(f(β

)+

g(1

/β))

.

⇓O

ccor

reun

algo

ritm

oco

nve

nie

nte

per

fare

ilca

lcol

odiun

pol

inom

ioa

coeffi

cien

tire

aliin

corr

ispon

den

zadiun

cert

ova

lore

.

Con

vers

ione

diun

real

eα

da

bas

eβ

1a

bas

eβ

2.

β1

−→10

−→β

2

↑↑

rappr

esen

tazi

one

pos

izio

nal

ediv

isio

nie

mol

tiplic

azio

nisu

cces

sive

ESEM

PIO

α=

(122

1)7,β

2=

2.

α=

1.73

+2.

72+

2.71

+1.

70−→

α=

(456

) 10−→

α=

(111

0010

00) 2

Valu

tazione

diun

polin

om

iore

ale

inx

=α.

pn(x

)=

a0x

n+

a1x

n−

1+

...+

an−

1x

+a

n

ai∈R

,a

06=

0

ALG

ORIT

MO

1.p←

1;

s←

an;

for

i=

n−

1,n−

2,..

.0⌊

p←

p∗α

;

s←

p∗a

i+

s;

stam

pa

s;

La

CO

MPLESSIT

A’CO

MPU

TA

ZIO

NA

LE

del

l’al

goritm

o(o

ssia

ilnum

ero

tota

lediop

eraz

ioni

aritm

etic

he

che

dev

ono

esse

refa

tte)

è2n

mol

tiplic

azio

nie

nad

diz

ioni.

ALG

ORIT

MO

2.Sibas

asu

llase

guen

terisc

ritt

ura

del

pol

inom

io:

pn(x

)=

(...((

(a0x

+a

1)x

+a

2)x

+a

3)x

+..

.)x

+a

n

Ese

mpio

:p(x

)=

4x

3+

5x

2+

x+

2

=((

4x

+5)x

+1)x

+2

s←

a0;

for

i=

1,..

.,n

⌊s←

s∗α

+a

i;

stam

pa

s;

La

CO

MPLESSIT

A’CO

MPU

TA

ZIO

NA

LE

èpar

ia

nm

oltiplic

azio

nie

nad

diz

ioni.

L’a

lgor

itm

opr

ende

ilnom

ediSCH

EM

AdiRU

FFIN

I-H

ORN

ER.