Multiplicación binaria y convolución de paridad

22

Esta pregunta es sobre la relación entre la multiplicación normal de números binarios y la multiplicación polinómica mod 2. Para concretar la pregunta, idealmente quisiera saber si hay una mejor solución para la pregunta de Knuth vol. 2, 3ª edición, página 420 que la que figura en el libro.

"¿Se puede facilitar la multiplicación de los polinomios del módulo 2 mediante el uso de operaciones aritméticas ordinarias en una computadora binaria, si los coeficientes se agrupan en palabras de computadora".

Knuth ofrece una reducción razonablemente sencilla que expande el número de bits en la entrada por un factor multiplicativo logarítmico en el peor de los casos. ¿Se puede reducir este factor de registro?

ds.algorithms reductions time-complexity Rafael
fuente
1
Para aclarar un poco, en realidad no estoy interesado en la parte de la pregunta "empaquetada en palabras de computadora" sino solo en la reducción. Para decirlo de manera más concisa, ¿podría ser realmente el caso que la multiplicación de dos números binarios es estrictamente más fácil (en el sentido de permitir una solución asintóticamente más rápida) que la multiplicación de los polinomios módulo 2? Esto parecería contrario a la intuición estándar tal como la entiendo.
Raphael el
Gracias Suresh! Espero que podamos evitar la planta rodadora para este :-)
Raphael
Por desgracia, parece que seguirá cayendo. lástima ...
Suresh Venkat
Me pregunto por qué es esto. Tal vez no lo expresé bien, pero la cuestión de si la multiplicación podría ser más fácil que la convolución (paritaria) debe ser una pregunta en la que al menos algunas personas deben haber pensado, dado lo bien establecidas que están las conexiones conocidas entre los dos problemas.
Raphael el

Respuestas:

2

Claro, puede reducirlo a un factor de 1, pero probablemente a costa del tiempo. Pero para responder la pregunta detrás de la pregunta: la multiplicación de polinomios mod 2 es más fácil desde el punto de vista del hardware (no es necesario propagar bits de acarreo), pero la multiplicación de enteros es una operación que las personas consideran esencial, por lo que tiene soporte directo en ALU y lenguajes de programación.

Peter Taylor
fuente
Estoy realmente interesado en la complejidad asintótica, no tanto en los aspectos prácticos. Una reducción lineal de tiempo y espacio respondería la pregunta.
Raphael