Why doesn't Knuth's linear-time multiplication algorithm "count"?

Question

The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of logarithmically-sized multiplications. It runs in linear time.

The article acts like this algorithm somehow doesn't count as a "true" multiplication algorithm. More significantly, it's considered to be an open question whether multiplication can be done in even O(n lg n) time!

What details of this algorithm disqualify it from counting as a "true" multiplication algorithm?

My guesses are:

• Precomputing the table takes more than linear time. On the other hand, it can still be done in n lg n time so that would still seem to be impressive.
• Random access is somehow not allowed. But then why can other algorithms use things like hash tables and pointers?
• It somehow scales wrong as you increase a machine's word size, like if you have a 256 bit machine that does 256 bit multiplications in a single instruction then there's no point to this algorithm until you have more than 2^256 elements. On the other hand, we bother with the inverse-ackermann factor in union-find.
• The "is there a linear time multiplication algorithm?" question is secretly in terms of some weaker machine, but this only gets hinted at.

Answer 1

While the algorithm you mention appears in Knuth's TAOCP, it is certainly not due to Knuth, and is more widely known as the Schönhage–Strassen algorithm; Knuth even attributes this algorithm to them in the text. This algorithm indeed runs in linear time in the so-called RAM machine, in which variables are allowed to hold integers of size $O(\log n)$, where $n$ is the size of the input. The bit complexity is, however, $O(n\log n\log\log n)$, and for this model, Fürer's algorithm is faster.

The quest for fast integer multiplication algorithms in the literature has concentrated on bit complexity as the complexity measure; this is like allowing your registers to hold only one bit (or only $C$ bits for some arbitrary constant $C$). It is expected that integer multiplication takes $\Omega(n\log n)$, though it's not clear whether this should be tight, and no non-trivial lower bounds are known (so this $\Omega(n\log n)$ is just a conjecture).

For a discussion of the "correct" model for practical multiplication of large integers, check Fürer's recent paper. His conclusion is in favor of the "practical" Schönhage–Strassen algorithm (there are two of them, and the other one has better bit complexity but performs worse in practice; Fürer addresses this issue in the paper).