mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2005-04-19, 15:16   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

236110 Posts
Default How Much Memory at Various Sizes?

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?
wblipp is offline   Reply With Quote
Old 2005-04-23, 18:47   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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

Code:
  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
akruppa is offline   Reply With Quote
Old 2005-04-23, 23:21   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3·787 Posts
Default

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 5349-1 and the 246 composite 19193-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
wblipp is offline   Reply With Quote
Old 2005-04-24, 09:03   #4
dave_dm
 
May 2004

8010 Posts
Default

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
dave_dm is offline   Reply With Quote
Old 2005-04-24, 17:42   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-04-24, 20:04   #6
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

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.
Mystwalker is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
"Hybrid Memory Cube" offers 1 Tb/s memory bandwith at just 1.4 mW/Gb/s ixfd64 Hardware 4 2011-12-14 21:24
Variable FFT sizes Mini-Geek Software 7 2008-01-14 17:33
FFT sizes Cruelty Riesel Prime Search 3 2006-07-12 15:15
Different word sizes/accuracy for forward/inverse transform? Dresdenboy Math 2 2003-12-29 22:55
Cache Sizes Unregistered Hardware 4 2003-12-06 13:43

All times are UTC. The time now is 07:57.

Fri Feb 26 07:57:34 UTC 2021 up 85 days, 4:08, 0 users, load averages: 1.52, 1.31, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.