4 ms·
Indeed! In fact, it occurs to me that you can get something of a 'best of both worlds' solution between the elegant mathematical solution and the exactness of t
by crntaylor 13y ago
Indeed! In fact, it occurs to me that you can get something of a 'best of both worlds' solution between the elegant mathematical solution and the exactness of the recursive solution very easily in Haskell, by defining the field extension* Q(√5), i.e. the rational numbers extended with the square root of 5
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)
It's now enough to notice that the coefficient of √5 in phi^n is half the n'th fibonacci number, so define
fib n = let a :+ b = phi^n in round (2 * b)
to get
>> fib 10
55
>> fib 20
6765
>> fib 80
23416728348467685 -- exact result in O(log n)!
* http://en.wikipedia.org/wiki/Field_extension http://en.wikipedia.org/wiki/Field_extension
- catnaroek 13y agoNow this is beautiful! Instead of dealing with all algebraic numbers, it extends the rationals with just the bare minimum needed to get the job done. :-)
- clebio 13y agoI can't upvote this comment enough. A lucid application of group theory to derive an operationally-efficient algorithm.
- jordigh 13y agoField theory, not group theory, at least not directly. The two are linked by the fundamental theorem of Galois theory.
- leephillips 13y agoThis is mind-blowing. This comment is the best answer I've seen yet to the question, "Why learn Haskell?".
- colomon 13y agoThe only reason I haven't actually implemented a number type like this in Perl 6 (someone proposed it to me years ago) is I didn't really it had such a lovely and practical application.
- colomon 13y agoProps to Haskell, though -- p6 makes it easy to do, but Haskell is definitely more elegant here. Though maybe if I keep playing with it...
- jordigh 13y agoThis is kind of pedestrian for a mathematician, and there aren't any features in use here that are exclusive to Haskell. Basically, you're just definining a new field of numbers where you throw in the sqrt(5) into the rational numbers. You could very easily do this in Python too: http://ideone.com/9dHQV9 http://ideone.com/9dHQV9
- gaze 13y agogrr. this has nothing to do with haskell.
- crntaylor 13y agoTure, but notice how easy and natural it is in Haskell. You can do the same thing in Python, as noted in the comment by jordigh -- but it takes ~40 lines, as opposed to ~8 lines in Haskell. I'm willing to bet that it's even more verbose in C++, and I don't even want to think about doing it in Java.
- jordigh 13y agoI aimed for clarity and some extra features in mine (e.g. __repr__ and __str__) instead of code golfing it. I also used the actual Binet formula instead of just approximation. 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.
- colomon 13y agoIt's O(log n) because Haskell is smart enough to implement exponentiation by repeated squaring and summing as appropriate? (There must be a better name for that.)
- crntaylor 13y agoYes -- see the source here: http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC-Real.html#%5E http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC...
- NoodleIncident 13y agoI believe that's called Russian Peasant Exponentiation.
- jfarmer 13y agoEarlier this year I implemented the arithmetic of ℚ[φ] in Ruby, to illustrate how something like this would work for my students: http://bit.ly/1gSQdpC http://bit.ly/1gSQdpC 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.
- JadeNB 13y ago> 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).