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ć?
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,