Una coppia di matematici, un australiano e un francese, ha scoperto un nuovo modo per moltiplicare numeri, risolvendo un problema algoritmico che ha lasciato perplessa la comunità matematica per quasi mezzo secolo.
Se moltiplicare numeri relativamente piccoli è piuttosto semplice, basta ricordarsi le tabelline, che cosa fare quando i numeri sono molto grandi? Mettendo da parte calcolatrici e computer, molti di noi inizierebbero a fare una lunga moltiplicazione, come ci è stato insegnato a scuola. C’è un solo problema: è un metodo lento.
Il motivo è che per ogni singola cifra in ogni numero, dovete svolgere una moltiplicazione separata prima di arrivare a sommare il tutto. Un problema relativo per chi si trova a svolgere lunghe moltiplicazioni di rado, ma tutt'altro problema per i computer, i cui limiti nello svolgimento di calcoli sono legati ai limiti degli assunti matematici di cui abbiamo comprensione.
Essenzialmente una moltiplicazione lunga è un algoritmo, ma non è tra più efficienti, dato che il processo dev’essere inevitabilmente accurato. I matematici hanno un modo per calcolare quanto è accurata la moltiplicazione lunga.
Il matematico David Harvey della UNSW in Australia spiega nel video che vedete in questa notizia, come in una moltiplicazione dove entrambi i numeri hanno tre cifre (n = 3), il numero di moltiplicazioni separate coinvolte sia 9, ovvero n2 (n alla seconda).
Il problema è che con la grandezza del numero, cresce anche la quantità di lavoro richiesto, sempre rappresentato da n alla seconda. Anche se inefficiente, l’algoritmo di moltiplicazione lunga era la soluzione più avanzata disponibile fino agli anni ‘60, quando il matematico russo Anatoly Karatsuba riuscì ad abbassare la complessità del problema a n alla 1,58.
Un decennio dopo una coppia di matematici tedeschi fece un’altra scoperta, dando vita all’algoritmo Schönhage–Strassen, il quale ipotizzava - ma non dimostrò mai - che fossero possibili ulteriori perfezionamenti.
“Predissero che sarebbe dovuto esistere un algoritmo che moltiplica numeri a n cifre usando essenzialmente operazioni di base n*log(n)”, ha spiegato Harvey. “Il nostro documento è un primo esempio noto di un algoritmo in grado di farlo”.
Secondo i ricercatori, moltiplicare due numeri con un miliardo di cifre ciascuno tramite il processo di moltiplicazione lunga richiederebbe a un computer mesi di calcoli. Usando l’algoritmo Schönhage-Strassen, servirebbero meno di 30 secondi, e con la nuova dimostrazione teorica si potrebbe essere ancora più veloci – teoricamente - tanto da costituire l'algoritmo di moltiplicazione più veloce matematicamente possibile.
"In questo senso, ci aspettiamo che il nostro lavoro sia la fine di questo problema, anche se non sappiamo ancora come dimostrarlo rigorosamente", ha affermato Harvey. "Le persone hanno cercato un algoritmo di questo genere per quasi 50 anni". Il nuovo algoritmo è utile solo per moltiplicare numeri molto grandi, ma quanto grandi esattamente?
"Non ne abbiamo idea", spiegano i ricercatori in una FAQ, anche se un esempio fornito nel documento equivale a 10 alla 214857091104455251940635045059417341952, che è un numero molto, molto, molto grande.
La comunità matematica sta ancora recependo le nuove scoperte, che devono ancora essere sottoposte a peer-review (revisione), anche se stanno già facendo discutere.
"Se il risultato è corretto, è decisamente importante nella teoria della complessità computazionale”, ha dichiarato a New Scientist Fredrik Johansson, matematico e informatico dell'INRIA Bordeaux e dell'Institut de Mathématiques de Bordeaux. "Le nuove idee presenti in questo lavoro dovrebbero ispirare ulteriori ricerche e potrebbero portare a miglioramenti reali”.
Harvey e il co-ricercatore Joris van der Hoeven dell’École Polytechnique in Francia affermano che il loro algoritmo deve essere ottimizzato, e sperano di non aver sbagliato qualcosa nella loro dimostrazione. "Gran parte del lavoro è stata convincere noi stessi che sia effettivamente corretto", ha detto Harvey ad AAP. "Sono terrorizzato dal fatto che potrebbe rivelarsi sbagliato".
I risultati sono disponibili nell’archivio aperto HAL.