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

 2018-01-24, 20:43 #1 bhelmes     Mar 2016 25×13 Posts Sieve of Eratosthenes A peaceful evening for all, There is an implementation of the sieve of Eratosthenes with use of a heap-construction and a bitwise used helparray availible: http://devalco.de/sieve_of_era.cpp Some few people will understand the construction and perhaps they like it. I got a runtime appr. 80 min for all prime <10^12 and an amazing small use of the memory. By the way, the code is a bit older, but the idea is still nice. Greetings from Eratosthenes Bernhard
2018-01-24, 21:06   #2
bsquared

"Ben"
Feb 2007

1110100010112 Posts

Quote:
 Originally Posted by bhelmes A peaceful evening for all, There is an implementation of the sieve of Eratosthenes with use of a heap-construction and a bitwise used helparray availible: http://devalco.de/sieve_of_era.cpp Some few people will understand the construction and perhaps they like it. I got a runtime appr. 80 min for all prime <10^12 and an amazing small use of the memory. By the way, the code is a bit older, but the idea is still nice. Greetings from Eratosthenes Bernhard
I tried it out and found it created correct counts up to 10^10 (where I stopped it).

The "delete" and "include" stuff in the code had me thinking that the heap size was dynamic; i.e. that you were changing the size of the allocation in the loop (which would be bad). But after a bit more poking around that isn't the case, the size is fixed and elements are swapped around.

All in all, a nice and compact implementation. I've added it to my collection of sieve of eratosthenes implementations that I've collected over the years

Performance wise, there is still some room for improvement:

Code:
primesieve 0 10^12 -t48
Sieve size = 32 kilobytes
100%
Primes  : 37607912018
Seconds : 14.457
Code:
./yafu "primes(0,10^12)" -threads 48

found 83224 sieving primes
elapsed time = 12.1653
37607912018

2018-01-25, 01:45   #3
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by bsquared Performance wise, there is still some room for improvement
Assuming his code is single-threaded, that's about 8x faster per core (notwithstanding the difficulties of efficient multithreading).

 2018-01-25, 02:22 #4 bsquared     "Ben" Feb 2007 3·17·73 Posts Yeah, and it is even better then that at lower upper bounds... 10^12 sized intervals are an ambitious undertaking.
2018-01-25, 03:23   #5
CRGreathouse

Aug 2006

135438 Posts

Quote:
 Originally Posted by bsquared Yeah, and it is even better then that at lower upper bounds... 10^12 sized intervals are an ambitious undertaking.
Definitely! I think it's a solid program.

2018-01-25, 04:10   #6
axn

Jun 2003

34·67 Posts

Quote:
 Originally Posted by CRGreathouse Assuming his code is single-threaded, that's about 8x faster per core (notwithstanding the difficulties of efficient multithreading).
8x slower. His runtime is 80 min, compare to yafu's 12 seconds

EDIT:- Obviously no idea which CPU he used - quite possibly a much older CPU than what b^2 did.

Last fiddled with by axn on 2018-01-25 at 04:11

 2018-01-25, 06:07 #7 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32·101 Posts It's a neat and very small implementation. I also have a collection of sieves and benchmarks. Note bsquared's results for yafu and primesieve are 48 threads. A big plus for yafu and primesieve, but I keep everything single threaded for easier comparison. I've added to my too-long todo list a note to make a web page with results and links to the codes / sources, as well as exact instructions on how to duplicate results (for those that are part of bigger projects). (Or maybe a github project?) Some of these are very small demo code, others quite large. Code: Segmented sieves | 10^9| 10^10| 10^11| 10^12| 10^13 yafu |0.285| 1.876| 20.241| 4m 27.8s| 54m 51s primesieve 5.4.2 |0.119| 1.661| 23.480| 4m 56.0s| 58m 18s MPU 0.66b |0.132| 2.022| 33.620| 6m 46.1s| 91m 46s primegen 0.97 |0.258| 2.750| 33.843| 9m 43.1s| 207m 56s MPU 0.66a |0.289| 3.177| 38.434| 8m 30.6s| 104m 48s MPU 0.41 |0.320| 3.529| 42.971| 9m 28.8s| 119m 3s MPU 0.36 |0.318| 3.531| 42.825| 10m 25.3s| TOeS v2 |0.422| 4.739| 55.283| 10m 41.7s| 121m 3s Roy algo3 v2 |0.435| 5.087| 64.456| 12m 28.0s| 150m 10s Flammenkamp |0.528| 5.937| 79.211| 16m 24.1s| tverniquet |0.643| 6.937| 80.876| 17m 27.7s| Roy algo3 v1 |0.611| 6.949| 77.846| Walisch bit segmnt|0.909| 8.226| 91.691| 19m 9.9s| TOeS v1 |0.778| 8.614| 104.218| Walisch byte sgmnt|0.890| 13.213| 208.519| Monolithic sieves: 10^9 10^10 10^11 10^12 Pari 2.6.2dev 0.998 9.940 1m 36.0s >3 hours MPU 0.36 0.907 12.333 2m 27.1s MPU 0.66 1.005 13.845 2m 55.7s // slower mach Mathisen 1998 1.820 21.197 3m 54.2s BHelmes Heap 1.989 21.813 4m 14.7s // <---- Zakiya 1.737 26.310 6m 34.9s Trivial odd SoE 2.529 30.018 6m 56.0s Lieberman 3.415 35.842 7m 2.5s Last fiddled with by danaj on 2018-01-25 at 06:12
2018-01-25, 07:01   #8
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by axn 8x slower. His runtime is 80 min, compare to yafu's 12 seconds
I meant that primesieve and yafu were about 8x faster, rather than the ~400x they seemed.

2018-01-25, 07:03   #9
CRGreathouse

Aug 2006

176316 Posts

Quote:
 Originally Posted by danaj I've added to my too-long todo list a note to make a web page with results and links to the codes / sources, as well as exact instructions on how to duplicate results (for those that are part of bigger projects). (Or maybe a github project?)
I'd love that.

Do you, by chance, know of any good factoring sieves? PARI has one now but I'm disappointed with its performance.

2018-01-25, 07:31   #10
axn

Jun 2003

34×67 Posts

Quote:
 Originally Posted by CRGreathouse I meant that primesieve and yafu were about 8x faster, rather than the ~400x they seemed.

In my defence, you didn't mention which is faster than which

2018-01-25, 14:19   #11
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by axn In my defence, you didn't mention which is faster than which
Sorry, I guess I thought context made it clear.

 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 21:36.

Thu Dec 1 21:36:20 UTC 2022 up 105 days, 19:04, 0 users, load averages: 0.92, 1.04, 0.97