srsieve/sr2sieve enhancements

[rob147147]

I've been working on my own implementation of a CUDA version of sr2sieve for some time. Its still very much a work in progress (it only sieves the -1 side atm, so k*b^n-1, and only prints factors to the terminal). On a 2070 MaxQ it can sieve between 3x and 10x faster than a single cpu core on various test files I've tried, and finds all factors in my test cases, but I'm not claiming it is perfect. It could miss factors in other test cases though I hope not.

I push the code updates to my github occasionally but its a bit out of date currently. https://github.com/rob147147/CUDA-Ri...0BranchTesting

-Q varies the number of subsequences. sr2sieve will rewrite a sequence k*b^n-1 as (k*b^r) * b^(Qm) - 1, where n=Q*m + r. So you sieve a greater number of (sub)sequences, over a smaller range (m instead of n). Sometimes it can help to vary this, often not. I don't have any test cases to hand where I noticed a reasonable difference. Will try to dig some up at some point.

[rogue]

Originally Posted by pepi37

PPS sieva?
Running on GPU for base2

I'm not touching ppsieve and srsieve2 will not replace it.

[rebirther]

@rogue:
I have a bigger difference in tests left between srsieve 1.0.5 and srsieve 1.1.4:


with R627 up to 100M (2.5-10k range)

srsieve 1.0.5: 1137188 tests left
srsieve 1.1.4: 1339442 tests left

[rogue]

Originally Posted by rebirther

@rogue:
I have a bigger difference in tests left between srsieve 1.0.5 and srsieve 1.1.4:

with R627 up to 100M (2.5-10k range)

srsieve 1.0.5: 1137188 tests left
srsieve 1.1.4: 1339442 tests left

I'll take a look. Are the sequences to be sieved on the CRUS site?

[rebirther]

Originally Posted by rogue

I'll take a look. Are the sequences to be sieved on the CRUS site?

If you need a file let me know. Its a new started base up to 2.5k for CRUS.

[rogue]

Originally Posted by rebirther

If you need a file let me know. Its a new started base up to 2.5k for CRUS.

I will since I didn't see it on the CRUS page.

[rebirther]

Originally Posted by rogue

I will since I didn't see it on the CRUS page.

Email sent.

[rogue]

The old code is removing algebraic factors that are not removed by the newer code (which was heavily reworked). Although I won't fix srsieve, I will ensure that srsieve2 removes those algebraic factors correctly.

[kuratkull]

I am using s2sieve v2 as a drop in replacement for an in-progress 1.8.11 sieve.
The 1.8.11 has a 65 mil p/sec rate on 4 threads, s2sieve 2 has a 50mil p/sec rate with the exact same arguments.

sr2sieve 1.8.11 -- A sieve for multiple sequences k*b^n+/-1 or b^n+/-k.
Read 11367 terms for 1 sequence from ABCD format file `sr_2.abcd'.
Split 1 base 2 sequence into 32 base 2^36 subsequences.
Wrote 1 Legendre symbol lookup tables to version 1 cache file `cache'.
Loaded Legendre symbol lookup tables for 1 sequences from `cache'.
Resuming from checkpoint pmin=5499307326589 in `checkpoint.txt'.
Expecting to find factors for about 507.80 terms in this range.
sr2sieve 1.8.11 started: 2221074 <= n <= 2300000, 5499307326589 <= p <= 20000000000000
5509220732291 | 39547695*2^2269624-1
p=5513128324607, 65904269 p/sec, 34 factors, 2.8% done, ETA 28 Sep 14:27

sr2sieve 2.0.0 -- A sieve for multiple sequences k*b^n+/-1 or b^n+/-k.
Read 11367 terms for 1 sequence from ABCD format file `sr_2.abcd'.
Split 1 base 2 sequence into 32 base 2^36 subsequences.
Loaded Legendre symbol lookup tables for 1 sequences from `cache'.
Resuming from checkpoint pmin=5484267013231 in `checkpoint.txt'.
Expecting to find factors for about 507.80 terms in this range.
sr2sieve 2.0.0 started: 2221074 <= n <= 2300000, 5484267013231 <= p <= 20000000000000
  5496333170473, 50718759 p/sec, 33 factors, 2.7% done, 0 sec/factor, ETA 29 Sep 09:21

IMPORTANT EDIT: sr2sieve v2 has niceness of 19, while 1.8 has 0, so that was the cause - my cpu was overburdened at the time of the testing.

But after giving ample cpu headroom I am still getting 85 mil p/sec vs 82 mil p/sec against v2

[storm5510]

Originally Posted by rogue

sr2seive 2.0.0 is attached. This version supports k up to 2^64, which required a number of code changes. This version also does additional validation to prevent the building of invalid Legendre tables, which can happen in all older releases. That is likely to happen for k > 2^31, but can happen for k < 2^31...

I tried running this yesterday. There are some items missing, according to the readme file. srsieve.exe and srfile.exe. Other references suggest sr1sieve.exe. I am looking for Windows builds! It would be nice to have all the pieces...

[rogue]

Originally Posted by storm5510

I tried running this yesterday. There are some items missing, according to the readme file. srsieve.exe and srfile.exe. Other references suggest sr1sieve.exe. I am looking for Windows builds! It would be nice to have all the pieces...

I suggest switching from srsieve to srsieve2 (part of the mtsieve distribution). srsieve and srfile are published in a separate post on this thread.