5 ms·

Dijkstra's Prime Number Algorithm

134 points by bpierre 11y ago

pyed 11y ago
I wish that he translated the algorithm in a common language so more people can read it.
amelius 11y ago
> 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 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
- Cyph0n 11y ago
  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 :)
  - nroets 11y ago
    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.27s_Sieve https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Euler.27...
- heinrichhartman 11y ago
  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.
  - davidamarquis 11y ago
    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.
- cdman 11y ago
  From the article: "this algorithm is an interesting mix between the Erathosenes Sieve..."
- deleted 11y ago
  [deleted]
jebediah 11y ago
This is slower than the sieve right?
- heinrichhartman 11y ago
  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.
  - ableal 11y ago
    (edit: typo gone, thanks for the interesting write-up)
    - heinrichhartman 11y ago
      Indeed! Thanks a lot. Its corrected now. ... no wait: It's corrected now. ;)
  - tromp 11y ago
    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 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)
sajid 11y ago
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-number-greater-than-1-and-its-square https://www.quora.com/Is-there-a-prime-between-every-natural...
goldenkey 11y ago
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-eulers-totient-function-for-counting-constellations-in-reduced-residue/1055504#1055504 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.
- theoh 11y ago
  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.
  - goldenkey 11y ago
    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
    - theoh 11y ago
cyphar 11y ago
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 https://www.youtube.com/watch?v=lEvXcTYqtKU
kmill 11y ago
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 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.
mrcactu5 11y ago
A long and detailed list of prime number structures in Haskell https://wiki.haskell.org/Prime_numbers 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_Wheels 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
- tromp 11y ago
  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.
oluckyman 11y ago
Given its author, it would be even more remarkable if this algorithm was incorrect. See my comment on the article.
- oluckyman 11y ago
  The algorithm is indeed incorrect, as I've explained in a more recent comment on the article.

134 points by bpierre 11y ago

pyed 11y ago

I wish that he translated the algorithm in a common language so more people can read it.

> 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 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Cyph0n 11y ago
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 :)
- nroets 11y ago
  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.27s_Sieve https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Euler.27...
heinrichhartman 11y ago
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.
- davidamarquis 11y ago
  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.
cdman 11y ago
From the article: "this algorithm is an interesting mix between the Erathosenes Sieve..."
deleted 11y ago
[deleted]

jebediah 11y ago

This is slower than the sieve right?

heinrichhartman 11y ago
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.
- ableal 11y ago
  (edit: typo gone, thanks for the interesting write-up)
  - heinrichhartman 11y ago
    Indeed! Thanks a lot. Its corrected now. ... no wait: It's corrected now. ;)
- tromp 11y ago
  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 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)

sajid 11y ago

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-number-greater-than-1-and-its-square https://www.quora.com/Is-there-a-prime-between-every-natural...

goldenkey 11y ago

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-eulers-totient-function-for-counting-constellations-in-reduced-residue/1055504#1055504 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.

theoh 11y ago
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.
- goldenkey 11y ago
  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
  - theoh 11y ago

cyphar 11y ago

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 https://www.youtube.com/watch?v=lEvXcTYqtKU

kmill 11y ago

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

mrcactu5 11y ago

A long and detailed list of prime number structures in Haskell https://wiki.haskell.org/Prime_numbers 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_Wheels 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

tromp 11y ago
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.

oluckyman 11y ago

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

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