22
$\begingroup$

This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a better solution to the question from Knuth vol. 2, 3rd edition, page 420 than that given in the book.

"Can the multiplication of polynomials modulo 2 be facilitated by using the ordinary arithmetic operations on a binary computer, if coefficients are packed into computer words."

Knuth gives a reasonably straightforward reduction which expands the number of bits in the input by a log multiplicative factor in the worst case. Can this log factor be reduced?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ To clarify a little, I am not actually interested in the "packed into computer words" part of the question but just the reduction. To put it more concisely, could it really be the case that multiplication of two binary numbers is strictly easier (in the sense of permitting an asymptotically faster solution) than the multiplication of polynomials modulo 2? This would seem counter to the standard intuition as I understand it. $\endgroup$
    – graffe
    Oct 23 '10 at 18:54
  • $\begingroup$ Thanks, Suresh! I hope we can avoid the tumbleweed for this one :-) $\endgroup$
    – graffe
    Oct 29 '10 at 14:42
  • $\begingroup$ alas, looks like it will continue to tumble. pity... $\endgroup$
    – Suresh Venkat
    Nov 4 '10 at 6:19
  • $\begingroup$ I wonder why this is. Maybe I didn't phrase it well but the question of whether multiplication could be easier than (parity) convolution must be a question that at least some people must have thought about, given how well established the known connections between the two problems are. $\endgroup$
    – graffe
    Nov 4 '10 at 8:01
2
$\begingroup$

Sure, you can reduce it to a factor of 1, but probably at the cost of time. But to answer the question behind the question: multiplication of polynomials mod 2 is easier from a hardware point of view (no need to propagate carry bits), but multiplication of integers is an operation people consider essential, and so has direct support in ALUs and programming languages.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I am really interested in the asymptotic complexity not so much practical aspects. A linear time and space reduction would answer the question. $\endgroup$
    – graffe
    Jan 16 '11 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.