current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 6 down vote favorite
1

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.
share|improve this question
    
This may be relevant: en.wikipedia.org/wiki/Transdichotomous_model –  R.. yesterday
add comment

1 Answer

up vote 8 down vote accepted

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

share|improve this answer
    
Thanks for the clarification. I don't have a copy of TAOCP so all I had to go by was what was in the wiki article (I see you've already edited it to fix the issue). –  Strilanc yesterday
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.