Multiplikasi biner dan konvolusi paritas

22

Pertanyaan ini adalah tentang hubungan antara perkalian bilangan biner normal dan perkalian polinomial mod 2. Untuk membuat pertanyaan konkret, saya ingin tahu apakah ada solusi yang lebih baik untuk pertanyaan dari Knuth vol. 2, 3 edisi, halaman 420 dari yang diberikan dalam buku ini.

"Dapatkah penggandaan modulin 2 polinomial difasilitasi dengan menggunakan operasi aritmatika biasa pada komputer biner, jika koefisien dimasukkan ke dalam kata-kata komputer."

Knuth memberikan pengurangan langsung yang cukup yang memperluas jumlah bit dalam input oleh faktor multiplikasi log dalam kasus terburuk. Bisakah faktor log ini dikurangi?

ds.algorithms reductions time-complexity Raphael
sumber
1
Untuk sedikit memperjelas, saya sebenarnya tidak tertarik pada bagian "dikemas dalam kata-kata komputer" tetapi hanya pengurangan. Singkatnya, mungkinkah perkalian dua bilangan biner benar-benar lebih mudah (dalam arti memungkinkan solusi yang asimtotik lebih cepat) daripada multiplikasi polinomial modulo 2? Ini tampaknya bertentangan dengan intuisi standar seperti yang saya mengerti.
Raphael
Terima kasih, Suresh! Saya harap kita dapat menghindari tumbleweed untuk yang satu ini :-)
Raphael
Sayangnya, sepertinya itu akan terus jatuh. Sayang sekali ...
Suresh Venkat
Saya bertanya-tanya mengapa ini. Mungkin saya tidak mengutarakannya dengan baik tetapi pertanyaan tentang apakah perkalian bisa lebih mudah daripada konvolusi (paritas) harus menjadi pertanyaan yang setidaknya dipikirkan oleh beberapa orang, mengingat seberapa baik hubungan yang diketahui antara kedua masalah tersebut.
Raphael

Jawaban:

2

Tentu, Anda dapat menguranginya menjadi faktor 1, tetapi mungkin dengan biaya waktu. Tetapi untuk menjawab pertanyaan di balik pertanyaan: multiplikasi polinomial mod 2 lebih mudah dari sudut pandang perangkat keras (tidak perlu menyebarkan bit carry), tetapi penggandaan bilangan bulat adalah operasi yang dianggap penting, dan karenanya memiliki dukungan langsung dalam ALU dan bahasa pemrograman.

Peter Taylor
sumber
Saya benar-benar tertarik pada kompleksitas asimptotik yang bukan aspek praktisnya. Pengurangan waktu dan ruang linear akan menjawab pertanyaan.
Raphael