From: C Erler <erlercw@...>
Date: 2006-05-29T10:42:18+09:00
Subject: Re: Fast Fibonacci method

------=_Part_232270_9990367.1148866935602
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On 28/05/06, Robert Klemme <shortcutter@googlemail.com> wrote:
>
> btw, did you try the iterative approach with results stored in an Array o=
r
> 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 Rub=
y
(1.8.2) is trying to trick us into using functional programming or
something.

class Integer
  def fib_tail_recursive a=3D1, b=3D0, p=3D1, q=3D0
    if modulo(2).zero?
      if zero?
        b
      else
        p_p =3D 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 =3D self, 1, 0, 1, 0
    while n.nonzero?
      a, b =3D p*(a + b) + a*q, a*p + b*q if n.modulo(2).nonzero?
      p_p =3D p*p
      n, p, q =3D n.div(2), p_p + 2*p*q, p_p + q*q
    end
    b
  end
end

start_time =3D Time.now
1_000_000.fib_tail_recursive
p Time.now - start_time
start_time =3D 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] =3D 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.

------=_Part_232270_9990367.1148866935602--