Re: Fast Fibonacci method

Ruby
1

Why are you interested in the millionth Fibonacci number, actually ?

2

On 28/05/06, [email protected] [email protected] wrote:

Why are you interested in the millionth Fibonacci number, actually ?

I just chose a relatively high number to give some comparison of
asymptotic
performance (performance as the input value goes to infinity). If you
have
an algorithm that loses with low numbers like one million, but starts to
beat the code I gave at some higher input value (and gives perfectly
correct
results without rounding errors), please let me know, since a hybrid of
the
two can be used.

3

btw, did you try the iterative approach with results stored in an Array
or Hash?

robert

4

On May 28, 2006, at 9:42 PM, C Erler wrote:

because it
if zero?
def fib_iterative
start_time = Time.now
43.095

I don’t believe it. Really. Ruby doesn’t do tail-call optimization,
and even if it did I don’t see how the recursive function would be
that much faster than the iterative one. Yet, running the script
myself I get similiar results:
% ruby fib.rb
12.628659
18.508037
logan:/Users/logan/Projects/Ruby Experiments% ruby fib.rb
11.399135
17.393642

Something fishy is going on here.

5

On 28/05/06, Robert K. [email protected] wrote:

btw, did you try the iterative approach with results stored in an Array or
Hash?

robert

I can’t make the previous code iterative without difficulty, because it
isn’t tail-recursive. Someone on #ruby-lang gave me a relatively-quick
tail-recursive method, but making it iterative made it slower. I think
Ruby
(1.8.2) is trying to trick us into using functional programming or
something.

class Integer
def fib_tail_recursive a=1, b=0, p=1, q=0
if modulo(2).zero?
if zero?
b
else
p_p = pp
div(2).fib_tail_recursive a, b, p_p + 2pq, p_p + qq
end
else
(self - 1).fib_tail_recursive p*(a + b) + aq, ap + b*q, p, q
end
end

def fib_iterative
n, a, b, p, q = self, 1, 0, 1, 0
while n.nonzero?
a, b = p*(a + b) + aq, ap + bq if n.modulo(2).nonzero?
p_p = pp
n, p, q = n.div(2), p_p + 2pq, p_p + q*q
end
b
end
end

start_time = Time.now
1_000_000.fib_tail_recursive
p Time.now - start_time
start_time = Time.now
1_000_000.fib_iterative
p Time.now - start_time

This produces the timings (for comparison, the previous fib method takes
about 7 seconds) :
29.297
43.095

I also initially thought you might have meant the standard F[n] = F[n -
1] +
F[n - 2] method with memoization, but it simply gave me more evidence
that
loading Windows XP’s task manager from disk only when it’s requested is
not
a good idea for those users who need to kill a task that is thrashing
the
disk due to memory exhaustion while their system is frozen for ten
minutes
straight.

6

2006/5/29, C Erler [email protected]:

On 28/05/06, Robert K. [email protected] wrote:

btw, did you try the iterative approach with results stored in an Array or
Hash?

I can’t make the previous code iterative without difficulty, because it
isn’t tail-recursive. Someone on #ruby-lang gave me a relatively-quick
tail-recursive method, but making it iterative made it slower.

This is the usual iterative solution:

class Integer

not thread safe!

@@fib = [0, 1]

def fib
for i in @@fib.length … self
@@fib << @@fib[i - 1] + @@fib[i - 2]
end
@@fib[self]
end
end

With a little more effort you can limit array size to two and prevent
the error I was seeing:

1_000_000.fib
(irb):7:in +': failed to allocate memory (NoMemoryError) from (irb):7:in fib’
from (irb):6:in fib' from (irb):13:in irb_binding’
from /usr/lib/ruby/1.8/irb/workspace.rb:52:in `irb_binding’
from ¢¾:0

:-))

I think Ruby
(1.8.2) is trying to trick us into using functional programming or
something.

Ruby is generally not good at recursion. Some hope this improves with
2.0.

Kind regards

robert

7 
@@fib[self]

end
end

With a little more effort you can limit array size to two and prevent
the error I was seeing:

like

def fib nbr
a0, a1 = 1, 0
(nbr-2).times{a1, a0 = a0, a0+a1}
a0
end

?

But this is way slower than the OPs one.

cheers

Simon