Fibonacci Calculator

Enter n to find the nth Fibonacci number.

A whole number from 0 to 10 000.

Try

Result

You enteredF100F_{100}

F100=354224848179261915075\displaystyle F_{100} = 354224848179261915075

Number of digits

21\displaystyle 21

Ratio to the previous

1.618034\displaystyle 1.618034
Show the work
  1. Fibonacci recurrence

    Each Fibonacci number is the sum of the two before it, starting from F0=0F_0 = 0 and F1=1F_1 = 1.

    Using Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}

    0,  1,  1,  2,  3,  5,  8,  13,  21,  34,  55,  89,  …0,\; 1,\; 1,\; 2,\; 3,\; 5,\; 8,\; 13,\; 21,\; 34,\; 55,\; 89,\; \dots
  2. Fast doubling

    Adding up 100100 terms one by one is slow for a large nn. Fast doubling instead reads the binary digits of nn from the left and, for each digit, jumps from FkF_k and Fk+1F_{k+1} to the pair for 2k2k or 2k+12k+1; that takes only about 77 doublings.

    Using F2k=Fk(2Fk+1−Fk)F2k+1=Fk2+Fk+12F_{2k} = F_k\left(2F_{k+1} - F_k\right) \quad F_{2k+1} = F_k^{2} + F_{k+1}^{2}

    100=11001002100 = 1100100_{2}
  3. Binet's formula as a check

    For a large nn the term ψn\psi^n is far too small to matter, so FnF_n is almost exactly φn/5\varphi^n / \sqrt{5}. That gives about 3.54225 times 10 to the power 20, which matches the leading digits 354224 of the answer.

    Using Fn=φn−ψn5F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}

    F100≈φ1005≈3.54225×1020F_{100} \approx \frac{\varphi^{100}}{\sqrt{5}} \approx 3.54225 \times 10^{20}
  4. Result

    So F100=354224848179261915075F_{100} = 354224848179261915075.

Worked examples