A multiple k/c sieve for Sierpinski/Riesel problems

[geoff]

Lavalamp has found a serious bug affecting srsieve versions 0.5.0 to 0.6.6.

The bug could cause factors for a sequence to be missed if both of the following conditions occur:

1. The sequence k*b^n+c has both odd and even exponents n in the sieve.
2. The subsequence base b^Q selected by srsieve has an odd exponent Q.

The first condition is easy to check, for sequences k*2^n+/-1 it applies to k that are multiples of 3. But the only way to check the second condition is probably to re-run srsieve using the original sieve file and parameters, and look for a message like:

`Split X base b sequences into Y base b^Q subsequences.'

If the exponent Q is odd then the bug might have affected the sequence. If the exponent Q is even, or if no message was printed, then the bug didn't affect the sequence.

Any missed factors will divide terms k*b^n+c with even n.

If anyone is faced with spending a large amount of CPU time searching for factors missed by this bug, let me know the details of the sieve by PM or email and I might be able to narrow the search space further.

This bug didn't affect any version of sr[125]sieve.

[BlisteringSheep]

Originally Posted by BlisteringSheep

Geoff, There's a compilation error in mulmod-ppc64.c, line 8, undeclared variable 'p'. I think it's just a copy-and-paste, where the function parameter is named 'b' and and should be 'p' instead. At least that's the change I made. :)

I suppose I should said this was against sr1sieve-1.2.0?

[geoff]

Originally Posted by BlisteringSheep

Geoff, There's a compilation error in mulmod-ppc64.c, line 8, undeclared variable 'p'. I think it's just a copy-and-paste, where the function parameter is named 'b' and and should be 'p' instead. At least that's the change I made. :)

Thanks, I'll fix it in the next release.

FYI, here's some startup info for v1.1.12 and v1.2.0 on a 970MP:

I don't expect the sr1sieve 1.2.x and sr2sieve 1.6.x versions to benefit the PPC64 yet, any change in speed so far is purely accidental :-)

[BlisteringSheep]

Originally Posted by geoff

I don't expect the sr1sieve 1.2.x and sr2sieve 1.6.x versions to benefit the PPC64 yet, any change in speed so far is purely accidental :-)

I didn't expect any speedup either. :) I mainly wanted to let you know that there also wasn't any slowdown, and also to let you see the step methods, etc., it was choosing

Keep up the good work! One question: is there a test suite like sr5check for sr1sieve?

[geoff]

Originally Posted by BlisteringSheep

Keep up the good work! One question: is there a test suite like sr5check for sr1sieve?

I will upload one on the next day or two. If you need something now you could convert the sr5check.txt to NewPgen format using `srfile -g sr5check.txt' then run `sr1sieve -i sr5check.txt -p 100e6 -P 150e6 -f factors.txt' on each of the individual .npg files.

[Cruelty]

Under linux x64, latest versions of both sr1 and sr2 do not print benchmark for "giant step" using -vv switch...

[geoff]

Originally Posted by BlisteringSheep

One question: is there a test suite like sr5check for sr1sieve?

I have uploaded an archive sr1check.zip in the same directory as the sr1sieve source. There are instructions in the README.

Originally Posted by Cruelty

Under linux x64, latest versions of both sr1 and sr2 do not print benchmark for "giant step" using -vv switch...

There is only one giant step method for x86-64 now, so no need for a benchmark.

[BlisteringSheep]

Originally Posted by geoff

I have uploaded an archive sr1check.zip in the same directory as the sr1sieve source. There are instructions in the README.

Thanks. Everything tested out fine, both with "make check" and with the sr1check files.

Is there any thing I could do to help you (tests to run, measurements to gather, etc.)? I've been working with some small projects that use sr1sieve instead of my normal sr2sieve. I'm always glad to run any tests you'd like of any of your programs or variants on any of my different PowerPCs.

[geoff]

This version has a new -j or --sobistrator switch will make sr2sieve behave in a similar way to JJsieve or proth_sieve, for compatibility with Sobistrator:

• Checkpoints will be written to SoBStatus.dat, including a kp/s speed measured using elapsed time.

• If no range is given on the command line, or if the range given matches the one in SoBStatus.dat, work will resume from SoBStatus.dat. If the range given on the command line is different to the one in SoBStatus.dat then the one given on the command line will be used and a warning given.

• After the current range finishes, subsequent ranges will be read from nextrange.txt.

• Factors will be written to fact.txt and duplicates to factexcl.txt (these file names can be overridden with the -f and -D switches.)

Idealy it should be possible to start a range with JJsieve and continue it with `sr2sieve -j -s', and vice versa.

[mdettweiler]

Originally Posted by geoff

This version has a new -j or --sobistrator switch will make sr2sieve behave in a similar way to JJsieve or proth_sieve, for compatibility with Sobistrator:

• Checkpoints will be written to SoBStatus.dat, including a kp/s speed measured using elapsed time.

• If no range is given on the command line, or if the range given matches the one in SoBStatus.dat, work will resume from SoBStatus.dat. If the range given on the command line is different to the one in SoBStatus.dat then the one given on the command line will be used and a warning given.

• After the current range finishes, subsequent ranges will be read from nextrange.txt.

• Factors will be written to fact.txt and duplicates to factexcl.txt (these file names can be overridden with the -f and -D switches.)

Idealy it should be possible to start a range with JJsieve and continue it with `sr2sieve -j -s', and vice versa.

Is it compatible with Rieselator, too?

[axn]

Originally Posted by Anonymous

Is it compatible with Rieselator, too?

Should be, on account of the fact that you can specify different file name instead of RieselStatus.dat (need to set it as SobStatus.dat, I guess). Everything else stays the same.

EDIT:- I would even say that Sobistrator and Rieselator are interchangeable !!