Sappiamo tutti che per moltiplicare due numeri complessi abbiamo la formula
$$(a+ib)(c+id) = ab-cd + i (bc + ad)$$
Nel computer la moltiplicazione è un’operazione molto più costosa della somma o della sottrazione, per cui la complessità computazionale di un algoritmo è data dal numero delle moltiplicazioni richieste. In tal caso abbiamo banalmente quattro moltiplicazioni.
Paradossalmente esiste un algoritmo alternativo, detto algoritmo di Karatsuba, che permette di moltiplicare numeri complessi in maniera più efficiente, ovvero utilizzando solamente tre moltiplicazioni. Infatti definiamo i tre numeri
$$k_1 = c(a+b)\\
k_2 = a (d-c)\\
k_3 = b (c+d)$$
Allora è facile verificare che
$$ab-cd = k_1 -k_3\\
bc + ad = k_1 + k_2$$
Perciò abbiamo ottenuto parte reale e immaginaria del prodotto utilizzando solamente tre moltiplicazioni. Il prezzo da pagare è che stiamo utilizzando più somme: mentre nel primo caso abbiamo solo due somme, ora ne abbiamo tre per definire i $k$ e poi due ancora, per un totale di cinque. Poiché tuttavia la somma è molto meno costosa della moltiplicazione, l’algoritmo è vantaggioso.