How Much Memory at Various Sizes?

[wblipp]

How much memory does GMP-ECM use for default stage 2 for ECM at sizes from 50 digits to 70 digits? How about P-1 and P+1? Is there a simple way to find this out?

[akruppa]

Paul Zimmermann wrote an estimate for the memory use which is in the CVS version. It looks like this:

  lgk = ceil_log2 (dF);
  mem = 9.0 + (double) lgk;
#if (MULT == KS)
  mem += 24.0; /* estimated memory for kronecker_schonhage */
  mem += 1.0;  /* for the wrap-case in PrerevertDivision   */
#endif
  mem *= (double) dF;
  mem *= (double) mpz_size (modulus->orig_modulus);
  mem *= (double) mp_bits_per_limb / 8.0;

To estimate dF:

B2 - B2min = k * dF * d and d/dF ~= 11...12 for large B2. Lets assume 12.
So dF ~= sqrt((B2-B2min)/k/12).

I'm a little surprised that the memory requirements for Kronecker-Schönhage are that high...

Alex

[wblipp]

Hmmm.

Could I get a worked example to help me understand how to apply this? I'm considering plans to work on the 244 digit composite 5³⁴⁹-1 and the 246 composite 19¹⁹³-1, possibly at B1=260M or 850M. In preparation for this, I'm considering upgrading my PC to have 1, 2, or 3 Gigabytes of RAM. How much is "enough"?

William

[dave_dm]

Something I've been thinking about:

The -treefile option stores the product tree of F on disk; this reduces the memory consumption from O(dF * log(dF) * log(n)) to O(dF * log(n)) at the cost of more expensive IO. However with a threaded approach we could run a new stage 1 at low priority during a (-treefile) stage 2; this should 'use up' most of the wasted cycles doing disk seeks.

So IMO, ecm probably doesn't require lots of memory, it's just easiest to implement that way.

Dave

[akruppa]

Since B1=B2min<<B2, we can take B2-B2min ~= B2 and
dF ~= sqrt(2.4e11/k/12) ~= 447213/sqrt(k), where 2.4e11 is the default B2 for B1=260M. Then ceil(log_2(dF))=19-k/2.

So you need dF* (9+25+19-k/2) residues in memory. Each number has 26 dwords plus 3 for the mpz_t, or 116 bytes.

Hence you can expect something line
447213/sqrt(k) * (53-k/2)*116 bytes, or about
50* (53-k/2)/sqrt(k) Megabytes.

For k=2, that is ~1.8 GB. With k=4, 1.3GB, and with k=8 866 MB.
With the treefile option (this eliminates the ceil(log_2(dF))-k/2 term) you'd need
1.2GB, 850MB or 600 MB respectively.

For B1=260M, 2GB should let you use default settings. With 1GB, you'll have to increase the number of blocks and perhaps use -treefile which will cost some speed. Disabling Kronecker-Schönhage multiplication would save a lot of memory (the +25 term), but also cost a lot of speed.

BTW, George mentioned in an email that he plans to look into DWT for bases != 2. This will greatly speed up stage 1 for your numbers.

Alex

[Mystwalker]

Xyzzy did some test for B1=26e7 here.
I've also experienced that the treefile option is not really that bad for performance. I'd guess it costs less speed than a higher k value - I did no in-depth testing, though.