From: jzakiya@... (Jabari Zakiya)
Date: 2002-04-10T10:31:45+09:00
Subject: Re: Fibonacci Number Generators

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 now what kind of alegraic 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 squar-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

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

"Christoph" <chr_news@gmx.net> wrote in message news:<a8oka8$br0$03$1@news.t-online.com>...
> <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.