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