Domanda Algoritmo per moltiplicazione intera.

[mattstack]

Buonasera, avrei una piccola domanda da porvi. Stavo guardando un po di algoritmi per effettuare i prodotti tra valori interi in maniera efficiente, scoprendo come le moltiplicazioni vengano effettivamente svolte dal processore; domanda che mi sono sempre posto ma alla quale non ho mai dato risposta. Quando mi è venuto in mente un algoritmo con complessità proporzionale al numero di bit necessari per rappresentare gli operandi della moltiplicazione (per intenderci con N bit per operando saranno necessarie N operazioni, tutte con complessità O(1)). Si basa sul semplice concetto di andare a riscrivere uno degli operandi sotto forma di somme di potenze di due, così da andare a semplificare la moltiplicazione in una serie di somme di prodotti con potenze di due, e quindi semplici ed efficienti shift aritmetici verso sinistra.
Cioè:

 a * b = a * (2^k0 + 2^k1 + 2^k3 ... + 2^kn )

Questa definizione dovrebbe essere corretta visto che ogni numero positivo, che sia pari o dispari, può essere riscritto sotto forma di somme di potenze di due.
Proprio perché b deve essere positivo, viene prima effettuato il complemento a due se negativo e impostato un flag che sarà controllato alla fine dell'algoritmo per complementare il risultato.
Per calcolare le potenze di due in cui è scomponibile il numero l'algoritmo analizza semplicemente la rappresentazione binaria di quest' ultimo, proprio per questo il numero di operazioni richieste equivale al numero di bit cui si compongono gli operandi.
Per esempio:

345 * 856 = (345 * 2^3) + (345 * 2^4) + (345 * 2^6) + (345 * 2^8) + (345 * 2^9).
Infatti 856 in binario equivale a: 1  1  0  1  0  1  1  0  0  0 -- bit.
                                   9  8  7  6  5  4  3  2  1  0 -- n. cifra.

Mi chiedo quindi se questo algoritmo esiste, e se esiste qual'è il suo nome grazie.
Inoltre vorrei sapere quanto potrebbe essere efficiente una sua implementazione a livello hardware. Teoricamente sono necessari un numero di cicli di clock pari al numero di bit richiesti per rappresentare l'operando scomposto (vengono analizzati i bit a zero anche se ignorati) e dovrebbe essere quindi poco efficiente già con valori a 32bit, o sbaglio?
Grazie.
(avrei dovuto utilizzare il tag MATH per scrivere qualche formula matematica più decorosa, ma non so come si faccia, scusate).

 

[St3ve]

È un argomento interessante e ancora più interessante è secondo me la storia che c'è dietro al primo miglioramento dell'algoritmo che facciamo con carta e penna: fino agli anni '60 si pensava che l'algoritmo più efficiente fosse il classico algoritmo quadratico che si spiega alle elementari e si credeva non si potesse fare di meglio. Uno dei motivi per cui si pensava che quello fosse il metodo più efficiente era dovuto al fatto che la moltiplicazione la conosciamo fin dai tempi antichi e nessuno aveva mai descritto metodi profondamente diversi. Negli anni '60 un algoritmo più efficiente è stato trovato da uno studente, una settimana dopo aver ascoltato il seminario di un suo professore che congetturava lower bound per la moltiplicazione fosse effettivamente $$\(\Omega(n^2)$$\), ovvero pensava che l'algoritmo che facciamo con carta e penna fosse ottimo. Quindi è da migliaia di anni che tutti facevano la moltiplicazione allo stesso modo e negli anni '60 sono bastati pochi giorni di uno studente per trovare un algoritmo migliore.

Mi chiedo quindi se questo algoritmo esiste, e se esiste qual'è il suo nome grazie.

