mersenneforum.org 1870L : Yield Rate
 Register FAQ Search Today's Posts Mark Forums Read

 2010-10-18, 14:12 #1 R.D. Silverman     Nov 2003 11100010000002 Posts 1870L : Yield Rate I have updated my siever to handle larger large primes, and recompiled with a larger sieve region per special q. I am a bit concerned about the yield and wonder if I might still have bugs. With factor base bounds of: 14.5 million for the algebraic side (925K ideals) and 86M for the rational (5 million ideals), large prime bounds of just under 30 bits on the algebraic side and just under 31 bits on the rational, I am getting a yield of about 4 relations per special q for q near 60 million. This seems too low. The sieve region is 9K x 18K for each special q. Sieving one special-q takes 17 seconds on my laptop (2.4Ghz i5) and about 13 seconds on a 3.2 Ghz core. The siever requires 850Mbytes of memory. Can anyone with experience with large(r) quartics suggest whether my yield rates might be too low?
 2010-10-19, 01:10 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22·2,281 Posts I'll try to sieve with similar parameters. For the similarly difficult 5,815L, the yield was lowish... so instead of sieving over a huge range we set out to sieve with lasieve16e (if I am not mistaken, that's over a 32Kx64K area; correct me here, guys, who remembers better); it was as fast (rel/s) as 15e and had 3 times the yield. I am not sure what yields Raman is getting for his new reservations for the 2,2334L/M (nominal snfs diff.234) and for 10,590M and 2,985- (nominal snfs diff.236 and 237), but if he has his cluster available only until April it will appear to be a miracle if he finishes even one of these. He's got five.
 2010-10-19, 01:52 #3 frmky     Jul 2003 So Cal 7FB16 Posts Yep, that's low. Using Code: n: skew: 1.41 c4: 1 c3: -2 c2: -6 c1: 12 c0: -4 Y1: 2^93 Y0: -(2^187+1) alim: 14500000 rlim: 86000000 lpba: 30 lpbr: 31 mfba: 60 mfbr: 62 alambda: 2.6 rlambda: 2.6 which I believe matches your parameters, and sieving using 14e (which has a slightly smaller sieve area of 16K x 8K), I sieved the range q = 60M to 60M+500. There were 27 special-q in the range, and it found 229 relations at a rate of 0.64 sec/relation on the slow Opteron (a Core 2 would get under 0.4 sec/relation). This is about 8.5 rels/special-q using a smaller sieve region.
2010-10-19, 04:38   #4
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

Quote:
 Originally Posted by Batalov I am not sure what yields Raman is getting for his new reservations for the 2,2334L/M (nominal snfs diff.234) and for 10,590M and 2,985- (nominal snfs diff.236 and 237), but if he has his cluster available only until April it will appear to be a miracle if he finishes even one of these. He's got five.
For 5,415+ I sieved upto 190 million range of special-q upon that rational side, from (110M-300M) with help of gnfs-lasieve4I15e. I presume that was anyway oversieved, 170M range would have been enough in order to build a matrix.

I got matrix of 14332614 rows, it will take upto 11 more days in order to finish off, at this moment. It is 68% done.

For rest of numbers, I only expect around 220 million range of special-q each, upon every number (on the rational side) over that average scale.

For 5,415+ I made use of following parameters:
Code:
n: 409070648357903876177895795121676558808515790800199330391475022633084608638318069844299258901345227277398314550159052254251424043657457443453213674736966457975676435972876537687720951817693078563918161701
m: 10339757656912845935892608650874535669572651386260986328125
c4: 1
c3: -1
c2: 1
c1: -1
c0: 1
skew: 1
type: snfs
rlim: 200000000
alim: 33554431
lpbr: 31
lpba: 29
mfbr: 62
mfba: 58
rlambda: 2.6
alambda: 2.6

2010-10-19, 06:48   #5
R.D. Silverman

Nov 2003

161008 Posts

Quote:
 Originally Posted by frmky Yep, that's low. Using Code: n: skew: 1.41 c4: 1 c3: -2 c2: -6 c1: 12 c0: -4 Y1: 2^93 Y0: -(2^187+1) alim: 14500000 rlim: 86000000 lpba: 30 lpbr: 31 mfba: 60 mfbr: 62 alambda: 2.6 rlambda: 2.6 which I believe matches your parameters, and sieving using 14e (which has a slightly smaller sieve area of 16K x 8K), I sieved the range q = 60M to 60M+500. There were 27 special-q in the range, and it found 229 relations at a rate of 0.64 sec/relation on the slow Opteron (a Core 2 would get under 0.4 sec/relation). This is about 8.5 rels/special-q using a smaller sieve region.
This is what I suspected..... Can you send/post the relations that it found?
Tracking down missed relations can be a real nuisance. The problem could
be anywhere........

