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

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “An Integer Formula For Fibonacci Numbers”

  1. matthew said
    April 26, 2016 at 6:45 PM

    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
    April 28, 2016 at 3:24 AM

    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

Leave a comment