mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2022-09-10, 07:56   #45
User140242
 
Jul 2022

22·13 Posts
Default

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 is offline   Reply With Quote
Old 2022-09-28, 07:04   #46
User140242
 
Jul 2022

22×13 Posts
Default

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.
User140242 is offline   Reply With Quote
Old 2022-09-28, 08:20   #47
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2·47·109 Posts
Default

Quote:
Originally Posted by User140242 View Post
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
LaurV is offline   Reply With Quote
Old 2022-09-28, 13:10   #48
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×17×73 Posts
Default

Quote:
Originally Posted by User140242 View Post
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
bsquared is offline   Reply With Quote
Old 2022-09-28, 13:31   #49
User140242
 
Jul 2022

1101002 Posts
Default

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.
User140242 is offline   Reply With Quote
Old 2022-09-28, 14:41   #50
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·17·73 Posts
Default

Quote:
Originally Posted by User140242 View Post
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
bsquared is offline   Reply With Quote
Old 2022-09-28, 15:08   #51
User140242
 
Jul 2022

1101002 Posts
Default

Quote:
Originally Posted by bsquared View Post

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.
User140242 is offline   Reply With Quote
Old 2022-09-28, 15:25   #52
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×17×73 Posts
Default

Quote:
Originally Posted by User140242 View Post
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.
bsquared is offline   Reply With Quote
Old 2022-09-29, 05:32   #53
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

280616 Posts
Default

Quote:
Originally Posted by bsquared View Post
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...
LaurV is offline   Reply With Quote
Old 2022-09-30, 18:46   #54
Jean Penné
 
Jean Penné's Avatar
 
May 2004
FRANCE

2·307 Posts
Default 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é
Jean Penné is online now   Reply With Quote
Old 2022-10-22, 07:13   #55
Citrix
 
Citrix's Avatar
 
Jun 2003

2×797 Posts
Default

You can use mtsieve to sieve k*b^n+c and sieve 2 to d-1 and then from d+1 to max.
Citrix is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New GPU accelerated sieve of Eratosthenes cseizert Programming 8 2016-10-27 05:55
Advantage of lattice sieve over line sieve binu Factoring 3 2013-04-13 16:32
Thinking of a new project: Sieve of Eratosthenes XYYXF Computer Science & Computational Number Theory 91 2013-01-19 12:19
Sieve of Eratosthenes Raman Programming 4 2009-01-19 17:12
Sieve of Eratosthenes jchein1 Homework Help 6 2007-08-27 13:51

All times are UTC. The time now is 16:23.


Wed Dec 7 16:23:48 UTC 2022 up 111 days, 13:52, 0 users, load averages: 0.92, 0.93, 0.92

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