3
$\begingroup$

I want to evaluate that Fibonacci[28143753246]. However the result is OverFlow[]. Is there any way to evaluate it?

Thank you.

$\endgroup$
  • 1
    $\begingroup$ See this question on PPCG, especially this Mathematica answer. While this question was about the one billionth Fibonacci number and your question is about the 28-billionth Fibonacci number, you may gain some ideas. $\endgroup$ – Stephen S Aug 3 '17 at 15:17
11
$\begingroup$

Have you thought about whether this is a reasonable thing to try to compute exactly?

There is a closed form formula for Fibonacci numbers which allows us to estimate the number of digits in the answer:

Fibonacci[k] // FunctionExpand
(* ((1/2 (1 + Sqrt[5]))^k - (2/(1 + Sqrt[5]))^k Cos[k π])/Sqrt[5] *)

For large k the answer is approximately

GoldenRatio^k / Sqrt[5]

therefore it will have about

k / (Log[10]/Log[GoldenRatio])

decimal digits, or

k / (Log[2]/Log[GoldenRatio])

binary digits.

Plugging in your value gives about $10^{10}$ binary digits. That is on the order of gigabytes of data, just to store the final result, not to mention computing it to the desired accuracy, and storing intermediate results.

To me, this suggests that:

  • This is not a particularly useful thing to compute exactly except for a very few very special uses
  • Computing it exactly requires a lot of resources, and probably an efficient custom approach (instead of a general system like Mathematica)
  • You can get an approximate result using the formula above

Could Mathematica do the exact computation in principle? I do not know how Fibonacci works, but Mathematica has a limit on the largest numbers it can handle. This differs from computer to computer and can be checked using

$MaxNumber
(* 1.605216761933662*10^1355718576299609 *)

As you can see, on my computer this limit is much higher than the result you are looking for, so in principle, Mathematica can store the final result (but perhaps not the intermediate ones). Any time $MaxNumber is exceeded, the result will be Overflow[].

I tried to evaluate your input, and after letting it run for 5 minutes I cancelled the evaluation. During this time it did not throw an Overflow[], but I do not know how long the computation would take.

What about the approximate result? That is easy:

N[GoldenRatio^28143753246/Sqrt[5]]
(* 2.040489385525467*10^5881696578 *)
$\endgroup$
  • $\begingroup$ Thanks for your responce. However, the result of the code N[GoldenRatio^28143753246/Sqrt[5]] is also OverFlow[] in my computer. $\endgroup$ – MATIRMAK Aug 3 '17 at 9:57
  • $\begingroup$ @MATIRMAK Are you using a very old 32-bit version? What does {$Version, $ReleaseNumber, $SystemWordLength} say? $\endgroup$ – Szabolcs Aug 3 '17 at 10:12
  • $\begingroup$ My computer says Versionis 8.0 and 64 bit, Releasenumber is 0 and SystemWordLenghtis 64. Since i am not expert of the using Mathematica well, i did not unberstand what are they. $\endgroup$ – MATIRMAK Aug 3 '17 at 10:43
  • $\begingroup$ @MATIRMAK I suspect it may be a limitation of version 8 then. Probably $MaxNumber is too low in that version, even in 64-bit. Version 10.0 can handle it, I have not tried 9.0. You could try to the free online version of Mathematica (which is at version 11.1). It has a time limit, but it should be able to do N[GoldenRatio^28143753246/Sqrt[5]] (which is instantaneous). $\endgroup$ – Szabolcs Aug 3 '17 at 10:49
  • 3
    $\begingroup$ Fibonacci[28143753246`100] could also be used to get the approximate result. $\endgroup$ – Carl Woll Aug 3 '17 at 15:59

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.