1. 9

  2. 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. ”