Pin It

Recentemente è apparso un articolo che contiene un risultato di grande rilievo sulla complessità computazionale di un problema classico: la moltiplicazione di due numeri interi di n cifre. Ce ne parla Fabio Di Benedetto dell’Università di Genova.

Nel mondo tecnologico di oggi, molte nostre attività sono possibili grazie ad un trattamento efficiente dei dati di grandi dimensioni; qualunque mezzo di calcolo (anche il nostro smartphone, quando ad esempio fa una ricerca in rete) deve fare i conti con la risorsa tempo per assicurare una risposta veloce anche quando deve processare miliardi di informazioni.

La complessità computazionale

La branca della matematica che si occupa di questo aspetto ha l’obiettivo di quantificare, data la dimensione \(n\) dei dati di un problema, il numero di passi \(C(n)\) richiesti per ottenere la soluzione. Problemi in cui \(C(n)\approx2^n\) sono chiaramente intrattabili per grandi dimensioni, mentre se la funzione \(C(n)\) è un polinomio di grado basso nella variabile \(n\) o ha altri andamenti (si veda ad esempio la Figura 1 qui sotto) diventa possibile avere risposte in tempo reale.

Figura 1. Crescita di alcune funzioni all’aumentare della dimensione \(n\).

Le tecniche generali adottate per studiare la complessità computazionale sono le seguenti:

  • Maggiorazione (Upper bound). L’idea più semplice e diretta: possiamo ad esempio affermare che \(C(n)\leq n^2\) nel momento che troviamo un algoritmo che risolve il problema in \(n^2\) operazioni. Ma il dubbio è: si può fare meglio??
  • Minorazione (Lower bound). Per rispondere alla domanda precedente, una tecnica molto sofisticata (e basata sull’algebra avanzata) consiste nel dimostrare che il numero minimo di operazioni necessarie è una certa funzione \(L(n)\). Purtroppo, trovare una simile limitazione è spesso molto difficile.
  • Equivalenza dei problemi. Per ovviare alle difficoltà, a volte è utile dimostrare che due problemi diversi \(P_1\) e \(P_2\) hanno la stessa complessità computazionale. Questo si ottiene facendo vedere che, se avessimo un algoritmo che risolve \(P_1\) in tempo \(C(n)\), allora con un tempo paragonabile saremmo in grado di risolvere anche \(P_2\), e viceversa.

La moltiplicazione tra numeri interi

Proprio di recente è stato pubblicato dai matematici Harvey e Van Den Hoeven un risultato di grande rilievo sulla complessità computazionale di un problema classico: la moltiplicazione di due numeri interi di \(n\) cifre [1 ]D. Harvey, J. Van Der Hoeven, Integer multiplication in time \(O(n \log n)\). HAL preprint (ffhal-02070778), 2019.. L’articolo dimostra una maggiorazione (quindi esibisce un algoritmo effettivo) che, per \(n\) molto grande, ha l’andamento \(n\cdot\log n\). Si noti, come mostrato in Figura 2, che il metodo classico che impariamo a scuola richiede invece \(n^2\) operazioni tra le singole cifre: quindi stiamo mettendo a confronto le curve blu e verde della Figura 1.

Figura 2. Metodo delle scuole elementari: ogni prodotto parziale sulle \(n\) righe richiede di moltiplicare \(n\) cifre; si ha quindi un costo totale \(n^2\).

Ma perché è interessante moltiplicare numeri di tantissime cifre in modo veloce?

Una risposta viene dalla crittografia: tutti i moderni sistemi di sicurezza informatica si appoggiano sul calcolo che coinvolge numeri primi molto grandi; impiegare poco tempo nella moltiplicazione permette di avere risultati di codifica e decodifica in tempo reale.

Una seconda risposta sta nell’equivalenza di problemi definita prima: se sappiamo moltiplicare velocemente interi di \(n\) cifre, allora siamo anche in grado di calcolare in poco tempo

— le 4 operazioni elementari tra numeri reali,

— la radice quadrata di un numero reale,

— le costanti matematiche \(e,\pi\), …

…il tutto con una precisione di \(n\) cifre decimali; cioè tutte le operazioni richieste da quanlunque procedimento di calcolo.

Sì, ma…a cosa serve tanta precisione?! In certi casi è importante, perché tutte le operazioni eseguite su un calcolatore fanno perdere precisione (qualcuna più qualcuna meno); in casi patologici, in cui l’accuratezza del risultato finale è messa seriamente a rischio dalle perdite di precisione durante il calcolo, è necessario lavorare in precisione estesa e il numero delle cifre può quindi crescere parecchio.

Lo stato dell’arte

