Crediti: Chuk Yong/Pixabay
Una coppia di matematici provenienti da Australia e Francia ha individuato un nuovo modo per svolgere le moltiplicazioni, risolvendo al contempo un problema algoritmico che ha lasciato perplesse le più grandi menti matematiche per più di mezzo secolo.
La maggior parte delle persone, per moltiplicare tra loro numeri relativamente piccoli, fa quasi sempre affidamento alle tavole pitagoriche (comunemente chiamate tabelline), uno strumento tanto utile quanto antico: fu introdotto per la prima volta dai Babilonesi, più di 4000 anni fa.
Cosa fare, invece, quanto i numeri iniziano a diventare grandi? Supponendo di non avere a disposizione calcolatrice scientifica o computer, la via più ovvia sarebbe svolgere una tradizionale (seppur lunga) moltiplicazione. L’unico inconveniente di questo metodo è che richiede una quantità di tempo direttamente proporzionale alla grandezza e alla quantità dei numeri coinvolti. Ogni singola cifra di un fattore deve essere moltiplicata per ogni cifra degli altri fattori, per poi sommare i prodotti ottenuti.
Il tempo, per la stragrande maggioranza della gente, potrebbe essere un parametro trascurabile, ma non lo è più se pensiamo alle moltiplicazioni che devono essere svolte dai computer: i cosiddetti colli di bottiglia che si possono incontrare durante l’esecuzione dei calcoli dipendono proprio dai limiti della matematica astratta che conosciamo.
La moltiplicazione (breve o lunga che sia) è un algoritmo, ma non è tra i più efficienti, in quanto richiede un livello di accuratezza molto alto. Esiste un modo per calcolare la complessità di un prodotto tra due numeri e lo spiega il prof. David Harvey (University of New South Wales, Australia).
Come si evince dal video, una moltiplicazione tra due numeri entrambi formati da 3 cifre (n) richiede un numero di moltiplicazioni separate pari a 9 (in generale, n2). Alla luce di questo è chiaro che, all’aumentare dei numeri, il lavoro di calcolo richiesto cresce esponenzialmente.
Nonostante sia inefficiente, l’algoritmo appena descritto era il più avanzato a disposizione fino agli anni ’60, quando Anatoly Karatsuba, matematico russo, riuscì a raggiungere un valore di complessità pari a n1.58. Quasi dieci anni dopo, una coppia di matematici tedeschi teorizzò l’algoritmo Schönhage–Strassen, col quale si ipotizzava (ma questo non fu mai provato) la possibilità che si potessero raggiungere ulteriori perfezionamenti.
Come charito da Harvey:
È stato predetto che dovrebbe esistere un algoritmo che moltiplica i numeri con n cifre usando essenzialmente n*log(n) operazioni di base.
La nostra ricerca fornisce il primo esempio noto di un algoritmo che raggiunge quest’obiettivo.
Sempre secondo i ricercatori, moltiplicare due numeri da un miliardo di cifre richiederebbe ad un computer mesi di lavoro. Utilizzando l’algoritmo di Schönhage–Strassen, sarebbero necessari meno di trenta secondi mentre con la loro dimostrazione il tempo impiegato sarebbe ancora inferiore: teoricamente, potrebbe essere il più veloce algoritmo di moltiplicazione matematicamente possibile.
È necessario puntualizzare che questo nuovo metodo è utile solo se si parla di moltiplicazioni tra numeri grandi. Ma grandi quanto? I ricercatori non hanno ancora una risposta certa, anche se un esempio fornito nella ricerca equivale a 10214857091104455251940635045059417341952.
La comunità matematica è al lavoro per assorbire le nuove scoperte, che comunque dovranno essere sottoposte a peer-review. Il teorico informatico Martin Fürer della Penn State University ha dichiarato a Science News “di essere rimasto molto sorpreso dalla scoperta“. Lo stesso Fürer, una decina d’anni fa, tentò di migliorare l’algoritmo Schönhage–Strassen, abbandonando poi il lavoro perché “sembrava non ci fossero speranze“.
La speranza, invece, è riapparsa, se il lavoro sarà verificato.
Anche il matematico e informatico Fredrik Johansson (INRIA Bordeaux and Institut de Mathématiques de Bordeaux) ha detto la sua:
Se il risultato raggiunto sarà confermato, rappresenterà un importante traguardo nella teoria della complessità computazionale.
Le idee presenti in questa ricerca potrebbero dare il via ad ulteriori approfondimenti e migliorie.
Nel frattempo, Harvey, a nome suo e del suo collega Joris van der Hoeven (École Polytechnique in France), ha spiegato:
Gran parte del lavoro ci convince che sia tutto corretto, ma siamo terrorizzati dal fatto che qualcosa possa rivelarsi sbagliata.
Per approfondire: Archivio aperto HAL
