Finding the n th term in Fibonacci series

Question

Solving a problem in coding contest I came across a problem, which on digging a bit lead me to the data set in this question . Since the program to enumerate and finding the solution was too complex and execution time was below par I jot down the logic to the equation of curve (a single line)

Upon further digging deep I found that I missed the series which was forming a Fibonacci Series, hence by Binet's fourmla I found the nth term of the series which was even efficient. Here is the code

import math
import sys

def powLF(n):
    if n == 1:     return (1, 1)
    L, F = powLF(n//2)
    L, F = (L**2 + 5*F**2) >> 1, L*F
    if n & 1:
        return ((L + 5*F)>>1, (L + F) >>1)
    else:
        return (L, F)

def fib(n):
    if n & 1:
        return powLF(n)[1]
    else:
        L, F = powLF(n // 2)
        return L * F

def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r

def _print(string):
    fo = open("output.txt", "w+")
    fo.write(string)
    fo.close()

try:
    f = open('input.txt')
except IOError:
    _print("error")
    sys.exit()
num = f.readline()
try:
   val = int(num)
except ValueError:
    _print("error")
    sys.exit()

sum = sum_digits(int(num))
f.close()

if (sum == 2):
    _print("1")
else:
    _print(str(int(math.ceil(fib(sum)))))

Although still the code doesn't seem to match the par criteria, how can I optimize the code further ?

Answer 1

The code looks fine to me apart from the fact that it can throw an exception. The function fib() powLF() are giving you the complexity of O(log(n)) plus the execution time of the function sum_digits() is 479 ns per loop which is perfectly fine.

> %timeit sum_digits(n)
1000000 loops, best of 3: 479 ns per loop

Take a look at Lecture 3 of the MIT Open Courseware course on algorithms for a good analysis of the matrix approach.

>>> timeit.timeit('fib(1000)', 'from __main__ import fibM as fib', number=10000)
0.40711593627929688
>>> timeit.timeit('fib(1000)', 'from __main__ import fibL as fib', number=10000)
0.20211100578308105

Answer 2

This is not fibonacci series. It's also recursively calculating the result which is almost certainly a bad idea if performance is at all important. For calculating fibonacci, it would be better to use some sort of list, for example:

def fib(n):
    f = [0,1,1]
    for i in xrange(3,n):
        f.append(f[i-1] + f[i-2])
    return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1])

If continued calls were to be made, then you should consider saving f and calculating only what is required to arrive at n.