[jshrjuga] direct Fibonacci formula without division

golden ratio:

phi = (1 + sqrt(5)) / 2

the version of Binet's formula for the nth Fibonacci number which uses the round-to-the-nearest-integer function is

F[n] = round( phi^n / sqrt(5) )

if that division by sqrt(5) is annoying, another way to write it is

F[n] = round( phi^(n-z) )

where

z = log( Base phi, sqrt(5) ) = log(5) / (2*log(phi)) ~= 1.6722759381845547461703191263944365539

.

not sure what this would be useful for.  you need exp and log to compute exponentiation by the non-integer exponent, in contrast to simpler exponentiation by squaring for the integer exponent in the original formula.