Warum zählt Knuths linearer Zeitmultiplikationsalgorithmus nicht?

Die Wikipedia-Seite über Multiplikationsalgorithmen erwähnt eine interessante von Donald Knuth . Im Grunde geht es darum, die Fourier-Transformationsmultiplikation mit einer vorberechneten Tabelle von Multiplikationen logarithmischer Größe zu kombinieren. Es läuft in linearer Zeit.

Der Artikel verhält sich so, als würde dieser Algorithmus nicht als "wahrer" Multiplikationsalgorithmus gelten. Noch wichtiger ist, dass es eine offene Frage ist, ob die Multiplikation in gerader O(n lg n)Zeit durchgeführt werden kann!

Welche Details dieses Algorithmus disqualifizieren ihn von der Zählung als "wahrer" Multiplikationsalgorithmus?

Meine Vermutungen sind:

• Das Vorberechnen der Tabelle dauert mehr als eine lineare Zeit. Auf der anderen Seite kann es immer noch rechtzeitig gemacht n lg nwerden, so dass es immer noch beeindruckend zu sein scheint.
• Zufälliger Zugriff ist irgendwie nicht erlaubt. Aber warum können andere Algorithmen dann Dinge wie Hash-Tabellen und Zeiger verwenden?
• Es skaliert irgendwie falsch, wenn Sie die Wortgröße einer Maschine erhöhen. Wenn Sie beispielsweise eine 256-Bit-Maschine haben, die 256-Bit-Multiplikationen in einem einzigen Befehl ausführt, hat dieser Algorithmus keinen Sinn, bis Sie mehr als 2 ^ 256 Elemente haben. Auf der anderen Seite beschäftigen wir uns mit dem Inverse-Ackermann-Faktor beim Union-Find.
• Der "Gibt es einen linearen Zeitmultiplikationsalgorithmus?" frage ist heimlich in bezug auf eine schwächere maschine, aber dies wird nur angedeutet.

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

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

Eine Diskussion des "richtigen" Modells für die praktische Multiplikation großer Ganzzahlen finden Sie in Fürers jüngster Veröffentlichung . Sein Fazit ist zugunsten des "praktischen" Schönhage-Strassen-Algorithmus (es gibt zwei davon, und der andere hat eine bessere Bit-Komplexität, schneidet aber in der Praxis schlechter ab; Fürer geht dieses Problem in der Arbeit an).