È l'algoritmo naive che conosciamo tutti, probabilmente ti è sembrato diverso per via del cambiamento di base. In base 10 si scrive
$$\[345 \times 856 = (356 \times 8 \cdot 10^2) + (356 \times 5 \cdot 10^1) + (356 \times 6 \cdot 10^0)$$\]in base 5, giusto per fare un altro esempio, abbiamo $$\(856 = 11411_5$$\) e la moltiplicazione diventa
$$\[345 \times 856 = (356 \times 1 \cdot 5^4) + (356 \times 1 \cdot 5^3) + (356 \times 4 \cdot 5^2) + (356 \times 1 \cdot 5^1) + (356 \times 1 \cdot 5^0)$$\]e in base 2 abbiamo $$\(856 = 1101011000_2$$\) e la moltiplicazione diventa
$$\[\begin{align*}345 \times 856 &= (356 \times 1 \cdot 2^9) + (356 \times 1 \cdot 2^8) + (356 \times 0 \cdot 2^7) + (356 \times 1 \cdot 2^6) + (356 \times 0 \cdot 2^5) + (356 \times 1 \cdot 2^4) + (356 \times 1 \cdot 2^3) + (356 \times 0 \cdot 2^2) + (356 \times 0 \cdot 2^1) + (356 \times 0 \cdot 2^0) \\&= (356 \times 2^9) + (356 \times 2^8) + (356 \times 2^6) + (356 \times 2^4) + (356 \times 2^3)\end{align*}$$\]che, come hai notato, è conveniente per un computer perché i numeri sono già espressi in binario e ognuna di queste moltiplicazioni si può implementare con un shift a sinistra.

 

[mattstack]

Effettivamente mi sono accorto dopo che questa cosa vale per ogni base. Sapresti inoltre dirmi quale algoritmo viene oggigiorno utilizzato dalla maggioranza dei processori, e quali sono gli svantaggi dell'uso di questo algoritmo naive. Non è comunque un buon compromesso in termini di costi implemetativi e efficenza?

 

[St3ve]

Premetto di essere largamente disinformato a riguardo, quindi sei benvenuto a mettere in discussione tutto quello che dico almeno nella migliore delle ipotesi riusciamo ad imparare qualcosa entrambi. Inizio a farti discorso forse ovvio, ma che non so se stai trascurando o dando per scontato. In hardware quello che conta principalmente è la dimensione del circuito logico (i.e., il numero di transistors) che vai ad implementare e la sua profondità. Visto che la quantità di transistor che si riescono a ficcare dentro una CPU è continuata ad aumentare esponenzialmente (legge di Moore) fino a pochi anni fa, la dimensione del circuito è sempre passata in secondo piano... a maggior ragione per operazioni super-importanti come la moltiplicazione. L'algoritmo che hai descritto si riesce ad implementare con poco hardware, però rimane fondamentalmente lento e poco parallelizzabile. A leggere wikipedia (scorrendo vari links, partendo da qui) mi pare di aver capito che le implementazioni hardware più efficienti si basano wallace tree e sui dadda tree, che però hanno un layout irregolare e leggermente asimmetrica che da un po' fastidio nel momento in cui la vuoi implementare in larga scala su un circuito integrato di dimensioni considerevoli. Le implementazioni più comuni post anni '70 credo derivino dai binary tree multipliers, che sono "peggiori" ma estremamente regolari e quindi facili da collegare in un circuito integrato, dai wallace multipliers e dai dadda multiplier. In particolare credo che i dadda multiplier (in qualche sua variante partizionata/ibridificata) siano tuttora il uso. Roba tipo il booth recoding e carry-lookahead adder, che trovi già menzionata nel paragrafetto che ti ho linkato, credo sia onnipresente indipendentemente dall'implementazione. Cosa facciano effettivamente Intel, AMD e gli altri big non credo si possa sapere.

Per roba software (e.g., moltiplicazione di big numbers) si usano principalmente varianti di Karatsuba, che sarebbe lo studente di cui ho scritto prima. In software non si riescono ad implementare gli stessi tricks che si fanno in hardware, perché il design degli algoritmi cambia profondamente: in software si ambisce a minimizzare il lavoro complessivo, mentre in hardware si ambisce a parallelizzarlo costruendo circuiti larghi ma poco profondi.

Questo articolo potrebbe interessarti. In particolare dicono che l'8086 del 1978 usava ancora l'algoritmo naive, menzionano che il Pentium 4 del 2000 usava i wallace tree (la fonte è un paper della Intel) e dicono che successivamente si sono iniziati a preferire i dadda tree. Immagino che gli anni '70 siano stati un po' un periodo di transizione. I lavori di Wallace e Dadda risalgono al 1964-1965.

 

[mattstack]

Ho scoperto che l'algoritmo naive si chiama algoritmo della moltiplicazione russa. Ho trovato questo sul sito della MAA(mathematical association of america): link.
Per il resto grazie per l'articolo.