A multiple k/c sieve for Sierpinski/Riesel problems

[geoff]

Originally Posted by lavalamp

Out of extreme, never ending, curiosity, how come there are four srsieves? They all seem to do quite similar things, though obviously they are optimised for particular areas, sr2sieve is more optimised for multiple ks whereas sr1sieve is optimised for a single k, but that could be dealt with using a simple if/else to call a one function or another.

It is a long term goal to combine all the srsieve programs back into one executable and release it as srsieve 1.0.0. There is no technical reason this can't be done, it is just a question of programmer effort. At the moment I find it easier to deal with the program by maintaining 4 seperate but simpler programs than a single more complex one.

[geoff]

These versions fix a problem introduced in verisons 1.7.0/1.3.0 that caused the elapsed time statistic reported in the checkpoint file and at the end of a range to be inaccurate.

[geoff]

I have built 64-bit Windows srsieve executables for testing.

Because of a bug in GCC 4.3.0 I have provided two executables compiled with different compiler optimisation levels. This bug was avoided in sr1sieve and sr2sieve by reducing the optimisation level from -O2 to -O1, without much affect on performance. However in srsieve the performance loss will probably be more severe because it has more critical code in C rather than assembly.

The compiler bug might not affect srsieve at all, but if it does it is hard to predict what the result will be, a segfault is possible. Please treat both executables with caution and check some results against the 32-bit or Linux versions.

Testing it on the http://www.geocities.com/sr5sieve/sr5check.zip data would be a good idea too: `srsieve sr5check.txt -f -p 100e6 -P 150e6' should find 10533 new factors.

[Cruelty]

Geoff,
What is the reason for versions 1.7.11 (sr2sieve) and 1.3.6 (sr1sieve)?

[geoff]

Originally Posted by Cruelty

Geoff,
What is the reason for versions 1.7.11 (sr2sieve) and 1.3.6 (sr1sieve)?

These versions fix a bug reported by Chuck Lasher that could cause junk characters to be printed at the end of some screen messages . It showed up when a long file name was specified as argument to the -C switch in sr1sieve.

[geoff]

This version has a new switch `-X --skip-cubic' which causes cubic and higher power residue tests to be skipped. This makes the algorithm more like that used by srsieve 0.6.x, and so might be faster and use less memory when there are very many sequences in the sieve or when the n-range is too short.

If you are currently sieving with srsieve 0.6.x because you have found it to be faster than sr2sieve, please try out sr2sieve -X and let me know whether it is faster.

[geoff]

Fixes a bug introduced in version 1.7.5 that allowed an invalid argument to the `-p --pmin' switch. This version ensures that the start of the p-range is above the level of the greatest k value in the sieve. (Sieving below this level needs to be done with srsieve instead).

There are new Makefile options for Intel Macs: `make ARCH=x86-osx' will build a 32-bit executable. `make ARCH=x86-64-osx' will build a 64-bit executable. Thanks to Michael Tughan for these contributions. (These options have also been added to the source for sr1sieve-1.3.7).

[geoff]

I realised that sieving the dual-form sequence b^n+/-k was actually faster than sieving the equivalent standard-form sequence k*b^n+/-1.

For k*b^n+c, previous versions used stored powers b,b^2,b^3,... to solve the equation b^n = -c/k. This was efficient when k=1 (dual form), but when |c|=1 (standard form) a modular inverse was required to find 1/k for each sequence.

This version uses the previous method for dual forms, but for standard forms it instead uses stored powers 1/b,1/b^2,1/b^3,... to solve the equation 1/b^n = -k/c, and so only one modular inverse is required to find 1/b instead of one per sequence to find 1/k.

Sieves with a large number of sequences and a small range of n will benefit most. With this change the current combined SoB.dat (15 sequences) is about 2% faster and the current sr5data.txt (214 sequences) about 12% faster.

The trade-off is that dual and standard forms can no longer be sieved together. There is a new switch `-d --dual'. If this switch is used then .dat format files will be interpreted in dual form (as 1*2^n+/-k instead of k*2^n+/-1). Without this switch dual-form ABCD files will be rejected.

[geoff]

This version changes the way process priority is set in an attempt to cope with the changing scheduling behaviour on machines with adjustable CPU frequency. This might change again, I am open to suggestions.

This version will no longer change priority by default. The meaning of the -z and -Z switches has changed to:

 -zz sets lowest priority (Linux nice 20, Windows IDLE)
 -z  sets low priority (Linux nice 10, Windows BELOW_NORMAL)
 -Z  sets high priority (Linux nice -10, Windows ABOVE_NORMAL)
 -ZZ sets highest priority (Linux nice -20, Windows HIGH)

My Linux system doesn't allow programs started by normal users to raise their priority, so -Z and -ZZ have no effect in this case. I believe that -zz will cause the CPU frequency to be lowered on some systems.

[mdettweiler]

Originally Posted by geoff

This version changes the way process priority is set in an attempt to cope with the changing scheduling behaviour on machines with adjustable CPU frequency. This might change again, I am open to suggestions.

This version will no longer change priority by default. The meaning of the -z and -Z switches has changed to:

 -zz sets lowest priority (Linux nice 20, Windows IDLE)
 -z  sets low priority (Linux nice 10, Windows BELOW_NORMAL)
 -Z  sets high priority (Linux nice -10, Windows ABOVE_NORMAL)
 -ZZ sets highest priority (Linux nice -20, Windows HIGH)

My Linux system doesn't allow programs started by normal users to raise their priority, so -Z and -ZZ have no effect in this case. I believe that -zz will cause the CPU frequency to be lowered on some systems.

So, does this mean that you now have to specify the -z or-zz options, or else it will get set to normal priority, across the board?

[geoff]

Originally Posted by Anonymous

So, does this mean that you now have to specify the -z or-zz options, or else it will get set to normal priority, across the board?

In practice, yes. (Actually it doesn't get set to normal priority, it just doesn't set the priority at all. So without -z, -Z, etc. sr2sieve will run at the same priority as the process that started it. In most cases that will be normal priority).

If anyone has a better plan then this is the time to say so. The problem with the old way of doing it (idle priority by default) is that I am getting a lot of questions about why sr2sieve is running slower on 64-bit operating systems than on 32-bit systems, which is because the (newer) 64-bit OS lowers the CPU frequency in situations that the (older) 32-bit OS doesn't.