¿Cuál es el mejor resultado para el número de puertas en un circuito que multiplica dos enteros de n bits?
El método obvio genera puertas . Hay mejores enfoques con puertas y .
No pude encontrar ninguna familia de circuitos booleanos que pueda manejar la multiplicación con puertas. Me pregunto si existe tal familia de circuitos.
Respuestas:
A continuación se muestra una encuesta detallada de 2008 que cubre los principales algoritmos teóricos para la multiplicación, incluidos los discutidos en los comentarios a su pregunta (incluido el algoritmo de Schönhage – Strassen y el Algoritmo de Fuerer, ver página 335 de la encuesta). Sin embargo, la implementación es una cuestión diferente y algunos de estos algoritmos pueden no considerarse prácticos; La encuesta no cubre implementaciones prácticas. Aunque la encuesta incluye algoritmos para polinomios, series de potencias, números reales y números de 2 adic, los enteros son un caso especial de estos (ver Figura 1 en la página 336).O ( n lognorte2Iniciar sesión∗norte)
Multiplicación rápida y sus aplicaciones , Bernstein (Teoría de números algorítmicos / Publicaciones de MSRI / Volumen 44, 2008)
fuente