From: sinara@...
Date: 2002-04-05T18:12:04+09:00
Subject: Re: Fibonacci Number Generators

In message "Re: Fibonacci Number Generators"
    on 02/04/05, Dave Thomas <Dave@PragmaticProgrammer.com> writes:

|> def fib(n)
|>     if n < 2 then
|> 	fib = n	 # for fib(0)=0 & fib(1)=1
|>     else
|> 	fib = f1 = 0
|> 	f2 = 1
|> 	(n-1).times do
|> 		fib = f1 + f2
|> 		f1 = f2
|> 		f2 = fib
|> 	end
|>     end
|>     fib
|> end

|There may well be some number theory here that let's you do amazing
|things, but otherwise all I'd do is remove the unnecessary variable:
|
|    def fib1(n)
|      return n if n < 2
|      f1, f2 = 0, 1
|      (n-1).times { f1, f2 = f2, f1+f2 }
|      f2
|    end

Here I show some examples inadequate for newbie's question :-)

1. The parallel assignment makes an Array object, so it costs
a little. It may be better to avoid that and use the temporary
variable which belongs to the outside of the iterator block:

  def fib2(n)
    return n if n < 2
    f1, f2 = 0, 1
    tmp = nil
    (n-1).times {
      tmp = f1; f1 = f2; f2 += tmp # swap
    }
    f2
  end

This resembles the original fib(n) as a result.

2. If you want to calculate fib(n) repeatedly, cashing the 
intermediate results is advantageous:

  def (Fib = [0, 1]).[](n)
    super || Fib[n] = Fib[n-1] + Fib[n-2]
  end

The disadvantage of this tricky code is that Fib can be defined
only at the top level and that Fib[10000] raises SystemStackError.

3. Algebraic solution. We can use "Algebra" package:

  http://www.ruby-lang.org/en/raa-list.rhtml?name=Algebra

  require "algebra"	
  def fib_alg(n)
    sqrt5 = AlgebraicExtensionField(Rational){|a| a**2 - 5}.var
    (((1+sqrt5)/2)**n - ((1-sqrt5)/2)**n)/sqrt5
  end

Of course this runs very slowly, because that this calculation
depends on the heavy operations of Rational.

Using Integer instead of Rational, the next is rather faster
than fib_alg(n):

  require "algebra"	
  def fib_alg_int(n)
    sqrt5 = AlgebraicExtensionField(Integer){|a| a**2 - 5}.var
    ((1+sqrt5)**n - (1-sqrt5)**n)*sqrt5 / 5 / 2**n
  end

Surprisingly, in spite of not optimizing 'Algebra' for such
computations, fib_alg_int(n) is 2.5 times as fast as fib2(n)
for n = 100000.

4. The reason that fib_alg_int(n) is faster than fib2(n) is :
fib2(n) costs O(n) but fib_alg_int(n) costs O(log(n)).
I take out the essential calculation from "algebra":

  class Quadratic5
    @@m = 5
    attr_reader :a, :b
  
    def initialize(a, b)
      @a, @b = a, b
    end
  
    def *(other)
      c, d = other.a, other.b
      type.new(@a * c + @b * d * @@m, @a * d + @b * c)
    end

    def **(n)
      if n == 0
        type.new(1, 0)
      elsif n == 1
        self
      elsif n > 1
        q , r = n.divmod 2
        x = self ** q
        x = x * x
        x = x * self if r > 0
        x
      end
    end
  end

  def fib_q(n)
    (Quadratic5.new(1, 1)**n).b >> n-1
  end

This is faster than fib2(n) even if n = 100.



Shin-ichiro HARA