From: sinara@...
Date: 2002-04-08T13:11:03+09:00
Subject: Re: Fibonacci Number Generators

Hi,

In message "Re: Fibonacci Number Generators"
    on 02/04/07, "Christoph" <chr_news@gmx.net> writes:

|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

It's very excellent!! Certainly, we have not to treat irrational
numbers (the solution of t^2 - t - 1 = 0). For n = 100000, your
QR runs twice as fast as Quadratic5([ruby-talk:37582]).

I thought about Z[t]/(t^2 - t - 1) too, but I didn't use it
because there isn't the canonical way to get the coefficient
of `t'. (i.e. it is not a graded ring.) But your code makes
me remember that `AlgebraicExtensionField#lift'(inherited
from `ResidueClassRing#lift') is available accidentally.
Here is a short code:

  require "algebra"
  def fib_alg_lift(n)
    ((AlgebraicExtensionField(Integer){|t| t**2-t-1}.var)**n).lift[1]
  end

Strangely, fib_alg_lift(n) is faster than QR for n = 100000.
I can't understand the reason.


|    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

The commented codes are fine, because the number of products
is three (originally four). Correcting the typo and the 
precedency of operators, I write QR again:

  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)
      type.new((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
        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

I estimated fib_qr3(n) for n = 100000. It is the fastest among all
as you mentioned!


|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.

Yes, you are right.

Furthermore, I should think about that the Bignum's bit
operators is not especially fast.


Finally, I add a one-liner. This is just the shortest, but slower
than fib_alg_lift(100000):

  $ruby -rmatrix -e"p((Matrix[[0, 1], [1, 1]]**99999)[1, 1])"



Shin-ichiro HARA