Quartic: Parameters

[R.D. Silverman]

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+??

[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.

[bsquared]

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+

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.

[jasonp]

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

[R.D. Silverman]

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.

[bsquared]

Originally Posted by bsquared

Here were the parameters for 2,925+

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:

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.

[R.D. Silverman]

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:

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.....

[bsquared]

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:

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.

[R.D. Silverman]

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:

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.

[fivemack]

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.