Idea for faster sieve

Citrix · 2007-05-12, 00:15

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.

paulunderwood · 2007-05-12, 09:14

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

VJS · 2007-05-12, 13:22

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<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?

Joe O · 2007-05-12, 13:55

Quote:

(Assuming n-range is directly proportional to speed.)

It's not!

Citrix · 2007-05-12, 15:00

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<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?

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.

Citrix · 2007-05-12, 15:39

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.

Citrix · 2007-05-12, 23:49

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

Citrix · 2007-05-13, 21:49

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

thommy · 2007-05-13, 22:08

"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.

Citrix · 2007-05-13, 22:10

A graph of above.

Citrix · 2007-05-13, 22:13

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.

2007-05-12, 00:15	#1
Citrix Jun 2003 11001010101₂ 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 2·2,333 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, 23:49	#7
Citrix Jun 2003 1,621 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, 22:10	#10
Citrix Jun 2003 1,621 Posts	A graph of above. Attached Thumbnails

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Windows 10 in Ubuntu, good idea, bad idea, or...?	jasong	jasong	8	2017-04-07 00:23
Idea (as always)	Dubslow	Forum Feedback	7	2016-12-02 14:26
Advantage of lattice sieve over line sieve	binu	Factoring	3	2013-04-13 16:32
idea ?	science_man_88	Homework Help	0	2010-04-23 16:33
An Idea	ThomRuley	Lone Mersenne Hunters	5	2003-07-15 05:51

2007-05-12, 13:22	#3
VJS Dec 2004 453₈ 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<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?

2007-05-12, 15:39	#6
Citrix Jun 2003 655₁₆ 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-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.