[Haskell-cafe] More on Fibonacci numbers
jerzy.karczmarczuk at info.unicaen.fr
jerzy.karczmarczuk at info.unicaen.fr
Wed Nov 7 04:30:30 EST 2007
[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
More information about the Haskell-Cafe
mailing list