Fibonacci Calculator
Enter n to find the nth Fibonacci number.
A whole number from 0 to 10 000.
Try
Result
You entered
Number of digits
Ratio to the previous
Show the work
Fibonacci recurrence
Each Fibonacci number is the sum of the two before it, starting from and .
Using
Fast doubling
Adding up terms one by one is slow for a large . Fast doubling instead reads the binary digits of from the left and, for each digit, jumps from and to the pair for or ; that takes only about doublings.
Using
Binet's formula as a check
For a large the term is far too small to matter, so is almost exactly . That gives about 3.54225 times 10 to the power 20, which matches the leading digits 354224 of the answer.
Using
Result
So .