A lot of people have mentioned Binet's formula. But I suspect this is not the most practical way to compute the nth Fibonacci number for large n, because it requires either having a very accurate value of $\sqrt{5}$ and carrying around lots of decimal places (if you want to do floating-point arithmetic) or expanding large powers of $1+\sqrt{5}$ using the binomial formula. The latter comes out to writing the Fibonacci number as a sum of binomial coefficients.

The following formulas hold, though: $$F(2n-1) = F(n)^2 + F(n-1)^2$$ $$F(2n) = (2F(n-1) + F(n)) \times F(n)$$ which you can find derivations of in the Wikipedia article on Fibonacci numbers. This lets you find $F(k)$, for any $k$ even or odd, in terms of two Fibonacci numbers with approximately half the index. The result is faster than Binet's formula.

A lot of people have mentioned Binet's formula. But I suspect this is not the most practical way to compute the nth Fibonacci number for large n, because it requires either having a very accurate value of $\sqrt{5}$ and carrying around lots of decimal places (if you want to do floating-point arithmetic) or expanding large powers of $1+\sqrt{5}$ using the binomial formula. The latter comes out to writing the Fibonacci number as a sum of binomial coefficients.

The following formulas hold, though:$$F_{2n-1}=F_n^2+F_{n-1}^2$$$$F_{2n}=(2F_{n-1}+F_n)\cdot F_n$$which you can find derivations of in the Wikipedia article on Fibonacci numbers. This lets you find $F_k$, for any $k$ even or odd, in terms of two Fibonacci numbers with approximately half the index. The result is faster than Binet's formula.

A lot of people have mentioned Binet's formula. But I suspect this is not the most practical way to compute the nth Fibonacci number for large n, because it requires either having a very accurate value of sqrt(5) and carrying around lots of decimal places (if you want to do floating-point arithmetic) or expanding large powers of (1+sqrt(5)) using the binomial formula. The latter comes out to writing the Fibonacci number as a sum of binomial coefficients.

The following formulas hold, though: F(2n-1) = F(n)^2 + F(n-1)^2 F(2n) = (2*F(n-1) + F(n)) F(n) which you can find derivations of in the Wikipedia article on Fibonacci numbers. This lets you find F(k), for any k even or odd, in terms of two Fibonacci numbers with approximately half the index. The result is faster than Binet's formula.

A lot of people have mentioned Binet's formula. But I suspect this is not the most practical way to compute the nth Fibonacci number for large n, because it requires either having a very accurate value of $\sqrt{5}$ and carrying around lots of decimal places (if you want to do floating-point arithmetic) or expanding large powers of $1+\sqrt{5}$ using the binomial formula. The latter comes out to writing the Fibonacci number as a sum of binomial coefficients.

The following formulas hold, though: $$F(2n-1) = F(n)^2 + F(n-1)^2$$ $$F(2n) = (2F(n-1) + F(n)) \times F(n)$$ which you can find derivations of in the Wikipedia article on Fibonacci numbers. This lets you find $F(k)$, for any $k$ even or odd, in terms of two Fibonacci numbers with approximately half the index. The result is faster than Binet's formula.