Divide by phi ((1 + sqrt(5)) / 2
) and round to nearest integer.
This works because the Nth Fibonacci number is
Fn = (Phi ^ n - Psi ^ n) / (Phi - Psi)
where Psi = -1 / Phi
. By rearranging the formula and massaging it a bit, you will get that the difference between F_n+1 / Phi
and F_n
is less than Psi ^ n
, and since | Psi | < 1
, rounding to the nearest integer will yield the correct result.