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

> On 28/05/06, Robert Klemme <shortcutter / googlemail.com> 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 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.