Fibonacci numbers in Ruby

ntk () — Thu, 22 Feb 2007 12:24:45 GMT

From: http://www.ruby-forum.com/topic/67217
Author: C Erler

http://www.swox.com/gmp/manual/Fibonacci-Numbers-Algorithm.html





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

#fibs = (5..10).map { |i| i.fib }

#fibs = (1..100000).map { |i| i.fib }

#puts fibs.size

#puts fibs.last

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]





#-----------------------------------------------------------------------





# From: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/37727

# Author: Shin-ichiro HARA





  class QR3

    attr_reader :a, :b



    def inspect

      "{#{@a},#{@b}}"

    end

    alias to_s inspect



    def initialize(a, b)

      @a, @b = a, b

    end



    def *(r)

      u = (@a + @b)*(r.a + r.b)

      v = (@a - @b)*(r.a - r.b)

      QR3.new((u + v)>>1, @b*r.b + ((u - v)>>1))

    end



    def **(n)

      if n == 0

        QR3.new(1, 0)

      elsif n > 0

        z = x = self

        n -= 1

        while (z*= x if n[0].nonzero?; (n >>= 1).nonzero?)

          x *= x

        end

        z

      end

    end

  end



  def fib_qr3(n)

    (QR3.new(0, 1)**n).b

  end



n = 1000



start_time = Time.now

fib_qr3(n)

p Time.now - start_time

Fibonacci without loops nor recursions //JavaScript Function

jonasraoni (Jonas Raoni Soares Silva) — Mon, 07 Nov 2005 14:53:10 GMT

[UPDATED CODE AND HELP CAN BE FOUND HERE]

usage



for(var i = 11; --i > -11; document.write(i, " = ", fibonacci(i), "
"));

code



//+ Jonas Raoni Soares Silva

//@ http://jsfromhell.com/math/fibonacci [v1.0]



fibonacci = function(n){

	return Math.round(Math.pow((Math.sqrt(5) + 1) / 2, Math.abs(n)) / Math.sqrt(5)) * (n < 0 && n % 2 ? -1 : 1);

};



/*this one requires very few recursions

fibonacci = function(n){

	var x;

	return n < 2 ? n : n % 2 ? (x = fibonacci(n = -(-n >> 1))) * x + (x = fibonacci(n - 1)) * x : (fibonacci(n >>= 1) + 2 * fibonacci(n - 1)) * fibonacci(n);

};

*/

DZone Snippets: fibonacci code

Fibonacci numbers in Ruby

Fibonacci without loops nor recursions //JavaScript Function