Binäre Multiplikation und Paritätsfaltung

22

Bei dieser Frage geht es um die Beziehung zwischen normaler Multiplikation von Binärzahlen und polynomialer Multiplikation Mod 2. Um die Frage zu konkretisieren, möchte ich im Idealfall wissen, ob es eine bessere Lösung für die Frage von Knuth vol. 2, 3. Auflage, Seite 420 als im Buch angegeben.

"Kann die Multiplikation von Polynomen modulo 2 durch Verwendung der gewöhnlichen arithmetischen Operationen auf einem Binärcomputer erleichtert werden, wenn Koeffizienten in Computerwörter gepackt werden?"

Knuth führt eine relativ einfache Reduktion durch, die die Anzahl der Bits in der Eingabe im ungünstigsten Fall um einen logarithmischen Multiplikationsfaktor erweitert. Kann dieser Log-Faktor reduziert werden?

ds.algorithms reductions time-complexity Raphael
quelle
1
Um es ein wenig zu verdeutlichen, ich interessiere mich eigentlich nicht für den in Computerwörter gepackten Teil der Frage, sondern nur für die Reduktion. Könnte es, um es kurz zu machen, tatsächlich sein, dass die Multiplikation zweier Binärzahlen (im Sinne einer asymptotisch schnelleren Lösung) strikt einfacher ist als die Multiplikation von Polynomen modulo 2? Dies scheint der üblichen Intuition zu widersprechen, wie ich es verstehe.
Raphael
Danke, Suresh! Ich hoffe, wir können den Tumbleweed für diesen vermeiden :-)
Raphael
leider sieht es so aus, als würde es weiter stürzen. Schade ...
Suresh Venkat
Ich frage mich, warum das so ist. Vielleicht habe ich es nicht gut formuliert, aber die Frage, ob Multiplikation einfacher sein könnte als (Paritäts-) Faltung, muss eine Frage sein, über die sich zumindest einige Leute Gedanken gemacht haben müssen, wenn man bedenkt, wie gut die bekannten Zusammenhänge zwischen den beiden Problemen hergestellt sind.
Raphael

Antworten:

2

Sicher, Sie können es auf den Faktor 1 reduzieren, aber wahrscheinlich auf Kosten der Zeit. Aber um die Frage hinter der Frage zu beantworten: Die Multiplikation von Polynomen Mod 2 ist aus Hardware-Sicht einfacher (keine Notwendigkeit, Übertragsbits zu verbreiten), aber die Multiplikation von ganzen Zahlen ist eine Operation, die von den Leuten als wesentlich angesehen wird, und hat daher direkte Unterstützung in ALUs und Programmiersprachen.

Peter Taylor
quelle
Ich interessiere mich wirklich für die asymptotische Komplexität, nicht so sehr für praktische Aspekte. Eine lineare Reduzierung von Zeit und Raum würde die Frage beantworten.
Raphael