Algoritmo de Toom-Cook

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]