Forum: Ruby Fast Fibonacci method

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
C Erler (Guest)
on 2006-05-27 03:15
(Received via mailing list)
The fastest pure-Ruby Fibonacci method I have been able to come up with
is a
copy of the GMP algorithm described at
http://www.swox.com/gmp/manual/Fibonacci-Numbers-A...

Is there a Ruby implementation that gets better time results for the
millionth Fibonacci number (timing code included at bottom) ?

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

  def fib
    return FibonacciCache[self]
  end

  def fib_uncached
    return FibonacciCache.dup[self]
  end
end

start_time = Time.now
1_000_000.fib
p Time.now - start_time
puts "Doesn't work !" unless (1..10).map { |i| i.fib } == [1, 1, 2, 3,
5, 8,
13, 21, 34, 55]
C Erler (Guest)
on 2006-05-27 03:40
(Received via mailing list)
A slightly faster method :

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

  def fib
    return FibonacciCache[self]
  end

  def fib_uncached
    return FibonacciCache.dup[self]
  end
end

start_time = Time.now
1_000_000.fib
p Time.now - start_time
puts "Doesn't work !" unless (1..10).map { |i| i.fib } == [1, 1, 2, 3,
5, 8,
13, 21, 34, 55]
Robert K. (Guest)
on 2006-05-27 13:37
(Received via mailing list)
Other suggesgtions (untested, i.e. unmeasured)

 - use shift operator instead of *2 and /2

 - put your 4 alternatives (i.e. key % 4) as lambdas into another hash
and then do
   algo[key % 4][subkey]

Kind regards

robert
C Erler (Guest)
on 2006-05-28 19:53
(Received via mailing list)
On 27/05/06, Robert K. <removed_email_address@domain.invalid> wrote:
>
> robert


Thanks for your suggestions.  I tried both, but could only get the same
speed.
This topic is locked and can not be replied to.