Finding the n th term in Fibonacci series 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) &gt;&gt; 1, L*F
    if n &amp; 1:
        return ((L + 5*F)&gt;&gt;1, (L + F) &gt;&gt;1)
    else:
        return (L, F)

def fib(n):
    if n &amp; 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 ?
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.

&gt; %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.

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