mersenneforum.org Idea for faster sieve
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-12, 00:15 #1 Citrix     Jun 2003 110001010112 Posts Idea for faster sieve I would like to propose a new idea for the sieve programs. Instead of looking at all primes (p%2==1) if we looked at primes that were p%4==1 only. Then we would test only 1/2 the primes and would only find 1/2 the factors in a given range. But, we would be able to test the range faster as primes with smooth p-1's can be tested faster due to SPH algorithm. So the extra 2 will make things faster. Also we don't need to test all factors of p-1, only the factors such that the product of these factors is less than 50M (worst case scenario). This should already have been implemented... Some of the problems people have raised with this method: 1) Some of the factors are missed, as only a fraction will be tested. 2) We will reach 2^62 very soon and very few factors will be found. 3) Difficult to keep track of which primes have already been tested. 4) Difficult to generate the smooth p-1 primes. Advantages: We can find more factors everyday and thus eliminate more candidates, saving PRP tests and increasing chances of finding primes. The projects may finish faster. Method: Overcomes the 4 problems stated above. 1) Assuming we are going to 50M, so we generate a array x of smooth numbers for which we want all our p-1 (of primes used) to be multiples of. 2) During the sieve of Eratosthenes step, first you sieve using array x and set value =1 of all values that have p-1 as smooth. Then you sieve further and see if any values are prime. (As normally most programs do). 3)Sieve the .dat file using these selected primes. This method solves problem 4. Problem 2, is not relevant as there are more than enough primes of this type under 2^62. I verified this using a simple program I wrote. Problem 3: This can be solved by doing the inverse of step 2. During the sieve of Eratosthenes step, first you sieve using array x and set value =0 of all values that have p-1 as smooth. Then you sieve further and see if any of the other values are prime. (As normally most programs do). Problem 1: Once this method has been used for finding the faster factors till 2^62, we can switch back to look for other factors. I would really request some one (people who have access to source of proth_sieve or jjsieve) to implement this, it should not take much time. It will save alot of tests and help find primes faster. Any other thoughts/ problems/ suggestions... Thank you.
 2007-05-12, 09:14 #2 paulunderwood     Sep 2002 Database er0rr E0A16 Posts Weight watchers cake Take a cake. Cut it half. Half the cake means half the calories. Eat half the cake and because it is half the calories you can eat the other half of the cake too Last fiddled with by paulunderwood on 2007-05-12 at 09:53
 2007-05-12, 13:22 #3 VJS     Dec 2004 13×23 Posts Cirtix, What type of speed increase are you expecting from this implementation? If it's not more than 400% I would say that it's a bad idea. I'm assuming that your implementation is basically a "arrayed" p-1. The only reason I say this is that the factor density basically halves for every double in p as you know. In addition we will eventually have to go back and "resieve" those ranges to pick up the missed ones. Also the "resieve" will not be any faster than it would have been without your first brush implementation. The only way I see this as a benifit is for projects like SoB where n is very large. In this case one may be able to test a very small range of n using your method with great speed. (Assuming n-range is directly proportional to speed.) One could "sieve" between 14M
2007-05-12, 13:55   #4
Joe O

Aug 2002

52510 Posts

Quote:
 (Assuming n-range is directly proportional to speed.)
It's not!

2007-05-12, 15:00   #5
Citrix

Jun 2003

62B16 Posts

Quote:
 Originally Posted by VJS Cirtix, What type of speed increase are you expecting from this implementation? If it's not more than 400% I would say that it's a bad idea. I'm assuming that your implementation is basically a "arrayed" p-1. The only reason I say this is that the factor density basically halves for every double in p as you know. In addition we will eventually have to go back and "resieve" those ranges to pick up the missed ones. Also the "resieve" will not be any faster than it would have been without your first brush implementation. The only way I see this as a benifit is for projects like SoB where n is very large. In this case one may be able to test a very small range of n using your method with great speed. (Assuming n-range is directly proportional to speed.) One could "sieve" between 14M

The main reason for implementing this algorithm is to save PRP tests. Lars had posted on one of the threads that we had done over 10,000 tests for which a factor was later found. I would like to find these easy factors first and avoid doing some of these tests, thus finding primes faster.

