0

my code is 80% right but there are 2 tests I cant pass.

here is my code 

import math
def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a

is right when I test fib(100)

but there are one more requirement is time. so here is my test 

# this should run in less than 5 seconds
print(fib(10 ** 6) % 10 ** 10)

is should under 5 second but my code speed like 10sec to run it.

# this should run in less than 10 seconds
print(math.floor(math.log10(fib ( 5 * 10 ** 6 ))))

so how to improve my code to run these two tests under 10 seconds.

any suggestion will be glad :)

slider
  • 12,810
  • 1
  • 26
  • 42
user3624415
  • 3
  • 4
  • Please update your test environment. Your machine specs, CPU, RAM etc. – Saleem Mar 13 '16 at 05:06
  • 2
    note the question [efficient calculation of fibonacci series](http://stackoverflow.com/questions/18172257/efficient-calculation-of-fibonacci-series) has a number of methods and their relative efficiencies. – LinkBerest Mar 13 '16 at 05:12
  • 1
    There's a non-iterative formular to calculate a number of the Fibonacci sequence. Check the Wikipedia or a similar source. – Klaus D. Mar 13 '16 at 05:14
  • Please also take a minute to reformat your question a bit; your code does not run without errors, and the formatting is inconsistent. – Joost Mar 13 '16 at 05:31
  • This seems like an odd requirement since speed depends so much on machine specs. Is this a class assignment? Where are the tests being run, on your local computer or some remote server? – ubadub Mar 13 '16 at 05:35
  • These requirements are very odd. There is nothing wrong with your `fib` function, but `fib(10**6)` is an over 200,000-digit number in base 10. All of the time is being spent doing extended-precision integer addition. I don't really think there are any shortcuts for this. – Tom Karzes Mar 13 '16 at 05:37
  • 1
    Please take a look at the second answer of this question: http://stackoverflow.com/questions/18172257/efficient-calculation-of-fibonacci-series – piglei Mar 13 '16 at 06:37

0 Answers0