It's been a busy few weeks since I last posted about my toying around with project euler, but never you mind. I did do some progress nontheless! HA!
Just so I won't bore you with the details, the most interesting thing I discovered is that the way I was calculating prime numbers was totally wrong. Not in the sense that it didn't work, but in the sense that it was only fast in theory. In practice it turns out that either my implementation was completely and utterly horrible or that I simply don't know enough about performance bottlenecks of clojure and made a boo boo somewhere.
Here's my original way of creating prime numbers and checking if a number is prime:
(defn any? [l]
(reduce #(or %1 %2) l))
(defn prime? [n known]
(loop [cnt (dec (count known)) acc []]
(if (< cnt 0) (not (any? acc))
(recur (dec cnt) (concat acc [(zero? (mod n (nth known cnt)))])))))
(defn next-prime [primes]
(let [n (inc (count primes))]
(let [lk (if (even? (inc (last primes))) (+ 2 (last primes)) (inc (last primes)))]
(loop [cnt lk p primes]
(if (>= (count p) n) (last p)
(recur (+ cnt 2) (if (prime? cnt p) (concat p [cnt]) p)))))))
(defn n-primes [n]
(loop [cnt 1 p [2]]
(if (>= cnt n) p
(recur (inc cnt) (concat p [(next-prime p)])))))
Not exactly certain what sieve I was using here, but the idea is that a number is prime if it isn't divisible by any primes smaller than the number you're checking. This works great in theory because you're always dividing with very few numbers.
But turns out, there's a much much faster way of doing it:
(defn any? [l]
(reduce #(or %1 %2) l))
(defn prime? [n]
(if (even? n) false
(let [root (num (int (Math/sqrt n)))]
(loop [i 3]
(if (> i root) true
(if (zero? (mod n i)) false
(recur (+ i 2))))))))
(defn n-primes [n]
(loop [num 2 p []]
(if (>= (count p) n) p
(recur (inc num) (if (prime? num) (concat p [num]) p)))))
This way of checking for primes just loops through all numbers smaller than the square root of the one we're checking by starting off with 3 and jumping by two places.
Obviously a very big improvement here is using the square root as the looping boundary, but turns out even adding this trick to the previous method only goes so far. The dumber version is still at least a 100 times faster. In fact the dumb version produced all primes under 2,000,000 in about a minute whereas the first version wasn't even finished after ten minutes.
So what's happening here? Considering the sparseness of prime number distribution I'm thinking that the dumber method performed at least ten times more divisions.
My theory is that maybe, just maybe, the problem was in copying that huge arse list of known primes around when performing function calls. Or maybe it was the appending of primes to the big list that was the problem ... whatever it was, I learned a valuable lesson: Keep it Stupid Simple For Realz.
Continue reading about Checking for primes? Dumber algorithm is faster algorithm
Semantically similar articles hand-picked by GPT-4
- Project euler is a fun way to become a better geek
- Comparing clojure and node.js for speed
- Collatz, Haskell and Memoization
- Python and lazy evaluation
- Learning me a Haskell
Learned something new?
Read more Software Engineering Lessons from Production
I write articles with real insight into the career and skills of a modern software engineer. "Raw and honest from the heart!" as one reader described them. Fueled by lessons learned over 20 years of building production code for side-projects, small businesses, and hyper growth startups. Both successful and not.
Subscribe below 👇
Software Engineering Lessons from Production
Join Swizec's Newsletter and get insightful emails 💌 on mindsets, tactics, and technical skills for your career. Real lessons from building production software. No bullshit.
"Man, love your simple writing! Yours is the only newsletter I open and only blog that I give a fuck to read & scroll till the end. And wow always take away lessons with me. Inspiring! And very relatable. 👌"
Have a burning question that you think I can answer? Hit me up on twitter and I'll do my best.
Who am I and who do I help? I'm Swizec Teller and I turn coders into engineers with "Raw and honest from the heart!" writing. No bullshit. Real insights into the career and skills of a modern software engineer.
Want to become a true senior engineer? Take ownership, have autonomy, and be a force multiplier on your team. The Senior Engineer Mindset ebook can help 👉 swizec.com/senior-mindset. These are the shifts in mindset that unlocked my career.
Curious about Serverless and the modern backend? Check out Serverless Handbook, for frontend engineers 👉 ServerlessHandbook.dev
Want to Stop copy pasting D3 examples and create data visualizations of your own? Learn how to build scalable dataviz React components your whole team can understand with React for Data Visualization
Want to get my best emails on JavaScript, React, Serverless, Fullstack Web, or Indie Hacking? Check out swizec.com/collections
Did someone amazing share this letter with you? Wonderful! You can sign up for my weekly letters for software engineers on their path to greatness, here: swizec.com/blog
Want to brush up on your modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com
By the way, just in case no one has told you it yet today: I love and appreciate you for who you are ❤️