Re: GCD algorithms
At 08:26 AM 12/29/2000 -0800, Phil Carmody wrote:
>On Thu, 28 December 2000, "Andrey Kulsha" wrote:The 218MB quote is a tad high. I think peak usage is less than 32MB. The
> > Why two 5000000-digit numbers requires 218 Mb of memory? I
> > think, 4 Mb is enough for them!
>The operation has two inputs, and an output, probably. It also needs to
>convert the numbers into FFT-usable form, which increases their size by
>about 3. It also may need temporary space to perform the FFTs.
>The figure given was probably the peak memory requirement for the operation.
218MB number is probably the memory usage for running an ECM curve
(a lot of large temporary variables are used).
Note that you can do a GCD with not much more than 4MB using the
standard Euclidian GCD algorithm which is O(n^2). Prime95 uses a
faster O (n log n log n) algorithm that I adapted from Richard Crandall's
Happy new year to all,