Ultima modifica:
È 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.
$$\[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.
È l'algoritmo naive che conosciamo tutti, probabilmente ti è sembrato diverso per via del cambiamento di base. In base 10 si scriveMi chiedo quindi se questo algoritmo esiste, e se esiste qual'è il suo nome grazie.
$$\[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.