For a more efficient Haskell implementation of fibonacci numbers, try

fibs :: [Integer] fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

fib n = fibs !! n

This is uglier, but just to keep using just plain recursion: fib = fib' 0 1 where fib' a b 0 = a fib' a b n = fib' b (a+b) (n-1) You may want "fib' a b n | a `seq` b `seq` n `seq` False = undefined" for strictness if the compiler isn't smart enough to figure out (sorry, didn't test it). And, *please* correct me if I said something stupid =). See ya, -- Felipe.

G'day all. Quoting Dan Weston :

In any case, to answer your question more specifically, the memoization of *constants*

I think you meant "CAFs".

You can just unroll the loop yourself to see. The following runs as fast as you'd expect:

fib00 = 0 fib01 = 1 fib02 = fib00 + fib01 [deletia] fib30 = fib28 + fib29

This is why we don't pay programmers by LOC.

For a parametrized function fib n, no mere syntactic transformation can be so made.

That's right, but you can do it by hand. Incidentally, we've been here before. Check out this thread: http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623 Cheers, Andrew Bromage

I assume you meant

fib n=(((1+s)/2)^n-((1-s)/2)^n)/s where s=sqrt 5

Your solution starts to diverge from reality at n = 76:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Prelude> let n = 76 in fibs !! n - round (fib n) 1 jerzy.karczmarczuk@info.unicaen.fr wrote:

Andrew Bromage:

...

G'day all. (MIS)Quoting Dan Weston:

...

...

fib00 = 0 fib01 = 1 fib02 = fib00 + fib01 [deletia] fib7698760 = fib7698759 + fib7698758

This is why we don't pay programmers by LOC. ... Incidentally, we've been here before. Check out this thread: http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623

There is one solution missing there (unless I skipped it) fib n=((1+s)/2)^n-((1-s)/2)^n)/s where s=sqrt 5 If some of you complain that this is real, not integer, please remember that Leonardo of Pisa thought of applying this to rabbits. Well, rabbits are not integers, they eat carrots and have long ears. They are real thing. Hm. Well, sqrt is Floating. Now, floating rabbits are less common. Jerzy Karczmarczuk

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

[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

Andrew Bromage:

I do note that nobody has tried it with continued fractions yet.

Now, it depends... If we take the PHI expansion as a CF: 1,1,1,1,1,... then the convergents constitue the (rations of) Fibonaccis, but it goes through the standard recurrence, so it is not so fancy. But we can take a decent representation of the Rabbit Number, in binary: 0.101101011011010110101101101011...., and then develop it in CF, which will give [0; 1, 2, 2, 4, 8, 32, 256, ...], then we find that those numbers are powers of Fibonaccis, 8=2^3, 32=2^5, 256=2^8, the next is 2^13, etc. It suffices to take the binary logarithm and the problem is solved. This is an industrial-strength, serious algorithm, involving lazy Rabbit Sequences, infinite Continued Fractions and Binary Logarithms, so everybody sees that it will for sure contribute to the Progress of the Western Civilization. I leave the homework for some Haskell newbies who want to become famous. Anyway, if somebody finds in his/her library The Fibonacci Quarterly, there is therein most probably much more about this fascinating subject, essential for our comprehension of the Universe, and of Phyllotaxis in particular. Jerzy Karczmarczuk

Stefan O'Rear wrote:

On Wed, Nov 07, 2007 at 10:30:30AM +0100, jerzy.karczmarczuk@info.unicaen.fr wrote:

...

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

People with real e-mail clients will still see it in the thread because you still have In-reply-to and References set up correctly. Changing the topic in mid-thread isn't hazardous to us.

In addition, if you take an arbitrary message in "FP design", hit "reply", erase all quoting, and change the subject line to "About Fibonacci again...", then In-Reply-To and References are still set up correctly so that real e-mail clients still put it under the tree structure of "FP design", so hopefully people with real e-mail clients will miss it.

Am Freitag, 9. November 2007 02:25 schrieb jerzy.karczmarczuk@info.unicaen.fr:

Since I have no idea what a "real" mail client is, you will not frighten me! My mail client is apparently complex.

As long as it's not purely imaginary...

Jerzy Karczmarczuk

Cheers, Daniel

On Tue, 6 Nov 2007 ajb@spamcop.net wrote:

However, this is still an O(log n) algorithm, because that's the complexity of raising-to-the-power-of. And it's slower than the simpler integer-only algorithms.

You mean computing the matrix power of /1 1\ \0 1/ ?

There are some nice formulae for the Fibonacci numbers that relate f_m to values f_n where n is around m/2. This leads to a tolerably fast recursive algorithm. Here's a complete implementation: fib 0 = 0 fib 1 = 1 fib 2 = 1 fib m | even m = let n = m `div` 2 in fib n*(fib (n-1)+fib (n+1)) | otherwise = let n = (m-1) `div` 2 in fib n^2+fib (n+1)^2 Combine that with the NaturalTree structure here: http://www.haskell.org/haskellwiki/Memoization and it seems to run faster than Mathematica's built in Fibonacci function taking about 3 seconds to compute fib (10^7) on my PC. -- Dan On 11/7/07, Henning Thielemann wrote:

On Tue, 6 Nov 2007 ajb@spamcop.net wrote:

...

However, this is still an O(log n) algorithm, because that's the complexity of raising-to-the-power-of. And it's slower than the simpler integer-only algorithms.

You mean computing the matrix power of

/1 1\ \0 1/

? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe