An Adventurous Juila Challenge

jzakiya · December 13, 2018, 3:24am

Hello,

I hope I put this post in the correct category, excuse me if not.

I’ve been following Julia sporadically for about two years. When it hit 1.0 I finally installed it on my laptop, but so far haven’t done anything extensive (really haven’t had the time to learn it). However, I look at the videos to see what people are doing with it.

One thing I really like about Julia is it seems like it was designed by math nerds (that’s positive) to solve problems. I’m sorta kinda one too. That’s a reason I think (hope) the community will respond to this.

So, I just released a paper that implements a fast Twin Prime Segmented Sieve of Zakiya (SSoZ). But I provide an extensive (brief) discussion of the mathematical basis behind the algorithm, that should be of interest too.

The algorithm in the paper is done in Nim. Here’s its source code.

gist.github.com

https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e#file-twinprimes_ssoz-nim

twinprimes_ssoz.nim

#[
 This Nim source file is a multiple threaded implementation to perform an
 extremely fast Segmented Sieve of Zakiya (SSoZ) to find Twin Primes <= N.
 
 Inputs are single values N, or ranges N1 and N2, of 64-bits, 0 -- 2^64 - 1.
 Output is the number of twin primes <= N, or in range N1 to N2; the last
 twin prime value for the range; and the total time of execution.
 
 This code was developed on a System76 laptop with an Intel I7 6700HQ cpu,
 2.6-3.5 GHz clock, with 8 threads, and 16GB of memory. Parameter tuning

This file has been truncated. show original

Here’s two links to the paper.

I see that Julia is a compiled, statically typed, and able to do true parallel processing. The Nim code has all these features, which are necessary to perform the algorithm optimally.

So I’m hoping someone(s), who feels a little adventurous|curious will do a Julia version, so I can see how it compares to the Nim version (in code size, style, readability, performance, etc). This would serve like a Rosetta Stone for me to really help me learn significant Julia features doing something serious.

Here are some of the specifics elements of the Nim code that are required for the algorithm.

It has to be a true parallel implementation using the max number of cpu threads.
Nim has a garbage collector that recovers memory after each thread finishes.
The code has specific compile time actions (computing a lot constant values).
I use a rudimentary segmentation strategy, which surely can be improved.
The segment arrays are byte arrays, but fast bitarrays could potentially be faster (if available).

The paper shows the Nim code performs better compared to a C++ project (primesieve.org), as a reference.
I assume Julia can meet all these requirement, and perform better(?) (A GPU version would actually be fastest)

That’s it. Thanks for indulging me.

Jabari