Eggs in my face. In my e-mail message of 1994/02/04 I compared FFT with
Sch"onhage-Strassen, arguing that the former is faster. This is of
course ridiculous, since FFT *is* the Sch"onhage-Strassen algorithm.
I had a modular method by Sch"onhage in mind, which is indeed always
slower than Sch"onhage-Strassen. Also the other method which seems to be
a little bit faster in practice is due to Nussbaumer (not Nu\3baum).

But the general method remains. For small numbers the ordinary scool
method (of order <n>^2) is best. For numbers with 100 decimal digits one
should use Karatsuba's trick. And only for numbers with more than 1000
decimal digits it is worth to use FFT or Nussbaumer's method.

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany