Fibbing a Sequence

The Fibonacci sequence is a one of those mathematical formulas that I learned in grade school and promptly went in one ear and out the other. This formula solved a rabbit breeding problem that Fibonacci created in one of his works in 1202. Recursive in nature, the formula creates a sequence of numbers where the sum of the last two numbers in the sequence create the next number.

For the first two numbers in the sequence they are defined as follows.

The next number is the sum of the last two numbers in the sequence.

By substituting the first two known numbers, the third number in the sequence would be.

And the fourth number would be.

The following Ruby program computes the Fibonacci sequence, using an array fibonacci_seq to store calculated numbers in the sequence. This makes it easy to compute higher numbers for F(n) where n > 1, as the numbers are easily accessible in the array.

Note: Due to some quirks in the Wordpress’ new sourcecode feature, I am unable to display the less-than symbol. I’ve had to use the greater-than symbol in conditionals where I wouldn’t normally put them.

# Generates the sequence of Fibonacci numbers starting
# from F(0) and ending at F(_max_amount_) where F is
# the Fibonacci formula.
# [+max_amount+]  The highest fibonacci number to
#                 generate in the sequence.
def generate_fibonacci_seq(max_amount)
  n = 0
  # An array of Fibonacci numbers
  fibonacci_seq = Array.new

  if (max_amount >= 0) then
    while (max_amount >= n)
      if n == 0 then
        # F(0) = 0
        fibonacci_seq.push(0)
      elsif n == 1 then
        # F(1) = 1
        fibonacci_seq.push(1)
      else
        # F(n) = F(n - 2) + F(n - 1)
        last_two_numbers = fibonacci_seq.last(2)
        fibonacci_seq.push(last_two_numbers[0] + last_two_numbers[1])
      end

      n = n + 1
    end
  end

  return fibonacci_seq
end

# Generate the first 32 Fibonacci numbers
fib_seq = generate_fibonacci_seq(31)
puts fib_seq

Ruby Rant: The abbreviated form of the conditional keyword elsif annoys me because other programming languages spell out the phrase as else if. I’d personally prefer being able to switch from one programming language to another without worrying these inconsistencies. One day I’m going to type an elsif in PHP and have my editor flag the conditional keyword as an error.

The output of the first five numbers are:

0
1
1
2
3

I’d prefer to display the number in a list that flows horizontally. The Array class provides a method each which iterates through each element in the array. Ruby provides a nice feature for quickly processing iterators, in this case the iterator is the each method, with a feature known as blocks. A (code) block appears to the right of the iterator method between braces {code_block}.

# Generate the first 32 Fibonacci numbers
fib_seq = generate_fibonacci_seq(31)
fib_seq.each { |element| print "#{element} " }
print "\n"

Within a block, the parameter appears between two pipe symbols |parameter|. In the above example, the parameter is element. To the right of the parameter are instructions for processing the element. For each element that I encounter, I’ll print the element with a trailing space to separate the next number.

Using the each iterator, the output for the first 32 number of the Fibonacci sequence is:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269