CODEWITHSUNDEEP
pythonpython-3.xtimemax
Mikail Cayoglu
Mikail Cayoglu

Reputation: 179

Find highest possible number under certain time span?

For Python 3, is there a possibility to find the highest possible calculated number in a function under a specific time span? For example if something would take almost 'forever', is there a way to find out the highest possible number to be calculated under 1 minute?

Here is the code:

def fibonacci5(n):
f1, f2 = 1, 0               
while n > 0:
    f1, f2 = f1 + f2, f1     
    n -= 1
return f2

I am trying to use the possible solution for finding the number that takes 1 second via timeit.

repeats = 10
t = timeit.Timer("fibonacci5(500000)", globals=globals())
time = t.timeit(repeats)
print ("average execution time:", time/repeats)

But 500.000 takes on average 2,6s, while 250.000 takes on average 0,6s - so that solution can't work.

Upvotes: 0

Views: 199

Answers (2)

hiro protagonist
hiro protagonist

Reputation: 46849

you could add a timer to your function to make it stop after a given time:

from datetime import datetime, timedelta

max_runtime = timedelta(seconds=1)

def fibonacci5(n):

    stop_time = datetime.now() + max_runtime

    f1, f2 = 1, 0
    while n > 0:
        f1, f2 = f1 + f2, f1
        n -= 1
        if datetime.now() > stop_time:
            return f2, 'timelimit reached'
    return f2

note that if it returns when the time has run out that it will not just return a number, but a tuple with the number and the string 'timelimit reached'. that way you can differentiate between normal termination and timeout (there may be better ways to handle that...).

the caveat here is that the if line (at least as long as your ints are still very small) is probably the line of the function that takes up the most amount of time... the results will therefore not represent the actual run-times very exactly...

also note that there are way more efficient ways to calculate fibonacci numbers.

Upvotes: 2

Azat Ibrakov
Azat Ibrakov

Reputation: 10953

if we write Fibonacci sequence generator like

def fibonacci():
    a, b = 0, 1
    while True:
        yield b
        a, b = b, a + b

it looks naive but works fast enough, e.g. if you need 500000th Fibonacci number we can use itertools.islice

from itertools import islice

fibonacci_500000 = next(islice(fibonacci(), 500000, 500001))
print(fibonacci_500000)

which took about 5 seconds on my old machine, output is too big to insert, but it looks like

47821988144175...more digits here...2756008390626

but if you really need to find out which value we've calculated after some time – we can use timedelta and datetime objects like

from datetime import datetime, timedelta


def fibonacci():
    a, b = 0, 1
    while True:
        yield b
        a, b = b, a + b


if __name__ == '__main__':
    duration = timedelta(seconds=5)
    fibonacci_numbers = fibonacci()
    stop = datetime.now() + duration
    for index, number in enumerate(fibonacci_numbers, start=1):
        if datetime.now() >= stop:
            break
    print(index)

which gives us 505352th Fibonacci number calculated after approximately 5 seconds (we can also print number, but it is too long)

Upvotes: 1

Related Questions