Come detto prima, a scuola impariamo a moltiplicare due numeri di \(n\) cifre impiegando \(n^2\) operazioni. Nel 1971, Schönage e Strassen  [2 ]A. Schönage, V. Strassen, Schnelle Multiplikation grosser Zahlen. Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292. presentarono un algoritmo alternativo che diminuiva bruscamente la complessità: esso richiedeva circa \(n\cdot\log n\cdot \log(\log n)\) passi. Inoltre, questo netto miglioramento suggerì agli autori una congettura: “sentivano” che la complessità del problema doveva essere ancora minore, esattamente \(n\cdot\log n\).

Lavorare per congetture è tipico della ricerca matematica (il famoso Teorema di Fermat è stato per secoli una congettura, fino a poco tempo fa): è anzitutto importante porsi domande e obiettivi, anche se al momento non si hanno risposte e soluzioni. Schönage e Strassen non avevano in mano un metodo che costasse così poco, nè sapevano come dimostrare una minorazione; ma il loro lavoro aprì una vera e propria “gara di velocità”, che forse si è conclusa oggi.

Parlando di algoritmi, in Tabella 1 è riportata la sequenza dei principali “record” che hanno progressivamente abbassato la soglia del tempo necessario ad eseguire la moltiplicazione. La bizzarra espressione \(\log^*n\) indica quanti logaritmi bisogna applicare in sequenza affinché \(\log(\log(\ldots(\log n)\ldots)\) scenda sotto il valore 1.

Riguardo alla minorazione, c’è invece ancora incertezza. È stato dimostrato che servono almeno \(n\cdot\log n\) passi per moltiplicare due numeri, ma con delle condizioni aggiuntive (e non richieste dalla pratica) sulle proprietà dell’algoritmo; potrebbe quindi bastare meno.

 

Tabella 1. Tempo richiesto dai vari algoritmi di moltiplicazione nel corso degli anni.
Metodo Complessità
metodo scolastico \(n^2\)
Karatsuba (1960) \(n^{1.58}\)
Schönage e Strassen (1971) \(n\cdot\log n\cdot \log(\log n)\)
Fürer (2007) \(n\cdot\log n\cdot 16^{\log^* n}\)
Harvey e Van Den Hoeven (2019) \(n\cdot\log n\)

L’idea di base

Concludiamo dando un’idea sommaria di quali trucchi servono per diminuire il tempo di calcolo, abbandonando il classico metodo delle elementari. Quanto segue era in parte già presente in Schönage e Strassen: il contributo recente di Harvey e Van Den Hoeven ha solo prodotto raffinamenti (però decisivi, visto il risultato) dell’idea originale del 1971.

Ancora una volta, la chiave sta nell’equivalenza dei problemi: in sequenza, ricondurremo quello di partenza ad altri due, che riguardano i polinomi.

Dalla moltiplicazione di numeri interi al prodotto di polinomi.

Siano \(a\) e \(b\) gli interi da moltiplicare, e \((a_{n-1} a_{n-2}\ldots a_2 a_1 a_0)\), \((b_{n-1} b_{n-2}\ldots b_2 b_1 b_0)\) le rispettive sequenze di \(n\) cifre. Abbiamo preferito indicizzarle in questo modo, apparentemente innaturale, perché così la cifra \(j\)-esima è proprio quella relativa alla potenza \(10^j\): ad esempio, \(2019=2\cdot10^3+0\cdot10^2+1\cdot10^1+9\cdot10^0\). Ma al contempo, se \(p(x)=2x^3+x+9\), la stessa uguaglianza ci suggerisce che 2019 è uguale al polinomio \(p(x)\) valutato per \(x=10\).

Il giochetto appena visto trasforma un numero intero di \(n\) cifre in un polinomio di grado \(n-1\), i cui coefficienti hanno una sola cifra. Ma funziona anche se raggruppiamo le cifre in blocchi, come illustrato in Figura 3: si abbassa il grado del polinomio, mentre aumentano le cifre dei coefficienti (quante quelle di ogni blocco).

Figura 3. Trasformazione di un intero a 16 cifre in un polinomio con 4 coefficienti di 4 cifre ciascuno, valutato nel punto \(x=10^4\).

Schönage e Strassen dimostrano che il raggruppamento più conveniente usa blocchi di \(q\approx\log n\) cifre, ottenendo un grado vicino a \(n/q\). A questo punto ai due fattori di partenza \(a\) e \(b\) possiamo associare due opportuni polinomi \(a(x)\) e \(b(x)\): noi cerchiamo il prodotto \(a\cdot b=a(10^q)\cdot b(10^q)\). Se riusciamo a calcolare velocemente i coefficienti del polinomio prodotto \(c(x)=a(x)b(x)\), ci basterà poi valutarlo per \(x=10^q\), operazione poco costosa. Ecco che abbiamo ricondotto il problema di partenza al nuovo problema di moltiplicare due polinomi (di grado \(n/q\)).

Dal prodotto di polinomi alla Trasformata di Fourier.

Non spaventatevi del nome, la Trasformata di Fourier (una pietra miliare del calcolo scientifico) non è un concetto così complicato. Si basa sul fatto che un polinomio può essere rappresentato in diversi modi:

(i) dalla sequenza dei suoi \(k\) coefficienti;

(ii) dai valori assunti su \(k\) punti diversi.

Esempi facili da comprendere ci vengono dalla geometria: un polinomio di primo grado (\(k=2\)) della forma \(mx+q\) ha come grafico una retta, pienamente caratterizzata da due punti per cui passa; per determinare i coefficienti di una parabola (\(k=3\)) basta imporre il passaggio per tre punti…e così via.

Passare dalla rappresentazione (i) alla (ii) si traduce nel procedimento di valutazione, mentre il procedimento inverso (passando dai valori ai coefficienti) prende il nome di interpolazione. Si parla di Trasformata di Fourier quando il polinomio viene valutato in \(k\) punti molto speciali: i numeri complessi \[\omega_1=\cos\frac{2\pi}{k}+i\sin\frac{2\pi}{k},\ \omega_2=\cos\frac{4\pi}{k}+i\sin\frac{4\pi}{k},\ \ldots,\ \omega_k=\cos2\pi+i\sin2\pi=1,\] detti radici \(k\)-esime dell’unità (a causa del fatto che ogni \(\omega_j\), elevato a \(k\), dà il valore 1). Nei primi anni ‘60, partendo da un’idea nota dai tempi di Gauss, è stato proposto un algoritmo molto veloce (detto FFT, che sta per Fast Fourier Transform) per valutare e interpolare sulle radici dell’unità. Il tempo richiesto è dell’ordine \(k\cdot\log k\); grazie a questo costo così basso, quasi tutte le elaborazioni su segnali e immagini adottate oggi si basano pesantemente su algoritmi che fanno uso della FFT.

E ora vediamo come la FFT può essere d’aiuto anche per noi. Ci eravamo ricondotti al problema di calcolare i coefficienti di un prodotto di polinomi: lo faremo in modo veloce…attraverso un giro dell’oca.

Dati i \(k\) coefficienti di \(a(x)\) e \(b(x)\), per avere i coefficienti di \(c(x)=a(x)\cdot b(x)\) (che sono \(2k-1\), visto che sommando i gradi di \(a\) e \(b\), entrambi uguali a \(k-1\), otteniamo quello di \(c\)) procediamo col seguente schema:

  • valutiamo \(a(x)\) e \(b(x)\) sulle radici \(m\)-esime dell’unità, con \(m\geq2k-1\) (algoritmo FFT);
  • per ogni radice \(\omega_j\), moltiplichiamo i valori ottenuti \(a(\omega_j)\cdot b(\omega_j)=c(\omega_j)\) (\(m\) moltiplicazioni);
  • ricostruiamo i coefficienti di \(c(x)\) a partire dai suoi valori, mediante interpolazione (ancora mediante l’algoritmo FFT).

Per quanto detto, tutti e tre i passi hanno un basso costo computazionale.

Il collo di bottiglia.

Tutto a posto? Non proprio…L’inghippo sta nel fatto che eravamo partiti dal moltiplicare due interi…ci siamo ricondotti a moltiplicare due polinomi…e per fare questo dobbiamo operare sui numeri complessi! Per di più, mentre i coefficienti di \(c(x)\) che cerchiamo sono interi (e piuttosto grandi), quasi tutte le radici dell’unità hanno come parte reale e immaginaria numeri irrazionali, e qualunque calcolo introduce errori di arrotondamento: dobbiamo quindi assicurarci che sia eseguito tutto con la sufficiente precisione, che garantisca tutte le cifre esatte per i coefficienti di \(c(x)\).

La differenza tra i vari metodi riassunti in Tabella 1 sta proprio nella precisione di calcolo adottata; in particolare, Harvey e Van Den Hoeven hanno avuto una trovata ingegnosa (ma troppo complicata per essere spiegata qui) che ha permesso di migliorare la precisione spendendo meno tempo dei loro predecessori.

Con questo, la ricerca sull’argomento non è finita. Non conoscendo ancora una minorazione, non possiamo escludere che si possa fare ancora meglio di \(n\log n\). Quindi…arrivederci al prossimo record!

Fabio Di Benedetto

 

 

Pin It

Note e riferimenti   [ + ]

1. D. Harvey, J. Van Der Hoeven, Integer multiplication in time \(O(n \log n)\). HAL preprint (ffhal-02070778), 2019.
2. A. Schönage, V. Strassen, Schnelle Multiplikation grosser Zahlen. Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292.
this site uses the awesome footnotes Plugin