Loading ...
Sorry, an error occurred while loading the content.

Re: GCD algorithms

Expand Messages
  • George Woltman
    Hi, ... The 218MB quote is a tad high. I think peak usage is less than 32MB. The 218MB number is probably the memory usage for running an ECM curve (a lot of
    Message 1 of 1 , Dec 29, 2000
    • 0 Attachment
      Hi,

      At 08:26 AM 12/29/2000 -0800, Phil Carmody wrote:
      >On Thu, 28 December 2000, "Andrey Kulsha" wrote:
      > > 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.

      The 218MB quote is a tad high. I think peak usage is less than 32MB. The
      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
      giants.c library.

      Happy new year to all,
      George
    Your message has been successfully submitted and would be delivered to recipients shortly.