Fibo.rb

benchmarks.out

                     user       system     total        real
Iterative (10)       0.000000   0.000000   0.000000  (  0.000006)
Formula   (10)       0.010000   0.000000   0.010000  (  0.010514)
Recursive (10)       0.000000   0.000000   0.000000  (  0.000004)
Iterative (20)       0.000000   0.000000   0.000000  (  0.000004)
Formula   (20)       0.040000   0.000000   0.040000  (  0.043513)
Recursive (20)       0.000000   0.000000   0.000000  (  0.000010)
Iterative (100)      0.010000   0.000000   0.010000  (  0.000048)
Formula   (100)      1.130000   0.010000   1.140000  (  1.141393)
Recursive (100)      0.000000   0.000000   0.000000  (  0.000034)
Iterative (200)      0.000000   0.000000   0.000000  (  0.000031)
Formula   (200)      4.450000   0.000000   4.450000  (  4.459401)
Recursive (200)      0.000000   0.000000   0.000000  (  0.000037)
Iterative (500)      0.000000   0.000000   0.000000  (  0.000145)
Formula   (500)      29.870000   0.100000  29.970000 ( 30.047385)

fibo.rb

require "bigdecimal"

module Fibo
  PRECISION = 1000

  ZERO      = BigDecimal.new("0.0")
  ONE       = BigDecimal.new("1.0")
  TWO       = BigDecimal.new("2.0")
  SQRT_5    = BigDecimal.new("5.0").sqrt(PRECISION)

  PHI_1     = (SQRT_5 + ONE) / TWO
  PHI_2     = (ONE - SQRT_5) / TWO
  COEF_B    = ONE / SQRT_5
  COEF_D    = - COEF_B

  class << self
    def iterative(n)
      return 0 if n == 0
      return 1 if n == 1
      fib_n_1 = 0
      fib_n   = 1
      (n-1).times do
        tmp     = fib_n_1
        fib_n_1 = fib_n
        fib_n   = fib_n + tmp
      end
      fib_n
    end

    def recursive(n, fib_n_1 = 0, fib_n = 1)
      return fib_n_1 if n == 0
      recursive(n-1, fib_n, fib_n + fib_n_1)
    end

    def formula(n)
      phi_e_n   = PHI_1.power(n, PRECISION)
      b_phi_e_n = COEF_B.mult(phi_e_n, PRECISION)

      phi2_e_n = PHI_2.power(n, PRECISION)
      d_phi2_e_n = COEF_D.mult(phi2_e_n, PRECISION)

      b_phi_e_n.add(d_phi2_e_n, PRECISION).round
    end
  end
end

if $0 == __FILE__
  require "benchmark"
    Benchmark.bm do |benchmark|
    [10, 20, 100, 200, 500].each do |position|
      benchmark.report("Iterative (#{position})") { Fibo.iterative(position) }
      benchmark.report("Recursive (#{position})") { Fibo.recursive(position) }
      benchmark.report("Formula   (#{position})") { Fibo.formula(position)   }
    end
  end
end

fibo_test.rb

require_relative "test_helper"
require_relative "../lib/fibo"

class FiboTest < Minitest::Unit::TestCase

  RESULT_50   = 12586269025
  RESULT_100  = 354224848179261915075
  RESULT_500  = 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
  RESULT_1000 = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

  def asserts_for_small_load(operation)
    assert_equal  0,  Fibo.send(operation, 0),  "Fibonacci #{operation} for 0"
    assert_equal  1,  Fibo.send(operation, 1),  "Fibonacci #{operation} for 1"
    assert_equal  1,  Fibo.send(operation, 2),  "Fibonacci #{operation} for 2"
    assert_equal  2,  Fibo.send(operation, 3),  "Fibonacci #{operation} for 3"
    assert_equal  3,  Fibo.send(operation, 4),  "Fibonacci #{operation} for 4"
    assert_equal  5,  Fibo.send(operation, 5),  "Fibonacci #{operation} for 5"
    assert_equal  55, Fibo.send(operation, 10), "Fibonacci #{operation} for 10"
  end

  def asserts_for_medium_load(operation)
    assert_equal  RESULT_50,    Fibo.send(operation, 50),   "Fibonacci #{operation} for 50"
    assert_equal  RESULT_100,   Fibo.send(operation, 100),  "Fibonacci #{operation} for 100"
  end

  def asserts_for_large_load(operation)
    assert_equal  RESULT_500,   Fibo.send(operation, 500),  "Fibonacci #{operation} for 500"
    assert_equal  RESULT_1000,  Fibo.send(operation, 1000), "Fibonacci #{operation} for 1000"
  end

  def test_recursive
    operation = :recursive

    asserts_for_small_load(operation)
    asserts_for_medium_load(operation)
    asserts_for_large_load(operation)
  end

  def test_formula
    operation = :formula

    asserts_for_small_load(operation)
    asserts_for_medium_load(operation)
  end

  def test_iterative
    operation = :iterative

    asserts_for_small_load(operation)
    asserts_for_medium_load(operation)
    asserts_for_large_load(operation)
  end
end

Improved by allowing Tail Recursion Optimisation, thanks to the idea raised by @belaustegui: https://gist.github.com/belaustegui/c1f6e5672915ee2d6327