lucas sequence benchmark

lucas_benchmark.rb

# we will benchmark our results to see just how much faster we can make this algorithm
require 'benchmark'

# original implementation
def lucas_number(n)
  if n == 0
    2
  elsif n == 1
    1
  elsif n > 1
    lucas_number(n - 1) + lucas_number(n - 2)
  else
    raise ArgumentError, "Lucas numbers are undefined for negative values"
  end
end

# these results show that the runtime for this algorithm increases exponentially. this is because as n grows, the number of times we must execute lucas_number grows at a rate of n * (n-1)
p 'lucas_number original benchmark'
p Benchmark.measure { lucas_number(0) }
p Benchmark.measure { lucas_number(2) }
p Benchmark.measure { lucas_number(20) }
p Benchmark.measure { lucas_number(30) }
p Benchmark.measure { lucas_number(35) }

# alternate recursive implementation
# the only change is that we call lucas_number(n-2) before lucas_number(n-1). this speeds up the runtime because it is n less recursive calls.
def lucas_number2(n)
  if n == 0
    2
  elsif n == 1
    1
  elsif n > 1
    lucas_number(n - 2) + lucas_number(n - 1)
  else
    raise ArgumentError, "Lucas numbers are undefined for negative values"
  end
end

# still, our results show a recursive implementation for a lucas sequence is still slow
p 'lucas_number2 alternative recursive benchmark'
p Benchmark.measure { lucas_number2(0) }
p Benchmark.measure { lucas_number2(2) }
p Benchmark.measure { lucas_number2(20) }
p Benchmark.measure { lucas_number2(30) }
p Benchmark.measure { lucas_number2(35) }

# iterative solution
# an iterative solution is much faster because we reduce the complexity of the algorithm from exponential to linear
def lucas_iterative(n)
  current_lucas, next_lucas = [2, 1]

  n.times do
    current_lucas, next_lucas = [next_lucas, (next_lucas + current_lucas)]
  end

  current_lucas
end

# our results back up the speed difference as well
p 'lucas_iterative iterative benchmark'
p Benchmark.measure { lucas_iterative(0) }
p Benchmark.measure { lucas_iterative(2) }
p Benchmark.measure { lucas_iterative(20) }
p Benchmark.measure { lucas_iterative(30) }
p Benchmark.measure { lucas_iterative(35) }