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

# Re: Fast Fibonacci method

**unknown**#2

On 28/05/06, removed_email_address@domain.invalid removed_email_address@domain.invalid 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.

**unknown**#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.

**unknown**#5

On 28/05/06, Robert K. removed_email_address@domain.invalid 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 = p*p
div(2).fib_tail_recursive a, b, p_p + 2*p

*q, p_p + q*q

end

else

(self - 1).fib_tail_recursive p*(a + b) + a

*q, a*p + 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) + a*q, a*p + b*q if n.modulo(2).nonzero?
p_p = p*p

n, p, q = n.div(2), p_p + 2

*p*q, 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.

**unknown**#6

2006/5/29, C Erler removed_email_address@domain.invalid:

On 28/05/06, Robert K. removed_email_address@domain.invalid 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

**unknown**#7

`@@fib[self]`

end

endWith 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