Двоичное умножение и свертка четности

22

Этот вопрос касается связи между нормальным умножением двоичных чисел и модулем умножения полиномов. Чтобы конкретизировать вопрос, я в идеале хотел бы знать, существует ли лучшее решение вопроса из Кнута тома. 2, 3-е издание, стр. 420, чем приведенное в книге.

«Может ли умножение многочленов по модулю 2 быть облегчено с помощью обычных арифметических операций на двоичном компьютере, если коэффициенты упакованы в компьютерные слова».

Кнут дает достаточно простое сокращение, которое увеличивает число битов на входе на логарифмический множитель в худшем случае. Можно ли уменьшить этот логарифмический фактор?

ds.algorithms reductions time-complexity Рафаэль
источник
1
Чтобы прояснить это немного, меня на самом деле не интересует часть вопроса, "упакованная в компьютерные слова", а просто сокращение. Проще говоря, может ли быть так, что умножение двух двоичных чисел строго проще (в смысле разрешения асимптотически более быстрого решения), чем умножение полиномов по модулю 2? Это кажется противоречащим стандартной интуиции, насколько я понимаю.
Рафаэль
Спасибо, Суреш! Я надеюсь, что мы сможем избежать переката для этого :-)
Рафаэль
увы, похоже, он продолжит падать. Жаль ...
Суреш Венкат
Интересно, почему это так? Может быть, я не очень хорошо сформулировал это, но вопрос о том, может ли умножение быть проще, чем (паритетная) свертка, должен быть вопросом, о котором, по крайней мере, некоторые люди должны думать, учитывая, насколько хорошо установлены известные связи между этими двумя проблемами.
Рафаэль

Ответы:

2

Конечно, вы можете уменьшить его в 1 раз, но, вероятно, ценой времени. Но чтобы ответить на вопрос, стоящий за вопросом: умножение полиномов мод 2 проще с аппаратной точки зрения (не нужно распространять биты переноса), но умножение целых чисел является операцией, которую люди считают существенной, и поэтому имеет прямую поддержку в ALU и языки программирования.

Питер Тейлор
источник
Меня действительно интересует асимптотическая сложность не столько практических аспектов. Линейное сокращение времени и пространства ответило бы на вопрос.
Рафаэль