mersenneforum.org Quartic: Parameters
 Register FAQ Search Today's Posts Mark Forums Read

 2009-02-18, 12:25 #1 R.D. Silverman     Nov 2003 746010 Posts Quartic: Parameters I have reserved 6,335-, but have run into some difficulty. I may not be able to do it. With a Linear Factor base bound of 58.8M (3.5 million primes), and a Algebraic bound of 12.2M (800K primes), my code requires 580Mbytes to run one instance. I am not sure that these bounds are optimal. I intend to try LFB of 4 and 4.5 million primes, and an AFB of only 600K to see what effect that has. Note that increasing the AFB to over 1 million primes (even 2 million!) has very little effect on yield and indeed slows the siever way down, (presumably from many false hits on the algebraic side) The sextic that I am using only requires 380Mbytes to run with factor bases of 2 million primes on each side! The difference is due to the fact that the norms for the quartic are rather small. Thus, many potential candidates get revealed during the initial sieve. Factoring the norms is done via resieve, and because of the large number of candidates, the hash tables that store the primes during resieve become quite large. Quartics have always required more memory for me than quintics or sextics for this reason. However, 6,335- is the first quartic I have done that requires greater than 500Mbytes of DRAM. About half my machines are dual core, but have only 1GB DRAM. Thus, I can only run one instance on these machines. This will slow me way down. May I ask: What parameters were used for 2,860+ and 2,925+??
 2009-02-18, 13:04 #2 jasonp Tribal Bullet     Oct 2004 3·1,181 Posts Maybe you should consider handling the resieving in batches; I was also concerned about getting so many hits that the choice is either using up too much memory or ignoring sieve reports, and in that case a good solution is to use a fixed-size structure and possibly resieve the same interval multiple times. In cases where you get a huge number of hits, the latency of the sieving is a small effect anyway.
2009-02-18, 15:05   #3
bsquared

"Ben"
Feb 2007

3·1,193 Posts

Quote:
 Originally Posted by R.D. Silverman May I ask: What parameters were used for 2,860+ and 2,925+??
Here were the parameters for 2,925+

Code:
n: 5688016226807831064044758914315660452874822911732021084198059235416884717188698621609682118091029853096510590721423450325168014323277731989012600970545984976786513017985287740035850980703007762825496957935313661984801
c4: 1
c3: -1
c2: 1
c1: -1
c0: 1
Y1: -1
Y0: 49039857307708443467467104868809893875799651909875269632
type: snfs
skew: 1
rlambda: 2.6
alambda: 2.6
lpbr: 31
lpba: 29
mfbr: 62
mfba: 58
alim: 25000000
rlim: 150000000
alim is the AFB bound, rlim is the LFB bound, so both are quite a bit bigger than what you report for 6,335-.

As a point of reference, the 32bit ggnfs lattice siever on windows requires ~380MB to run one instance with either rlim=150M or rlim=100M.

 2009-02-18, 15:38 #4 jasonp Tribal Bullet     Oct 2004 3·1,181 Posts Code: rlambda: 2.6 alambda: 2.6 lpbr: 31 lpba: 29 mfbr: 62 mfba: 58 alim: 25000000 rlim: 150000000 By way of explanation: [ra]lim = rational / algebraic factor base limits [ra]lambda = multiplier of the number of bits in [ra]lim that triggers an attempt to trial factor a sieve value lpb[ra] = bits in large primes mfb[ra] = number of bits left over in rational/algebraic sieve values after trial division, that triggers factorization with different algorithms
2009-02-18, 18:19   #5
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by jasonp Maybe you should consider handling the resieving in batches; I was also concerned about getting so many hits that the choice is either using up too much memory or ignoring sieve reports, and in that case a good solution is to use a fixed-size structure and possibly resieve the same interval multiple times. In cases where you get a huge number of hits, the latency of the sieving is a small effect anyway.
Certainly possible. But I have no time at the moment to rewrite my code.

2009-02-18, 18:55   #6
bsquared

"Ben"
Feb 2007

3×1,193 Posts

Quote:
 Originally Posted by bsquared Here were the parameters for 2,925+ Code: n: 5688016226807831064044758914315660452874822911732021084198059235416884717188698621609682118091029853096510590721423450325168014323277731989012600970545984976786513017985287740035850980703007762825496957935313661984801 c4: 1 c3: -1 c2: 1 c1: -1 c0: 1 Y1: -1 Y0: 49039857307708443467467104868809893875799651909875269632 type: snfs skew: 1 rlambda: 2.6 alambda: 2.6 lpbr: 31 lpba: 29 mfbr: 62 mfba: 58 alim: 25000000 rlim: 150000000 alim is the AFB bound, rlim is the LFB bound, so both are quite a bit bigger than what you report for 6,335-. As a point of reference, the 32bit ggnfs lattice siever on windows requires ~380MB to run one instance with either rlim=150M or rlim=100M.
Sorry, I had an error in the rlim=150M case. For rlim=150M, ggnfs requires ~495MB of main memory and ~380MB for rlim=100M.

I tried your number as well and with these parameters:

Code:
rlambda: 2.6
alambda: 2.6
lpbr: 30
lpba: 28
mfbr: 60
mfba: 56
alim: 12200000
rlim: 58800000
ggnfs needs ~243MB for one instance of the 15e siever (32768x16384 sieve region).

By a very rough estimate, this job would need about 13e6 seconds to finish sieving on a single 3GHz CPU (woodcrest 5160, using the amd64 optimized 64bit binary), or about 152 days. I have no idea how that compares to your siever - I'd love to hear about a comparison, and would be willing to do one myself if I had your code or a binary.

Last fiddled with by bsquared on 2009-02-18 at 19:05

2009-02-18, 20:47   #7
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by bsquared Sorry, I had an error in the rlim=150M case. For rlim=150M, ggnfs requires ~495MB of main memory and ~380MB for rlim=100M. I tried your number as well and with these parameters: Code: rlambda: 2.6 alambda: 2.6 lpbr: 30 lpba: 28 mfbr: 60 mfba: 56 alim: 12200000 rlim: 58800000 ggnfs needs ~243MB for one instance of the 15e siever (32768x16384 sieve region). By a very rough estimate, this job would need about 13e6 seconds to finish sieving on a single 3GHz CPU (woodcrest 5160, using the amd64 optimized 64bit binary), or about 152 days. I have no idea how that compares to your siever - I'd love to hear about a comparison, and would be willing to do one myself if I had your code or a binary.

I can provide my code, but it is written for Windows; It includes MASM
assembly. It appears that GGNFS is much more space efficient than mine.

One major change that would decrease my space usage is to store primes
during the resieve into unused portions of the sieve array, rather than
keeping separate hash tables. Also, I suspect that GGNFS uses
Kleinjung-style lattice sieving while mine uses Pollard-style. The latter
requires computation of the sieve boundaries for each prime sub-lattice.
This takes space. And is probably slightly slower.

One of these days, I may recode my siever. If ever I can find the time.....

2009-02-18, 20:57   #8
bsquared

"Ben"
Feb 2007

3·1,193 Posts

Quote:
 Originally Posted by R.D. Silverman I can provide my code, but it is written for Windows; It includes MASM assembly. It appears that GGNFS is much more space efficient than mine. One major change that would decrease my space usage is to store primes during the resieve into unused portions of the sieve array, rather than keeping separate hash tables. Also, I suspect that GGNFS uses Kleinjung-style lattice sieving while mine uses Pollard-style. The latter requires computation of the sieve boundaries for each prime sub-lattice. This takes space. And is probably slightly slower. One of these days, I may recode my siever. If ever I can find the time.....
Chris Monico's website says:
Quote:
 Jens Franke's lattice siever is included...
so I think you're right.

I'll PM you with contact info for your code then, thanks. Hopefully I can get it to compile somehow....

- ben.

Last fiddled with by bsquared on 2009-02-18 at 20:58

2009-02-18, 22:19   #9
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by bsquared Sorry, I had an error in the rlim=150M case. For rlim=150M, ggnfs requires ~495MB of main memory and ~380MB for rlim=100M. I tried your number as well and with these parameters: Code: rlambda: 2.6 alambda: 2.6 lpbr: 30 lpba: 28 mfbr: 60 mfba: 56 alim: 12200000 rlim: 58800000 ggnfs needs ~243MB for one instance of the 15e siever (32768x16384 sieve region). By a very rough estimate, this job would need about 13e6 seconds to finish sieving on a single 3GHz CPU (woodcrest 5160, using the amd64 optimized 64bit binary), or about 152 days. I have no idea how that compares to your siever - I'd love to hear about a comparison, and would be willing to do one myself if I had your code or a binary.
2,860+ and 6,335- are very close in size. Does anyone have the parameters
used for 2,860+?

I can trivially provide a windows binary.

 2009-02-18, 23:24 #10 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 22×32×179 Posts Parameters for 2+860 Code: n: 37360387694127510821188227330071397026603186697457573335739293573903838744149624314101536096673587305145124803665871388272088935341673817060806283660516368010552176540988879158504987136934647756081 c4: 1 c3: -1 c2: 1 c1: -1 c0: 1 Y1: -1 Y0: 5986310706507378352962293074805895248510699696029696 type: snfs skew: 1 rlambda: 2.6 alambda: 2.6 lpbr: 30 lpba: 29 mfbr: 60 mfba: 58 alim: 12000000 rlim: 60000000 So almost exactly the same parameters as you. Sieved rational side Q=42M .. 60M getting 58.8M relations, it took 9.1 million CPU-seconds with the Kleinjung siever. Last fiddled with by fivemack on 2009-02-18 at 23:25

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Operazione Doppi Mersennes 2 2015-07-08 15:28 VolMike YAFU 8 2012-10-03 14:18 fivemack Factoring 6 2011-12-12 05:08 JoeCrump Factoring 3 2009-12-06 14:50 Spider Factoring 24 2006-06-05 23:42

All times are UTC. The time now is 00:14.

Tue Nov 30 00:14:10 UTC 2021 up 129 days, 18:43, 0 users, load averages: 1.76, 1.31, 1.22