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
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)].
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. ”
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:
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)].
http://ideone.com/NWQe38
edit: Oh, I should have read that more carefully. Yours is a Z[phi] version, not a Q[sqrt(5)]. Oh well.
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. ”