A multiple k/c sieve for Sierpinski/Riesel problems

[geoff]

Some changes made in version 1.8.6 to improve performance for sieves with a large number of sequences had the opposite effect on smaller sieves. This came to notice after the dual Sierpinski sieve reduced in size from 4 to 3 sequences. Hopefully this version will strike a better balance.

[lavalamp]

I've tried the latest 64 bit srsieve version, but it sometimes crashes on Vista 64 bit SP1.

When the k is very large, srsieve 0.6.13 crashes, but for lower ks it looks to be OK. The 32 bit version of 0.6.13 runs fine.

These are the reported problem details:

Problem signature:
  Problem Event Name:	APPCRASH
  Application Name:	srsieve-x86_64-windows.exe
  Application Version:	0.0.0.0
  Application Timestamp:	493aac3a
  Fault Module Name:	srsieve-x86_64-windows.exe
  Fault Module Version:	0.0.0.0
  Fault Module Timestamp:	493aac3a
  Exception Code:	c0000005
  Exception Offset:	0000000000002e3f
  OS Version:	6.0.6001.2.1.0.256.1
  Locale ID:	2057
  Additional Information 1:	1ada
  Additional Information 2:	da552492854acfcc74f88a7a3c746c6d
  Additional Information 3:	760a
  Additional Information 4:	5c49b1674939be78afe310fbcc681f15

The k I'm sieving for is over 100 trillion (which is why I'm not using sr1sieve since I'd have to start sieving with p>k but the large bulk of the factors are <k), the sieve depth is a bit over 250 billion.

[geoff]

Originally Posted by lavalamp

I've tried the latest 64 bit srsieve version, but it sometimes crashes on Vista 64 bit SP1.

Thanks for the report, I will have a look at the info you posted and see if I can find what is wrong, but it could be that I will just add a warning to use the 32-bit version instead. If you are able to produce the crash with the Linux version I will give it more priority, but if it is just the Win64 version then the most likely cause is a mingw-w64 compiler bug. sr2sieve and sr1sieve have been through a long and painful process of trial and error that resulted in many mingw-w64 compiler bugs being worked around, but srsieve code hasn't had that treatment.

The k I'm sieving for is over 100 trillion (which is why I'm not using sr1sieve since I'd have to start sieving with p>k but the large bulk of the factors are <k), the sieve depth is a bit over 250 billion.

The latest version of sr1sieve doesn't have this restriction, you can use it to sieve k*b^n+/-1 with p < k, provided p > b.

[lavalamp]

Originally Posted by geoff

The latest version of sr1sieve doesn't have this restriction, you can use it to sieve k*b^n+/-1 with p < k, provided p > b.

Oh excellent, this should bring a nice speed boost.

As for testing on Linux, I'm afraid I don't have any Linux boxes. Every so often I have a dabble, but I always come back to Windows in the end.

[geoff]

This version incorporates a workaround for a possible problem with variable length automatic (stack-allocated) arrays when compiling with the mingw-w64 (GCC 4.3.0) compiler.

I don't know whether this is the bug that caused Lavalamp's crash, or even if srsieve is affected by this problem at all, but it doesn't cost much to use the workaround just in case.

[geoff]

This version fixes a serious bug that potentially affected all 64-bit executables for srsieve versions 0.6.4 to 0.6.14. This bug could find bogus factors, and thus incorrectly eliminate some terms from the output sieve file, if ALL of these conditions were met:

1. Version 0.6.4-14 of any 64-bit srsieve executable was used, and

2. The -c (--check) switch was NOT used, and

3. k > 65535 OR |c| > 65535 for ANY sequence k*b^n+c in the sieve.

If the -c switch was used to check the factors then srsieve would have stopped with an error message when the first incorrect factor was found. However there is no mention of the -c switch in the README, so chances are that this feature wasn't used.

As from version 0.6.15 all factors will be checked by default unless the new --no-check switch is used.


What to do if you are affected:
-------------------------------

Don't despair! It is actually quite easy to work out exactly which if any terms the bug incorrectly eliminated, even if you no longer have the original sieve files.

For a start, the only bogus factors p will be in the range 257 < p < LIM, where LIM is the greatest value of k or |c| for the sequences k*b^n+c sieved.

Also, factors above 2^32 were not affected, so if any value of k or |c| is greater than 2^32 then just set LIM = 2^32 (LIM ~ 4295e6).


Procedure to discover any missing terms:
----------------------------------------

1. Start a new sieve and sieve up to p=LIM with the BUG-AFFECTED srsieve executable (http://www.geocities.com/g_w_reynolds/srsieve/bug64.zip). Save the output file in ABC format (use the -w switch for srsieve), and rename it to OLD.abc

2. Start a new sieve and sieve up to p=LIM with srsieve 0.6.15 or later, or with any 32-bit srsieve executable. Save the output file in ABC format (-w switch) and rename it to NEW.abc

3. Create a third ABC file containing terms in NEW.abc that are missing from OLD.abc. In unix you can do this with the commands

tail -n+2 OLD.abc | cat - NEW.abc | sort -k2,2 -n | uniq -u > MISSED.abc


Now you can continue sieving MISSED.abc, then PRP test what remains in the usual way or merge it with the original sieve if that is still in progress.

If necessary you can email me a copy of the bug-affected sieve file and I will create the file of missing terms for you. If the file is small then send the whole thing in .zip format. If is is large (megabytes), send me just the list of sequences k*b^n+c and the range of n.


Geoffrey Reynolds. (See srsieve README for email address).

[geoff]

This version fixes an array overrun bug that can cause a segfault during sieving, although is more likely to show up at the end of a sieve range when memory is freed, perhaps with an error message from the free() library function. This bug affected versions 1.8.7-1.8.8.

Also included in this version is a new command-line switch: `sr2sieve --log-factors ...' will cause new factors to be reported in sr2sieve.log with a timestamp.

[geoff]

This version fixes a bug where memory is freed twice when a sequence is removed from the sieve, which happens when a factor is found for each remaining term of the sequence.

The exact effect of this bug is hard to predict, but it can cause memory corruption and so it is possible that those results produced after a sequence is removed are invalid.

Thanks to Jayson King for reporting this bug and locating the problem in the source. Jayson also found the bug affecting 64-bit executables that was fixed in version 0.6.15.

[geoff]

This version fixes an array overrun that can occur when using a subsequence base b^Q with Q < 16. This bug was introduced in version 1.8.6, and the most likely symptom is a crash during initialization.

The source also fixes a problem compiling recent versions on Intel Mac, and has some changes to allow compilation on Haiku OS.

[geoff]

This version reorganises the algorithm to allow an earlier short-circuit when all terms in the sieve are quadratic non-residues. If there are x sequences in the sieve then this happens about 1 time in 2^x.

It should be faster when there are 4 or fewer sequences, but unfortunately it is a little slower when there are more than that, so use 1.8.10 instead for now.

[mdettweiler]

Geoff, could you possibly enable the ability to save directly to a sieve file in sr2sieve? If memory serves, it's in sr5sieve, so I'm guessing it wouldn't be hard; it would definitely be quite handy for those of us doing smaller (i.e. non-distributed) sieve efforts for which removing the factors from the sieve file is an extra and somewhat superfluous step.