GNFS estimates

10metreh · 2009-02-01, 18:28

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.

jasonp · 2009-02-01, 20:59

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.

10metreh · 2009-02-02, 12:55

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 q-values 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.9-1.3M spq: anything much higher than that will need more.

10metreh · 2009-02-14, 09:49

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.9M-1.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.

Andi47 · 2009-02-14, 12:06

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      600-700k       2.3-2.5M           ?

c101  12e      520k           3.7M-3.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      1100-1110k     4.7-4.9M           124-143 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)

Edit:

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.

10metreh · 2009-03-25, 21:09

Quote:

Originally Posted by Andi47

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      600-700k       2.3-2.5M           ?
 
c101  12e      520k           3.7M-3.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      1100-1110k     4.7-4.9M           124-143 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)

Edit:

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.

I've only just noticed that our estimates for number of relations for a C98 are completely different (yours is 1.9M, mine is 3.6M). I presume that is because you used 25-bit large primes for your C98; I used 26-bit large primes for all my C98s. I did use 25-bit large primes for my C97s, though.

Jeff Gilchrist · 2009-03-25, 23:21

Quote:

Originally Posted by Andi47

Ooops, I wanted to post my data for GNFS here, but then I forgot for some reason...

I have been doing lots of C134/135's lately and I'm using the 13e siever and only need about 15.4M relations for each one so I think you would be better off with the 13e siever.

Jeff.

Andi47 · 2009-03-26, 05:26

Quote:

Originally Posted by 10metreh

I've only just noticed that our estimates for number of relations for a C98 are completely different (yours is 1.9M, mine is 3.6M). I presume that is because you used 25-bit large primes for your C98; I used 26-bit large primes for all my C98s. I did use 25-bit large primes for my C97s, though.

For the latest c98 I GNFSed, postprocessing was happy with 1.97M relations. I am using 25 bit large primes up to c99.

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 not-so-optimal parameters) - I don't have tested the parameters for >c130 used in gnfs.ub yet.

Jeff Gilchrist · 2009-03-26, 10:39

Sorry I lied, I am using the 14e siever for the C135's but only needing 15.4M relations.

fivemack · 2009-03-26, 11:09

The large-prime bound is the major influence on the number of relations needed. At a given large-prime bound, larger numbers tend to need more relations, but this is a much less substantial effect.

The small-prime 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 small-prime and large-prime bounds, and the range of Q used, as well as the number of relations and the time taken.

FactorEyes · 2009-03-27, 01:40

Quote:

Originally Posted by Jeff Gilchrist

Sorry I lied, I am using the 14e siever for the C135's but only needing 15.4M relations.

Hmm. I'm running a C136 now, and 13e looked like the best choice here. I think the default fact[Lat|Msieve].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.

2009-02-01, 18:28	#1
10metreh Nov 2008 2×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.

2009-02-02, 12:55	#3
10metreh Nov 2008 2×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 q-values 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.510^97 is roughly the limit for 0.9-1.3M spq: anything much higher than that will need more. Last fiddled with by 10metreh on 2009-02-02 at 12:56*

2009-03-26, 11:09	#10
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	Some basics The large-prime bound is the major influence on the number of relations needed. At a given large-prime bound, larger numbers tend to need more relations, but this is a much less substantial effect. The small-prime 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 small-prime and large-prime bounds, and the range of Q used, as well as the number of relations and the time taken. Last fiddled with by fivemack on 2009-03-26 at 15:57 Reason: add a table

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
P-1 B2 time estimates	henryzz	GMP-ECM	8	2009-12-31 17:51
c97 GNFS not possible?	Andi47	Msieve	5	2009-01-26 18:19
Chebyshev's Estimates	brownkenny	Math	2	2009-01-22 17:21
Msieve QS estimates	henryzz	Msieve	27	2009-01-21 18:37
Accuracy of completion date estimates?	kdq	Software	4	2008-10-04 05:02

2009-02-01, 20:59	#2
jasonp Tribal Bullet Oct 2004 6725₈ 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.

2009-02-14, 09:49	#4
10metreh Nov 2008 2322₁₀ 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.9M-1.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.

2009-03-26, 10:39	#9
Jeff Gilchrist Jun 2003 Ottawa, Canada 495₁₆ Posts	Sorry I lied, I am using the 14e siever for the C135's but only needing 15.4M relations.