SCACCHIERE DI NEPEROSCACCHIERE DI NEPERO

(alle origini dell’aritmetica binaria)(alle origini dell’aritmetica binaria)

by corrado bonfanti - 2009

AntefattoAntefatto

algoritmi aritmetici degli scribi dell’antico Egitto

Algoritmo della Algoritmo della moltiplicazionemoltiplicazione per raddoppio per raddoppio

Un esempio: 237 45 = ??

Algoritmo della Algoritmo della moltiplicazionemoltiplicazione per raddoppio per raddoppio

1

2

4

8

16

32

64

128

…...

Un esempio: 237 45 = ??

Passo 1Passo 1 Avere a disposizione la tabella (precompilata) delle potenze di 2.

Algoritmo della Algoritmo della moltiplicazionemoltiplicazione per raddoppio per raddoppio

1

2

4

8

16

32

64

128

…...

Un esempio: 237 45 = ??

Passo 2Passo 2 Posizionare il moltiplicatore 4545 in corrispondenza della potenza di 2 immediatamente inferiore ad esso ……

4545

Algoritmo della Algoritmo della moltiplicazionemoltiplicazione per raddoppio per raddoppio

1

2

4

8

16

32

64

128

…...

Un esempio: 237 45 = ??

Passo 2Passo 2 …… e scomporlo sottraendo di volta in volta la potenza di 2 più grande possibile.

11-1=0

55-4=1

1313-8=5

4545-32=13

Algoritmo della Algoritmo della moltiplicazionemoltiplicazione per raddoppio per raddoppio

1

2

4

8

16

32

64

128

…...

Un esempio: 237 45 = ??

Passo 3Passo 3 Posizionare il moltiplicando 237237 sulla prima riga ……

1-1=0

5-4=1

13-8=5

45-32=13

237237

Algoritmo della Algoritmo della moltiplicazionemoltiplicazione per raddoppio per raddoppio

1

2

4

8

16

32

64

128

…...

Un esempio: 237 45 = ??

Passo 3Passo 3 …… e raddoppiarlo ripetutamente.

1-1=0

5-4=1

13-8=5

45-32=13

237237

474

948

1896

3792

7584

Algoritmo della Algoritmo della moltiplicazionemoltiplicazione per raddoppio per raddoppio

11

2

44

88

16

3232

64

128

…...

Un esempio: 237 45 = ??

Passo 4Passo 4 Scegliere i raddoppi corrispondenti alla scomposizione del moltiplicatore.

1-1=0

5-4=1

13-8=5

45-32=13

237

474

948

1896

3792

7584

237237

948948

18961896

75847584

Algoritmo della Algoritmo della moltiplicazionemoltiplicazione per raddoppio per raddoppio

1

2

4

8

16

32

64

128

…...

Un esempio: 237 45 = ??

Passo 5Passo 5 Fare la somma ……

1-1=0

5-4=1

13-8=5

45-32=13

237

474

948

1896

3792

7584

237

948

1896

7584

1066510665

Algoritmo della Algoritmo della moltiplicazionemoltiplicazione per raddoppio per raddoppio

1

2

4

8

16

32

64

128

…...

Un esempio: 237 45 = ??

1-1=0

5-4=1

13-8=5

45-32=13

237

474

948

1896

3792

7584

237

948

1896

7584

… ed ecco il risultato: 237 45 = 10665 10665

CorollarioCorollario

1

2

4

8

16

32

64

128

……

1-1=0

5-4=1

13-8=5

45-32=13

Ritorniamo alla scomposizione di 45 ……

1

2

4

8

16

32

64

128

…...

1-1=0

5-4=1

13-8=5

45-32=13

11

11

11

11

…… associamo 11 alle righe utilizzate ……

CorollarioCorollario

1

2

4

8

16

32

64

128

……

1-1=0

5-4=1

13-8=5

45-32=13

11

00

11

11

00

11

…… e associamo 00 alle righe non utilizzate.

CorollarioCorollario

1

2

4

8

16

32

64

128

……

1-1=0

5-4=1

13-8=5

45-32=13

11

00

11

11

00

11

Gli scribi egizi non potevano esserne consapevoli, ma ……

CorollarioCorollario

1

2

4

8

16

32

64

128

……

1-1=0

5-4=1

13-8=5

4545-32=13

11

00

11

11

00

11

…… sorpresa! Avevano inventato la numerazione binarianumerazione binaria, quella che oggi si usa nei computer: 45451010 = 101101 10110122

CorollarioCorollario

Gli scribi egizi non potevano esserne consapevoli, ma ……

4141Un esempio: 539 : 41 = ??

Passo 1Passo 1 Prendere il divisore 4141 ……

Algoritmo della Algoritmo della divisionedivisione per raddoppio e tentativi per raddoppio e tentativi

