Multiplication binaire et convolution de parité

22

Cette question concerne la relation entre la multiplication normale des nombres binaires et la multiplication polynomiale mod 2. Pour rendre la question concrète, j'aimerais idéalement savoir s'il existe une meilleure solution à la question de Knuth vol. 2, 3e édition, page 420 que celle donnée dans le livre.

"La multiplication des polynômes modulo 2 peut-elle être facilitée en utilisant les opérations arithmétiques ordinaires sur un ordinateur binaire, si les coefficients sont regroupés dans des mots informatiques."

Knuth donne une réduction raisonnablement simple qui augmente le nombre de bits dans l'entrée par un facteur multiplicateur logarithmique dans le pire des cas. Ce facteur de log peut-il être réduit?

ds.algorithms reductions time-complexity Raphael
la source
1
Pour clarifier un peu, je ne suis pas réellement intéressé par la partie "emballée dans des mots informatiques" de la question mais juste par la réduction. Pour être plus concis, pourrait-il vraiment être le cas que la multiplication de deux nombres binaires est strictement plus facile (dans le sens de permettre une solution asymptotiquement plus rapide) que la multiplication de polynômes modulo 2? Cela semblerait contraire à l'intuition standard telle que je la comprends.
Raphael
Merci, Suresh! J'espère que nous pourrons éviter le tumbleweed pour celui-ci :-)
Raphael
hélas, on dirait qu'il continuera de s'effondrer. dommage ...
Suresh Venkat
Je me demande pourquoi. Peut-être que je ne l'ai pas bien formulé, mais la question de savoir si la multiplication pourrait être plus facile que la convolution (paritaire) doit être une question à laquelle au moins certaines personnes doivent avoir pensé, compte tenu de la solidité des liens connus entre les deux problèmes.
Raphael

Réponses:

2

Bien sûr, vous pouvez le réduire à un facteur 1, mais probablement au prix du temps. Mais pour répondre à la question derrière la question: la multiplication des polynômes mod 2 est plus facile d'un point de vue matériel (pas besoin de propager des bits de transport), mais la multiplication des entiers est une opération que les gens considèrent comme essentielle, et a donc un support direct dans les ALU et langages de programmation.

Peter Taylor
la source
Je suis vraiment intéressé par la complexité asymptotique, pas tant par les aspects pratiques. Une réduction linéaire du temps et de l'espace répondrait à la question.
Raphael