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

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”?

**EDIT 2** I just tried it with memoize and got about the same 11-minute result. I suspect that the recursive nature of the “fast” code doesn’t memoize well. But, for giggles, I ran the memoized version a second time, and giggled.

#### 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
```

## Footnotes:

[1] Here is the recent question: Why is this seemingly basic clojure function so slow? - Stack Overflow

[2] Link-giving answer by kawas44 here: Why is this seemingly basic clojure function so slow? - Stack Overflow . The RosettaCode Clojure link is this: https://www.rosettacode.org/wiki/Fibonacci_sequence#Clojure

[3] The doubling algorithm code came from here: How to implement this fast doubling Fibonacci algorithm in Clojure? - Stack Overflow