Fibonacci with Ruby

Question

This was a problem, which i solved:

@cache={}
@cache[1]=0
@cache[2]=1

def fib(n)
  @fibs[n-1]
end

def fib_m(n)
  @cache[n] ||= fib_m(n-1) + fib_m(n-2)
end

@fibs=[]
@fibs=(1..100000).map{|n| fib_m(n)}

But this looks hacky. It seems like I am doubling the caching, and I have to hard code some upper limit. Is there a cleaner way to do this?

Check for example: https://stackoverflow.com/questions/24438655/ruby-fibonacci-algorithm — iGian, Aug 29 '18 at 02:13
iGian, thanks for the link, the above is what I am up with after that link and a few others. It works, is performant, but is just hacky. — Cliff Stamp, Aug 30 '18 at 00:35

Stefan · Answer 1 · 2018-08-29T07:46:01.563

1

Is there a cleaner way to do this?

You can assign a default_proc to calculate missing hash values dynamically:

fib = { 0 => 0, 1 => 1 }
fib.default_proc = ->(f, n) { f[n] = f[n-1] + f[n-2] }

fib[10]
#=> 55

fib
#=> {0=>0, 1=>1, 2=>1, 3=>2, 4=>3, 5=>5, 6=>8, 7=>13, 8=>21, 9=>34, 10=>55}

Note that this approach is limited by Ruby's stack size.

edited Aug 29 '18 at 07:46

answered Aug 29 '18 at 07:40

Stefan

109,145
14
143
218

1

Nice way of using `default_proc`. – Aleksei Matiushkin Aug 29 '18 at 07:48

score 0 · Answer 2 · answered Aug 29 '18 at 04:08

0

If you enable tail call optimization in Ruby, you might achieve the same result recursively, which is faster, less memory consuming and more elegant.

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,  
  trace_instruction: false  
}

def fib(curr = 1, acc = 0, n)
  n <= 0 ? acc : fib(acc, curr + acc, n - 1)
end

fib(100_000).to_s.length
#⇒ 20899

answered Aug 29 '18 at 04:08

Aleksei Matiushkin

119,336
10
100
160

1

Note that `RubyVM` is a private internal implementation detail of YARV, and will not work on MRI (which some tutorials still use), JRuby, IronRuby, Rubinius, MagLev, or Opal. Also note that neither the Ruby Language Specification, nor RubySpec, nor Programming Ruby, nor the RDoc documentation guarantee TCO. – Jörg W Mittag Aug 29 '18 at 21:07

Fibonacci with Ruby

2 Answers2