mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-01-24, 20:43   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

15916 Posts
Default 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
bhelmes is offline   Reply With Quote
Old 2018-01-24, 21:06   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·3·293 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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
Threads    = 48
100%
Primes  : 37607912018
Seconds : 14.457
Code:
./yafu "primes(0,10^12)" -threads 48


found 83224 sieving primes
elapsed time = 12.1653
37607912018
bsquared is offline   Reply With Quote
Old 2018-01-25, 01:45   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

Quote:
Originally Posted by bsquared View Post
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).
CRGreathouse is offline   Reply With Quote
Old 2018-01-25, 02:22   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

351610 Posts
Default

Yeah, and it is even better then that at lower upper bounds... 10^12 sized intervals are an ambitious undertaking.
bsquared is offline   Reply With Quote
Old 2018-01-25, 03:23   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-01-25, 04:10   #6
axn
 
axn's Avatar
 
Jun 2003

2×2,539 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
axn is offline   Reply With Quote
Old 2018-01-25, 06:07   #7
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

22·227 Posts
Default

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
danaj is offline   Reply With Quote
Old 2018-01-25, 07:01   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by axn View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-01-25, 07:03   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

Quote:
Originally Posted by danaj View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-01-25, 07:31   #10
axn
 
axn's Avatar
 
Jun 2003

117268 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
axn is offline   Reply With Quote
Old 2018-01-25, 14:19   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135338 Posts
Default

Quote:
Originally Posted by axn View Post
In my defence, you didn't mention which is faster than which
Sorry, I guess I thought context made it clear.
CRGreathouse 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 18:03.


Tue Jul 27 18:03:33 UTC 2021 up 4 days, 12:32, 0 users, load averages: 1.72, 1.97, 2.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.