Monday, March 9, 2015

Coding The Fibonacci Sequence

The Fibonacci sequence is a special mathematical set of integers. It is tied to many concepts, and has no "real" function, and only way to describe it formulaically is through a recursive definition. And this is how you write code for it...

Before getting to the computer science, let me first describe what Fibonacci Numbers are. The sequence starts at $0$ or $1$. By convention of modern mathematics, we'll start at $0$, and our code will consider only this situation. You may have seen the Fibonacci Sequence before, it is often described as a sequence found in nature, and Tim and Moby used rabbit breeding to describe it in their BrainPop video. The sequence and formula goes like:


$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... $
$F_n = F_{n-1} + F_{n-2}$

As you can tell, the sequence follows a simple formula, but we cannot really call it a function, because the next term always relies on the previous terms. Though there are closed form representations of the Fibonacci sequence, that may be worth an entirely new blog post. Each term, as you can observe, is the sum of the previous two terms in the sequence. Of course, $0 + 1 = 1$, so that is why $1$ is the second and third term. Then, it's $1 + 2$, $2 + 3$, $3 + 5$, $...$ until the end. There's no real ratio between these numbers. It has been observed, though, that the larger the sequence gets, if the $n$th and $n-1$th terms are divided, that value will be close to the Golden Ratio, $φ = 1.6180...$. We will display this relationship in our program.

 
G O L D E N S P I R A L

So, how do we code this mess? It's actually pretty simple. I think CS is a great tool for solving math puzzles. I will also shamelessly link to another post on my blog on how to solve computer science problems, as I will be following the pattern of thinking that I describe there. If we were posed with the problem of:

Create a program that displays the Fibonacci sequence until the nth term, as described by a stop number.

So, again, what is this really asking of us? Are there any special cases that we need to consider? Here are some questions to ask yourself before even touching your IDE.
  • Does this program require any type of input? What kind of input?
  • Does this program have any type of output? What kind of output?
  • Can I write what I expect the program to output?
  • Can I create an algorithm based on a formula I already know?
Of course, if you scroll up, you will see that we have already discussed everything you need to know about the Fibonacci sequence, including a formula. Now, how would you translate this into code? First, let us consider some test cases, or documentation of what we expect our program to do.

Test Cases
possible inputs expected output
-2 ???
0 0...
1 0, 1...
4 0, 1, 1, 2...
... ...

Woah. So let's go over our expectations for our program. We know that we're going to tell the program to stop printing the sequence at a certain "stop" number. This stop is our input integer, representing the $n$th term that we stop at. This number can take on many forms:
  • all negative integers
  • zero (a border case)
  • one
  • all other positive integers 
It's up to you, the programmer, to determine whether your program should include a condition for these cases. What if a negative number is inputted? Should it crash, show an error message, take the absolute value, or what? The same goes for $0$. Since the sequence starts at $0$ traditionally, you could just print the first term, $0$. You could also code it to start at $1$, where term one is actually $0$. However you choose, you should remain consistent. As long as you think about these inputs and outputs, creating the program will become simpler.

The next step is to write pseudocode, or plain-English step-by-step instructions that you can understand. Using our recursive formula above, let's try to generate some sort of algorithm for finding the $n$th Fibonacci.

1. stop = get stop number
2. term1 = 0
3. term2 = 1
4. current = 0
5. counter = 0
6. print term1
7. print term2
8. while (counter <= stop):
9.      current = term1 + term2
10.     print current
11.     term1 = term2
12.     term2 = current
13.     counter = counter + 1

The code above will work (in Python, maybe lol). Essentially, we start our terms at $0$ and $1$. We print these values out on new lines, then create a while loop with a counter that we start at $0$, and let it act as a ticker for each consecutive term. So as long as we are less than our stop value, we can go through the loop. The loop then (given the condition is met), will set the current term to the sum of the previous two terms (sound familiar?). Then, it prints out the current term, then makes some adjustments. It sets the first term to the second, and the second term to the current term. This is to walk through the sequence while gathering all of the right numbers. See the GIF below for a visual representation of what this loop is actually doing.
This will continue until the current term is the same value as the stop term.
 

As it turns out, there's an even simpler way of doing this. How about just checking if the $n$th term is $0$ or $1$, and then returning the sum of the Fibonacci numbers for the $n-1$ and the $n-2$ terms? That's the more elegant solution. Of course, the above code will work, too. Below is the Java representation of the code, as well as a screenshot from their outputs.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Fibonacci {
    //the GOLDEN RATIO
    private static final double PHI = (float)(1 + Math.sqrt(5)) / 2;
    
    /**
     * fibonacci is a method that, using {@code int}, returns
     * the nth Fibonacci number. The algorithm checks if the parameter is zero
     * or one, of whose nth number in the Fibonacci sequence are zero and one, 
     * respectively. If the parameter is neither of these integers, then it 
     * returns <i> the sum of the immediate previous Fibonacci number in the 
     * sequence and the second previous Fibonacci number in the sequence. </i> 
     * 
     * <p>This sequence follows the definition of the Fibonacci sequence, where 
     * F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub>. This is a
     * <i>recurrence relation</i> whose Power Series can be represented as
     * the sum of <i>(n-k-1) choose (k) starting from k = 0 to n - 1</i>, where
     * <i>n</n> belongs to the set of all natural numbers. This is one of 
     * many series representations of the Fibonacci Numbers. The accepted
     * closed-form expression of these representations is the rational function
     * <i>(t)/(1-t-t<sup>2</sup>)</i>.
     * 
     * @param x         The nth term in the Fibonacci sequence.    
     * @return          An algorithmic recursive call to fibonacci resulting in
     *                  that nth Fibonacci number.
     */
    private static int fibonacci(int x) {
        //TODO negafibonacci
        if (x == 0) 
            return 0;
        else if (x == 1)
            return 1;
        else
            return fibonacci(x - 1) + fibonacci(x - 2);
    }
    
    /**
     * printFib is a method that, from a {@code int} describing the nth
     * term of the Fibonacci sequence, keeps a String of all terms in the
     * sequence until the stop term is met using the method fibonacci(). The 
     * stop parameter is set to its absolute value, to prevent issue with the 
     * call to fibonacci(). It is assumed that the parameter will not be of
     * incompatible type, though catching this error can be easily implemented.
     * 
     * @param stop          The nth term to stop printing of the sequence on.
     * @return              The created string of all Fibonacci numbers in the
     *                      sequence until the nth term, stop.
     */
    private static String printFib(int stop) {
        StringBuilder sb = new StringBuilder();
        stop = Math.abs(stop);
        for (int i = 0; i <= stop; i++) {
            if (i != stop)
                sb.append(fibonacci(i)).append(", ");
            else
                sb.append(fibonacci(i)).append("...");
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        System.out.println(printFib(-12));
        double silver = (float)fibonacci(19) / fibonacci(18);
        System.out.print("goldenratio: " + PHI + "\n19th / 18th: " + silver);
    }
}

Remember we wanted to compare the terms' ratio? As it turns out, when you get to the nineteenth Fibonacci number, if you divide the $19$th term by the $18$th term, you will get the golden ratio. Here is a screenshot of the output of the Java program.

As a fun little additive, I will show you how quickly the Fibonacci sequence grows (very quickly). Here is a fun GIF:


Posted by