mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-02-01, 18:28   #1
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default 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.
10metreh is offline   Reply With Quote
Old 2009-02-01, 20:59   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110100002 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2009-02-02, 12:55   #3
10metreh
 
10metreh's Avatar
 
Nov 2008

232210 Posts
Default 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.5*10^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
10metreh is offline   Reply With Quote
Old 2009-02-14, 09:49   #4
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

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.
10metreh is offline   Reply With Quote
Old 2009-02-14, 12:06   #5
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

9B216 Posts
Default

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.

Last fiddled with by Andi47 on 2009-02-14 at 12:19 Reason: added some more info
Andi47 is offline   Reply With Quote
Old 2009-03-25, 21:09   #6
10metreh
 
10metreh's Avatar
 
Nov 2008

1001000100102 Posts
Default

Quote:
Originally Posted by Andi47 View Post
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.
10metreh is offline   Reply With Quote
Old 2009-03-25, 23:21   #7
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

22248 Posts
Default

Quote:
Originally Posted by Andi47 View Post
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.
Jeff Gilchrist is offline   Reply With Quote
Old 2009-03-26, 05:26   #8
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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.
Andi47 is offline   Reply With Quote
Old 2009-03-26, 10:39   #9
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

22×293 Posts
Default

Sorry I lied, I am using the 14e siever for the C135's but only needing 15.4M relations.
Jeff Gilchrist is offline   Reply With Quote
Old 2009-03-26, 11:09   #10
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13·491 Posts
Default 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
fivemack is offline   Reply With Quote
Old 2009-03-27, 01:40   #11
FactorEyes
 
FactorEyes's Avatar
 
Oct 2006
vomit_frame_pointer

23×32×5 Posts
Default

Quote:
Originally Posted by Jeff Gilchrist View Post
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.
FactorEyes is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 13:25.

Wed Apr 14 13:25:50 UTC 2021 up 6 days, 8:06, 0 users, load averages: 1.19, 1.51, 1.82

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.