Sieve of Eratosthenes

[User140242]

I don't want to waste anyone's time but I don't have a high-performance PC available. The only comparison I was able to make is on ideone.com and kimwalisch/segmented_bit_sieve gives the result in 1.24s for n=10^9 instead this wheel_sieve gives the result in 0.96s for n=10^9 and modulus 210.


I would like to understand if the sieve is performing, does anyone have a chance to make a comparison for n=10^12 and modulus 2310, input segmented_bit_sieve_wheel(1000000000000,2310).

[User140242]

I renew my request in reference to the post #45, I would need your help to understand if the sieve is fast and how to make it multithreaded. Here you find a version that I think can be used for large numbers and here the theoretical explanation.

Thanks in advance.

[LaurV]

Originally Posted by User140242

The only comparison I was able to make

There are many tools to sieve for primes. Former versions of yafu can also do it (I believe that in the newer versions Ben moved this out like a standalone program?). Can you beat yafu?

[bsquared]

Originally Posted by User140242

I don't want to waste anyone's time but I don't have a high-performance PC available. The only comparison I was able to make is on ideone.com and kimwalisch/segmented_bit_sieve gives the result in 1.24s for n=10^9 instead this wheel_sieve gives the result in 0.96s for n=10^9 and modulus 210.


I would like to understand if the sieve is performing, does anyone have a chance to make a comparison for n=10^12 and modulus 2310, input segmented_bit_sieve_wheel(1000000000000,2310).

The code at that link has different parameters for input to the segmented_bit_sieve_wheel function... it appears to want a start and stop interval, not stop and wheel_size parameters.

But anyway, I tried it. I compiled with icpc -O2 -g

time ./wheel_test
primes count= 5761455
0.095u 0.001s 0:00.29 31.0% 0+0k 0+0io 0pf+0w

compared to

./yafu "primes(0,100000000)"

elapsed time = 0.0114
ans = 5761455

And then with 10^9 / 30 for the second parameter I get

time ./wheel_test
primes count= 50847534
2.174u 0.001s 0:02.79 77.7% 0+0k 440+0io 1pf+0w

compared to

./yafu "primes(0,1000000000)"

elapsed time = 0.1084
ans = 50847534

Ok, so maybe you want larger wheels... lets try 210. changing the n_PB variable to 4 and changing the second function parameter to 10^10 / 210 I get:

time ./wheel_test
primes count= 455052495
20.177u 0.003s 0:20.74 97.2% 0+0k 440+0io 1pf+0w


compared to:

./yafu "primes(0,10000000000)"

elapsed time = 1.1660
ans = 455052511

So. For me to test any further you need to explain better how to use your program to achieve correct results.

Edit:
Nevermind, I didn't see your original link to github, which works like you said and also gives correct results. I was using the stackexchange code you linked to later.

Here are a couple timings for the 2310 wheel. 10^12 will take a while...
time ./wheel_test
primes < 10000000000: 455052511
10.787u 0.010s 0:11.24 95.9% 0+0k 408+0io 1pf+0w

time ./wheel_test
primes < 100000000000: 4118054813
204.513u 0.012s 3:25.03 99.7% 0+0k 408+0io 1pf+0w

[User140242]

In sieve is a modified version of the Eratosthenes sieve with wheel factorization. In practice, the multiples of the primes of the base are not stored. This allows the use of less memory and even if more complex in theory it makes it faster.

In the link of the post #45 there is the version where the arrays C1 and C2 are calculated first this allows to use lower modulus values.
Prime numbers from 0 to n are counted and the input is (n, modulus).

In the first link of post #46 instead there is a version that can be used with larger numbers the input is k_start and k_end where is it k_start=n_start/bW and k_end=n_end/bW+1, but the coefficients are calculated from time to time is a little slower.

[bsquared]

Originally Posted by User140242

In sieve is a modified version of the Eratosthenes sieve with wheel factorization. In practice, the multiples of the primes of the base are not stored. This allows the use of less memory and even if more complex in theory it makes it faster.

Yafu does this too. Multithreading in yafu works by taking the wheel concept a step further. We set up N sieve arrays, each array is a bitvector over one of the residue classes of the wheel parameter. E.g., if we are using 30, then there are 8 arrays:
{1, 31, 61, 91, 121, ...}
{7, 37, 67, 97, 127, ...}
...
{29, 59, 89, 119, 149, ...}

Each thread sieves its own array, and counts set bits in its array when finished. When the interval and wheel size is large, this is very efficient. When they are small it's not as efficient but, we don't care much because when they are small the sieve basically finishes instantly anyway.

New result for 10^12, 2310:
time ./wheel_test
primes < 1000000000000: 37607912018
4342.279u 0.020s 1:12:23.04 99.9% 0+0k 408+0io 1pf+0w


And for comparison:

./yafu "primes(0,10^11)" -threads 1
elapsed time = 15.3575
ans = 4118054813

./yafu "primes(0,10^12)" -threads 1
elapsed time = 210.2783
ans = 37607912018

./yafu "primes(0,10^11)" -threads 8
elapsed time = 2.0205
ans = 4118054813

./yafu "primes(0,10^12)" -threads 8
elapsed time = 28.9238
ans = 37607912018

[User140242]

Originally Posted by bsquared

New result for 10^12, 2310:
...

Well thanks, I was not able to test it for large numbers but obviously by increasing the module there is no advantage the sieve is very slow.

[bsquared]

Originally Posted by User140242

Well thanks, I was not able to test it for large numbers but obviously by increasing the module there is no advantage the sieve is very slow.

You should not be discouraged, your sieve does very well and demonstrates knowledge of several important optimizations. And the 2310 version is definitely the best way to go for a huge interval like 10^12. Kim Walish and I have each put years and thousands of lines of code into our sieves, I show the comparisons just to illustrate what is possible.

[LaurV]

Originally Posted by bsquared

Here are a couple timings...

This was kind of expected, wasn't it? I mean, from the explanation for the Sundaram sieve they give on Wikipedia, you kinda sieve with all composites, while the classical way only sieves with primes. You expect a n/log increasing time. One interesting optimization would be to "tickle" that i+j+2ij in such a way to avoid repeating the sieving process multiple times for the same seed, as much as possible. I assume this is not easy or feasible...

[Jean Penné]

Does somebody knows an efficient program to prime-sieve integers of the form (k*b^n+c)/d ? (d > 1 indeed!)
Thank you by advance!

Jean Penné

[Citrix]

You can use mtsieve to sieve k*b^n+c and sieve 2 to d-1 and then from d+1 to max.