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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: