An Integer Formula For Fibonacci Numbers
April 26, 2016
Today’s exercise isn’t really an exercise but an astonishing integer formula for computing the nth Fibonacci number; here it is in Python:
def fib(n):
return (4 << n*(3+n)) // ((4 << 2*n) − (2 << n) − 1) & ((2 << n) − 1)
You can see an explanation here and discussion here.
Your task is to translate the program to your favorite language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
I wondered if that would show up. Nice piece by Paul Hankin. Here’s a base 10 version, generalized a bit so we can start with different base values, a and b, and it’s more interesting, I think, to show the whole number computed, which contains a complete initial segment of the series. The
int(...)expression is attempting to calculate how many digits are needed for each value, I haven’t formally verified it & I suspect a tighter bound is possible, but it seems about right:import math def f(n,a,b): X = 10**int(1 + math.log10(max(a,b)) + n*math.log10(1.618)) return (b*X + a)*X**n//(X*X-X-1) print(f(20,0,1)) # Fibonacci # 100001000020000300005000080001300021000340005500089001440023300377006100098701597025840418106765 print(f(20,-1,2)) # Lucas # 200001000030000400007000110001800029000470007600123001990032200521008430136402207035710577809349Here’s a more or less literal translation to Haskell. To make it look more like the Python version we locally define an operator for left shift. It’s left associative (the l in infixl) and has a precedence less than that of addition, so we don’t need to add extra parentheses.
import Data.Bits fib :: Int -> Integer fib n = (4 << n*(3+n)) `rem` ((4 << 2*n) - (2 << n) - 1) .&. ((2 << n) - 1) where infixl 5 << (<<) = shiftL main :: IO () main = mapM_ (print . fib) [1..10]