41

82

164

328

656

Un esempio: 539 : 41 = ??

Passo 1Passo 1 …… e raddoppiarlo ripetutamente.

Algoritmo della Algoritmo della divisionedivisione per raddoppio e tentativi per raddoppio e tentativi

4141 1 =

2 =

4 =

8 =

16 =

……

41

82

164

328

656

Un esempio: 539 : 41 = ??

Passo 2Passo 2 Dalla colonna dei raddoppi, scegliere, per tentativiper tentativi, i numeri la cui somma S sia minore del dividendo 539 e tale che la differenza 539 - S sia minore del divisore 41.

Algoritmo della Algoritmo della divisionedivisione per raddoppio e tentativi per raddoppio e tentativi

41 1 =

2 =

4 =

8 =

16 =

……

41

82

164

328

656

Un esempio: 539 : 41 = ??

Passo 3Passo 3 I numeri che “vanno bene” nel nostro esempio sono quelli trascritti in rosso. (N.B. Si procede per tentativi, ma la soluzione è unica.)

Algoritmo della Algoritmo della divisionedivisione per raddoppio e tentativi per raddoppio e tentativi

41 1 =

2 =

4 =

8 =

16 =

……

4141

164164

328328

41

82

164

328

656

Un esempio: 539 : 41 = ??

Passo 3Passo 3 Infatti, vedi sopra.

Algoritmo della Algoritmo della divisionedivisione per raddoppio e tentativi per raddoppio e tentativi

41 1 =

2 =

4 =

8 =

16 =

4141

164164

328328

4141 + 164164 + 328328 = 533533 < 539 e

539 - 533533 = 6 < 41

41

82

164

328

656

Un esempio: 539 : 41 = ??

Il risultato è quindi 539 : 41 = 11 + 44 + 88 = 1313 col resto di 66.

Algoritmo della Algoritmo della divisionedivisione per raddoppio e tentativi per raddoppio e tentativi

41 11 =

2 =

44 =

88 =

16 =

41

164

328

41 + 164 + 328 = 533 < 539 e

539 - 533 = 66 < 41

11

00

11

11

Un esempio: 539 : 41 = ??

CorollarioCorollario: 13131010 = 1101110122

Algoritmo della Algoritmo della divisionedivisione per raddoppio e tentativi per raddoppio e tentativi

41 11

2

44

88

16

Scacchiere binario di NeperoScacchiere binario di Nepero

(dalla Rabdologia del 1617)

Dopo più di duemila anni, all’inizio del XVII secolo, NeperoNepero adotta (probabilmente reinventandolo) il metodo egizio per la numerazione binaria.

Metodo che è il fondamento dello scacchiere binarioscacchiere binario.

SCACCHIERE BINARIO DI NEPEROSCACCHIERE BINARIO DI NEPEROAi bordi di uno scacchiere sono annotate, in ordine crescente dal basso verso l’alto, le potenze di 2

col. 8192 = 213

col. 16 = 24

riga 512 = 29

Ciascuna casella assume un valore diverso a seconda che la si consideri appartenente a una riga in diagonale ( ) oppure a una delle colonne parallele ai lati ( ).

Un esempio: 19 13 = ??

SCACCHIERE BINARIO DI NEPEROSCACCHIERE BINARIO DI NEPERO

Un esempio: 19 13 = ??

Passo 1Passo 1 Scomporre il moltiplicando in potenze di 2 ottenendo 1919 = 1616 [=24] + 22 [=21] + 11 [=20] e impostare la sua rappresentazione posizionando i gettoni nelle caselle appropriate.

1919

SCACCHIERE BINARIO DI NEPEROSCACCHIERE BINARIO DI NEPERO

Un esempio: 19 13 = ??

1313

Passo 2Passo 2 Scomporre il moltiplicatore in potenze di 2 ottenendo 1313 = 88 [=23] + 44 [=22] + 11 [=20] e replicare nelle colonne appropriate la disposizione dei gettoni già posizionati.

SCACCHIERE BINARIO DI NEPEROSCACCHIERE BINARIO DI NEPERO

Un esempio: 19 13 = ??

Passo 3Passo 3 Individuare, secondo le righe orizzontali, il valore delle caselle “gettonate” …...

SCACCHIERE BINARIO DI NEPEROSCACCHIERE BINARIO DI NEPERO

Un esempio: 19 13 = ??

Passo 3Passo 3 Individuare, secondo le righe orizzontali, il valore delle caselle “gettonate” …… e sommarli, con le rispettive molteplicità.

Risultato 19 13 = 247247

128 + 64 +

16 + 16 + 8 + 8 +

4 + 2 +

1 =

SCACCHIERE BINARIO DI NEPEROSCACCHIERE BINARIO DI NEPERO