How to implement this fast doubling Fibonacci algorithm in Clojure?

Question

Here is my way of finding the nth Fibonacci number:

(defn fib-pair [[a b]]
  "Return the next Fibonacci pair number based on input pair."
  [b (+' a b)])    ; Use +' for automatic handle large numbers (Long -> BigInt).

(defn fib-nth [x]
  "Return the nth Fibonacci number."
  (nth (map first (iterate fib-pair [0 1])) x))

I know this may be not the most efficient way, and I found the fast doubling algorithms.

The algorithm contains matrix and math equations, I don't know how to set them in Stack Overflow, please visit:

https://www.nayuki.io/page/fast-fibonacci-algorithms

I tried the Python implementation provided by that website, it is really fast. How to implement it in Clojure?

Edit: Python implementation provided by that website:

# Returns F(n)
def fibonacci(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    return _fib(n)[0]


# Returns a tuple (F(n), F(n+1))
def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2)
        c = a * (2 * b - a)
        d = b * b + a * a
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

Mike Fikes · Accepted Answer · 2014-12-14 13:18:03Z

6

I haven't checked for performance, but this appears to be a faithful implementation in Clojure:

(defn fib [n]
  (letfn [(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)]))))]
    (first (fib* n))))

edited Dec 14, 2014 at 13:18

answered Dec 14, 2014 at 4:40

Mike Fikes

3,52716 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Nick Over a year ago

Thank you! The code works. I'm new to Clojure, some of the concept which is easy to others may be hard to me. I still need to learn more about it. By the way, due to prefix arithmetic operator, I still need some get-used-to work to read the math equations.

Collectives™ on Stack Overflow

How to implement this fast doubling Fibonacci algorithm in Clojure?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related