Dijkstra's Prime Number Algorithm | Hacker News Reader

Dijkstra's Prime Number Algorithm

heinrichhartmann.com

134 pointsbpierre23 comments

> What is remarkable about this algorithm is, that it uses no divisions at all!

The same holds for the Sieve of Eratosthenes [1]

[1] https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

One of the first algorithms I implemented in Python was the prime sieve. I used it extensively when solving Project Euler problems as well. Good days :)

You can solve much more problems from Project Euler using a DFS variation of the Sieve of Euler. It is a depth first search of all the numbers less than n. It visits every number exactly once. When it visits a number, the prime factorization of the number is available (or any quantity derived from the factorization, like Euler's phi function).

And it uses no divisions.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Euler.27...

Author here: Yes, that true, thanks for pointing it out. [In fact, Erathosthenes is mentioned later in that note.]

I still find it remarkable, that you can avoid divisions, while not to computing all multiples up-front and marking the results in a large table.

The algorithm is very nice. But I think you should think about what it means to divide one integer by another. The quotient of that operation is an integer. The remainder is an integer.

Can you express the number in terms of the quotient and remainder?

Using this expression write an algorithm that outputs the quotient and remainder using only addition, multiplication and checking equality with integers.

I think doing this would make the algorithm seem less surprising.

From the article: "this algorithm is an interesting mix between the Erathosenes Sieve..."

There's a simple combinatorial proof of the existence of a prime between n and n^2:

https://www.quora.com/Is-there-a-prime-between-every-natural...

The gaps between primes are easily produced using two operations on a list of numbers, mirroring and partitioning.

Each prime generates a spacing sequence to find future primes, each prime is effectively casting a new periodic wave function. 2 produces a wave that hits all even numbers. 3 produces a wave that hits every 6 numbers (2 already gets everything else.) 5 does every {20,10}, etc...

You can see the process of generating the sieve waveform, or more technically, the prime gaps, here:

http://math.stackexchange.com/questions/311610/modified-eule...

Look at the 2nd answer, it explains the process. Remember, all prime numbers do, is cast a waveform onto the existing sieve waveform. Just chaotic interference. Division as an immediate reaction to primes is moreso because primes are taught pretty poorly. As mystic nuggets. Rather than chaotic interference.

You've posted about this "waveform" idea before, and to be honest it seems like you are making a big deal out of the obvious fact that each newly found prime eliminates some possible greater numbers from the search by being a factor.

With friendly intentions, I have to tell you that you risk sounding like a math crank.

The waveform idea is simply to convey the sieve to non math folk in a more intriguing way. I dont see how talking about first differences of reduced residue sets of primorials is crank. Its being studied as we speak by PHD Fred Holt from UWashington...

Wheres the issue with the method of mirroring and partitioning I discussed? Do you have something better than wont involve division?

Also, there is a lot of merit in understanding how the sieve works because gap sequences work until the next prime squared. As the primes tend toward infinity, the sieve matches all primes. Its a valid way to study primes aside from the attacks on the Zeta function

I am open to being convinced that you have new insights, but the reduced residue sets idea is not a magic bullet. If it was a magic bullet we would be having a different conversation.

Basically I am encouraging you to discuss this in a way or in a context in which people will engage more readily with your ideas, either to accept or reject them. HN is not full of number theorists.

Edit: This is a case where textual communication is really inadequate to determine the seriousness and, dare I say it, credibility of an interlocutor.

You can see Fred's papers here: http://arxiv.org/find/math/1/au:+Holt_F/0/1/0/all/0/1

You misunderstand me. I don't claim that the dRRS is a magic bullet. But it certainly isn't crank..

The coolest technique I know of for checking primes is a variant of the Lucas sequence method (which is what GIMPS uses to find Mersenne primes)[1]. Essentially, you generate terms in a sequence in a constant-memory fashion that doesn't require you to know the factors, using just a modulo in a generating function.

[1]: https://www.youtube.com/watch?v=lEvXcTYqtKU

This algorithm seems similar to one I found* which is a Sieve of Eratosthenes that doesn't require deciding how big of an array to allocate at the beginning. Essentially, you reverse the order of the two main loops, modifying the main data structure accordingly.

http://www.kylem.net/stuff/sieve_eratosthenes.html

I don't completely understand it yet, but I think the Dijkstra version might have optimized the structure which contains the multiples of known primes, where I just put it into a dictionary.

* I initially saw it in a paper about how the Sieve is generally implemented incorrectly in Haskell, but I made a small Python generator implementation.

A long and detailed list of prime number structures in Haskell

https://wiki.haskell.org/Prime_numbers

And a long list of algorithms. Many of which are surprising and probably not that efficient. The first few are:

https://wiki.haskell.org/Prime_numbers_miscellaneous#Prime_W...

Efficiency is kind of a relative issue, since you don't know the job beforehand or which one would be optimal

There's also this obfuscated

    let f='.';o c(x:y)=x:c y;z c(x:y)=f:c y;p n='p':ap fix p(o.n)in f:f:p z

defining the `bitmap' of prime numbers

    ..pp.p.p...p.p...p.p...p.....p.p.....p...p.p...p..  ...

while avoiding arithmetic altogether.

This is slower than the sieve right?

I think so, but the memory usage is drastically lower: Only O(x/ln(x)) vs. O(x), for getting all primes up to x.

(edit: typo gone, thanks for the interesting write-up)

Indeed! Thanks a lot. Its corrected now.

... no wait: It's corrected now. ;)

While there are only about x/ln(x) primes, each one takes at least log(x) bits to represent, so there's no memory savings after all.

In fact, there's an increasing loss as we optimize the constant factor in the sieve's O(x).

To wit, Dijkstra's algorithm takes 776MB to store all 203280221 primes under 2^32 at 4 bytes per prime.

A simple version of Eratosthenes' sieve, using 1 bit per odd number, takes 2^31 bits, which is only 256MB.

A more streamlined sieve like the one on my webpage at

http://tromp.github.io/pearls.html

implicitly filters out multiples of 2, 3, and 5, leaving only 8 potential primes in every 30 consecutive integers, conveniently fitting in a byte, for a total of 137MB.

(for some reason, compiling with nonzero optimization gives a gcc 4.8.5 internal compiler error on my SUSE Linux box)

Given its author, it would be even more remarkable if this algorithm was incorrect. See my comment on the article.

The algorithm is indeed incorrect, as I've explained in a more recent comment on the article.

Reply on news.ycombinator.com