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
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: