From: Nuralanur@...
Date: 2006-05-29T04:25:24+09:00
Subject: Re: Fast Fibonacci method

-------------------------------1148844315
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit

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 
 

-------------------------------1148844315--