Module: CompSci::Fibonacci

Defined in:
lib/compsci/fibonacci.rb

Class Method Summary collapse

Class Method Details

.cache_iterative(n) ⇒ Object 



14
15
16
17
18
 
# File 'lib/compsci/fibonacci.rb', line 14

def self.cache_iterative(n)
  cache = [0, 1]
  2.upto(n) { |i| cache[i] = cache[i-1] + cache[i-2] }
  cache[n]
end

.cache_recursive(n, cache = {}) ⇒ Object 



9
10
11
12
 
# File 'lib/compsci/fibonacci.rb', line 9

def self.cache_recursive(n, cache = {})
  return n if n < 2
  cache[n] ||= cache_recursive(n-1, cache) + cache_recursive(n-2, cache)
end

.classic(n) ⇒ Object 



5
6
7
 
# File 'lib/compsci/fibonacci.rb', line 5

def self.classic(n)
  n < 2 ? n : classic(n-1) + classic(n-2)
end

.dynamic(n) ⇒ Object 



20
21
22
23
24
 
# File 'lib/compsci/fibonacci.rb', line 20

def self.dynamic(n)
  a, b = 0, 1
  n.times { a, b = b, a+b }
  a
end

.matrix(n) ⇒ Object

gist.github.com/havenwood/02cf291b809327d96a3f slower than dynamic until around n == 500



28
29
30
 
# File 'lib/compsci/fibonacci.rb', line 28

def self.matrix(n)
  (Matrix[[0, 1], [1, 1]] ** n.pred)[1, 1].to_i
end