Fibonacci summary

The code to generate the nth Fibonacci number should be pretty simple, the Haskell I provided does it.

fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

The real question though was two part, what happens when we ask for the Fibonacci number for a negative n and what would the code look like to generate this?

What I was really hoping to read was some descriptions of how people went about discovering the pattern of the numbers for negative n. But I didn't get any of that :(

Unfortunately I didn't keep the code that Jeroen and I wrote when we first did this (we were just doing it for fun as I was showing him how Haskell works using the interactive ghci shell). We quickly realised that we needed something that was a bit more convenient to put values into than this:

let fib 1 = 1; fib 2 = 1; fib n = fib (n-1) + fib (n-2)

The problem with this formula is that it focuses on the wrong thing, what is the nth Fibonacci whilst what we wanted to do was to ask what sequence we would get from different starting values. We started by looking at something like this:

let fibseq (a:b:rs) = (a+b) : a : b : rs

This takes a list of a Fibonacci sequence in reverse and puts the next value at the head. This is a good start, but we want to see more of the values. The obvious step is to make it recursive:

let fibseq (a:b:rs) = fibseq ( (a+b) : a : b : rs )

There is a clear drawback to this though, no ground case means an infinite loop. We fixed this by adding an extra parameter to determine how long a sequence we should generate.

let fibseq l 0 = l; fibseq (a:b:rs) n = fibseq ( (a+b) : a : b : rs ) (n-1)

This gives some rather pleasant output:

Prelude> fibseq [ 1,1 ] 10
[ 144,89,55,34,21,13,8,5,3,2,1,1 ]

It's the right sequence, but it's reversed. What's a little more awkward is that the start sequence is also reversed.

Prelude> fibseq [ 1,0 ] 10
[ 89,55,34,21,13,8,5,3,2,1,1,0 ]

So long as we keep our wits about us we can keep trying to guess what the next earlier number should be. If the rest of the sequence looks right we're fine. Of course I wasn't able to keep my wits about me so we ended up wanting to reverse things so that they were in the order we expected. The output was easy:

Prelude> let fibseq l 0 = reverse l; fibseq (a:b:rs) n = fibseq ( (a+b) : a : b : rs ) (n-1)
Prelude> fibseq [ 0,1 ] 10
[ 1,0,1,1,2,3,5,8,13,21,34,55 ]

But that doesn't help with the input side, and frankly that's where we're more likely to get confused (even doing it again now I've already confused myself several times with this). Now I suspect that there's a very clever way of doing this without needing a wrapper function, but we went with the pragmatic approach:

Prelude> fibseq ( reverse [ 0,1 ] ) 10
[ 0,1,1,2,3,5,8,13,21,34,55,89 ]
Prelude> fibseq ( reverse [ 1,0 ] ) 10
[ 1,0,1,1,2,3,5,8,13,21,34,55 ]

But what was the next earlier number?

Prelude> fibseq ( reverse [ -1,1 ] ) 10
[ -1,1,0,1,1,2,3,5,8,13,21,34 ]

The next one was harder to find:

Prelude> fibseq ( reverse [ -2,-1 ] ) 10
[ -2,-1,-3,-4,-7,-11,-18,-29,-47,-76,-123,-199 ]
Prelude> fibseq ( reverse [ 3,-1 ] ) 10
[ 3,-1,2,1,3,4,7,11,18,29,47,76 ]
Prelude> fibseq ( reverse [ 0,-1 ] ) 10
[ 0,-1,-1,-2,-3,-5,-8,-13,-21,-34,-55,-89 ]
Prelude> fibseq ( reverse [ 2,-1 ] ) 10
[ 2,-1,1,0,1,1,2,3,5,8,13,21 ]
Prelude> fibseq ( reverse [ 2,-1 ] ) 15
[ 2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233 ]

When we got the next one Jeroen spotted a trend (he's much quicker than I am):

Prelude> fibseq ( reverse [ -3,2 ] ) 15
[ -3,2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144 ]
Prelude> fibseq ( reverse [ -89,55 ] ) 15
[ -89,55,-34,21,-13,8,-5,3,-2,1,-1,0,-1,-1,-2,-3,-5 ]
Prelude> fibseq ( reverse [ 89,-55 ] ) 15
[ 89,-55,34,-21,13,-8,5,-3,2,-1,1,0,1,1,2,3,5 ]
Prelude> fibseq ( reverse [ 89,-55 ] ) 30
[ 89,-55,34,-21,13,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765 ]

There's a symmetry about the zeroth Fibonacci with the negative side alternating between positive and negative values. To turn this into a properly working fib function though is best done in an editor and gives this:

fib n
    | n == 0 = 0
    | n == 1 = 1
    | n > 1 = fib (n-1) + fib (n-2)
    | n < 0 && odd n = fib (-n)
    | otherwise = -(fib (-n))

And we can verify that we get what we expect:

*Main> map fib [ -20..20 ]
[ -6765,4181,-2584,1597,-987,610,-377,233,-144,89,-55,34,-21,13,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765 ]

That last takes an appreciable amount of time to run on my Core 2 Duo desktop. For a much quicker solution (at least for positive n and in Haskell) you want to take a look at No "fib"bing; getting into the monad groove (thanks pphetra). Not that you really need the monad though:

fib n
    | n == 0 = 0
    | n > 0 = fib' n
    | n < 0 && odd n = fib' (-n)
    | otherwise = -(fib' (-n))
        where
            fibseq l 0 = reverse l
            fibseq (a:b:hs) s = fibseq ((a+b):a:b:hs) (s-1)
            fib' n = ( fibseq [ 1,0 ] n ) !! n

Running this over the integers -100 to 100 took no appreciable time on my machine. This is of course kind of nice because it means that fibseq function turned out to be pretty useful in the end.