Number of primes below a given number

Specific Domains Numerics
21

Pew pew @StefanKarpinski :smiley:

9 Likes
22

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.

39 Likes
23

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
24

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)
31 Likes
25 
julia> @time solve_this_thing;
  13 hours

Julia :heart:

18 Likes
26

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
27

I suspect you are correct …

28

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
29

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.

7 Likes
30

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).

31

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

3 Likes
32

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
33

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.

16 Likes
34

primecount_jll v6.5.0 comes with the shared libraries libprimecount and libprimesieve in addition to the primecount executable. Wait for https://github.com/JuliaRegistries/General/pull/33760 to be merged

8 Likes
35

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
6 Likes
36

Perhaps this could be incorporated as a primecount() function into Primes.jl?

6 Likes
37

Yup - that would add a dependency to primecount, but I think that’s accessible. If any newcomers want to PR that, feel free to DM and I’ll mentor through the process.

Concretely, we wouldn’t want to spawn an external process with run(...) every time we want to count primes - we want to call to the C ABI with @ccall so that this is just a direct function call:

julia> myprimecount(x) = @ccall libprimecount.primecount_pi(x::Clonglong)::Clonglong
myprimecount (generic function with 1 method)

julia> @time myprimecount(1e8)
  0.001004 seconds
5761455

julia> @time myprimecount(1e14)
  0.149201 seconds
3204941750802

This would include wrapping up the different options in the exposed command line options with appropriate dispatches.

This means that your mission, should you choose to accept it, would be a Pull Request to Primes.jl that

  1. adds primecount_jll as a dependency (easy: fork the repo, dev the repo, activate the environment, and add primecount as a normal package).
  2. add functions + dispatch for all the appropriate @ccalls exposed in the commandline options in primecount’s README.
  3. add tests to make sure that everything you added works.

Once that’s done, a good open source citizen would also PR the primecount github repo’s README to add Primes.jl as an Julia wrapper in their documentation (and/ or buy kimwalish et al a coffee).

14 Likes
38

Also enough people from JuliaMath here to figure out if we want that right away.

1 Like
39

Bonus round:
The same author has a library for calculating the sum of prime numbers up to n.

https://github.com/kimwalisch/primesum

4 Likes
40

Note that https://github.com/haampie/FastPrimeSieve.jl is more or less a native julia implementation of libprimesieve. More or less because it doesn’t do tricks for fast prime sieving of large prime numbers (2^32 to 2^64), for < 2^32 I would expect similar performance.

There’s an open PR to merge this sieve into Primes.jl.

Libprimecount apparently uses a special algorithm with better time complexity to just count primes. So if you just want to count them and don’t want to do anything interesting with them, libprimecount will beat FastPrimeSieve.jl.

8 Likes