Posts Tagged ‘prob25’

Problem 25 – More Fibonacci Numbers

September 19, 2009

In problem 25 we are asked to find the first Fibonacci number with a given number of digits. Actually, we are only asked to find which Fibonacci number it is (its index in the sequence of Fibonacci numbers), instead of the number itself. We’ve already visited Fibonacci numbers in problem 2, and had useful work there. For this problem, it will be helpful to note that the number of digits of n can be found as \lfloor \log_{10} n\rfloor + 1, where \lfloor x\rfloor denotes the “floor” function, equal to the greatest integer less than x (on a not-particularly-related note, this isn’t the formula I would have used a week ago, glad I got that cleared up).

I decided to do some performance comparisons with this problem, with a few different versions of code. [GRR. WordPress seems to not be doing the sourcecode “tag” like I thought it should below. Or I’m messing something up…]

In version 1, I’ll compute each Fibonacci number successively, using the recurrence relation, then calculate the number of digits until I’ve found a big enough number. My function looks like:

def solve(n):
    ret = 1
    prev, cur = 0, 1
    while(cur < 10**(n-1)):
        prev, cur = cur, prev + cur
        ret += 1
    return ret

In the second version, I’ll compute the n-th Fibonacci number using the formula

F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^2-\left(\frac{1-\sqrt{5}}{2}\right)^2\right)

that was used last time we saw Fibonacci numbers. In fact, I’ll wrap that up into its own function, “digs_fib” that takes in an “n” and gives the number of digits of the appropriate Fibonacci number. Now my code is basically:

def fib(n):
    """ The nth fibonacci number """
    alpha = (1 + 5**.5) / 2
    beta = (1 - 5**.5) / 2
    return (1/5**.5) * (alpha**n - beta**n)
def digs_fib(n):
    """ Number of digits of fib(n) """
    return int(math.log(fib(n), 10)) + 1
def solve(n):
    ret = 1
    while(digs_fib(ret) < n):
        ret += 1
    return ret

Of course, that second term in the formula is smallish, and raised to big powers it gets smaller, so we could maybe ignore it. And then we’re taking the log of products and powers, so we can use log rules to re-write the expression for the number of digits, without directly calculating the Fibonacci number. My “digs_fib” function changes to the following:

def digs_fib(n):
    """ The approximate number of digits of the nth fibonum """
    alpha = (1+5**.5)/2
    return int(n*math.log(alpha,10)-.5*math.log(5, 10))+1

Finally, given a target number of digits d, we could just about solve for n in

d \approx \lfloor n\log_{10}((1+\sqrt{5})/2) - \frac{1}{2}\log_{10}(5)\rfloor + 1

and obtain

n\approx \dfrac{d-1+\frac{1}{2}\log_{10}(5)}{\log_{10}((1+\sqrt{5})/2)}.

This means that given d we can get an approximation to which Fibonacci number gives us that many digits in basically constant time. Now my “solve” is just

def solve(n):
    num = n - 1 + .5*math.log(5, 10)
    num /= math.log((1+5**.5)/2, 10)
    return int(num+1) # round up, approximately

I ran each of these through my little performance evaluation script and came up with a reasonable graph. I could only go up to asking for 300 digits, because after that the second version fails, since the numbers are too big. The other versions have no problem at all going up to 1000 digits (and well beyond). But anyway, here’s my graph:

You can barely see that constant time algorithm there along the x-axis. The scale of the y-axis is some linear change in actual time taken, but the shape of these graphs is what’s important anyway. Right?

Advertisements