Overview

The Fibonacci sequence is an algorithm. We give input to the algorithm, the algorithm runs, and we get an outcome. Most applications follow this basic idea. Your basic web interface takes your input ( "GET /" for example ) and returns output in the form of a properly ( hopefully! ) formatted HTTP response.

The objective here is create an algorithm using ruby that can take input, use the Fibonacci sequence on the input, then give us output. We expect the output to be an array of numbers that line up with our expected output of the classical mathematical work.

Building

First let's do a quick and dirty example here. This is sort of the brute force approach to solving the problem. In the interest of clean code I'm going to do explain the code here in the post, but leave the code in a state without comments. This way I can keep the conversation about the code separate from the code itself. You are welcome and encouraged to clone this repo and explore the code on your own.

  • Seed array with 1,1 to get everything started
  • Set the number of times we want to iterate
  • Iterate n number of times
  • For each iteration:
    • Set a and b using our current iteration and iteration + 1
    • Add both a and b together and store the result
    • Push the result to the seeded array
  • Output the result to STDOUT
krogebry@ubuntu-secure:~/dev/krogebry.github.io/code/fib$ ./fib_big.rb 
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]

Forward looking

Now let's say that we want to do what we normally do with things like this and make this into something that someone else can consume. We're going to skip the mechanics of building gems and all of that, and just go with a basic example of how we can implement this as a basic function.

Code

The idea here is just to move the basic logic into a function that performs the same actions and creates the same output. 

krogebry@ubuntu-secure:~/dev/krogebry.github.io/code/fib$ ./fib_func.rb 
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]

This is about as quick and dirty as we can get. This would allow us to implement the fib(N) function somewhere else. Luckily this is still within the boundaries of linear time: O(n). This isn't very fancy or elegant, but probably would pass the KISS concept.

Tribonacci sequence

Example

[1, 1, 1, 3, 5, 9, 17, 31, 57, 105]

This is basically building on what we have with fib in that we're just adding one more element to the sequence. The easy solution is to just add a "c" element to our loop and be done with it. However, I made the choice to KISS the "Forward looking" part, but I'm not going to make that same choice here.

Instead I'm going to choose to take this one step further and build on the idea of an Nth processing system. This will allow for an arbitrary number of "nacci" sequences. I feel that this more appropriately demonstrates the real-world example of increasing complexity in an unknown future state.

Code

We're moving things around a little here. First we're creating an integer for num_naccis which is used in our main loop when creating the sequence. We're also implementing a new function called make_fib_array(n). 

def make_fib_array(num_naccis)
  Array.new(num_naccis, 1)
end

This serves two important purposes:

  • Breaking some basic functionality out into another function allows us to change it later if needed.
  • Most importantly this allows us to wrap some unit testing around this function in the future.

Next we're changing how we're calculating the value of the next element. Here we're using the num_naccis to add each element of the array. 

  num_fib_iterations.times do |i|
    result = 0
    num_naccis.times do |nacci_i|
      result += fib_array[i+nacci_i]
    end
    fib_array.push( result )
  end

Example: first iteration of the loop

  • fib_array: [1,1,1]
  • The method adds element 0,1,2, which is: 1+1+1=3

Example: second iteration of the loop

  • fib_array: [1,1,1,3]
  • The method adds element 1,2,3, which is: 1+1+3=5

Output n=3

krogebry@ubuntu-secure:~/dev/krogebry.github.io/code/fib$ ./nth_nacci.rb 
[1,
 1,
 1,
 3,
 5,
 9,
 17,
 31,
 57,
105,
193,
355,
653,
1201,
2209,
4063,
7473,
13745]

Output n=4

krogebry@ubuntu-secure:~/dev/krogebry.github.io/code/fib$ ./nth_nacci.rb 
[1,
 1,
 1,
 1,
 4,
 7,
 13,
 25,
 49,
 94,
 181,
 349,
 673,
 1297,
 2500,
 4819,
 9289,
 17905,
 34513]