From: C Erler <erlercw@...>
Date: 2006-05-29T12:27:51+09:00
Subject: Re: Fast Fibonacci method

------=_Part_232828_27511861.1148873268852
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On 28/05/06, Nuralanur@aol.com <Nuralanur@aol.com> wrote:
>
> 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


Thanks, I'll take a look at that, but it may be a little while from the
looks of the paper :).

------=_Part_232828_27511861.1148873268852--