From: Christoph <chr_news@...>
Date: 2002-04-10T07:20:30+09:00
Subject: RE: Fibonacci Number Generators

It looks like that the mailing list and comp.lang-ruby.org are pretty
much disconnected these days???  For this reason I'll included  a
complete repost of Jabari Zakiya remarks and older post of mine.

>Jabari Zakiya" <jzakiya@mail.com> wrote 
> After looking at the submitted Fibonacci code, I'm
> getting a "better" idea of how Ruby works, and a
> "much better" education into the esoterica of
> "closed form" solutions and "generator functions".
> 
> So, now that I know what kind of algebraic tricks are
> being conducted to generate Fib(n), let me suggest
> a faster method, though I don't know how to code it
> in Ruby. I submit this as proposal to take up.
> 
> OK, here we go...
> 
> The closed form solution to generate Fib(n) is:
> 
> Fib(n) = (Phi**n - phi**n)/(5**0.5)
> 
> where the Golden Ratio, Phi = (1 + 5**0.5)/2 = 1.61803..
> 
> and phi = (Phi - 1) = 0.61803... and -phi = -0.61803...
> 
> Because phi is < 1, phi**n is <<< 1, as n because larger.
> 
> Thus, Fib(n) can be approximated by
> 
> Fib(n)'~ (Phi**n)/(5**0.5)
> 
> To do this we have 1 exponention (**), 1 division and 
> 1 square-root operation to do.
> 
> When we perform this we will get non-integer values,
> which only need to be roundedup to get the correct answer.
> 
> n = 2    Fib(2)'  ~ 1.1708..... roundup=> Fib(2) = 1
> n = 3    Fib(3)'  ~ 1.8944..... roundup=> Fib(3) = 2
> n = 4    Fib(4)'  ~ 3.0652..... roundup=> Fib(4) = 3
> n = 5    Fib(5)'  ~ 4.9596..... roundup=> Fib(5) = 5
> ..
> n = 10   Fib(10)' ~ 55.0036.... roundup=> Fib(10)= 55
> ..
> n = 30   Fib(30)' ~ 832040.00.. roundup=> Fib(30)= 832040
> ..
> 
> But the following may be a faster way to do the computations.
> 
> Using   Phi**2 = Phi + 1 = 2.61803... let's do instead
> 
> (Fib(n)')**2 = [(Phi**n)/(5**0.5)]**2 = (Phi**2n)/5 = (Phi+1)**n/5
> 
> where (Phi+1) = (3 + 5**0.5)/2 has the same number of operations
> as Phi
> 
> and thus    Fib(n)' ~ [(Phi+1)**n/5]**(0.5)
> 
> Thus, we now have an exopnentionation of an irrational number
> by 'n', but with a division by the integer 5. After this, we
> just take the square-root to get the final answer.
> 
> So,
> 1)in Ruby, which of these two forms can be coded to run faster?
> and
> 2) are these two forms faster than doing the full computations?
> 
> Jabari Zakiya


Your algorithm ``only'' calculates an approximation. The whole point of
the algebraic solution is to calculate the exact integer solution.  To
answer your question it seems to me that 1) must be faster simply
because it does not involve the final ``sqrt''. Anyway here is the
translation of your first algorithm into rubynese.

----
include Math
Phi = (sqrt(5) + 3)/ 2
Sqrt5 = sqrt 5
Low_values = [0,1,1,2,3,5]

def fib(n)
    return i if i < 2
    ((Phi**n)/ Sqrt5).round
end
----



My previous post:
<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 be easy to
implement).

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

....

/Christoph