Fibonacci Seq. strange output forms (Haskell)

Question

I was watching the results of my Fibobacci sequence implementation in Haskell when I realised some "strange" forms in the optput of the numbers.

First of all, this is the Haskell code I've come up with:

fib :: Integer -> [Integer]
fib 0 = [0]
fib 1 = [0, 1]
fib a = (fib' 0 1 [0,1] 1 a)

fib' :: Integer -> Integer -> [Integer] -> Integer -> Integer -> [Integer]
fib' n1 n2 l cont n 
        | cont == n = l
        | otherwise = (fib' n2 n3 (l++[n3]) (cont+1) n)
             where n3 = n2 + n1

For something like fib 10 the output would be : [0,1,1,2,3,5,8,13,21,34,55] Then I wanted to try something like fib 1000, while the numbers are incredibly big and all... what I saw was some strange elipses formed by the "," that is printed out between each Integer from the list, for example:

example1

So I've maxed the size of the output window to see if this strange pattern would still repeat, and the answer is yes:

example2

And my question is:

Does anybody know why appears this pattern in "," between the Integers from the list? Shouldn't it be more random and less like elipses?

Answer 1

Fibonacci numbers grow as an exponential function of n.

The length of a number in decimal is essentially its logarithm base 10. Thus, the length of a Fibonacci grows like a linear function of n, because the logarithm and exponential cancel each other.

Thus, if you printed them in a column, you'd see a straight line. But you print them one by another, so the positions accumulate. If you're taking cumulative sums of a linear sequence, you get a quadratic sequence.

Locally, every line contains about the same number of Fibonacci numbers, let's call it k. This means two things:

1. The line number changes linearly with n.
2. To compute the real positions of commas (relative to the window's left edge), we need to take the remainder of the cumulative "absolute position" modulo the line length. That's equivalent (on average) to subtracting 1/k per every increment of n. This adjustment is linear and does not change the quadratic behaviour of the position.

So what you're seeing is a parabola — the graph of a quadratic function.

Answer 2

There's nothing strange when you come to think about it. Neighbouring Fibonacci numbers have similar length, and the length is increasing with the sequence. So assume you have a 30-character screen size, and your current F(n) have 29 digits, then for the next several numbers, the length could be:

29, 29, 29, 30, 30, 30, 31, 31, 31

Which gives you the left -> stable -> right movement.