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 ?

• Toby Speight: Does the code work as required? You say it throws an exception - you should probably do something about that before this code is ready for review. You could either avoid it by rejecting out-of-range inputs, or fix your code to handle larger values.
• CMouse: Code works as required for smaller integers but for integers greater than 4 digits it throws exception.
• CocoCrisp: The code looks fine to me apart from the fact that it can throw an exception. The function fib()``powLF() are giving you complexity of log(n) plus the execution time of the function sum_digits() is 479 ns per loop which is perfectly fine.
• Peilonrayz: @Milind Answers should go in answers, not comments.
• CMouse: I am still getting my solution rated as poor and I cannot understand why ! @Peilonrayz @Milind

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.

• CocoCrisp: This is certainly not the correct solution, the code does not need to store the series, the series can extend up to very large n, also he needs to find the nth term not, according to ti this, he will need to find all the terms.