A multiple k/c sieve for Sierpinski/Riesel problems

[Citrix]

Originally Posted by geoff

Another idea like this could be to implement a sieve using the Pollard Rho method. This doesn't guarantee to find all factors, but you could use it to sieve ahead of the main sieve to get the easy factors. It would probably be a lot eastier to implement than SPH.

I am not sure how the pollard Rho will be faster than SPH or baby or giant step method. The wiki page says the run time is the same. Btw, the SPH can be applied to pollard rho also.

edit: Also pollard rho cannot be restricted to a range of n. Though a modification can help.
Read http://citeseer.ist.psu.edu/cache/pa...1computing.pdf
On the other hand Pollard rho can be used for a range of n, if you plan to use SPH, where only the order will be reduced.

Though I could be wrong on this one. Read ( http://www.free-dc.org/forum/showthr...ht=pollard+rho )post #20

yes I see your point. It might work, I am not sure. If the proportion of the factors that get tested is too small then you might quickly reach 2^62 without finding enough to make it worthwhile. Or the lower density of larger primes might mean you quickly reach a lower limit than 2^62 where it becomes faster to go back to normal sieving.

I was thinking smooth values of t, say around a million. So 2^62/2^20 = 2^42 = around 4 trillion values.
I think there are enough values to test for each smooth t. If t is very smooth and the sieve is fast then these 4 trillion values can be tested in the same time it takes to test 1-2 billion values and find the extra factors.

[Cruelty]

Do srsieve and sr(x)sieve remove algebraic factors?
I have received following messages while sieving with srsieve:

WARNING: 4*3^n-1 has algebraic factors.

[thommy]

Originally Posted by Cruelty

Do srsieve and sr(x)sieve remove algebraic factors?
I have received following messages while sieving with srsieve:

WARNING: 4*3^n-1 has algebraic factors.

For n even: 4*3^n-1=(2*3^(n/2)-1)*(2*3^(n/2)+1).
Guess those will not be removed automatically.

[geoff]

Originally Posted by Cruelty

Do srsieve and sr(x)sieve remove algebraic factors?
I have received following messages while sieving with srsieve:

WARNING: 4*3^n-1 has algebraic factors.

No they are not removed. Only some simple algebraic factors are detected by srsieve as a consequence of checking whether any subsequences consist of generalised Fermat numbers, there may well be others that are not detected. sr[125]sieve don't check for any algebraic factors.

[geoff]

Some more improvements to the SSE2 code: mulmods now done in groups of 8 or 16 instead of groups of 4. (32-bit SSE2 machines only).

I don't know whether this is faster on anthing other than the Northwood P4, any benchmarks will be a help.

Here are some times for my 2.9GHz Northwood P4 at p=100e12:

         19k SoB.dat  68k riesel.dat  237k sr5data.txt
         -----------  --------------  ----------------
1.4.39:   293 kp/s     161 kp/s        77 kp/s
1.4.40:   377 kp/s     194 kp/s        85 kp/s

[Cruelty]

I'm sieving 4*3^n-1 using sr1sieve linux.x86-64 executable and the speed increased from 5.84M to 5.95M (~2%).
CPU = C2D 4300 @ 2.4 GHz

[em99010pepe]

I'm sieving 43046721*2^n+1 using sr1sieve and sieve speed decreased from 30.6 Mp/s to 29.2 Mp/s.
CPU = AMD 64 3000 2.0 GHz

[ltd]

Sieving on a PSP only (11K) SoB.dat with a Pentium M (Centrino) with 1.6GHz.

Version 1.4.39: around 350kp/sec
Version 1.4.40: Around 333kp/sec

By the way jjsieve on the same range/dat file combination 331kp/sec

[Flatlander]

Speed up of about 4% on Core2Duo E4300 running sr1sieve on both cores.
(k = 55 and k = 105)

[geoff]

Thanks for the benchmarks everyone, I don't have any solutions for those suffering a slowdown yet, so I'll keep the old versions available for download.

I have discovered that the Windows binary is reporting elapsed time when it should be reporting CPU time. I have fixed this in sr2sieve version 1.4.41.

In sr2sieve 1.4.42 I have implemented some of the ideas from the SSE2 code for other 32-bit machines. It is faster on my P3 but no change on P2, probably because of the slow L2 cache on the P2. Here are some times for my 600MHz Coppermine P3 at p=100e12:

         19k SoB.dat    68k riesel.dat    237k sr5data.txt
         -----------    --------------    ----------------
1.4.40:   92 kp/s        53 kp/s           30 kp/s
1.4.42:  100 kp/s        58 kp/s           31 kp/s

I have put a benchmark program mulmod8.zip here. It measures the speed of the SSE2 vs non-SSE2 mulmods. It would be interesting to see the results for some other machines. Here are results for my 2.9GHz Northwood P4:

length = 1000, iterations = 10000, b = 2, p = 4611686018427387817:
         :  57.812 million mulmods per second.
     CMOV:  54.953 million mulmods per second.
     SSE2: 106.400 million mulmods per second.

[ltd]

Benchmarks for a P3, the Pentium M and a P4 HT 3.06GHz will come on thursday . I have no time now as i am on my way to England to visit a customer the next two days.

Lars