Algoritmo de Toom-Cook

El algoritmo de Toom-Cook, a veces conocido como Toom-3, nombrado así por los autores Andrei Toom y Stephen Cook, es un algoritmo de multiplicación, un método para multiplicar dos números enteros que son muy grandes.

Dados 2 números enteros, a y b, Toom-Cook divide los números a y b en k partes más pequeñas, todas de longitud l, y realiza las operaciones sobre las partes, Conforme la k va creciendo va combinando muchas de las suboperaciones de multiplicación, reduciendo así poco a poco la complejidad total del algoritmo. Las suboperaciones de multiplicación ahora sí se pueden realizar recursivamente usando de nuevo el método de multiplicación Toom-Cook, y así sucesivamente. Aunque los términos "Toom-3" y "Toom-Cook" se utilizan a veces incorrectamente como sinónimos, Toom-3 es una única instancia del algoritmo de Toom-Cook, donde k = 3.

Referencias

• D. Knuth. The Art of Computer Programming, Volumen 2. Tercera edición, Addison-Wesley, 1997. Sección 4.3.3.A: Métodos digitales, pág. 294.

• Datos: Q1522355