```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
==============================================================

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