Por que o algoritmo de multiplicação de tempo linear de Knuth não conta?

A página da Wikipedia sobre algoritmos de multiplicação menciona uma página interessante de Donald Knuth . Basicamente, envolve combinar a multiplicação por transformada de fourier com uma tabela pré-computada de multiplicações de tamanho logaritmicamente. É executado em tempo linear.

O artigo age como esse algoritmo de alguma forma não conta como um algoritmo de multiplicação "verdadeiro". Mais significativamente, é considerado uma questão em aberto se a multiplicação pode ser feita em O(n lg n)tempo uniforme !

Que detalhes desse algoritmo o desqualificam da contagem como um algoritmo de multiplicação "verdadeiro"?

Minhas suposições são:

• A pré-computação da tabela leva mais que o tempo linear. Por outro lado, ainda pode ser feito a n lg ntempo, para que ainda pareça impressionante.
• O acesso aleatório de alguma forma não é permitido. Mas então por que outros algoritmos podem usar coisas como tabelas de hash e ponteiros?
• De alguma forma, a escala é incorreta à medida que você aumenta o tamanho da palavra de uma máquina, como se você tivesse uma máquina de 256 bits que faz multiplicações de 256 bits em uma única instrução, então não há sentido em usar esse algoritmo até que você tenha mais de 2 ^ 256 elementos. Por outro lado, nos preocupamos com o fator inverso-ackermann na busca por união.
• O "existe um algoritmo de multiplicação de tempo linear?" A pergunta é secretamente em termos de uma máquina mais fraca, mas isso só é sugerido.

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

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

Para uma discussão do modelo "correto" para multiplicação prática de números inteiros grandes, consulte o artigo recente de Fürer . Sua conclusão é a favor do algoritmo "prático" de Schönhage-Strassen (existem dois deles, e o outro tem melhor complexidade de bits, mas apresenta pior desempenho na prática; Fürer aborda essa questão no artigo).