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 Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany