mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-02-18, 12:25   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default 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+??
R.D. Silverman is offline   Reply With Quote
Old 2009-02-18, 13:04   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2009-02-18, 15:05   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×19×59 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post


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.
bsquared is offline   Reply With Quote
Old 2009-02-18, 15:38   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

353410 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2009-02-18, 18:19   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-02-18, 18:55   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×19×59 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
bsquared is offline   Reply With Quote
Old 2009-02-18, 20:47   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.....
R.D. Silverman is offline   Reply With Quote
Old 2009-02-18, 20:57   #8
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·19·59 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
bsquared is offline   Reply With Quote
Old 2009-02-18, 22:19   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-02-18, 23:24   #10
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

637910 Posts
Default 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
fivemack is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
mmff parameters MattcAnderson Operazione Doppi Mersennes 2 2015-07-08 15:28
YAFU cli parameters VolMike YAFU 8 2012-10-03 14:18
Don't fear the quartic fivemack Factoring 6 2011-12-12 05:08
SNFS 200 parameters JoeCrump Factoring 3 2009-12-06 14:50
ECM parameters for RSA Spider Factoring 24 2006-06-05 23:42

All times are UTC. The time now is 04:09.

Thu Jan 28 04:09:48 UTC 2021 up 56 days, 21 mins, 1 user, load averages: 3.22, 3.11, 3.10

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