> < ^ From:

> < ^ Subject:

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

is necessary.

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.

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

> < [top]