And of course the sane solution is to use exponentiation by squaring on the 2x2 matrix whose elements are all 1s, except the right-bottom one, which is 0. Not surprisingly, (1 + phi) is an eigenvalue of that matrix.
import Data.Ratio
-- The number (a :+ b) represents (a + b √5)
data Q5 = Rational :+ Rational deriving (Show)
instance Num Q5 where
(a :+ b) + (c :+ d) = (a + c) :+ (b + d)
(a :+ b) * (c :+ d) = (a * c + 5 * b * d) :+ (a * d + b * c)
phi = (1 % 2) :+ (1 % 2)
fib n = let a :+ b = phi^n in round (2 * b)
>> fib 10
55
>> fib 20
6765
>> fib 80
23416728348467685 -- exact result in O(log n)!
The only big Haskell feature here is a default implementation of binary exponentiation, but this is a library feature, not an innate feature of the language. It would be easy enough to augment existing standard Python libraries with such a corresponding feature.
I've noticed that people with a mathematical background tend to be very attracted to Haskell. There's a great blog post by Dan Piponi enumerating eleven reasons to use Haskell as a mathematician:
http://blog.sigfpe.com/2006/01/eleven-reasons-to-use-haskell...
Or perhaps people who care about foundations in general.
(1 % 2) :+ (1 % 2)
<__main__.Qsqrt5 instance at 0xffee4d6c>
1/2 + 1/2 sqrt(5)
Obviously the Haskell implementation more directly expresses the idea! I found it easier to implement ℚ[φ] than ℚ[√5], even though the two are isomorphic as fields.
In fact they are equal (as opposed to, say, ℝ[x]/(x^2 + 1) and ℂ, which are 'merely' isomorphic).
By the way, if you want to pick up a book on cool applications of linear algebra, I recommend this one (PDF available for free):
Jiří Matoušek - Thirty-three miniatures (Mathematical and algorithmic applications of linear algebra) http://kam.mff.cuni.cz/~matousek/la-ams.html
Yes, if you take the simplest recurrence and say "calculate it" it may sound artificial. But all the tools that can be used for this example -- direct formula, repeated squaring, dynamic programming -- can be used for more complicated recurrences also.
I once tried to implement a library for exact Euclidean geometry, and I couldn't find any way to implement even the constructible numbers with reasonable efficiency.
For the less mathematically trained: constructible numbers are the smallest set containing the integers which is closed under addition, subtraction, multiplication, division, and square roots. If you start with a line segment from (0, 0) to (0, 1), and use only compass and straightedge constructions, the points you can construct (i.e., that are the intersection either of two lines, two circles, or a circle and a line) are exactly those whose coordinates are constructible. This is how one proves that trisecting angles with compass and straightedge is impossible, BTW.