## 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.

Pages: 1 2

### 2 Responses to “An Integer Formula For Fibonacci Numbers”

1. matthew said

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
# 200001000030000400007000110001800029000470007600123001990032200521008430136402207035710577809349
```
2. Globules said

Here’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]
```
```\$ ./intfib
1
2
3
5
8
13
21
34
55
89
```