From: Christoph <chr_news@...>
Date: 2002-04-07T14:36:57+09:00
Subject: Re: Fibonacci Number Generators

<sinara@blade.nagaokaut.ac.jp> wrote in,
....
> The following is a non-recursive version of **:
>
>   def **(n)
>     if n == 0
>       type.new(1, 0)
>     elsif n > 0
>       z = x = self
>       n -= 1
>       while (n & 1 != 0 and z *= x; (n >>= 1) != 0)
>         x = x * x
>       end
>       z
>     end
>   end
>

Thank you very much for your interesting and innovative posts!
Here is a variant of your algebraic method which is more canonical
and also a bit faster.  It can be easily generalized to arbitrary Fibonacci
type sequences of any order.  I guess the Fibonacci speed champion
would combine caching for smaller values and an algebraic method for
larger ones.

----
# ``QR == Z [t] / (t^2 - t - 1)''
class QR
    attr_reader :a, :b
    def inspect
      "{#{@a},#{@b}}"
    end
    alias to_s inspect

    def initialize(a, b)
      @a, @b = a, b
    end

    def *(r)
      type.new(@a * r.a + @b * r.b, @a * r.b + @b * r.a + @b * r.b)
      # the following variant is faster for large @a, @b ...
      #  u = (@a + @b)*(r.a + r.b)
      #  v = (@a - @b)*(r.a - r.b)
      #  new.type((u +v )>>1, @b*r.b + (u - v)>> 1)
    end

    def **(n)
     if n == 0
       type.new(1, 0)
     elsif n > 0
       z = x = self
       n -= 1
        # rewrite of your ``**'' -loop for mere mortals
       while (z*= x if n[0].nonzero?; (n >>= 1).nonzero?)
         x *= x
       end
       z
     end
   end


  end

  def fib_q(n)
    (QR.new(0, 1)**n).b
  end


def p8
  puts (0..7).collect { |i,*j|  yield i,*j}.join ', '
end

p8 { |i|  fib_q(i)}
p8  { |i| QR.new(0,1)**i}
----
0, 1, 1, 2, 3, 5, 8, 13
{1,0}, {0,1}, {1,1}, {1,2}, {2,3}, {3,5}, {5,8}, {8,13}
----


/Christoph

Ps. In your time/space estimation you probably mend the ``local cost''.
The overall cost of a conventional Fibonacci is O(n^2) versus O(nlog(n))
for an algebraic version - well at least in theory since Ruby's Bignum
class probably does not sport a fast asymptotic multiplication.