## An Integer Formula For Fibonacci Numbers

### April 26, 2016

Here is a Scheme version that uses the bitwise operators in R6RS:

```(define (fib n)
(bitwise-and
(quotient
(ash 4 (* n (+ 3 n)))
(- (ash 4 (* 2 n)) (ash 2 n) 1))
(- (ash 2 n) 1)))```

> (map fib (range 25))
(0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584
4181 6765 10946 17711 28657 46368 75025)

You can run the program at http://ideone.com/phPnOi, where you will also see the `range` function as well as the bitwise operators if your Scheme doesn’t provide them. Astonishing.

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
```