5 ms·

The Fibonacci example is flawed, in that the given definition, in terms of phi = (1 + sqrt 5) / 2.0, is inaccurate even for moderately-sized inputs. A standard,

The Fibonacci example is flawed, in that the given definition, in terms of phi = (1 + sqrt 5) / 2.0, is inaccurate even for moderately-sized inputs. A standard, O(n) definition for computing fibonacci numbers is >> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs) >> let fib n = fibs !! fromIntegral n The constant-time approximation is >> let fib' n = let phi (1 + sqrt 5) / 2.0 in round (phi^n / sqrt 5) Around n = 80 the constant-time solution starts giving incorrect results >> fib 80 -- exact O(n) 23416728348467685 >> fib' 80 -- approximate O(1) 23416728348467676

catnaroek 13y ago
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.
- 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.
zvrba 13y ago
Everybody seems to forget that addition in exact (arbitrary-precision) arithmetic is not O(1), so the "O(n)" solution is no longer O(n).
- crntaylor 13y ago
  Fair point! It's interesting to figure out what the complexity must be. There are certainly n additions to perform, and the numbers being added on the k'th step are of size O(phi^k) which will take O(log(phi^k)) = O(k log(phi)) to add. Therefore the total running time is 1 + 2 + ... + n = O(n^2) so the theory predicts quadratic, not linear time. I wonder if this is borne out by numerical experiments.
  - leephillips 13y ago
    I take a small stab at this here: http://lee-phillips.org/lispmath/ http://lee-phillips.org/lispmath/
jordigh 13y ago
This isn't a fair criticism for the C implementation. The output doesn't even remotely fit in a 32-bit int, which is what this implementation is for. "Moderately sized inputs" is a misleading thing to say for a function that grows exponentially. Would you protest that the ones digit in exp(80) is wrong in double-precision IEEE 754 arithmetic? The formula isn't innacurate. It's simply using data types that can't fit everything. The point of the article is that Binet's formula is something that should at least be mentioned when presenting the classical introductory examples of recursion to programmers. It's unfair to praise simplistic recursive functions without even mentioning that the same result can be obtained in a much more mathematically elegant way.
- kazagistar 13y ago
  If you are doing a fib function that is not valid up to an input of 80, you might as well just have a lookup table with 80 values in it. So much for mathematical elegance.
  - jordigh 13y ago
    How about a fib function that is valid for an input of 40.5? Binet's formula smoothly interpolates the Fibonnaci numbers. Quite elegant! And even without the interpolation, the original formula is accurate enough if you change the return type from int to double. Besides, writing Binet's formula is much shorter in the source code than hardwiring the lookup table. Way more elegant.

catnaroek 13y ago

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

zvrba 13y ago

Everybody seems to forget that addition in exact (arbitrary-precision) arithmetic is not O(1), so the "O(n)" solution is no longer O(n).

crntaylor 13y ago
Fair point! It's interesting to figure out what the complexity must be. There are certainly n additions to perform, and the numbers being added on the k'th step are of size O(phi^k) which will take O(log(phi^k)) = O(k log(phi)) to add. Therefore the total running time is 1 + 2 + ... + n = O(n^2) so the theory predicts quadratic, not linear time. I wonder if this is borne out by numerical experiments.
- leephillips 13y ago
  I take a small stab at this here: http://lee-phillips.org/lispmath/ http://lee-phillips.org/lispmath/

jordigh 13y ago

This isn't a fair criticism for the C implementation. The output doesn't even remotely fit in a 32-bit int, which is what this implementation is for. "Moderately sized inputs" is a misleading thing to say for a function that grows exponentially. Would you protest that the ones digit in exp(80) is wrong in double-precision IEEE 754 arithmetic? The formula isn't innacurate. It's simply using data types that can't fit everything. The point of the article is that Binet's formula is something that should at least be mentioned when presenting the classical introductory examples of recursion to programmers. It's unfair to praise simplistic recursive functions without even mentioning that the same result can be obtained in a much more mathematically elegant way.

kazagistar 13y ago
If you are doing a fib function that is not valid up to an input of 80, you might as well just have a lookup table with 80 values in it. So much for mathematical elegance.
- jordigh 13y ago
  How about a fib function that is valid for an input of 40.5? Binet's formula smoothly interpolates the Fibonnaci numbers. Quite elegant! And even without the interpolation, the original formula is accurate enough if you change the return type from int to double. Besides, writing Binet's formula is much shorter in the source code than hardwiring the lookup table. Way more elegant.