Mengapa algoritma multiplikasi linear-waktu Knuth tidak menghitung?

Halaman wikipedia tentang algoritma perkalian menyebutkan yang menarik oleh Donald Knuth . Pada dasarnya, ini melibatkan penggabungan fourier-transform multiplication dengan tabel pra-komputasi dari perkalian berukuran logaritmik. Ini berjalan dalam waktu linier.

Artikel tersebut bertindak seperti algoritma ini entah bagaimana tidak dihitung sebagai algoritma perkalian "benar". Lebih penting lagi, ini dianggap sebagai pertanyaan terbuka apakah multiplikasi dapat dilakukan dalam O(n lg n)waktu yang genap !

Apa detail dari algoritma ini yang mendiskualifikasi dari penghitungan sebagai algoritma multiplikasi "benar"?

Dugaan saya adalah:

• Mengomputasi tabel membutuhkan lebih dari waktu linier. Di sisi lain, itu masih bisa dilakukan n lg ntepat waktu sehingga masih terkesan mengesankan.
• Akses acak entah bagaimana tidak diizinkan. Tapi mengapa algoritma lain bisa menggunakan hal-hal seperti tabel hash dan pointer?
• Entah bagaimana skala salah ketika Anda meningkatkan ukuran kata mesin, seperti jika Anda memiliki mesin 256 bit yang melakukan 256 bit perkalian dalam satu instruksi maka tidak ada gunanya algoritma ini sampai Anda memiliki lebih dari 2 ^ 256 elemen. Di sisi lain, kita peduli dengan faktor invers-ackermann dalam pencarian-serikat.
• "Apakah ada algoritma penggandaan waktu linear?" pertanyaan diam-diam dalam hal beberapa mesin yang lebih lemah, tetapi ini hanya diisyaratkan.

$O(\log n)$$n$$O(n\log n\log\log n)$

$C$$C$$\Omega(n\log n)$$\Omega(n\log n)$

Untuk diskusi tentang model "benar" untuk perkalian praktis bilangan bulat besar, periksa makalah terbaru Fürer . Kesimpulannya mendukung algoritma Schonhage-Strassen "praktis" (ada dua di antaranya, dan yang lain memiliki kompleksitas bit yang lebih baik tetapi berkinerja lebih buruk dalam praktik; Fürer membahas masalah ini di koran).