- Moltiplicare grandi numeri è difficile. Nel 1971, due professori tedeschi predissero un algoritmo che lo avrebbe reso più facile, ma nessuno lo ha mai dimostrato.
- Fino ad ora.
- I matematici australiani e francesi dicono che il loro algoritmo può rendere la moltiplicazione e altri tipi di aritmetica molto più efficiente.
Dalla scuola elementare in poi, la moltiplicazione complessa è stata un mal di testa. Ma un assistente professore della University of New South Wales Sydney in Australia ha sviluppato un nuovo metodo per moltiplicare insieme numeri giganti che è più efficiente della “moltiplicazione lunga” che viene insegnata a molti in tenera età.
“Più tecnicamente, abbiamo dimostrato una congettura del 1971 di Schönhage e Strassen sulla complessità della moltiplicazione dei numeri interi”, dice il professore associato David Harvey nel video qui sotto.
L’algoritmo di Schönhage-Strassen, sviluppato da due matematici tedeschi, è stato effettivamente il metodo più veloce di moltiplicazione dal 1971 al 2007. Anche se un metodo più veloce è stato sviluppato nel 2007, è raramente usato oggi.
Schönhage e Strassen hanno previsto che un algoritmo che moltiplica numeri di n cifre usando n * log(n) operazioni di base dovrebbe esistere, dice Harvey. Il suo articolo è la prima prova conosciuta che esiste.
Harvey sceglie l’esempio di 314 moltiplicato per 159 – una grande equazione, certo, ma equazioni molto più grandi sono usate ogni giorno in scenari di vita reale. Per risolvere il problema, alla maggior parte delle persone viene insegnato a moltiplicare ogni singolo numero insieme, e poi sommare le somme:
9 viene moltiplicato per 4, 1 e 3; poi 5 viene moltiplicato per 4, 1 e 3, e così via. Il risultato finisce con 9 prodotti per cifra.
Questo metodo è chiamato n2 o n al quadrato, perché bisogna moltiplicare n per n un certo numero di volte. Otterrà la risposta corretta, ma Schönhage e Strassen hanno progettato un metodo più veloce. Era in grado di andare oltre n2 in qualcosa di più piccolo, ma una sfida si presentava ancora sotto forma di n * log(n).
Per alcuni, vedere una parola nel mezzo di un problema matematico potrebbe essere sufficiente per far loro brillare gli occhi come durante le lezioni di algebra. Come aggiornamento: log è l’abbreviazione di logaritmo, che aiuta le persone a decifrare gli esponenti che rendono i numeri al quadrato o al cubo o anche qualcosa di più alto. Così 2⁵ è 32, ma espresso logaritmicamente, sarebbe come log₂(32)=5. Anche se può sembrare uno scioglilingua, i logaritmi sono cruciali quando i numeri diventano molto più grandi.
Il metodo Schönhage-Strassen è molto veloce, dice Harvey. Se un computer dovesse usare il metodo dei quadrati insegnato a scuola su un problema in cui due numeri hanno un miliardo di cifre ciascuno, ci vorrebbero mesi. Un computer che usa il metodo Schönhage-Strassen potrebbe farlo in 30 secondi.
Ma se i numeri continuano a salire verso i trilioni e oltre, l’algoritmo sviluppato da Harvey e dal collaboratore Joris van der Hoeven all’École Polytechnique in Francia potrebbe trovare soluzioni più velocemente dell’algoritmo di Schönhage-Strassen del 1971.
“Significa che puoi fare tutti i tipi di aritmetica in modo più efficiente, per esempio divisione e radici quadrate”, dice. “Si possono anche calcolare le cifre di pi greco in modo più efficiente di prima. Ha anche applicazioni a problemi che coinvolgono enormi numeri primi.
“Le persone sono state a caccia di un tale algoritmo per quasi 50 anni”, continua. Non era una conclusione scontata che qualcuno alla fine avrebbe avuto successo. Si sarebbe potuto scoprire che Schönhage e Strassen avevano torto, e che nessun algoritmo del genere è possibile.
“Ma ora sappiamo meglio”, dice.