20070512, 00:15  #1 
Jun 2003
3^{2}×5^{2}×7 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 p1'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 p1, 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 p1 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 p1 (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 p1 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 p1 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. 
20070512, 09:14  #2 
Sep 2002
Database er0rr
2·1,723 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 20070512 at 09:53 
20070512, 13:22  #3 
Dec 2004
299_{10} 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" p1. 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 nrange is directly proportional to speed.) One could "sieve" between 14M<n<15M for all smooth factors to 2^62 very quickly before they are prp'ed for the first time. I'm more curious about how much of a speed increase you would expect? 
20070512, 13:55  #4  
Aug 2002
3·5^{2}·7 Posts 
Quote:


20070512, 15:00  #5  
Jun 2003
3^{2}×5^{2}×7 Posts 
Quote:
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" p1." Could you describe this, so I know if I am talking about the same thing or not. Last fiddled with by Citrix on 20070512 at 15:04 

20070512, 15:39  #6 
Jun 2003
3^{2}×5^{2}×7 Posts 
Anyother speed up of this method is that you do not have to store factorization of p1 etc, all you need to store is the factorization of array x, which you can re use over and over again.

20070512, 23:49  #7 
Jun 2003
1575_{10} 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 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 20070513 at 00:34 
20070513, 21:49  #8 
Jun 2003
1575_{10} 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 20070513 at 21:54 
20070513, 22:08  #9 
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 n1 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. 
20070513, 22:10  #10 
Jun 2003
3^{2}·5^{2}·7 Posts 
A graph of above.

20070513, 22:13  #11 
Jun 2003
3^{2}·5^{2}·7 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Windows 10 in Ubuntu, good idea, bad idea, or...?  jasong  jasong  8  20170407 00:23 
Idea (as always)  Dubslow  Forum Feedback  7  20161202 14:26 
Advantage of lattice sieve over line sieve  binu  Factoring  3  20130413 16:32 
idea ?  science_man_88  Homework Help  0  20100423 16:33 
An Idea  ThomRuley  Lone Mersenne Hunters  5  20030715 05:51 