Multiplicação binária e convolução de paridade

22

Esta questão é sobre a relação entre multiplicação normal de números binários e multiplicação polinomial mod 2. Para tornar a questão concreta, eu gostaria de saber se existe uma solução melhor para a questão de Knuth vol. 2, 3ª edição, página 420 do que a apresentada no livro.

"A multiplicação dos polinômios módulo 2 pode ser facilitada usando as operações aritméticas comuns em um computador binário, se os coeficientes forem agrupados em palavras de computador".

Knuth fornece uma redução razoavelmente direta que expande o número de bits na entrada por um fator multiplicativo de log no pior caso. Esse fator de log pode ser reduzido?

ds.algorithms reductions time-complexity Rafael
fonte
1
Para esclarecer um pouco, não estou realmente interessado na parte da pergunta "empacotada em palavras de computador", mas apenas na redução. Para ser mais conciso, poderia realmente ser o caso de a multiplicação de dois números binários ser estritamente mais fácil (no sentido de permitir uma solução assintoticamente mais rápida) do que a multiplicação dos polinômios módulo 2? Isso parece contrário à intuição padrão como eu a entendo.
Raphael
Obrigado, Suresh! Espero que possamos evitar o tumbleweed para este :-)
Raphael
infelizmente, parece que continuará caindo. pena ...
Suresh Venkat
Eu me pergunto por que isso é. Talvez eu não tenha expressado bem a frase, mas a questão de saber se a multiplicação poderia ser mais fácil do que a convolução (paridade) deve ser uma pergunta que pelo menos algumas pessoas devam ter pensado, dado o quão bem estabelecidas são as conexões conhecidas entre os dois problemas.
Raphael

Respostas:

2

Claro, você pode reduzi-lo a um fator de 1, mas provavelmente ao custo do tempo. Mas, para responder à pergunta por trás da pergunta: multiplicação de polinômios mod 2 é mais fácil do ponto de vista de hardware (não é necessário propagar bits de transporte), mas a multiplicação de números inteiros é uma operação que as pessoas consideram essencial e, portanto, tem suporte direto em ALUs e linguagens de programação.

Peter Taylor
fonte
Estou realmente interessado na complexidade assintótica, não em aspectos práticos. Uma redução linear de tempo e espaço responderia à pergunta.
Raphael