From: Christoph <chr_news@...>
Date: 2002-04-10T10:31:46+09:00
Subject: Re: Fibonacci Number Generators

<sinara@blade.nagaokaut.ac.jp> wrote in,
....
>   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.

This sounds like good news about the implementation quality
of Algebra package to me!!!

....

Since a previous post to comp.lang.ruby never made to the
mailing.list here is an url of the current gnu-gmp Fibonacci
implementation (it only uses 2 multiplication in each
iteration step but seems to easy  implement).

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

>
>
> 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])"

- i.e. all you need is a fast matrix-multiplication??


/Christoph