1. 9
    1. 5

      Fibonacci numbers also have a closed-form answer: it’s possible to compute them without recursion or iteration using Binet’s formula. If you’re using doubles you’ll diverge from the correct answer (at n=75), but I found a lovely Haskell arbitrary precision example:

      data ZPhi = ZPhi !Integer !Integer
        deriving (Eq, Show)
      instance Num ZPhi where
        fromInteger n = ZPhi n 0
        negate (ZPhi a b) = ZPhi (-a) (-b)
        (ZPhi a b) + (ZPhi c d) = ZPhi (a+c) (b+d)
        (ZPhi a b) * (ZPhi c d) = ZPhi (a*c+b*d) (a*d+b*c+b*d)
      fib n = let ZPhi _ x = phi^n in x
        where phi = ZPhi 0 1
      1. 4

        I wrote the equivalent Python version when someone brought up the Haskell version. It’s a bit longer ‘cause I tried to make it a bit more generic and instructive, so that it would be clear how to define arithmetic in any number field, not just Q[sqrt(5)].


        edit: Oh, I should have read that more carefully. Yours is a Z[phi] version, not a Q[sqrt(5)]. Oh well.

    2. 1

      By using the matrix form (https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form) you can compute them “in n O(log(n)) arithmetic operations and in time O(M(n) log(n)), where M(n) is the time for the multiplication of two numbers of n digits. ”