5 ms·

In all fairness, if there were a type of algebraic numbers, the calculations would be exact. (But probably not O(1) anymore.) And of course the sane solution i

In all fairness, if there were a type of algebraic numbers, the calculations would be exact. (But probably not O(1) anymore.) 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.

NotOscarWilde 13y ago
This solution -- O(log n) through repeated squaring -- is a good illustration of usefulness of many areas that "neighbor" computer science, such as linear algebra, combinatorics and graph theory. 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 http://kam.mff.cuni.cz/~matousek/la-ams.html
- jules 13y ago
  I don't think this illustrates the practical usefulness of mathematics. This is not a practical problem, it's a mathematical problem. It's no surprise that maths is useful for solving it. A better case for math can be made with machine learning, image and audio processing, etc.
  - NotOscarWilde 13y ago
    Calculating recurrences is a very common problem in CS. We have an entire toolset -- dynamic programming -- built around it. 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.
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 ago
  Now 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 ago
  I can't upvote this comment enough. A lucid application of group theory to derive an operationally-efficient algorithm.
  - jordigh 13y ago
    Field theory, not group theory, at least not directly. The two are linked by the fundamental theorem of Galois theory.
- leephillips 13y ago
  This is mind-blowing. This comment is the best answer I've seen yet to the question, "Why learn Haskell?".
  - colomon 13y ago
    The 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 ago
      Props 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 ago
    This 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
taejo 13y ago
> In all fairness, if there were a type of algebraic numbers, the calculations would be exact. (But probably not O(1) anymore.) 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.

NotOscarWilde 13y ago

This solution -- O(log n) through repeated squaring -- is a good illustration of usefulness of many areas that "neighbor" computer science, such as linear algebra, combinatorics and graph theory. 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 http://kam.mff.cuni.cz/~matousek/la-ams.html

jules 13y ago
I don't think this illustrates the practical usefulness of mathematics. This is not a practical problem, it's a mathematical problem. It's no surprise that maths is useful for solving it. A better case for math can be made with machine learning, image and audio processing, etc.
- NotOscarWilde 13y ago
  Calculating recurrences is a very common problem in CS. We have an entire toolset -- dynamic programming -- built around it. 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.

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 ago
Now 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 ago
I can't upvote this comment enough. A lucid application of group theory to derive an operationally-efficient algorithm.
- jordigh 13y ago
  Field theory, not group theory, at least not directly. The two are linked by the fundamental theorem of Galois theory.
leephillips 13y ago
This is mind-blowing. This comment is the best answer I've seen yet to the question, "Why learn Haskell?".
- colomon 13y ago
  The 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 ago
    Props 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 ago
  This 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

taejo 13y ago

> In all fairness, if there were a type of algebraic numbers, the calculations would be exact. (But probably not O(1) anymore.) 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.