Catherine Greenhill writes in her e-mail message of 1994/02/02
I was wondering how integer multiplication is implemented in the GAP
core, and whether anything like the Schoenhage-Strassen algorithm is used
in the implementation...
Sch"onhage-Stra\3en? Are you kidding? GAP only uses the scool method,
and even that is not implemented very efficiently. We never do more than
Seriously. The scool method, if implemented efficiently, is quite fast.
Karatsuba begins to pay of at about 100 decimal digits (on a mips R3000).
FFT begins to pay of at about 1000 decimal digits. Nu\3baum's method may
or may not be a bit faster than FFT in practice. Sch"onhage-Stra\3en is
never the fastest method.
The next version of the integer arithmetic will implement the Karatsuba
method, but none of the other methods.
I wonder why you wonder how ...
Care to comment?
-- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany