[I changed the subject, so (hopefully) rare people who just follow the thread may miss it, but I couldn't look at the name of Fibonacci with two errors in it anymore...] Andrew Bromage rebukes me once more that the fl. point solution diverges from the integer one [as if I didn't know that...], and proposes to make this calculation in an algebraic extension field. OK. His program has just 20 lines. It seems that we are slowly streaming to the generation of all possible and impossible Fibonacci generators, which - as everybody knows - is absolutely essential for the future of Humanity. So, I have another contribution. I hope that the complexity is linear, but I don't want to check. The generation function of Fibonaccis: SUM_{n=0}^infty f_n*x^n, where x is a formal variable, is equal to x/(1-x-x^2). Thus, it suffices to represent this rational expression as formal power series in x. Let's write a small *lazy* package which manipulates such power series, implemented as lists: u_0 + u_1*x + u_2*x^2 + ... ==> [u_0, u_1, u_2,...]. I have written such a package some 12 years ago, then Doug McIlroy wrote independently a Functional Pearl paper about series... Here you are just a fragment of it, without transcendental functions (nor sqrt), without reversal, composition, or other thinks the series lovers appreciate. -- ******************* -- The 'x' variable is a series with coeff_1=1, remaining: zero. So: zeros = 0 : zeros x = 0:1:zeros -- Good to have something to multiply series by scalars. infixr 7 *> c *> s = map (c*) s -- Num instance. Only interesting line is the multiplication, co-recursive. instance (Num a) => Num [a] where fromInteger n = fromInteger n : zeros (+) = zipWith (+) (-) = zipWith (-) (u0:uq)*v@(v0:vq) = u0*v0 : u0*>vq + v*uq -- The division. Reconstructed from the multiplication. Also co-recursive. instance (Fractional a) => Fractional [a] where fromRational c = fromRational c : zeros (u0:uq) / v@(v0:vq) = let w0 = u0/v0 in w0:(uq - w0*>vq)/v -- and now the solution: fibs = x/(1-x-x*x) -- ********************** If you complain that you don't want floating point numbers, just add the signature :: [Rational] (and import Ratio before). Everything becomes fraction with denominator 1. Now Fritz Ruehr can take the Haskell Wiki page and reconstruct from it a new instance of the 'Evolution of Haskell Programmer', based on the most useless Fibonacci algorithms. BTW, for your general culture: you *should* know that Fibonacci numbers have been invented by an Indian mathematician and grammarian Pangala, famous for his book Chandas Shastra. Not too much is known about him. WP says: "In Indian literary tradition, Pingala is identified as the younger brother of Panini..." [who was a great grammarian from 4BC, and who - as some think also invented a specific version of Italian hot sandwiches. This brings us nearer to Leonardo Pisano]. Jerzy Karczmarczuk