mersenneforum.org > Math Sieve of Eratosthenes
 Register FAQ Search Today's Posts Mark Forums Read

 2022-09-10, 07:56 #45 User140242   Jul 2022 22×13 Posts 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).
 2022-09-28, 07:04 #46 User140242   Jul 2022 22×13 Posts 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.
2022-09-28, 08:20   #47
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3×5×683 Posts

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

Last fiddled with by LaurV on 2022-09-28 at 08:35

2022-09-28, 13:10   #48
bsquared

"Ben"
Feb 2007

612 Posts

Quote:
 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

Last fiddled with by bsquared on 2022-09-28 at 13:22 Reason: Trying newer code

 2022-09-28, 13:31 #49 User140242   Jul 2022 22×13 Posts 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.
2022-09-28, 14:41   #50
bsquared

"Ben"
Feb 2007

72118 Posts

Quote:
 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:

elapsed time = 15.3575
ans = 4118054813

elapsed time = 210.2783
ans = 37607912018

elapsed time = 2.0205
ans = 4118054813

elapsed time = 28.9238
ans = 37607912018

2022-09-28, 15:08   #51
User140242

Jul 2022

22·13 Posts

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

2022-09-28, 15:25   #52
bsquared

"Ben"
Feb 2007

612 Posts

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

2022-09-29, 05:32   #53
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3·5·683 Posts

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

 2022-09-30, 18:46 #54 Jean Penné     May 2004 FRANCE 2·5·61 Posts Sieving of (k*b^n+c)/d 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é
 2022-10-22, 07:13 #55 Citrix     Jun 2003 37·43 Posts You can use mtsieve to sieve k*b^n+c and sieve 2 to d-1 and then from d+1 to max.

 Similar Threads Thread Thread Starter Forum Replies Last Post cseizert Programming 8 2016-10-27 05:55 binu Factoring 3 2013-04-13 16:32 XYYXF Computer Science & Computational Number Theory 91 2013-01-19 12:19 Raman Programming 4 2009-01-19 17:12 jchein1 Homework Help 6 2007-08-27 13:51

All times are UTC. The time now is 08:45.

Sat Nov 26 08:45:25 UTC 2022 up 100 days, 6:13, 0 users, load averages: 0.92, 0.91, 0.91