nth fibonacci number in sublinear time

Question

Is there any algorithm to compute the nth fibonacci number in sub linear time?

Answer 1

Fixed point arithmetic is inaccurate. Jason's C# code gives incorrect answer for n = 71 (308061521170130 instead of 308061521170129) and beyond.

For correct answer, use a computational algebra system. Sympy is such a library for Python. There's an interactive console at http://live.sympy.org/ . Copy and paste this function

phi = (1 + sqrt(5)) / 2
def f(n):
    return floor(phi**n / sqrt(5) + 1/2)

Then calculate

>>> f(10)
55

>>> f(71)
308061521170129

You might like to try inspecting phi.

Answer 2

Here's a one-liner that computes F(n), using integers of size O(n), in O(log n) arithmetic operations:

for i in range(1, 50):
    print(i, pow(2<<i, i, (4<<2*i)-(2<<i)-1)//(2<<i))

Using integers of size O(n) is reasonable, since that's comparable to size of the answer.

To understand this, let phi be the golden ratio (the largest solution to x^2=x+1) and F(n) be the n'th Fibonacci number, where F(0)=0, F(1)=F(2)=1

Now, phi^n = F(n-1) + F(n)phi.

Proof by induction: phi^1 = 0 + 1*phi = F(0) + F(1)phi. And if phi^n = F(n-1) + F(n)phi, then phi^(n+1) = F(n-1)phi + F(n)phi^2 = F(n-1)phi + F(n)(phi+1) = F(n) + (F(n)+F(n-1))phi = F(n) + F(n+1)phi. The only tricky step in this calculation is the one that replaces phi^2 by (1+phi), which follows because phi is the golden ratio.

Also numbers of the form (a+b*phi), where a, b are integers are closed under multiplication.

Proof: (p0+p1*phi)(q0+q1*phi) = p0q0 + (p0q1+q1p0)phi + p1q1*phi^2 = p0q0 + (p0q1+q1p0)phi + p1q1*(phi+1) = (p0q0+p1q1) + (p0q1+q1p0+p1q1)*phi.

Using this representation, one can compute phi^n in O(log n) integer operations using exponentiation by squaring. The result will be F(n-1)+F(n)phi, from which one can read off the n'th Fibonacci number.

def mul(p, q):
    return p[0]*q[0]+p[1]*q[1], p[0]*q[1]+p[1]*q[0]+p[1]*q[1]

def pow(p, n):
    r=1,0
    while n:
        if n&1: r=mul(r, p)
        p=mul(p, p)
        n=n>>1
    return r

for i in range(1, 50):
    print(i, pow((0, 1), i)[1])

Note that the majority of this code is a standard exponentiation-by-squaring function.

To get to the one-liner that starts this answer, one can note that representing phi by a large enough integer X, one can perform (a+b*phi)(c+d*phi) as the integer operation (a+bX)(c+dX) modulo (X^2-X-1). Then the pow function can be replaced by the standard Python pow function (which conveniently includes a third argument z which calculates the result modulo z. The X chosen is 2<<i.

Answer 3

using R

l1 <- (1+sqrt(5))/2
l2 <- (1-sqrt(5))/2

P <- matrix(c(0,1,1,0),nrow=2) #permutation matrix
S <- matrix(c(l1,1,l2,1),nrow=2)
L <- matrix(c(l1,0,0,l2),nrow=2)
C <- c(-1/(l2-l1),1/(l2-l1))

k<-20 ; (S %*% L^k %*% C)[2]
[1] 6765

Answer 4

If you want the exact number (which is a "bignum", rather than an int/float), then I'm afraid that

It's impossible!

As stated above, the formula for Fibonacci numbers is:

fib n = floor (phiⁿ/√5 + ¹/₂)

fib n ~= phiⁿ/√5

How many digits is fib n?

numDigits (fib n) = log (fib n) = log (phiⁿ/√5) = log phiⁿ - log √5 = n * log phi - log √5

numDigits (fib n) = n * const + const

it's O(n)

Since the requested result is of O(n), it can't be calculated in less than O(n) time.

If you only want the lower digits of the answer, then it is possible to calculate in sub-linear time using the matrix exponentiation method.

Answer 5

see divide and conquer algorithm here

The link has pseudocode for the matrix exponentiation mentioned in some of the other answers for this question.

Answer 6

You can use the weird square rooty equation to get an exact answer. The reason is that the $\sqrt(5)$ falls out at the end, you just have to keep track of the coefficients with your own multiplication format.

def rootiply(a1,b1,a2,b2,c):
    ''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
    return a1*a2 + b1*b2*c, a1*b2 + a2*b1

def rootipower(a,b,c,n):
    ''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
    ar,br = 1,0
    while n != 0:
        if n%2:
            ar,br = rootiply(ar,br,a,b,c)
        a,b = rootiply(a,b,a,b,c)
        n /= 2
    return ar,br

def fib(k):
    ''' the kth fibonacci number'''
    a1,b1 = rootipower(1,1,5,k)
    a2,b2 = rootipower(1,-1,5,k)
    a = a1-a2
    b = b1-b2
    a,b = rootiply(0,1,a,b,5)
    # b should be 0!
    assert b == 0
    return a/2**k/5

if __name__ == "__main__":
    assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
    assert fib(10)==55