Performant BIG fibonacci in Clojure?

[Webdev_Tory]

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

[Webdev_Tory]

oops. I just re-read the stack overflow problem and see that it was doing different things. It was calculating some fibonacci’s a billion times, not calculating the billionth fibonacci. So I can’t compare his results to mine. But the question stands, can Clojure go any faster than this? Or is 11 minutes as fast as I’m going to get on my machine with plain Clojure (as opposed to, say, using one of Dragan’s libraries and connecting my GPU to the problem)?

[joinr]

Performance seems generally consistent with the original author’s observations:

If you extend the trend out to 1E9, you get ~1E3 seconds, ~16.7 minutes I think. Looks like the same ballpark.

I just tried it with memoize and got about the same 11-minute result.

If you ran it a second time (as I did), it’s relatively instantaneous since it doesn’t have to recompute all the dependent values. However, the first time through will always incur the cost. The algorithm implemented will guarantee to drive the input n down to 0 via recursive applications of fib* to (quot n 2) inputs prior to doing any non-tail recursive work to leverage the intermediate results.

[didibus]

I replied to the StackOverFlow with an example Clojure version that runs as fast as their Java version.

Why is this seemingly basic clojure function so slow?

[Webdev_Tory]

This is an excellent, instructive answer. Thanks for putting in the legwork to work this out so instructively!

[didibus]

With fib, you can’t use primitives though if you want to be able to get big fibs, because they will quickly grow beyond the size a primitive long can store. You have to use BigInt, and that will always be boxed, and slower in general.

I think all you can do is just get rid of reflection where you can, and maybe use arrays instead of vectors, but otherwise you can’t speed it up too much, it’ll have to rely on the BigInt methods and won’t be able to do primitive math on such large integers.

If you restrict yourself to fibs that fit inside a long, then if you apply the same treatment of using primitive math and primitive long types, you can get big speedups as well.