Forum: Ruby Re: Fast Fibonacci method

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
67bb4df2775f6a6b603347dce7119571?d=identicon&s=25 unknown (Guest)
on 2006-05-28 21:27
(Received via mailing list)
Dear Erlercw,

just speculating ....
I think one method that might seem a little far-fetched, but maybe
worthwhile, if
you want to calculate big Fibonacci numbers via the formula of Wilf's
book, could use continued fractions (see
_http://mathworld.wolfram.com/ContinuedFraction.html_
(http://mathworld.wolfram.com/ContinuedFraction.html) ).
The point is that the continued fraction representation [a_0,a_1, ....]
of
1/2+sqrt(5)/2 is [1,1,1,...], so it's periodic.

Now, in _ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-0760.pdf_
(ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-0760.pdf)  ,
formulas (14) and (15), there is a method for potentiating and taking
logarithms of
arbitrary continued fractions.

I'd now replace the millionfold multiplication by
a multiplication of the logarithm, and exponentiate once for each of
the terms, and convert back, in the hope of finding some pattern
in the continued fraction (depending on the exponent).

My feeling is that there has to be some point where it's more costly
to multiply on and on in contrast to such a method, but I don't now
whether it's already reached at F_{10**6}, and it's clear that
you have to count implementation time for the methods also....


Best regards,

Axel
E2a9d30a2487a924165aaaa016b54f87?d=identicon&s=25 C Erler (Guest)
on 2006-05-29 05:29
(Received via mailing list)
On 28/05/06, Nuralanur@aol.com <Nuralanur@aol.com> wrote:
> The point is that the continued fraction representation [a_0,a_1,
> a multiplication of the logarithm, and exponentiate once for each of
>
> Axel


Thanks, I'll take a look at that, but it may be a little while from the
looks of the paper :).
This topic is locked and can not be replied to.