Moltiplicazioni di interi più rapide | Tangente

In base 10, un numero si scrive come somma di potenze di 10. Così, 307 si scrive 7 x 1 + 0 x 10 + 3 x 10². Analogamente, in una base N (che supponiamo «grande»), un numero intero A si scrive

A = a + b × N + c × N² + ...

dove a, b, c… sono numeri interi compresi tra 0 e N – 1. Per moltiplicare due numeri di n cifre, usando l’algoritmo classico insegnato alla scuola elementare, si eseguono n² moltiplicazioni di numeri a una cifra, poi circa n addizioni (che, in pratica, sono «trascurabili» rispetto alle precedenti n² moltiplicazioni). Con un computer, il tempo di calcolo è dunque proporzionale a n². Se raddoppiate il numero di cifre, moltiplicate per quattro il tempo di calcolo. Naturalmente, ciò è «visibile» solo per numeri con diverse migliaia di cifre.

Tuttavia, questa prestazione può essere notevolmente migliorata mediante la trasformata di Fourier, la cui definizione si basa sui numeri complessi.

-