I primarly use Ruby for math/science problems/projects because it’s so easy to program in, and it allows me to think about how to solve problems without worrying about how to code it. I’ve also played around with Crystal (aka Ruby on steroids) but it’s still young, and doesn’t let me (currently) do what I want, or without a lot of hassles, and I’ve just recently started looking at Nim (less than a month at time of writing).
I played with Go sometime ago but never had any time/reason to really learn and use it. But now maybe I have incentive to do so.
I developed a prime sieve called the Sieve of Zakiya (SoZ), and it’s companion the Segmented Sieve of Zakiya (SSoZ). I wrote a paper, The Segmented Sieve of Zakiya (SSoZ) which describes its mathematical foundations and algorithm, and provide a working C++ implementation at the end of the paper (compiled, run, and verified), though I don’t consider myself a C++ programmer, just funcitonal enough in it. It’s a relatively short program.
Here’s a link to read and download the paper:
My humble request/challenge is for a/some skilled Golanger(?) to translate the code into idiomatic Go to demonstrate the best way to code the algorithm in it. Extra points if someone can do a true parallel version of the algorithm, which I attempted to do using OpemMP, but what I did didnt’ seem to make the code faster than the serial version (see paper).
I assume coding this the Go way would look different than the C++ code, and be quite different than a direct translation into Go using the same (probably suboptimal) structure.
Ultimately, I’d like to publish the results of benchmarks in different languages doing the SSoZ in an updated paper.
If anyone would be willing to take up the challenge I’d be pleased to answer any questions the best I can.
Was your paper published in some scientific journal?
You’ve asked similar questions already. How may replies did you get so far? Did anybody implement your algorithm in any other language you don’t master yourself?
Besides, as having a degree in Mathematics: can you provide a proof that a) your algorithm is correct, and b) what runtime complexity it has?
I don’t understand what you mean by proofs. The math and the code works. Have you tried to run the C++ code?
I originally did all my work to develop the math and techniques in Ruby, and have created a rubygem named primes-utils, and its companion Primes Utils Handbook which you can read/download from below. Maybe this is what you’re looking for. You can play with this to your hearts content to see that everything works!
By proof I mean the mathematical proof that an algorithm does what it is expected to do. For primes this would include that the algorithm returns primes, all primes, and only primes. Such a proof is not the same as writing an implementation, letting it run, and taking a look at the results. A proof is also not a benchmark or the comparison of different implementation.
To reason about an algorithm, no implementation for required. Pseudo code should be enough.
Ahh, you mean a mathematical type “proof” using axioms and theorems and funny characters…
I assume you haven’t read my paper (because of problems downloading it). If you try this link below you should not only see my paper you can download, but you’ll also see C++ source code for different versions. If this link doesn’t work let me know. (It seems the Scribd link might impose geolocation restrictions.)
But yes, the algorithm is “proven” to work (will identify primes, and only primes), and it’s way faster than Eratosthenes, and is designed so it can be implemented easily parallizable. But I hope you can download and read the paper (finally), and run the code, to see the results and performance yourself. I think after you do then a lot of your questions will be answered.
