Mnożenie binarne i splot parzystości

22

To pytanie dotyczy związku między normalnym mnożeniem liczb binarnych a wielomianowym mnożeniem mod 2. Aby uczynić pytanie konkretnym, idealnie chciałbym wiedzieć, czy istnieje lepsze rozwiązanie pytania z Knuth vol. 2, wydanie trzecie, strona 420 niż podano w książce.

„Czy mnożenie wielomianów modulo 2 można ułatwić, stosując zwykłe operacje arytmetyczne na komputerze binarnym, jeśli współczynniki są upakowane w słowa komputerowe”.

Knuth daje dość prostą redukcję, która w najgorszym przypadku zwiększa liczbę bitów na wejściu o współczynnik logarytmiczny. Czy ten współczynnik logarytmiczny można zmniejszyć?

ds.algorithms reductions time-complexity Raphael
źródło
1
Żeby trochę wyjaśnić, tak naprawdę nie interesuje mnie część pytania „spakowana słowami komputerowymi”, a jedynie redukcja. Mówiąc bardziej zwięźle, czy naprawdę może być tak, że mnożenie dwóch liczb binarnych jest ściśle łatwiejsze (w sensie pozwalającym na asymptotycznie szybsze rozwiązanie) niż mnożenie wielomianów modulo 2? To wydaje się sprzeczne ze standardową intuicją, tak jak ją rozumiem.
Raphael
Dzięki, Suresh! Mam nadzieję, że uda nam się uniknąć tego przypadku :-)
Raphael
Niestety, wygląda na to, że nadal będzie się obracać. szkoda ...
Suresh Venkat
Zastanawiam się, dlaczego tak jest. Może nie sformułowałem tego dobrze, ale pytanie, czy pomnażanie może być łatwiejsze niż splot (parzystość), musi być pytaniem, o którym przynajmniej niektórzy musieli pomyśleć, biorąc pod uwagę, jak dobrze znane są znane powiązania między tymi dwoma problemami.
Raphael,

Odpowiedzi:

2

Jasne, możesz zmniejszyć go do 1, ale prawdopodobnie kosztem czasu. Ale aby odpowiedzieć na pytanie leżące u podstaw pytania: mnożenie wielomianów mod 2 jest łatwiejsze z punktu widzenia sprzętowego (nie ma potrzeby propagowania bitów przenoszenia), ale mnożenie liczb całkowitych jest operacją, którą ludzie uważają za niezbędną, a więc ma bezpośrednie wsparcie w ALU i języki programowania.

Peter Taylor
źródło
Naprawdę interesuje mnie asymptotyczna złożoność, nie tyle praktyczne aspekty. Liniowa redukcja czasu i przestrzeni odpowiada na pytanie.
Raphael