mersenneforum.org A multiple k/c sieve for Sierpinski/Riesel problems
 Register FAQ Search Today's Posts Mark Forums Read

2007-04-22, 03:05   #265
Citrix

Jun 2003

3·521 Posts

Quote:
 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.
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

Quote:
 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.

Last fiddled with by Citrix on 2007-04-22 at 03:30

 2007-04-25, 12:50 #266 Cruelty     May 2005 2×809 Posts Do srsieve and sr(x)sieve remove algebraic factors? I have received following messages while sieving with srsieve: Code: WARNING: 4*3^n-1 has algebraic factors.
2007-04-25, 15:44   #267
thommy

Dec 2006

1000012 Posts

Quote:
 Originally Posted by Cruelty Do srsieve and sr(x)sieve remove algebraic factors? I have received following messages while sieving with srsieve: Code: 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.

Last fiddled with by thommy on 2007-04-25 at 15:44

2007-04-26, 04:32   #268
geoff

Mar 2003
New Zealand

100100001012 Posts

Quote:
 Originally Posted by Cruelty Do srsieve and sr(x)sieve remove algebraic factors? I have received following messages while sieving with srsieve: Code: 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.

 2007-05-06, 00:25 #269 geoff     Mar 2003 New Zealand 22058 Posts sr1sieve 1.0.23, sr2sieve 1.4.40 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: Code:  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
 2007-05-06, 06:49 #270 Cruelty     May 2005 2·809 Posts 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 Last fiddled with by Cruelty on 2007-05-06 at 06:51
 2007-05-06, 13:43 #271 em99010pepe     Sep 2004 54168 Posts 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
 2007-05-07, 08:12 #272 ltd     Apr 2003 14048 Posts 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
 2007-05-07, 12:28 #273 Flatlander I quite division it     "Chris" Feb 2005 England 81D16 Posts Speed up of about 4% on Core2Duo E4300 running sr1sieve on both cores. (k = 55 and k = 105)
 2007-05-08, 01:44 #274 geoff     Mar 2003 New Zealand 115710 Posts 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: Code:  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: Code: 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.
 2007-05-08, 04:33 #275 ltd     Apr 2003 11000001002 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post robert44444uk Open Projects 587 2016-11-13 15:26 robert44444uk Conjectures 'R Us 139 2007-12-17 05:17 rogue Conjectures 'R Us 11 2007-12-17 05:08 michaf Conjectures 'R Us 2 2007-12-17 05:04 michaf Conjectures 'R Us 49 2007-12-17 05:03

All times are UTC. The time now is 14:56.

Mon Aug 3 14:56:29 UTC 2020 up 17 days, 10:43, 0 users, load averages: 1.63, 1.56, 1.57