0
\$\begingroup\$

I'm facing an unexpected behavior due to computational limits, I guess.

I have a function Log(x) which, for some high value in the Fibonacci series n 187 = 5.38·10^38 returns Infinity.

Is there a way I could follow to avoid this and always have computed numbers?

\$\endgroup\$
2
\$\begingroup\$

Here is a more numerically stable (for large values) way of getting Log(Fn) where Fn is the nth Fibonacci number. Let φ = (1 + sqrt(5)) / 2 and ψ = (1 - sqrt(5)) / 2. Then the nth Fibonacci number is:

      φⁿ - ψⁿ         1 - (ψ/φ)ⁿ
Fn = —————————  =  φⁿ ——————————
       φ - ψ            φ - ψ

The logarithm of Fn is therefore:

Log(Fn) = Log(φⁿ) + Log(1 - (ψ/φ)ⁿ) - Log(φ - ψ)

Which is the same as:

Log(Fn) = n Log(φ) + Log(1 - (-ψ/φ)ⁿ) - Log(φ - ψ)

This last expression is simple to compute and will not overflow.

You can see some example C# code here, with results up to Fib(1000): http://ideone.com/7VaRrK (the value for Fib(2) suffers from a minor rounding error, you could handle 1 and 2 as special cases if it is really important to you)

\$\endgroup\$
3
  • \$\begingroup\$ If my feelings are correct this is really the answer I was looking for, thank you. But I need to ask you some explainations since I'm quite a monkey trying to use math. Could you highlight how you definition of F(n) meets the canonical one? Why 1+sqrt(5)/2? I feel like I'm asking obvious questions but unfortunately I actually need the answer :) \$\endgroup\$ – Leggy7 Mar 17 '16 at 20:06
  • \$\begingroup\$ It is called Binet’s formula. You’ll find plenty of information on the Wikipedia page about Fibonacci numbers. \$\endgroup\$ – sam hocevar Mar 18 '16 at 8:13
  • \$\begingroup\$ Note that I slightly changed the notation used in my answer, adopting the more commonly used φ and ψ values. The result is exactly the same. \$\endgroup\$ – sam hocevar Mar 18 '16 at 10:02
3
\$\begingroup\$

You're trying to get the floating point logarithm of a number that isn't representable in a (single sized-)float. The limit of floating point numbers is around 3.402823e+38, larger than your number, truncating it to (positive) infinity.

If you want a logarithm for such large numbers you're going to have to use your own implementation.

However if you just want to use the fibonacci sequence you can simply store their logarithms calculated via an arbitrary precision calculator like dc.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.