> < ^ From:

< ^ Subject:

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

> < [top]