3.3.1. Multiplicación rápida de enteros largos.
Cálculo de la multiplicación con divide y vencerás:
u·v = 102S·w·y + 10S·(w·z+x·y) + x·z
El problema de tamaño n es descompuesto en 4 problemas de tamaño n/2. La combinación (suma) se puede realizar en un tiempo lineal O(n).
t(n) = 4·t(n/2) + d·n ? O(nlog24) = O(n2), no mejora el método clásico.
Multiplicación rápida de enteros largos (Karatsuba y Ofman):
u·v = 102S·w·y + 10S·[(w-x)·(z-y) + w·y + x·z] + x·z
En este caso se requieren 3 multiplicaciones de tamaño n/2:
t(n) = 3·t(n/2) + d’·n ? O(nlog23) ? O(n1.59)
El método es asintóticamente mejor que el método clásico. Sin embargo, las constantes son mucho mayores. La combinación es muy costosa.
En la práctica se obtiene beneficio con números de más de 500 bits.