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

13

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.
Craig Gidney
źródło
Może to być istotne: en.wikipedia.org/wiki/Transdichotomous_model
R .. GitHub ZATRZYMAJ LODĘ

Odpowiedzi:

16

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(logn)nO(nlognloglogn)

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 ).dodoΩ(nlogn)Ω(nlogn)

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).

Yuval Filmus
źródło
2
Dziękuję za wyjaśnienie. Nie mam kopii TAOCP, więc wszystko, co musiałem przejść, to to, co było w artykule wiki (widzę, że już go edytowałeś, aby rozwiązać problem).
Craig Gidney