¿Cuántas puertas lógicas se necesitan para multiplicar dos enteros de n bits?

Los multiplicadores directos de matriz binaria toman el orden de [math] n ^ 2 [/ math] compuertas combinacionales (usaré [math] \ sim [/ math] a continuación para “en el orden de”). Los recuentos exactos varían y dependen de las puertas que permita sin dividirlas en puertas más simples. Por ejemplo, puertas de sumador medias y completas. Es posible implementar la multiplicación de matrices usando un circuito secuencial con menos puertas, pero será más lento. Por cierto, los recuentos de puertas asintóticas coinciden con las estimaciones de tiempo de ejecución en una computadora no paralela (esencialmente, se puede realizar una puerta a la vez).

El algoritmo / circuito de Karatsuba es solo un poco más complicado que la multiplicación de matrices, pero requiere puertas [math] \ sim n ^ {1.585} [/ math]. Comienza a superar la multiplicación de matriz (en tamaño de circuito) para números con al menos cien bits. En general, cuanto más complicado es el algoritmo, mayor es la constante principal junto a la expresión asintótica para su tamaño. Dado que tales algoritmos solo son útiles para números bastante grandes, implementar un circuito completamente combinacional no es práctico: se utilizan circuitos secuenciales, con menos puertas.

La multiplicación Toom-Cook (una familia de algoritmos) es más complicada, pero se ejecuta más rápido para números con al menos varios cientos de bits. Uno de los algoritmos de esta familia utiliza [math] \ sim n ^ {1.465} [/ math] steps / gates.

La multiplicación asintóticamente más rápida conocida puede ilustrarse mediante el algoritmo de Schönhage-Strassen y, más recientemente, el algoritmo de Fürer. Funcionan un poco más lento que [math] n \ log n [/ math] time, pero son útiles solo para números muy grandes, un par de miles de bits o más. Dichos algoritmos son muy complicados y hacer que funcionen bien es un problema de investigación abierto. Aparentemente, algunos algoritmos recientes para la multiplicación de enteros no se han implementado. Aquí no hay mucho espacio para la mejora asintótica, ya que necesita al menos una puerta por bit de entrada. Pero hay mucho margen de mejora para reducir los costos reales de estos algoritmos.

Finalmente, si uno de sus números es una constante, hay una serie de técnicas y optimizaciones que hacen innecesarios los enfoques anteriores. Por ejemplo, para calcular un número binario por 15, primero puede multiplicar por 16 (que es solo un desplazamiento binario) y luego restar el número original. Para multiplicar por 45, primero multiplique por 15, luego multiplique por 3 (primero, multiplique por 2 – un desplazamiento binario, – luego sume el número).