A multiple k/c sieve for Sierpinski/Riesel problems

[geoff]

A new command-line switch `--ladder METHOD' allows the ladder mulmod method to be set manually. E.g. `--ladder gen/6' will force use of the gen/6 method.

The `-d --dual' switch is now optional if the sieve is read from an ABCD format file. If not given, then dual/standard mode will be set according to the form of the first sequence in the file.

[geoff]

This version corrects the way the ABC format file header is written (when using the -w switch), from $a*2^$b+$c to $a*2^$b$c. LLR, Phrot (>= 0.60), and PFGW should now all be able to read ABC files written by srsieve.

[geoff]

This version removes the k < p restriction, so it is now only necessary to sieve k*b^n+/-1 for factors up to p=b with another program before switching to sr1sieve. In earlier versions it was necessary to sieve up to p=max(k,b).

(But in practice it is still a good idea to sieve to at least p=1e6 or so before switching to sr1sieve, as removing more small factors can allow the sequence to be reduced to a smaller set of subsequences).

This change makes it practical to sieve much larger k, but the memory requirements for the Legendre symbol tables have not changed and so it maybe necessary to use the -x switch for large squarefree k.

[Flatlander]

Windows 32 bit.

When running a batch file and exiting with CTRL-C, there is a message:
"Terminate batch job (Y/N)?"
It exits when I press N.
(Workaround, don't press CTRL-C!)

[lavalamp]

If you're running a batch file by double clicking on it, and then when you cancel srsieve and there are no more commands after it, of course the batch file will exit.

You can have the batch file command prompt window stay open though by putting "pause" on a line of its own at the end of the batch file.

[rogue]

Originally Posted by Flatlander

Windows 32 bit.

When running a batch file and exiting with CTRL-C, there is a message:
"Terminate batch job (Y/N)?"
It exits when I press N.
(Workaround, don't press CTRL-C!)

Is that Windows, CygWin, or MSys because that doesn't look like an srsieve prompt?

[Xentar]

Originally Posted by Flatlander

Windows 32 bit.

When running a batch file and exiting with CTRL-C, there is a message:
"Terminate batch job (Y/N)?"
It exits when I press N.
(Workaround, don't press CTRL-C!)

It has nothing to do with srsieve.
It is the usual windows behaviour when running a batch file.

Try the following:
make a batch file, with the following code:
:test
echo blah
goto test

now run this batch file, and press CTRL + C, to interrupt this infinite loop. You will see the same question.

[geoff]

This version has a new command line switch `-x --no-lookup' to compute Legendre symbols as needed instead of precomputing lookup tables. This is normally slower, but saves memory and initialization time when there are many sequences in the sieve or when the k values have large squarefree parts.

There are also new switches `--scale-giant X' and `--min-giant NUM' for manually tuning the baby-step/giant-step ratios. These should not normally be needed, but a scale factor above 1.0 and/or minimum above 1 might help reduce cache thrashing for very large sieves.

[geoff]

This version doesn't double-check duplicate factors unless the `-D --duplicates' switch is used. Previously all factors were passed up to the parent thread which performed a double-check then looked up the entry in the bitmaps to see whether it was a duplicate, and then reported the factor. In this version the child thread checks the bitmaps itself and only passes new factors up to the parent thread.

This might help reduce the multithreading overhead early in the sieve when there are many factors being found.

[geoff]

In this version I have reorganised some of the data structures to reduce L2 cache usage when there are many (100's - 1000's) of sequences in the sieve.

The range of subsequence base exponent Q has also been expanded to allow selection of smaller Q. This should give better results when there are many sequences relative to the range of n. Run with the -vv switch to see a report on the available choices of Q and use the -Q switch to set the value manually.

When sieving large numbers of sequences the algorithm really needs to be changed to allow sequences to be processed in batches that fit into L2 cache.

[geoff]

This version removes a redundant calculation of 1/k mod p in the power residue tests for the dual sieve. The dual algorithm is now identical to the standard one, but with b = 1/b.

There is some new x86/x86_64 code for reducing p mod k (used to compute indices into the Legendre symbol tables) that should be faster for sieves with many k's.