L’algoritmo di Ahmes per la moltiplicazione: ancora oggi usato dalle moderne CPU

Chi sia l’autore dell’algoritmo non è dato saperlo. Ciò che si sa è che il papiro su cui si trova è firmato dallo scriba Ahmes. Si tratta di un potentissimo algoritmo per eseguire le moltiplicazioni, che viene ancora oggi utilizzato dalle unità artimetico logiche delle moderne CPU.

 

Se si chiede un algoritmo per le moltiplicazioni, ne viene subito in mente tanto banale quanto inefficiente. Vediamolo di seguito con la sintassi del linguaggio C:

int moltiplica (int a, int b) {
int risultato = 0;
while (a != 0) {
risultato = risultato + b;
a = a - 1;
}
return risultato;
}

L’algoritmo può essere ottimizzato in modo tale da partire dal minore fra a e b, ma in ogni caso, questo algoritmo deve compiere un numero di passaggi almeno eguale al minore tra i due valori.

Ecco però l’algoritmo di Ahmes (sempre presentato in sintassi C):

int ahmes (int a, int b) {
int risultato = 0;
while (a != 0) {
if (a % 2 == 1)
risultato = risultato + b;
a = a / 2;
b = b * 2;
}
return risultato;
}

Ad una prima occhiata, non si capisce nemmeno come possa funzionare, ma in realtà il meccanismo è molto semplice.

Infatti, se a è un multiplo di 2, allora la divisione per 2 sarà precisa e pertanto dividendo a per 2 e moltiplicando b per 2 si mantiene tutto inalterato. Invece, se a fosse dispari, la divisione intera per 2 avrebbe come risultato l’eliminazione di un’unità. Per questo motivo, solamente se a è dispari è necessario sommare il valore di b al risultato. Vediamo un’esempio effettuando la divisione di 25 per 17.

Lo stato iniziale è il seguente: risultato = 0, a = 25, b = 17. Vediamo come viene modificato ad ogni ciclo (da notare che nella tabella è indicato lo stato finale ad ogni ciclo, non fatevi trarre in inganno dal fatto che il valore di b viena raddoppiato, la somma infatti avviene prima del raddoppiamento):

Ciclo a b Risultato
12 34 17
6 68 17
3 136 17
1 272 153
0 544 425

Magia. In solo cinque passaggi (contro i 17 minimi di cui aveva bisogno il nostro primo algoritmo) abbiamo trovato il risultato.

Questo algoritmo è efficientissimo e viene ad oggi utilizzato dalle moderne CPU quando si chiede loro di fare una moltiplicazione. Il motivo è anche da ricercare nell’architettura dei calcolatori che funzionano con il sistema binario. Infatti, nel sistema binario, è incredibile semplice moltiplicare a dividere per 2 basta, rispettivamente, aggiungere uno 0 (shift a sinistra) o eliminare l’ultima cifra (shift a destra).