Ruby Fibonacci algorithm
Solution 1
Naive fibonacci makes a lot of repeat calculations - in fib(14)
fib(4)
is calculated many times.
You can add memoization to your algorithm to make it a lot faster:
def fib(n, memo = {})
if n == 0 || n == 1
return n
end
memo[n] ||= fib(n-1, memo) + fib(n-2, memo)
end
fib 14
# => 377
fib 24
# => 46368
fib 124
# => 36726740705505779255899443
Solution 2
As others have pointed out, your implementation's run time grows exponentially in n
. There are much cleaner implementations.
Constructive [O(n) run time, O(1) storage]:
def fib(n)
raise "fib not defined for negative numbers" if n < 0
new, old = 1, 0
n.times {new, old = new + old, new}
old
end
Memoized recursion [O(n) run time, O(n) storage]:
def fib_memo(n, memo)
memo[n] ||= fib_memo(n-1, memo) + fib_memo(n-2, memo)
end
def fib(n)
raise "fib not defined for negative numbers" if n < 0
fib_memo(n, [0, 1])
end
Recursive powers of a matrix multiplication using squared halving of the power for when you just gotta know really big factorials like 1_000_000.fib [O(log n) run time and storage (on stack)]:
def matrix_fib(n)
if n == 1
[0,1]
else
f = matrix_fib(n/2)
c = f[0] * f[0] + f[1] * f[1]
d = f[1] * (f[1] + 2 * f[0])
n.even? ? [c,d] : [d,c+d]
end
end
def fib(n)
raise "fib not defined for negative numbers" if n < 0
n.zero? ? n : matrix_fib(n)[1]
end
Solution 3
Your program has exponential runtime due to the recursion you use.
Expanding only the recursive calls a few levels to show you why:
fib(14) = fib(13) + fib(12)
= (fib(12) + fib(11)) + (fib(11) + fib (10))
= (((fib(11) + fib(10)) + (fib(10) + fib(9))) (((fib(10) + fib(9)) + (fib(9) + fib(8)))
= ... //a ton more calls
The terrible runtime might be causing your program to hang, as increasing fib(n)
by 1 means you have a TON more recursive calls
Solution 4
your program overflows as Kevin L explained.
instead, you can use an iterative algorithm like this:
def fib (n)
return 0 if n == 0
return 1 if n == 1 or n == 2
x = 0
y = 1
(2..n).each do
z = (x + y)
x = y
y = z
end
return y
end
(0..14).map { |n| fib(n) }
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
Solution 5
I tried comparing the run time of two fibonacci methods on repl.it
require 'benchmark'
def fib_memo(n, memo = {})
if n == 0 || n == 1
return n
end
memo[n] ||= fib_memo(n-1, memo) + fib_memo(n-2, memo)
end
def fib_naive(n)
if n == 0 || n == 1
return n
end
fib_naive(n-1) + fib_naive(n-2)
end
def time(&block)
puts Benchmark.measure(&block)
end
time {fib_memo(14)}
time {fib_naive(14)}
Output
0.000000 0.000000 0.000000 ( 0.000008)
0.000000 0.000000 0.000000 ( 0.000099)
As you can see, the runtime is quite different. As @Uri Agassi suggested, use memoization. The concept is explained quite well here https://stackoverflow.com/a/1988826/5256509
user3769323
Updated on December 08, 2022Comments
-
user3769323 over 1 year
The following is a method I wrote to calculate a value in the Fibonacci sequence:
def fib(n) if n == 0 return 0 end if n == 1 return 1 end if n >= 2 return fib(n-1) + (fib(n-2)) end end
It works uptil n = 14, but after that I get a message saying the program is taking too long to respond (I'm using repl.it). Anyone know why this is happening?
-
Casimir et Hippolyte almost 10 yearsI have dreamed about that and Ruby makes it possible.
-
Daniël Knippers almost 10 yearsYour code does not run by the way, there should not be an
end
after theif
before theelse
, andrange
is not valid either. I will edit your code to make it work, revert / adjust if you disagree. -
sertsedat almost 10 yearswell, I just wrote it with a sleepy head, I would appreciate the edit.
-
pjs almost 10 yearsVery elegant, nice job.
-
Anatoly over 8 yearsthis called not caching but memoization instead
-
JCC about 4 yearsThis method seems to return the number after the one you want. fib(5) should return 3 and not 5 which is the number after.
-
Uri Agassi about 4 years@JCC - like everything in computing - this was implemented as a zero based vector, meaning the first element is
fib(0)
. This means thatfib(5)
retrieves the 6th element in the list... -
JCC about 4 years@UriAgassi What would we have to do to make it start on fib(1)?
-
Uri Agassi about 4 years@JCC - that's a great question - give it a try! see if you can make the minimal change to enable this - remember to check rigorously (including edge cases!)
-
Pablo over 3 yearsThe Fibonacci series is: 0, 1, 1, 2, 3, 5, 8, 13, 21.... Your algorithm is not producing the correct result. For example, for the 20th element in the fibonacci series it returns 10946 instead of 6765; it's doing an extra iteration. Also, it should return 1 when the input is 2. To fix these issues, the range shoud be
(2..n)
and you should add the linereturn 1 if n == 2
. I like your algorithm though.