10^263-1 sieving

[R.D. Silverman]

Originally Posted by Andi47

I will take 40-42 (A side)

I will start sieving on Jan 7th or 8th, but I want to grab one of the low ranges which (presumably?) take less memory due to the lower alim, as long as these ranges are available. (please correct me if I'm wrong about memory useage.) (these huge GNFSes are almost maxing out what is the highest memory usage for the siever to run (almost) invisible on my office box, i.e. to not slow down other programs too much)

I am unfamiliar with (is this msieve or GGNFS?) the application
specific terminology.

May I suggest that we ALL use a non-application specfic terminology
for these discussions instead of the application specific abbreviations and
TLA's? e.g. linear factor base bound, algebraic factor base bound,
sieve region size, linear large prime bound, etc. etc...

I have a *proof* (similar to the one I published for line sieving) that
the smaller special q's should have a LARGER sieve region and that the
size of the sieve region should gradually decrease as q increases.
Note that the yield rate decreases as q decreases.

The rate of decrease should be proportional to the rate of decrease
in the yield rate, with the proportionality constant being a certain
eigenvalue that pops out of the calc-of-variations optimization problem.
Unlike for line sieving, I don't have a geometric interpretation for the
value of this eigenvalue.

I realize of course that in practice one can not implement such a gradual
decrease because sieving works fastest (owing to how fast computers &
compilers can actually address memory) when the sieve region size is a
power of 2. However, one can implement a decreasing step function
for the sieve region size.

I am guessing from context that 'alim' is somehow related to sieve region
size?? If so, the smaller q's should have a larger 'alim'.

Why?

Because the yield rate is higher for smaller q, and my published proof
shows that it is better to do more sieving where the yield rate is higher.
This should be intuititively obvious.

[Andi47]

Originally Posted by R.D. Silverman

I am guessing from context that 'alim' is somehow related to sieve region
size?? If so, the smaller q's should have a larger 'alim'.

Why?

Because the yield rate is higher for smaller q, and my published proof
shows that it is better to do more sieving where the yield rate is higher.
This should be intuititively obvious.

GGNFS requires alim to be smaller or equal than q if sieving on the algebraic side, and rlim to be smaller or equal than q if sieving on the rational side.

[R.D. Silverman]

Originally Posted by Andi47

GGNFS requires alim to be smaller or equal than q if sieving on the algebraic side, and rlim to be smaller or equal than q if sieving on the rational side.

You still have not DEFINED 'alim'........

[henryzz]

Originally Posted by R.D. Silverman

You still have not DEFINED 'alim'........

algebraic factor base limit

[R.D. Silverman]

Originally Posted by henryzz

algebraic factor base limit

Ah. So it is not related to the size of the sieve region....

My comments about the size of the sieve region still apply.
Memory requirements should DECREASE as q increases.

Also, my siever sieves the entire factor base, regardless of the
special-q value. Sieving of the larger primes in the factor base
only takes a small fraction of the run time. I see no reason
to restrict what you call alim to be a function of the q values.
I use a static value for the size of both factor bases throughout
the sieving of all the q values. Note also that I use values of special q
that are inside the factor base.... I find that the increased yield rate more
than compensates for the extra duplicates you get this way.

OTOH:

Note that my siever does require more memory than what I have seen
reported for GGNFS. Currently, for 7,277+ with factor base bounds
of 35 million for both the linear and algebraic factor bases, and a large
prime bound of 800 million, my siever requires about 382Mbytes of
memory per instance.

[J.F.]

35-40M is done. Fivemack, would you mind checking the result? Like Xyzzy, I also did some scripting to automate the process (generating jobs, poly input, postprocessing and such), and I just want to make sure everything is ok.

Reserving 42-50M.

[fivemack]

I've checked the result (at least: there is a cliff in the distribution of primes in the right place in each file so you've been changing alim and q0 in harmony, the largest large primes are the right size, msieve doesn't give 1400000 'wrong relation' errors); thanks for the calculations, and carry on!

[Xyzzy]

for i in $(seq 30000000 10000 30990000); do ./gnfs-lasieve4I15e -r poly -f ${i} -c 10000 -o ${i}r && chmod 400 ${i}r; done

Our updated script is below. The "-w" is important. We had a problem using large numbers with "seq" because they were output in scientific notation. We have one distro with "seq" that exhibits this behavior and one that does not. We just happen to prefer the distro that does the scientific notation stuff. Plus, this script is a little easier to edit when it is time to resume a job.

for i in $(seq -w 0 99); do ./gnfs-lasieve4I15e -r poly -f 30${i}0000 -c 10000 -o 30${i}0000r && chmod 400 30${i}0000r; done

[Xyzzy]

We installed our preferred system with just the console stuff plus all of our special tools. The hard drive was formatted as EXT3 with the "largefile4" option. Roughly 110MiB of the space used are results files.

$ df -h
Filesystem            Size  Used Avail Use% Mounted on
/dev/sda1             466G  754M  442G   1% /
tmpfs                 2.9G     0  2.9G   0% /lib/init/rw
udev                   10M   44K   10M   1% /dev
tmpfs                 2.9G     0  2.9G   0% /dev/shm

$ df -i
Filesystem            Inodes   IUsed   IFree IUse% Mounted on
/dev/sda1             119264   26361   92903   23% /
tmpfs                 747112       2  747110    1% /lib/init/rw
udev                  747112     421  746691    1% /dev
tmpfs                 747112       1  747111    1% /dev/shm

[bsquared]

Originally Posted by Andi47

I will take 40-42 (A side)

I'll take the R side.

[Syd]

Reserving 60-65, both sides