4 ms·
For anyone interested in implementations of the Sieve of Erastothenes, here is a very interesting paper about functional ones, which are harder than they appear
by hyperfekt 9y ago
For anyone interested in implementations of the Sieve of Erastothenes, here is a very interesting paper about functional ones, which are harder than they appear at first:
https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
- bjoli 9y agoI implemented that in chez scheme recently, and it is pretty darn fast. https://bitbucket.org/bjoli/primes/src https://bitbucket.org/bjoli/primes/src (the file lazy-prime-sieve.scm) it uses Nietzsche which can be found in my repos. On my three year old computer, it computes the first ten million primes in about 40 seconds (up to, and including 179424673). That is only about 4 times slower than the optimized non-lazy naive sieve.
- nerdponx 9y agoThat's pretty cool. Lest we forget, "computers are fast." I imagine computing the first ten million primes once upon a time required a super computer and hundreds of hours.
- agumonkey 9y agoYears don't tell much, what kind of CPU is it ? Still very nice to see.
- bjoli 9y agoIt is an Ivy Bridge or Haswell mobile i7. It was pretty high en for a laptop in late 2013/early 2014.