# Re: Fast Fibonacci method

**URL:** <https://www.ruby-forum.com/t/re-fast-fibonacci-method/95329>\
**Category:** Ruby\
**Created:** [May 28, 2006, 9:27pm UTC](https://www.ruby-forum.com/t/re-fast-fibonacci-method/95329 "2006-05-28T21:27:29Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [May 28, 2006, 9:27pm UTC](https://www.ruby-forum.com/t/re-fast-fibonacci-method/95329/1 "2006-05-28T21:27:29Z")

</div>

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_)  
([Continued Fraction -- from Wolfram MathWorld](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

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [May 29, 2006, 5:29am UTC](https://www.ruby-forum.com/t/re-fast-fibonacci-method/95329/2 "2006-05-29T05:29:43Z")

</div>

On 28/05/06, removed\_email\_address@domain.invalid [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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 :).