Ok, sorry for posting this. I figured it out myself. Turns out that my eratosthenes function took much, much longer on primes and near-primes than it does on the average number. And, of course, the numbers that pass through the wheel factorization filter are just that.
So the good news is that I figured it out... the bad news is that, for smallish numbers, wheel factorization doesn't appear to provide a significant improvement over the unadorned Sieve of Eratosthenes. Thanks, -Luke On Mar 12, 2:07 pm, levand <[email protected]> wrote: > So, I'm doing the whole Euler thing, and I'm writing a function for > finding primes using wheel factorization in combination with the Sieve > of Eratosthenes. > > The algorithm is correct, but very slow. I've managed to isolate the > part that's having unexpectedly bad performance. > > I just can't see why the last of these four expressions is so slow. > The only overhead it ought to have is a single "if" statement. I am > beginning to think there's something about the implementation of > filter that I'm missing... Any help would be greatly appreciated. > > The code below uses only 2 functions... "wheelfactor?" returns a > boolean if the number is a good candidate for a prime by wheel > factorization, "eratosthenes" checks a given number against a sieve. > For the purposes of this demonstration I've defined the sieve to > merely be the first 1000 primes - so the answers returned here aren't > necessarily correct, but the performance factors ought to be about the > same. I have ran all the benchmarks multiple times against a warmed-up > JVM, so that's not the issue. > > ;;See how long wheelfactor? takes to run over 100k > (time (dorun (filter wheelfactor? (range 1 100000)))) > ;;30 milliseconds > > ;;See how long a simple eratosthenes takes to run over 100k > (time (dorun (filter #(eratosthenes % sieve) (range 1 100000)))) > ;;13 seconds > > ;;See how many numbers < 100k are potential primes? > (count (filter wheelfactor? (range 1 100000))) > ;;26687 > > ;;See how long it takes to run eratosthenes > ;;to evaluate 26687 large numbers: > (time (dorun (filter #(eratosthenes % sieve) (range (- 100000 26687) > 100000)))) > ;;3 seconds > > ;;See how long it takes to run a combination > ;;I expect ~3 seconds, from the previous tests > (time (dorun (filter #(if (wheelfactor? %) > (eratosthenes % sieve)) > (range 1 100000)))) > ;;13 seconds!? > ;;But I put a trace in eratosthenes and it still only runs 26687 > times!? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
