{"id":7910,"date":"2026-07-15T02:28:58","date_gmt":"2026-07-14T23:28:58","guid":{"rendered":"https:\/\/www.schooler.org.ua\/uk-uamatematiki-dosi-ne-znajut-najshvidshogo-sposobu-mnozhennja\/"},"modified":"2026-07-15T02:28:58","modified_gmt":"2026-07-14T23:28:58","slug":"uk-uamatematiki-dosi-ne-znajut-najshvidshogo-sposobu-mnozhennja","status":"publish","type":"post","link":"https:\/\/www.schooler.org.ua\/it\/uk-uamatematiki-dosi-ne-znajut-najshvidshogo-sposobu-mnozhennja\/","title":{"rendered":"Il mistero della matematica che nessuno ha risolto (ancora)"},"content":{"rendered":"

I bambini imparano le tabelline a scuola. Memorizzateli. Buona fortuna con i numeri a tre cifre. \u00c8 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. \u00c8 lento. Brutalmente lento per i big data. Poi nel 1960 un ragazzo di 23 anni cambi\u00f2 tutto. Il mistero della velocit\u00e0 di moltiplicazione rimane aperto. <\/p>\n

Perch\u00e9 \u00e8 importante<\/h3>\n

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. <\/p>\n

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 \u00e8 O(n^2). Quadratico. Se il tuo numero cresce di 1.000, l\u2019opera esplode di un milione. <\/p>\n

\n

Il carico di lavoro scala con il quadrato del numero di cifre. <\/p>\n<\/blockquote>\n

Fin dall’antichit\u00e0, 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\u2019Universit\u00e0 statale di Mosca: \u201cCi vuole O(n^2).\u201d \u00c8 una congettura formale. Una sfida. Aspetta che qualcuno lo dimostri o lo rompa. <\/p>\n

Ci \u00e8 voluta una settimana. Anatoly Karatsuba era seduto tra il pubblico. Aveva 23 anni. Torn\u00f2 con la prova che Kolmogorov si sbagliava. Il professore rimase sbalordito. Kolmogorov in realt\u00e0 scrisse lui stesso l\u2019articolo per una rivista prestigiosa, ma vi mise sopra il nome di Karatsuba. Il ragazzo non lo sapeva finch\u00e9 non arrivarono le ristampe per posta. <\/p>\n

Il trucco<\/h3>\n

Karatsuba ha realizzato qualcosa di semplice ma profondo. Le moltiplicazioni sono costose. Le aggiunte sono economiche. Perch\u00e9 non scambiarli? <\/p>\n

Prendi 12×34.
\nDividilo.
\n12 \u00e8 10 + 2.
\n34 \u00e8 30 + 4. <\/p>\n

Tradizionalmente si eseguono quattro moltiplicazioni:
\n1×3
\n1×4
\n2×3
\n2×4 <\/p>\n

Karatsuba ha trovato il modo di farlo con tre.
\nCalcola la prima parte: 1×3 = 3.
\nCalcola l’ultima parte: 2×4 = 8. <\/p>\n

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\u00e0 conosci. 21 – 3 – 8 = 10.
\nBum. Hai ottenuto il termine medio con una moltiplicazione in pi\u00f9. <\/p>\n

Ne vale la pena?
\nNon per piccoli numeri. Il sovraccarico di suddivisione e aggiunta ti costa.
\nMa per 1.234 x 5.678? Dividilo a met\u00e0. Ricorsione. Dividi quelle met\u00e0. Fallo di nuovo. Il composto di risparmio.
\nL’algoritmo scende a circa O(n^1.585).
\nI numeri di mille cifre richiedevano un milione di multipli a una cifra. Adesso ci vogliono meno di 57,00 passi. Enorme. <\/p>\n

Questa non \u00e8 solo teoria. \u00c8 in Python.
\nPython utilizza la matematica scolastica standard per piccoli input. Abbastanza liscio.
\nUna volta raggiunte circa 63 cifre decimali (a seconda della base della macchina), Python attiva un interruttore. Karatsuba prende il sopravvento. Non vedi che ci\u00f2 accada. Ma \u00e8 l\u00ec. Gestire la tua crittografia. <\/p>\n

Algoritmi galattici<\/h3>\n

La corsa continu\u00f2 per decenni. Possiamo andare pi\u00f9 veloci?
\nIl 2019 ha portato l\u2019ultimo shock. David Harvey e Joris van Der Hoeven hanno pubblicato un algoritmo che batte di gran lunga Karatsuba.
\nO(n log n). <\/p>\n

Leggilo di nuovo.
\nI logaritmi crescono incredibilmente lentamente.
\nn log n \u00e8 appena pi\u00f9 grande di n.
\nFondamentalmente, moltiplicare due numeri enormi ora richiede pi\u00f9 o meno lo stesso tempo di leggerli. <\/p>\n

\u00c8 sconcertante. Il tetto teorico sembra essere stato toccato.
\nO forse no.
\nEcco il problema.
\nNon funziona per i numeri a cui teniamo. <\/p>\n

L\u2019algoritmo di Harvey e Van Der Hoeven diventa pi\u00f9 veloce di Karatsuba solo quando i numeri diventano davvero<\/em> grandi. Non “numero di carta di credito” grande. Grande galattico.
\nIn informatica abbiamo un termine per questo: algoritmo galattico.
\nBella teoria. Utilizzo pratico nullo. I numeri richiesti sono pi\u00f9 grandi della maggior parte delle transazioni digitali nella storia umana messe insieme. <\/p>\n

Siamo bloccati nel mezzo.
\nUtilizzando i trucchi degli anni ’60 per la maggior parte dei nostri computer quotidiani.
\nIndossare abiti del 21\u00b0 secolo oltre alla matematica del 20\u00b0 secolo. <\/p>\n

Utilizziamo mai effettivamente O(n log n) nel mondo reale?
\nForse quando elaboriamo i dati imposta la dimensione delle galassie.
\nFino ad allora aspettiamo.
\nPer il prossimo trucco.
\nO meglio hardware per nascondere la nostra pigrizia. <\/p>\n

La risposta potrebbe ancora essere quadratica.
\nPotrebbe essere lineare.
\nNon lo sappiamo ancora.<\/p>\n","protected":false},"excerpt":{"rendered":"

I bambini imparano le tabelline a scuola. Memorizzateli. Buona fortuna con i numeri a tre cifre. \u00c8 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. \u00c8 lento. Brutalmente lento per i big data. Poi nel […]<\/p>\n","protected":false},"author":1,"featured_media":7909,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"tdm_status":"","tdm_grid_status":""},"categories":[1],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.schooler.org.ua\/it\/wp-json\/wp\/v2\/posts\/7910"}],"collection":[{"href":"https:\/\/www.schooler.org.ua\/it\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.schooler.org.ua\/it\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/it\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/it\/wp-json\/wp\/v2\/comments?post=7910"}],"version-history":[{"count":0,"href":"https:\/\/www.schooler.org.ua\/it\/wp-json\/wp\/v2\/posts\/7910\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/it\/wp-json\/wp\/v2\/media\/7909"}],"wp:attachment":[{"href":"https:\/\/www.schooler.org.ua\/it\/wp-json\/wp\/v2\/media?parent=7910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/it\/wp-json\/wp\/v2\/categories?post=7910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/it\/wp-json\/wp\/v2\/tags?post=7910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}