20101018, 14:12  #1 
Nov 2003
1110001000000_{2} 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 specialq 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? 
20101019, 01:10  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{2}·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. 
20101019, 01:52  #3 
Jul 2003
So Cal
7FB_{16} Posts 
Yep, that's low. Using
Code:
n: <the number> 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 
20101019, 04:38  #4  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
Quote:
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 specialq 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 

20101019, 06:48  #5  
Nov 2003
16100_{8} Posts 
Quote:
Tracking down missed relations can be a real nuisance. The problem could be anywhere........ 

20101019, 06:51  #6  
Nov 2003
2^{6}×113 Posts 
Quote:
rlambda? 

20101019, 07:11  #7  
Nov 2003
2^{6}·113 Posts 
Quote:
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 30bit special q's before collecting enough relations to finish. Last fiddled with by R.D. Silverman on 20101019 at 07:12 

20101019, 07:26  #8  
"Frank <^>"
Dec 2004
CDP Janesville
4062_{8} Posts 
Quote:
Quote:


20101019, 07:48  #9  
Nov 2003
2^{6}×113 Posts 
Quote:
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 rewrite my siever. Whether I can still do 2,1870L will depend on whether I can solve the yield problems. 

20101019, 07:53  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23A4_{16} 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 quartics230 are as hard as sextics270. 
20101019, 11:22  #11 
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 continuedfractionbased 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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Bad LLD Success Rate  TheMawn  Data  14  20141013 20:19 
SNFS polynomial with very low yield  ryanp  Factoring  9  20130403 06:33 
Distributed finishing for 2,1870L  R.D. Silverman  Cunningham Tables  64  20110227 21:39 
ggnfs sieving yield wierdness  jrk  Factoring  10  20090507 17:41 
EFF prize and error rate  S485122  PrimeNet  15  20090116 11:27 