If we find primes faster and have fewer k's in the sieve, the whole project will then speed up.

I don't know how fast the project will become overall (sieve+prp), but if we save 10,000 tests we are saving almost 100 days of PRP work.

I expect the sieve client to be atleast 20 times faster. BTW what is "I'm assuming that your implementation is basically a "arrayed" p-1." Could you describe this, so I know if I am talking about the same thing or not.

Last fiddled with by Citrix on 2007-05-12 at 15:04

 2007-05-12, 15:39 #6 Citrix     Jun 2003 1,579 Posts Anyother speed up of this method is that you do not have to store factorization of p-1 etc, all you need to store is the factorization of array x, which you can re use over and over again.
 2007-05-12, 23:49 #7 Citrix     Jun 2003 1,579 Posts I analyzed my method further. Code: Looked at the first 2500 primes from 10^15 to...10^15+89353 and found. We can look at 84% of the primes by doing only 30% of the work We can look at 75% of the primes by doing only 17% of the work We can look at 65% of the primes by doing only 12% of the work We can look at 50% of the primes by doing only 7% of the work We can look at 22% of the primes by doing only 1.8% of the work We can look at 4% of the primes by doing only 0.30% of the work Clearly 10% of the factors take almost 2/3 of the time the program runs. I see no point to test these numbers .. now and even later. I think we should only look for the 75% of the factors which can be tested really fast. It would be best to divide sieving into stage 1 and stage2. In stage 1 we can look at only 25% of the primes and find the easy factors first. (upto 2^62) Then we go back in stage 2 and look at the other 50%. No need to look at the remaining 25% or so.. Last fiddled with by Citrix on 2007-05-13 at 00:34
 2007-05-13, 21:49 #8 Citrix     Jun 2003 1,579 Posts Some more data. Code: If we look at 97% of the primes only, we can find 0.97 times many more factors everyday. Cutoff:10000 If we look at 91% of the primes only, we can find 1.82 times many more factors everyday. Cutoff:4090 If we look at 85% of the primes only, we can find 2.55 times many more factors everyday. Cutoff:2300 If we look at 80% of the primes only, we can find 3.20 times many more factors everyday. Cutoff:1500 If we look at 76% of the primes only, we can find 3.80 times many more factors everyday. Cutoff:1083 If we look at 72% of the primes only, we can find 4.32 times many more factors everyday. Cutoff:843 If we look at 69% of the primes only, we can find 4.83 times many more factors everyday. Cutoff:671 If we look at 66% of the primes only, we can find 5.28 times many more factors everyday. Cutoff:563 If we look at 63% of the primes only, we can find 5.67 times many more factors everyday. Cutoff:491 If we look at 60% of the primes only, we can find 6.00 times many more factors everyday. Cutoff:421 If we look at 58% of the primes only, we can find 6.38 times many more factors everyday. Cutoff:379 If we look at 55% of the primes only, we can find 6.60 times many more factors everyday. Cutoff:343 If we look at 53% of the primes only, we can find 6.89 times many more factors everyday. Cutoff:317 If we look at 51% of the primes only, we can find 7.14 times many more factors everyday. Cutoff:293 If we look at 49% of the primes only, we can find 7.35 times many more factors everyday. Cutoff:273 If we look at 48% of the primes only, we can find 7.68 times many more factors everyday. Cutoff:263 If we look at 46% of the primes only, we can find 7.82 times many more factors everyday. Cutoff:251 If we look at 44% of the primes only, we can find 7.92 times many more factors everyday. Cutoff:239 If we look at 43% of the primes only, we can find 8.17 times many more factors everyday. Cutoff:229 If we look at 42% of the primes only, we can find 8.40 times many more factors everyday. Cutoff:219 If we look at 41% of the primes only, we can find 8.61 times many more factors everyday. Cutoff:211 If we look at 40% of the primes only, we can find 8.80 times many more factors everyday. Cutoff:203 If we look at 37% of the primes only, we can find 8.88 times many more factors everyday. Cutoff:189 If we look at 36% of the primes only, we can find 9.00 times many more factors everyday. Cutoff:183 If we look at 35% of the primes only, we can find 9.10 times many more factors everyday. Cutoff:179 If we look at 34% of the primes only, we can find 9.18 times many more factors everyday. Cutoff:173 If we look at 34% of the primes only, we can find 9.52 times many more factors everyday. Cutoff:169 If we look at 33% of the primes only, we can find 9.57 times many more factors everyday. Cutoff:165 If we look at 32% of the primes only, we can find 9.60 times many more factors everyday. Cutoff:163 If we look at 31% of the primes only, we can find 9.61 times many more factors everyday. Cutoff:159 If we look at 30% of the primes only, we can find 9.90 times many more factors everyday. Cutoff:155 If we look at 29% of the primes only, we can find 10.15 times many more factors everyday. Cutoff:151 If we look at 28% of the primes only, we can find 10.36 times many more factors everyday. Cutoff:147 If we look at 26% of the primes only, we can find 10.40 times many more factors everyday. Cutoff:141 If we look at 25% of the primes only, we can find 10.50 times many more factors everyday. Cutoff:139 If we look at 25% of the primes only, we can find 10.75 times many more factors everyday. Cutoff:137 If we look at 24% of the primes only, we can find 10.80 times many more factors everyday. Cutoff:133 If we look at 23% of the primes only, we can find 11.04 times many more factors everyday. Cutoff:129 If we look at 21% of the primes only, we can find 11.13 times many more factors everyday. Cutoff:123 If we look at 20% of the primes only, we can find 11.40 times many more factors everyday. Cutoff:121 If we look at 18% of the primes only, we can find 11.52 times many more factors everyday. Cutoff:115 If we look at 17% of the primes only, we can find 11.56 times many more factors everyday. Cutoff:113 If we look at 15% of the primes only, we can find 11.70 times many more factors everyday. Cutoff:109 If we look at 14% of the primes only, we can find 11.90 times many more factors everyday. Cutoff:107 If we look at 13% of the primes only, we can find 12.61 times many more factors everyday. Cutoff:103 If we look at 9% of the primes only, we can find 13.59 times many more factors everyday. Cutoff:93 If we look at 8% of the primes only, we can find 13.60 times many more factors everyday. Cutoff:91 If we look at 5% of the primes only, we can find 14.80 times many more factors everyday. Cutoff:83 If we look at 1% of the primes only, we can find 16.94 times many more factors everyday. Cutoff:69 If we look at 0% of the primes only, we can find 17.2296 many more factors everyday. Cutoff:67 If we look at 0% of the primes only, we can find 17.5604 many more factors everyday. Cutoff:65 If we look at 0% of the primes only, we can find 17.9340 many more factors everyday. Cutoff:63 If we look at 0% of the primes only, we can find 18.4136 many more factors everyday. Cutoff:61 Last fiddled with by Citrix on 2007-05-13 at 21:54
 2007-05-13, 22:08 #9 thommy     Dec 2006 3·11 Posts "If we look at 1% of primes only, we can find 16.94 times many more factors everyday". I cant belive that. So this is all based on: checking if n divides x is faster when n-1 is smooth? Why is that? If you would find 18 times more factors per day, just code that thing and start it on some machines but continue with normal sieve effort. so no real slowdown there (just finding some duplicates) there but more new factors overall. But the idea seems pretty memory consuming, don't think it will turn out faster.
 2007-05-13, 22:10 #10 Citrix     Jun 2003 157910 Posts A graph of above. Attached Thumbnails
2007-05-13, 22:13   #11
Citrix

Jun 2003

1,579 Posts

Quote:
 Originally Posted by thommy checking if n divides x is faster when n-1 is smooth? Why is that?
Thats how the SPH algorithm works.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 8 2017-04-07 00:23 Dubslow Forum Feedback 7 2016-12-02 14:26 binu Factoring 3 2013-04-13 16:32 science_man_88 Homework Help 0 2010-04-23 16:33 ThomRuley Lone Mersenne Hunters 5 2003-07-15 05:51

All times are UTC. The time now is 05:18.

Fri Mar 5 05:18:42 UTC 2021 up 92 days, 1:30, 0 users, load averages: 2.57, 2.40, 2.21