Algoritmi di moltiplicazione

Per algoritmi di moltiplicazione si intende la serie di passaggi elementari che deve compiere una generica CPU per eseguire l'operazione di moltiplicazione senza ricorrere ad una banale addizione ripetuta.

Interi senza segno

Per eseguire l'operazione di moltiplicazione le ALU dei microprocessori utilizzano alcuni algoritmi che consentono con una serie di addizioni e shift di calcolare una moltiplicazione.

Prima di tutto un po' di definizioni:

moltiplicando  x
moltiplicatore =
Prodotto

Primo Algoritmo

Siano

• il Moltiplicatore un registro a 32 bit inizializzato con il valore del moltiplicatore,
• il Prodotto un registro a 64 bit inizializzato a 0,
• il Moltiplicando un registro a 64 bit inizializzato con il valore del moltiplicando nei 32 bit più a destra e tutti 0 nei 32 bit più a sinistra.

Sia Moltiplicatore0 il bit meno significativo del Moltiplicatore allora un possibile algoritmo è il seguente:

 for (i=0;i<32;i++){
   if (Moltiplicatore0 == 1)
     Prodotto += Moltiplicando;
 
   Shifta il Moltiplicando a sx di 1 bit;
   Shifta il Moltiplicatore a dx di 1 bit;  
 }

Secondo Algoritmo

È possibile elaborare un miglioramento di questo algoritmo. Dato che metà dei bit del Moltiplicando rimangono sempre a 0, solo metà del registro (a 64 bit) contiene bit utili. Perché allora, invece di scalare il Moltiplicando a sx non scaliamo il prodotto a dx? In questo modo il Moltiplicando rimane fisso ed è sufficiente un registro a 32 bit. Ecco un'implementazione dell'algoritmo:

Sia il Moltiplicatore un registro a 32 bit inizializzato con il valore del moltiplicatore, Prodotto un registro a 64 bit inizializzato a 0, e il Moltiplicando un registro a 32 bit inizializzato con il valore del moltiplicando.

 for (i=0;i<32;i++){
   if (Moltiplicatore0 == 1)
     32 bit più a sx del Prodotto += Moltiplicando;
 
   Shifta il Prodotto a dx di 1 bit;
   Shifta il Moltiplicatore a dx di 1 bit;
 }

Terzo Algoritmo

È possibile eseguire un ulteriore miglioramento dell'algoritmo. Si nota che il registro Prodotto spreca uno spazio corrispondente alla dimensione del moltiplicatore: a mano a mano che lo spazio sprecato del prodotto scompare, scompaiono anche i bit del moltiplicatore. Per questo motivo questa ultima versione dell'algoritmo combina la metà più a destra del prodotto con il moltiplicatore. Il bit da controllare ora è il bit meno significativo di Prodotto ovvero Prodotto0. Ecco una possibile implementazione:

Inizializziamo il registro Prodotto nel seguente modo: nei 32 bit più a destra mettiamo il valore del moltiplicatore, nei 32 bit più a sinistra mettiamo tutti 0. Inizializziamo Moltiplicando con il valore del moltiplicando.

 for (i=0;i<32;i++){
   if (Prodotto0 == 1)
     32 bit più a sx del Prodotto += Moltiplicando;
 
   Shifta il Prodotto a dx di 1 bit;
 }

Interi con segno

Il metodo più semplice per gestire una moltiplicazione con segno è trasformare il moltiplicatore e il moltiplicando in interi senza segno e ricordare i segni, l'algoritmo dovrebbe poi effettuare 31 iterazioni (1 in meno per via del segno). Alla fine il numero verrà scritto positivo o negativo a seconda dei segni dei fattori.

Metodo alternativo di moltiplicazione

L'algoritmo classico di moltiplicazione ha complessità $O(n^{2})$: infatti si eseguono n2 operazioni di moltiplicazione tra singole cifre e una somma di n prodotti parziali, ciascuno di 2n cifre al più.

Vediamo ora un algoritmo più veloce, esso fu proposto per la prima volta nell'ambito del calcolo elettronico da Anatolij Alekseevič Karatsuba e pertanto è anche noto come algoritmo di Karatsuba.

Siano dati due numeri naturali $A$ e $B$ scritti con una notazione posizionale moltiplicativa con l'ausilio di $n$ cifre e $k$ simboli. Supponiamo per semplicità che n sia una potenza di 2 e che, ma è solo una scelta colta a rendere più comprensibile l'essempio sotto e non un attributo necessario, la base della notazione posizionale sia 10.

Chiamiamo $A_{sin}$ e $A_{des}$ rispettivamente le prime e ultime n/2 cifre di A e con e $B_{sin}$ e $B_{des}$ le prime e ultime n/2 cifre di B, cioè:

$A=A_{sin}10^{\frac {n}{2}}+A_{des}$

$B=B_{sin}10^{\frac {n}{2}}+B_{des}$

Da cui:
$AB=A_{sin}B_{sin}10^{n}+(A_{sin}B_{des}+A_{des}B_{sin})10^{\frac {n}{2}}+A_{des}B_{des}$

Poiché:
$(A_{sin}+A_{des})(B_{sin}+B_{des})=A_{sin}B_{sin}+A_{sin}B_{des}+A_{des}B_{sin}+A_{des}B_{des}$

Abbiamo:

$AB=A_{sin}B_{sin}10^{n}+((A_{sin}+A_{des})(B_{sin}+B_{des})-A_{sin}B_{sin}-A_{des}B_{des})10^{\frac {n}{2}}+A_{des}B_{des}$

Quindi abbiamo ridotto la moltiplicazione fra A e B a tre moltiplicazioni fra numeri di n/2 cifre più alcune addizioni, sottrazioni e traslazioni (per moltiplicare per $10^{\frac {n}{2}}$ e $10^{n}$). La relazione di ricorrenza per il tempo di esecuzione dell'algoritmo è la seguente:

                                             $T(1)=d$
                                             $T(n)=3T\left({\frac {n}{2}}\right)+cn$

che implica che $T(n)$ ha complessità $O(n^{\log _{2}3})$, cioè circa $O(n^{1.59})$, che è un risultato migliore di $O(n^{2})$. Esistono anche algoritmi ancora più efficienti per la moltiplicazione.

Voci correlate

• Algoritmo di Karatsuba
• Algoritmi di elevamento a potenza