Poca cantidad de puertas para la multiplicación

9

¿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 .θ(norte2)θ(norteIniciar sesiónnorteIniciar sesiónIniciar sesiónnorte)θ(norteIniciar sesiónnorte2Iniciar sesión(norte))

No pude encontrar ninguna familia de circuitos booleanos que pueda manejar la multiplicación con puertas. Me pregunto si existe tal familia de circuitos.norteIniciar sesiónnorte

Amir
fuente
1
¿Está buscando un circuito aritmético o un circuito booleano?
Suresh Venkat
1
Estoy buscando un circuito booleano.
Amir
para el registro, ¿qué es el algoritmo ? ¿No usaría tantas puertas? O(norteIniciar sesiónnorte)
vzn
3
@vzn No, el algoritmo de Martin Fuerer es el más conocido, y da un circuito con puertas . Schonhage-Strassen se usa realmente en algunos sistemas de álgebra computacional para números muy grandes. O(norteIniciar sesiónnorte2Iniciar sesiónnorte)
Sasho Nikolov
44
Hay algo de sobrecarga para convertir una TM en un circuito. Las puertas de un algoritmo de tiempo no dan un circuito con puertas t ( n ) . La traducción general no puede ser mejor que la complejidad del circuito del problema del valor del circuito. Por otro lado, la mejor complejidad uniforme no implica un límite inferior en la complejidad del circuito, ya que existe una sobrecarga también en la dirección inversa, es decir, puede haber circuitos de tamaño O ( n lg n ) incluso si no hay TM con ese funcionamiento tiempo de multiplicación t(norte)t(norte)O(nortelgnorte)
Kaveh

Respuestas:

2

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(norteIniciar sesiónnorte2Iniciar sesiónnorte)

Multiplicación rápida y sus aplicaciones , Bernstein (Teoría de números algorítmicos / Publicaciones de MSRI / Volumen 44, 2008)

vzn
fuente
El documento vinculado no tiene páginas 335 o 336. ¿Quizás quiso vincular a un archivo diferente?
argentpepper
¡Uy! Gracias por la propina. versión anterior marcada como borrador. Esta versión con pg #s citados es quizás final?
vzn
1
@vzn: Incluso ese papel tiene una gran O alrededor del .Iniciar sesión(norte)