Number of primes below a given number

Thank you for your thoughtful response! I’ll fiddle with it in AM… I suspected, once your raise this to 5 or 6 orders of magnitude, this quarter second will be 6 hours or more… : /

Yes, I suspect primesieve is using an analytical prime-counting function, which will be much faster than sieving.

He goes into detail about how it works on the site, but leads with “primesieve generates primes using the segmented sieve of Eratosthenes with wheel factorization. This algorithm has a run time complexity of operations and uses memory. Furthermore primesieve uses the bucket sieve algorithm which improves the cache efficiency when generating primes > 2^32. primesieve uses 8 bytes per sieving prime, hence its memory usage is about bytes per thread.”

Ah, I thought primesieve might use the author’s other library, primecount, but it appears not.

2 Likes

Making a BinaryBuilder package for the primecount program & library seems like it would be pretty easy and it seems to be the state of the art in fast prime counting. Someone could also probably port its algorithm to Julia without too much difficulty, although the code base is larger and more involved than one would naively expect.

7 Likes

Pew pew @StefanKarpinski :smiley:

9 Likes

Also, if you ever think this BinaryBuilder.jl business is just Dark Arts By Those Compiler Gurus That I Just Will Never Learn About, I recorded myself doing a brief tutorial on how YOU could have done this.

36 Likes

Bravo! :clap: It’s still mind blowing to me that that’s all it takes to build binaries that work on every platform where Julia runs and make it available to every Julia user.

8 Likes

Ready for use :slight_smile:

julia> @time countprimes(10^8)
  0.172059 seconds (358 allocations: 37.440 MiB, 1.32% gc time)
5761455

julia> using primecount_jll

julia> @time run(`$(primecount()) 1e8`);
5761455
  0.007801 seconds (586 allocations: 67.656 KiB)

@HexSpin 10^14 you said? There you go:

julia> @time run(`$(primecount()) 1e14`);
3204941750802
  0.397191 seconds (586 allocations: 67.656 KiB)
29 Likes
julia> @time solve_this_thing;
  13 hours

Julia :heart:

17 Likes

Looking at the orgs of some the contributors of GitHub - JuliaPackaging/Yggdrasil: Collection of builder repositories for BinaryBuilder.jl I get the impression that what it took to master Binary Building was the need to compile half century old fortran code. There is a theme here of course.

1 Like

I suspect you are correct …

Amazing. This has to be the best solution. I’ll get back to you as soon as I overcome whatever it is causing this error code I keep getting. Thank you, Miguel Raz!
(What a crazy cool community).

5 Likes

I wrote a package that, among other things, does this. It uses the previous binary deps system. The package has fallen into disrepair. IIRC, I made an interface that combined primecount and lookup tables. The package does a few things that might be better split up. At the time I wrote it, it was much faster than other Julia packages for prime pi, prime sieves, etc. And just to be clear: using a sieve to compute the prime pi function is inefficient.

6 Likes

Do you happen to know how your prime generation performs against Kim Walisch’s primesieve benchmarks? A faster than primes.jl tool with your listed functions would be wonderful…but, alas, I’m on OSX so all academic (If I’m reading your notes correctly).

PrimeSieve.jl wraps a few C/C++ libraries, including Kim Walisch’s libprimesieve.

3 Likes

I most likely wrote that note seven years ago, so the availability of libraries might have changed. I suppose there is a way to build osx libraries and make them available as well.

1 Like

I’m not volunteering you to do this or anything, but just so you know, it’s usually very easy these days to do what @miguelraz did and make a BinaryBuilder recipe that compiles C/C++ libraries for all supported platforms. The way BB works is that it compiles all binaries using the same Linux-based tool chain, configured to cross-compile for each platform. (Making that work was the part that required wizardry, but pay no attention to the man behind the curtain!) So getting a thing to compile in that one simple Linux environment is often enough to generate binaries for all platforms, including macOS, Windows and FreeBSD.

The binaries that are produced still need to interact with their native systems correctly, so for libraries that interact with the platform extensively, configuring them to cross-compile correctly can still be tricky, but for purely numerical libraries like this, it’s usually trivial since they pretty much take numbers as input, do some compute and give you numbers back out without ever needing to do anything platform-dependent. Once the binaries are built by Yggdrasil, they can just be downloaded onto end-user systems and used as-is with no modifications, and of course Pkg does that for you automatically. The whole thing is pretty magical and makes distributing binary dependencies super reliable and reproducible.

15 Likes

primecount_jll v6.5.0 comes with the shared libraries libprimecount and libprimesieve in addition to the primecount executable. Wait for New version: primecount_jll v6.5.0+0 by jlbuild · Pull Request #33760 · JuliaRegistries/General · GitHub to be merged

8 Likes

Thanks to @giordano , we have AVX2 speedups from the most recent build :muscle:

julia> using primecount_jll

julia> @time run(`$(primecount()) 1e8`);
5761455
  0.011614 seconds (467 allocations: 33.562 KiB)

julia> @time run(`$(primecount()) 1e14`);
3204941750802
  0.181341 seconds (467 allocations: 33.562 KiB)

julia> versioninfo()
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-4710HQ CPU @ 2.50GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, haswell)

(@v1.6) pkg> st primecount_jll
      Status `~/.julia/environments/v1.6/Project.toml`
  [ba3b429d] primecount_jll v6.5.0+0
5 Likes