I bambini imparano le tabelline a scuola. Memorizzateli. Buona fortuna con i numeri a tre cifre. È qui che entrano in gioco gli algoritmi. Impili le cifre. Moltiplica riga per riga. Per migliaia di anni abbiamo pensato che fosse la cosa migliore che potessimo fare. È lento. Brutalmente lento per i big data. Poi nel 1960 un ragazzo di 23 anni cambiò tutto. Il mistero della velocità di moltiplicazione rimane aperto.
Perché è importante
Le moltiplicazioni non sono solo compiti a casa. Gestisce Internet. Crittografia, intelligenza artificiale, elaborazione audio. Tutto si basa sulla moltiplicazione. Moltiplicazione pesante. Quando moltiplichi numeri enormi milioni di volte al secondo, ogni passo conta. Un leggero aumento di efficienza fa risparmiare miliardi.
Guarda il metodo della scuola elementare. Due cifre significano quattro moltiplicazioni a una cifra. Tre cifre? Nove. Si ridimensiona quadraticamente. Raddoppia la lunghezza, quadruplica il lavoro. Raddoppialo ancora, il lavoro aumenta di sedici volte. Gli informatici ignorano i secondi. L’hardware accelera comunque. Contano i passi. La chiamiamo notazione Big O. La scuola elementare è O(n^2). Quadratico. Se il tuo numero cresce di 1.000, l’opera esplode di un milione.
Il carico di lavoro scala con il quadrato del numero di cifre.
Fin dall’antichità, i maghi della matematica presumevano che questo limite quadratico fosse una legge della natura. Andrey Kolmogorov, una leggenda sovietica, ci scommise la reputazione in una conferenza del 1960. Ha detto agli studenti dell’Università statale di Mosca: “Ci vuole O(n^2).” È una congettura formale. Una sfida. Aspetta che qualcuno lo dimostri o lo rompa.
Ci è voluta una settimana. Anatoly Karatsuba era seduto tra il pubblico. Aveva 23 anni. Tornò con la prova che Kolmogorov si sbagliava. Il professore rimase sbalordito. Kolmogorov in realtà scrisse lui stesso l’articolo per una rivista prestigiosa, ma vi mise sopra il nome di Karatsuba. Il ragazzo non lo sapeva finché non arrivarono le ristampe per posta.
Il trucco
Karatsuba ha realizzato qualcosa di semplice ma profondo. Le moltiplicazioni sono costose. Le aggiunte sono economiche. Perché non scambiarli?
Prendi 12×34.
Dividilo.
12 è 10 + 2.
34 è 30 + 4.
Tradizionalmente si eseguono quattro moltiplicazioni:
1×3
1×4
2×3
2×4
Karatsuba ha trovato il modo di farlo con tre.
Calcola la prima parte: 1×3 = 3.
Calcola l’ultima parte: 2×4 = 8.
Adesso il centro. Normalmente faresti (1×4) + (2×3). Due moltiplicazioni. Aggiungi invece i primi numeri: 1+2=3. Aggiungi gli ultimi numeri: 3+4=7. Moltiplica quelle somme: 3×7=21. Sottrai le parti che già conosci. 21 – 3 – 8 = 10.
Bum. Hai ottenuto il termine medio con una moltiplicazione in più.
Ne vale la pena?
Non per piccoli numeri. Il sovraccarico di suddivisione e aggiunta ti costa.
Ma per 1.234 x 5.678? Dividilo a metà. Ricorsione. Dividi quelle metà. Fallo di nuovo. Il composto di risparmio.
L’algoritmo scende a circa O(n^1.585).
I numeri di mille cifre richiedevano un milione di multipli a una cifra. Adesso ci vogliono meno di 57,00 passi. Enorme.
Questa non è solo teoria. È in Python.
Python utilizza la matematica scolastica standard per piccoli input. Abbastanza liscio.
Una volta raggiunte circa 63 cifre decimali (a seconda della base della macchina), Python attiva un interruttore. Karatsuba prende il sopravvento. Non vedi che ciò accada. Ma è lì. Gestire la tua crittografia.
Algoritmi galattici
La corsa continuò per decenni. Possiamo andare più veloci?
Il 2019 ha portato l’ultimo shock. David Harvey e Joris van Der Hoeven hanno pubblicato un algoritmo che batte di gran lunga Karatsuba.
O(n log n).
Leggilo di nuovo.
I logaritmi crescono incredibilmente lentamente.
n log n è appena più grande di n.
Fondamentalmente, moltiplicare due numeri enormi ora richiede più o meno lo stesso tempo di leggerli.
È sconcertante. Il tetto teorico sembra essere stato toccato.
O forse no.
Ecco il problema.
Non funziona per i numeri a cui teniamo.
L’algoritmo di Harvey e Van Der Hoeven diventa più veloce di Karatsuba solo quando i numeri diventano davvero grandi. Non “numero di carta di credito” grande. Grande galattico.
In informatica abbiamo un termine per questo: algoritmo galattico.
Bella teoria. Utilizzo pratico nullo. I numeri richiesti sono più grandi della maggior parte delle transazioni digitali nella storia umana messe insieme.
Siamo bloccati nel mezzo.
Utilizzando i trucchi degli anni ’60 per la maggior parte dei nostri computer quotidiani.
Indossare abiti del 21° secolo oltre alla matematica del 20° secolo.
Utilizziamo mai effettivamente O(n log n) nel mondo reale?
Forse quando elaboriamo i dati imposta la dimensione delle galassie.
Fino ad allora aspettiamo.
Per il prossimo trucco.
O meglio hardware per nascondere la nostra pigrizia.
La risposta potrebbe ancora essere quadratica.
Potrebbe essere lineare.
Non lo sappiamo ancora.
