Moltiplichiamo in tempo quasi lineare!

La notizia è arrivata alla fine di marzo: i matematici David Harvey e Joris van der Hoeven hanno dimostrato che la moltiplicazione di grandi numeri interi è «quasi lineare», confermando una congettura formulata nel 1971 sulla scorta di un’intuizione di Volker Strassen. Riscopriamo una delle operazioni fondamentali dell’aritmetica!

La scrittura di un intero A in base N assomiglia a quella di un polinomio:

A = a + bN + cN ² +… dove a, b, c… sono numeri interi compresi tra 0 e N – 1. Per sommare due numeri di n cifre, usando l’algoritmo classico insegnato nella scuola primaria, si eseguono n addizioni di numeri a una cifra, con, all’occorrenza, n addizioni dovute ai riporti. Verifichiamo infatti che, usando un computer, il tempo di calcolo per numeri molto grandi è proporzionale a n. Più precisamente, è maggiorato da una costante moltiplicata per n, cosa che si indica con O(n) («o grande di n»). Si dice che la sua complessità – un modello matematico del tempo di calcolo – è lineare.

Usando l’algoritmo classico insegnato a scuola, la moltiplicazione non è lineare bensì quadratica, cioè ha complessità O(n²), poiché si eseguono n ² moltiplicazioni di numeri a una cifra, seguite da circa n addizioni. Verifichiamo infatti che, usando un computer, il tempo di calcolo per numeri grandi è proporzionale a n ².

I computer sono diventati così potenti che queste misure risultano visibili solo per numeri di diverse migliaia di cifre. Ma se raddoppiate il numero di cifre, il tempo di calcolo si moltiplica per 4. Nel caso dell’addizione, invece, il tempo di calcolo raddoppia soltanto: è qui tutta la differenza fra complessità lineare e complessità quadratica.

L’algoritmo di Strassen ============================