Algoritmi di moltiplicazione

Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

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.

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

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;  
 }

È 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;
 }

È 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;
 }

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.

L'algoritmo classico di moltiplicazione ha complessità ${\displaystyle 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 ${\displaystyle A}$ e ${\displaystyle B}$ scritti con una notazione posizionale moltiplicativa con l'ausilio di ${\displaystyle n}$ cifre e ${\displaystyle 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 ${\displaystyle A_{sin}}$ e ${\displaystyle A_{des}}$ rispettivamente le prime e ultime n/2 cifre di A e con e ${\displaystyle B_{sin}}$ e ${\displaystyle B_{des}}$ le prime e ultime n/2 cifre di B, cioè:

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

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

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

Poiché:
${\displaystyle (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:

${\displaystyle 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 ${\displaystyle 10^{\frac {n}{2}}}$ e ${\displaystyle 10^{n}}$). La relazione di ricorrenza per il tempo di esecuzione dell'algoritmo è la seguente:

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

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

• Algoritmo di Karatsuba
• Algoritmi di elevamento a potenza

Portale Informatica: accedi alle voci di Teknopedia che trattano di Informatica