Intro

A recent stack overflow question asked about Clojure performance compared to other implementations, with Python and raw java performing vastly better than Clojure¹. Now, this is Clojure, so there must be a better way. One of the answers pointed to RosettaCode and Clojure fibonacci implementations there², so I felt pretty good grabbing the “Doubling Algorithm (Fast)” version given there, which is based on an off-the-cuff github answer from Clojure optimization guru Mike Fikes³.

My trouble is, running the “fast” version still took me an hour on my machine (16gb ram, 4x 1.8ghz cpu), not counting the times I died by accidentally printing the result or blew my stack by trying to “tweak” Mike’s answer.

What is the way to performantly get the billionth fibonacci number in Clojure? Can it be done without an external library?

EDIT: I ran this exact same code a second time and it came back in under 11 minutes. There must be something here about “warming the JVM”?

Result

user> (def billion (bigint 1000000000))
(defn fib* [n]
  (if (zero? n)
    [0 1]
    (let [[a b] (fib* (quot n 2))
          c (*' a (-' (*' 2 b) a))
          d (+' (*' b b) (*' a a))]
      (if (even? n)
        [c d]
        [d (+' c d)]))))
(defn fib [n]
  (first (fib* n)))

#'user/billion#'user/fib*#'user/fib
user> (def fibbres (time (fib billion))) ;; use def here because the number is so big it breaks the repl if it prints
"Elapsed time: 3415836.050247 msecs" ;; Would JVM warmup help here?
#'user/fibbres
user> (/ 3415836 1000 60.0)
56.9306 ;; minutes to get the billionth fibonacci number

Attempt with memoize

I decided to try with memoize, realizing that the memoization itself might be a memory issue with such a large number. Also, I’m not sure if memoize is going to be effectual here due to the recursive nature of the algorithm, which might not memoize until it’s all done.

(defn msecs-to-mins [n] (/ n 1000 60.0))
#'user/msecs-to-mins
user> (msecs-to-mins 636674)
10.611233333333333
user> (def fib*mem
  (memoize (fn [n]
             (if (zero? n)
               [0 1]
               (let [[a b] (fib*mem (quot n 2))
                     c (*' a (-' (*' 2 b) a))
                     d (+' (*' b b) (*' a a))]
                 (if (even? n)
                   [c d]
                   [d (+' c d)]))))))
  (defn fib [n]
    (first (fib*mem n)))


#'user/fib*mem#'user/fib
user> (def fibbres2 (time (fib billion)))
"Elapsed time: 635701.196383 msecs"
#'user/fibbres2
user> (msecs-to-mins 635701)
10.595016666666668 ;; minutes
user> (def fibbres3 (time (fib billion)))
"Elapsed time: 0.358505 msecs" ;; giggles. Same thing as asking the time on checking the value of the def. 
#'user/fibbres3

Resources

https://clojureverse.org/t/performant-big-fibonacci-in-clojure/8832

Footnotes

¹ Here is the recent question: https://stackoverflow.com/questions/71790601/why-is-this-seemingly-basic-clojure-function-so-slow

² Link-giving answer by kawas44 here: https://stackoverflow.com/a/71793196/5641201 . The RosettaCode Clojure link is this: https://www.rosettacode.org/wiki/Fibonacci_sequence#Clojure

³ The doubling algorithm code came from here: https://stackoverflow.com/questions/27466311/how-to-implement-this-fast-doubling-fibonacci-algorithm-in-clojure/27466408#27466408