Dlaczego algorytm mnożenia czasu liniowego Knutha nie „liczy się”?

Strona wikipedii na temat algorytmów mnożenia wspomina o interesującym autorstwa Donalda Knutha . Zasadniczo polega na połączeniu mnożenia transformacji Fouriera ze wstępnie obliczoną tabelą mnożenia wielkości logarytmicznych. Działa w czasie liniowym.

Artykuł działa tak, jakby ten algorytm jakoś nie liczy się jako „prawdziwy” algorytm mnożenia. Co ważniejsze, uważa się za otwarte pytanie, czy pomnożenie może być wykonane nawet w O(n lg n)czasie!

Jakie szczegóły tego algorytmu dyskwalifikują go przed liczeniem jako „prawdziwego” algorytmu mnożenia?

Moje domysły to:

• Wstępne obliczenie tabeli zajmuje więcej niż czas liniowy. Z drugiej strony nadal można to zrobić na n lg nczas, aby nadal wydawało się imponujące.
• Losowy dostęp jest jakoś niedozwolony. Ale dlaczego inne algorytmy mogą używać takich rzeczy jak tabele skrótów i wskaźniki?
• Jakoś skaluje się niepoprawnie, gdy zwiększasz rozmiar słowa maszyny, na przykład jeśli masz maszynę 256-bitową, która wykonuje 256-bitowe multiplikacje w pojedynczej instrukcji, to nie ma sensu dla tego algorytmu, dopóki nie będziesz mieć więcej niż 2 ^ 256 elementów. Z drugiej strony przeszkadza nam czynnik odwrotny-ackermann w znajdowaniu związków.
• „Czy istnieje algorytm liniowego mnożenia czasu?” pytanie jest potajemnie związane z jakąś słabszą maszyną, ale tylko o tym się mówi.

Chociaż wspomniany algorytm pojawia się w TAOCP Knutha, z pewnością nie jest on spowodowany Knuthem i jest szerzej znany jako algorytm Schönhage – Strassen ; Knuth przypisuje im nawet ten algorytm w tekście. Algorytm ten rzeczywiście działa w czasie liniowym na tak zwanej maszynie RAM , w której zmienne mogą przechowywać liczby całkowite o rozmiarze , gdzie jest rozmiarem danych wejściowych. Złożoność bitów wynosi jednak , a dla tego modelu algorytm Fürera jest szybszy.$O(\log n)$$n$$O(n\log n\log\log n)$

Poszukiwanie algorytmów szybkiego mnożenia liczb całkowitych w literaturze koncentrowało się na złożoności bitów jako miary złożoności; to tak, jakby pozwolić rejestrom na przechowywanie tylko jednego bitu (lub tylko bitów dla dowolnej stałej ). Oczekuje się, że mnożenie liczb całkowitych zajmuje , choć nie jest jasne, czy powinno być ciasno, i nie są znane żadne trywialne dolne granice (więc to jest tylko przypuszczeniem ).$C$$C$$\Omega(n\log n)$$\Omega(n\log n)$

Omówienie „poprawnego” modelu praktycznego mnożenia dużych liczb całkowitych można znaleźć w najnowszej pracy Fürera . Jego konkluzja jest za „praktycznym” algorytmem Schönhage – Strassen (są dwa z nich, a drugi ma większą złożoność bitową, ale w praktyce gorzej; Fürer odnosi się do tego problemu w artykule).