2010-10-19, 06:51   #6
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by frmky Yep, that's low. Using Code: n: skew: 1.41 c4: 1 c3: -2 c2: -6 c1: 12 c0: -4 Y1: 2^93 Y0: -(2^187+1) alim: 14500000 rlim: 86000000 lpba: 30 lpbr: 31 mfba: 60 mfbr: 62 alambda: 2.6 rlambda: 2.6 which I believe matches your parameters, and sieving using 14e (which has a slightly smaller sieve area of 16K x 8K), I sieved the range q = 60M to 60M+500. There were 27 special-q in the range, and it found 229 relations at a rate of 0.64 sec/relation on the slow Opteron (a Core 2 would get under 0.4 sec/relation). This is about 8.5 rels/special-q using a smaller sieve region.
For you inputs: what are the last 4 parameters? mfba, mfbr, alambda,
rlambda?

2010-10-19, 07:11   #7
R.D. Silverman

Nov 2003

26·113 Posts

Quote:
 Originally Posted by R.D. Silverman For you inputs: what are the last 4 parameters? mfba, mfbr, alambda, rlambda?
I suspect that I may have to give up on 2,1870L.

My siever was first written 7 years ago.... It was not designed to handle
numbers of this size; it is very memory inefficient, and uses Pollard
style sieving: one computes a reduced basis for each prime in the factor
bases, yielding a skewed sieve region for each one. The boundaries of
the region need to be computed... This is overhead that is not incurred
by the Kleinjung approach.

The bucket sieving is also a memory pig;

I fear that I may have to redesign/rewrite the siever completely.
However, the only remaining Cunningham composites within reach of
my resources (even with a more efficient siever) are 2,1870L, 2,1870M.

A complete rewrite would take many months (I have real work).

In order to finish 2,1870L, I will need to track down why my yield rate
is low. Otherwise, a simple calculation shows that I will run out of
30-bit special q's before collecting enough relations to finish.

Last fiddled with by R.D. Silverman on 2010-10-19 at 07:12

2010-10-19, 07:26   #8
schickel

"Frank <^>"
Dec 2004
CDP Janesville

40628 Posts

Quote:
 Originally Posted by R.D. Silverman For you inputs: what are the last 4 parameters? mfba, mfbr, alambda, rlambda?
Here's a quote from Chris Monico's draft documentation for the GGNFS suite:
Quote:
 Originally Posted by cmonico ‘rlambda’ describes how far from perfect sieve values we should actually look for good relations. It is essentially a fudge factor, and higher means more sieve entries will be closely examined. If this is too low, you’ll miss too many potential good relations. If it’s too high, the siever will spend too much time looking at locations which do not give a good location. Generally, good values are somewhere between 1.5 and 2.6 (maybe even a little larger - I haven’t done any very large factorizations yet, so I don’t have enough experience to say for sure). You guessed it - ‘alambda’ is the same thing on the algebraic side.

2010-10-19, 07:48   #9
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by Batalov I'll try to sieve with similar parameters. For the similarly difficult 5,815L, the yield was lowish... so instead of sieving over a huge range we set out to sieve with lasieve16e (if I am not mistaken, that's over a 32Kx64K area; correct me here, guys, who remembers better); it was as fast (rel/s) as 15e and had 3 times the yield.

32K x 64K is 2 Gbytes! That is just the sieve array. It does not
include storage for the factor bases, polynomial roots, etc. I thought that
the 16e siever fit in just over 1 Gbyte?

Run time should be proportional to the sieve area.... A larger sieve area
means that the coordinates of the lattice points (a,b) will be larger on
average. Thus one would expect norm(a,b) to be somewhat larger and
the yield rate (per unit area) lower for a larger region. Yet you say
that the 16e had 3 times the yield of 15e and was every bit as fast.
This puzzles me.

It is clear that I need to completely re-write my siever. Whether I can
still do 2,1870L will depend on whether I can solve the yield problems.

 2010-10-19, 07:53 #10 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23A416 Posts Even KF siever gets strained on quartics above 230. Around 230 is where the 16e siever becomes a good contender (it is a bit slower, but yields not 2 but almost 3 times more, and that allows to sieve in a lesser range and with twice lower FB limits; and given that, it goes on par if not better than 15e). Also around 230, LP limits will have to be doubled (viz. 30/32). For "normal" numbers, 16e becomes useful only around 270. So there, again, roughly quartics-230 are as hard as sextics-270.
 2010-10-19, 11:22 #11 jasonp Tribal Bullet     Oct 2004 3×1,163 Posts The KF siever does not explicitly declare the entire rectangular (c,d) plane when sieving by vectors; instead it uses a continued-fraction-based method to determine the approximate region of the (c,d) plane where each factor base entry will hit next, then bucket sorts based on that. While I haven't examined the source closely, it probably fills up a small rectangle of the (c,d) plane at a time.

 Similar Threads Thread Thread Starter Forum Replies Last Post TheMawn Data 14 2014-10-13 20:19 ryanp Factoring 9 2013-04-03 06:33 R.D. Silverman Cunningham Tables 64 2011-02-27 21:39 jrk Factoring 10 2009-05-07 17:41 S485122 PrimeNet 15 2009-01-16 11:27

All times are UTC. The time now is 12:19.

Fri Oct 23 12:19:20 UTC 2020 up 43 days, 9:30, 0 users, load averages: 1.41, 1.38, 1.37