mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2010-10-18, 14:12   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Default 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?
R.D. Silverman is offline   Reply With Quote
Old 2010-10-19, 01:10   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,281 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2010-10-19, 01:52   #3
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

7FB16 Posts
Default

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
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.
frmky is offline   Reply With Quote
Old 2010-10-19, 04:38   #4
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
Raman is offline   Reply With Quote
Old 2010-10-19, 06:48   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Default

Quote:
Originally Posted by frmky View Post
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
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........
R.D. Silverman is offline   Reply With Quote
Old 2010-10-19, 06:51   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by frmky View Post
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
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?
R.D. Silverman is offline   Reply With Quote
Old 2010-10-19, 07:11   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2010-10-19, 07:26   #8
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

40628 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
schickel is offline   Reply With Quote
Old 2010-10-19, 07:48   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-10-19, 07:53   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23A416 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2010-10-19, 11:22   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default

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.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bad LL-D Success Rate TheMawn Data 14 2014-10-13 20:19
SNFS polynomial with very low yield ryanp Factoring 9 2013-04-03 06:33
Distributed finishing for 2,1870L R.D. Silverman Cunningham Tables 64 2011-02-27 21:39
ggnfs sieving yield wierdness jrk Factoring 10 2009-05-07 17:41
EFF prize and error rate 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.