20090201, 18:28  #1 
Nov 2008
2×3^{3}×43 Posts 
GNFS estimates
This thread is for the RAM needed for postprocessing, as well as other estimates such as relations needed, in the same vein as the "Msieve QS estimates" thread.

20090201, 20:59  #2 
Tribal Bullet
Oct 2004
110111011001_{2} Posts 
Note that in my experience, the windows memory allocator is more conservative than whatever is in glibc, so the same job run on a windows machine will probably use less RAM than if it was run in linux.

20090202, 12:55  #3 
Nov 2008
2×3^{3}×43 Posts 
SNFS too, please!
SNFS estimates are also welcome.
Fot the C98 GNFS (leading digits 2436) that I just did on my P4 @1.7GHz: 3.6M relations, sieved special qvalues from 0.9M to 1.3M with 12e; 86MB was needed for the matrix building (it was 199775 x 200023) and 52MB for the Lanczos. The 3.6M relations were barely enough: I decided to go ahead with the postprocessing although matbuild suggested I was almost exactly on the boundary. This seems to show that 2.5*10^97 is roughly the limit for 0.91.3M spq: anything much higher than that will need more. Last fiddled with by 10metreh on 20090202 at 12:56 
20090214, 09:49  #4 
Nov 2008
2·3^{3}·43 Posts 
Why does no one want to post here?
I've just done another C98, this time leading digits 6698. I also managed to get away with 0.9M1.3MQ on this one, but only because the poly was 10% better. This led to 3.7M relations. The matrix, 194K x 194K, took 83MB to build and 51MB to solve. 
20090214, 12:06  #5 
Oct 2004
Austria
2482_{10} Posts 
Ooops, I wanted to post my data for GNFS here, but then I forgot for some reason...
I have not protocoled the leading digits, sorry. Code:
size siever Q range size relations needed RAM f. postprocessing c97 12e 450k 1.45 M 38.2 MB c98 12e 500k 1.94 M 65 MB c99 12e 600700k 2.32.5M ? c101 12e 520k 3.7M3.8M 102 MB c102 12e <650k <4.4M 82 MB (very oversieved) c103 12e 640k 3.94M 104.5 MB c106 12e 990k 4.68M 135.9 MB c107 12e 11001110k 4.74.9M 124143 MB c108 12e 1.22M 4.76M 147 MB c111 13e <800k <8.3M 146.2 MB (oversieved) c112 13e 900k <7.6M 195.4 MB c114 13e 1.12M 7.55M 216 MB c117 13e 1.5M 8.5M 191 MB (slightly oversieved) c118 13e 2.501M 8.1M 256 MB (a little less relations failed) c127 13e 5.5M 11M 318 MB (oversieved, 10.3M rels might suffice) c135 14e 4.5M 18.6M 521 MB (13e siever might be better) c136 14e 5.19M 21.25M 648 MB (13e siever might be better, crossover 13e / 14e is near c140) My ubasic script uses quite tight estimations of the needed Special Q range size, and it prints the needed Q range size and relation count to a stats.txt file. If you are using version 1.05a or earlier, you might want to download version 1.06 (just posted a few minutes ago), as the earlier versions did not print the Q range size correctly. Last fiddled with by Andi47 on 20090214 at 12:19 Reason: added some more info 
20090325, 21:09  #6  
Nov 2008
2·3^{3}·43 Posts 
Quote:


20090325, 23:21  #7  
Jun 2003
Ottawa, Canada
495_{16} Posts 
Quote:
Jeff. 

20090326, 05:26  #8  
Oct 2004
Austria
4662_{8} Posts 
Quote:
You can look up the source code of gnfs.ub for the parameters I use. Note that the parameters for ~c130 and upwards are rough estimates (based on a few threads posted here, including fivemacks huge factorizations). I have done 2 factorizations of c13x's using 14e (and perhaps notsooptimal parameters)  I don't have tested the parameters for >c130 used in gnfs.ub yet. 

20090326, 10:39  #9 
Jun 2003
Ottawa, Canada
3×17×23 Posts 
Sorry I lied, I am using the 14e siever for the C135's but only needing 15.4M relations.

20090326, 11:09  #10 
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
Some basics
The largeprime bound is the major influence on the number of relations needed. At a given largeprime bound, larger numbers tend to need more relations, but this is a much less substantial effect.
The smallprime bound is quite important, it's disastrous if set too low. If set too high, you're using more memory than needed and running slower than needed, but generally this isn't a serious issue. The choice of siever influences three things: speed, yield, and duplication rate. If you use too small a siever, you find that you can't get enough relations without sieving a huge Q range, and that when you try to sieve a huge Q range, you get fewer unique relations per input relation than you expect. example: for 109!+1, range 132000000 .. 132001000 : 12e total yield: 159, q=132001003 (1.42182 sec/rel) 13e total yield: 371, q=132001003 (0.66625 sec/rel) 14e total yield: 811, q=132001003 (0.43149 sec/rel) 15e total yield: 1750, q=132001003 (0.43537 sec/rel) so 12e and 13e are right out; and I'm using 15e rather than 14e, even though it's not quite as fast, because the doubled yield per Q lets you mine more relations from the smaller Q at which the relations are more richly distributed. For a table of this sort, it's really helpful (if you've got them) to tabulate the smallprime and largeprime bounds, and the range of Q used, as well as the number of relations and the time taken. Last fiddled with by fivemack on 20090326 at 15:57 Reason: add a table 
20090327, 01:40  #11 
Oct 2006
vomit_frame_pointer
101101000_{2} Posts 
Hmm. I'm running a C136 now, and 13e looked like the best choice here. I think the default fact[LatMsieve].pl script  long since edited to death on my machines  puts up 13e for C134 and 14e for C135. I suspect that this cutoff point should be higher.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P1 B2 time estimates  henryzz  GMPECM  8  20091231 17:51 
c97 GNFS not possible?  Andi47  Msieve  5  20090126 18:19 
Chebyshev's Estimates  brownkenny  Math  2  20090122 17:21 
Msieve QS estimates  henryzz  Msieve  27  20090121 18:37 
Accuracy of completion date estimates?  kdq  Software  4  20081004 05:02 