Eccoci arrivati all’approfondimento del secondo algoritmo citato nell’articolo precedente, l’algoritmo per la moltiplicazione utilizzato nell’antico Egitto.

L’articolo in cui l’ho introdotto è il seguente (se non l’hai ancora letto ti consiglio di darci un’occhiata) : Alla scoperta di algoritmi antichi e curiosi.

Ecco qui la pseudocodifica dell’algoritmo di cui andremo a parlare tra poco:

a,b interi

z = 0

finchè (a>0):

se a dispari -> z=z+b

a=a//z (divisione intera)

b=b*2

risultato z

Prima di cominciare con un breve approfondimento dedicato, ho pensato di introdurre l’argomento con un video in cui ci sono alcuni esempi. I passaggi seguiti non sono proprio evidenti ma ti assicuro che è esattamente ciò che viene definito dall’algoritmo scritto qui sopra.

Penso che possa anche risultarti più chiaro il funzionamento.

https://www.youtube.com/watch?v=J4q3NAO6zeY

Andiamo ora a vedere il funzionamento dell’algoritmo “ragionando in base 2”. Ti dico questo perchè il codice prima citato può essere adattato ad una qualsiasi base.

I due casi che si possono presentare in prima battuta sono i seguenti:

1. a pari
2. a dispari

Scriviamo quindi a=2a’ nel primo caso e a=2a”+1 nel secondo.

Analizziamo ora il primo caso.

In tali condizioni z diventerà uguale alla seguente espressione: (2a’)b = a’ (2b) in quanto moltiplicare a*b o o (a/2)*(2b) è la stessa cosa.

Pertanto le operazioni da eseguire dopo il “finchè” nel primo caso non sono rilevanti più di tanto.

Ma andiamo ora ad analizzare il secondo caso, ossia con a dispari.

z=ab=(2a”+1)b=2a”b + b = a” (2b) +b

Ora quindi siamo nelle stesse condizioni del caso precedente per il primo addendo, abbiamo però una addendo “b” in più. Per cui possiamo dire di fare (a/2)*(2b) ed assegnare tale espressione alla variabile z, ricordandoci però di quel “+b” che compare nell’espressione prima citata.

Per cui nel caso a sia dispari, mi vado a ricordare di b e lo sommo a priori a z.

Andando quindi a riassumere il tutto, che probabilmente non ti è ancora del tutto chiaro (è difficile spiegare un algoritmo scrivendo 🙂 ), diciamo che l’algoritmo della moltiplicazione egizia si basa su un un principio unico.

Esso è il seguente: A * B = (A/2) * (2B).

Questo è infatti ciò che viene eseguito a priori in questo algoritmo.

Tuttavia nel caso A sia dispari, nel dividere per 2 (con la divisione intera) si andrebbe a perdere qualcosa. Pertanto, siccome so che succede sempre così, mi faccio trovare pronto e sommo a priori B a z. Così da non perdermi nulla nella divisione intera di a.

Spero di averti chiarito abbastanza il comportamento di questo algoritmo.

In caso tu abbia dubbi, critiche o suggerimenti (come al solito) non esitare a commentare o contattarmi.