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.

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.

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.

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.

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)
[/code]

Edit:

My [URL="http://www.mersenneforum.org/showthread.php?p=162793#post162793"]ubasic script[/URL] 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.

[quote=Andi47;162799]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)
[/code]

Edit:

My [URL="http://www.mersenneforum.org/showthread.php?p=162793#post162793"]ubasic script[/URL] 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.[/quote]

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.

[QUOTE=Andi47;162799]Ooops, I wanted to post my data for GNFS here, but then I forgot for some reason...[/QUOTE]

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.

[QUOTE=10metreh;166676]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.[/QUOTE]

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 [URL="http://www.mersenneforum.org/showthread.php?t=11438"]gnfs.ub[/URL] 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.

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

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.

[QUOTE=Jeff Gilchrist;166732]Sorry I lied, I am using the 14e siever for the C135's but only needing 15.4M relations.[/QUOTE]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.