mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Sierpinski/Riesel Base 5

Reply
 
Thread Tools
Old 2007-04-22, 03:05   #265
Citrix
 
Citrix's Avatar
 
Jun 2003

3·521 Posts
Default

Quote:
Originally Posted by geoff View Post

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

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
Citrix is offline   Reply With Quote
Old 2007-04-25, 12:50   #266
Cruelty
 
Cruelty's Avatar
 
May 2005

2×809 Posts
Default

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.
Cruelty is offline   Reply With Quote
Old 2007-04-25, 15:44   #267
thommy
 
thommy's Avatar
 
Dec 2006

1000012 Posts
Default

Quote:
Originally Posted by Cruelty View Post
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
thommy is offline   Reply With Quote
Old 2007-04-26, 04:32   #268
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

100100001012 Posts
Default

Quote:
Originally Posted by Cruelty View Post
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.
geoff is offline   Reply With Quote
Old 2007-05-06, 00:25   #269
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

22058 Posts
Default 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
geoff is offline   Reply With Quote
Old 2007-05-06, 06:49   #270
Cruelty
 
Cruelty's Avatar
 
May 2005

2·809 Posts
Default

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
Cruelty is offline   Reply With Quote
Old 2007-05-06, 13:43   #271
em99010pepe
 
em99010pepe's Avatar
 
Sep 2004

54168 Posts
Default

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
em99010pepe is offline   Reply With Quote
Old 2007-05-07, 08:12   #272
ltd
 
ltd's Avatar
 
Apr 2003

14048 Posts
Default

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
ltd is offline   Reply With Quote
Old 2007-05-07, 12:28   #273
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

81D16 Posts
Default

Speed up of about 4% on Core2Duo E4300 running sr1sieve on both cores.
(k = 55 and k = 105)
Flatlander is offline   Reply With Quote
Old 2007-05-08, 01:44   #274
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

115710 Posts
Default

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.
geoff is offline   Reply With Quote
Old 2007-05-08, 04:33   #275
ltd
 
ltd's Avatar
 
Apr 2003

11000001002 Posts
Default

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
ltd is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Very Prime Riesel and Sierpinski k robert44444uk Open Projects 587 2016-11-13 15:26
Sierpinski/ Riesel bases 6 to 18 robert44444uk Conjectures 'R Us 139 2007-12-17 05:17
Sierpinski/Riesel Base 10 rogue Conjectures 'R Us 11 2007-12-17 05:08
Sierpinski / Riesel - Base 23 michaf Conjectures 'R Us 2 2007-12-17 05:04
Sierpinski / Riesel - Base 22 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.