Algoritmi di moltiplicazione

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

È 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[modifica | modifica sorgente]

È 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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.

Siano dati due numeri naturali A e B con n cifre e supponiamo per semplicità che n sia una potenza di 2.

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[modifica | modifica sorgente]

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