From: C Erler <erlercw@...>
Date: 2006-05-27T08:38:16+09:00
Subject: Re: Fast Fibonacci method

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

A slightly faster method :

class Integer
  FibonacciCache =3D Hash.new do |hash, key|
    if hash.has_key?(key - 1) and hash.has_key?(key - 2)
      hash[key] =3D hash[key - 1] + hash[key - 2]
    elsif hash.has_key?(key + 1) and hash.has_key?(key + 2)
      hash[key] =3D hash[key + 2] - hash[key + 1]
    else
      subkey =3D key.div(2)
      case key.modulo(4)
        when 1
          hash[key] =3D (2*hash[subkey] + hash[subkey - 1])*(2*hash[subkey]=
 -
hash[subkey - 1]) + 2
        when 3
          hash[key] =3D (2*hash[subkey] + hash[subkey - 1])*(2*hash[subkey]=
 -
hash[subkey - 1]) - 2
        else
          hash[key] =3D hash[subkey] * (hash[subkey] + 2*hash[subkey - 1])
      end
    end
  end
  FibonacciCache[0] =3D 0
  FibonacciCache[1] =3D 1

  def fib
    return FibonacciCache[self]
  end

  def fib_uncached
    return FibonacciCache.dup[self]
  end
end

start_time =3D Time.now
1_000_000.fib
p Time.now - start_time
puts "Doesn't work !" unless (1..10).map { |i| i.fib } =3D=3D [1, 1, 2, 3, =
5, 8,
13, 21, 34, 55]

------=_Part_45675_512083.1148686690033--