0
\$\begingroup\$

This code calculates, from a list of integers, the next fibonacci number for each integer. It does this for the first 60 numbers in the sequence. Any pointers on improving computing time, code readability, etc. are what I'm looking for.

def getFib(limit):
    a = 1
    b = 1
    res = [a, b]

    for i in range(1, limit):
        temp = a
        a = b
        b = temp + b
        res.append(b)
    return res

def nextFibonacci(fib, n):

    for x in n:
        if x < 1 or x > fib[len(fib)-1]:
            print("Value is out of range.")
        else:
            temp = x

            for c in fib:
                if c > temp:
                    temp = c
                    break

                print(temp)

def main():
    listMe = [1, 9, 22]
    fib = getFib(60)

    nextFibonacci(fib, listMe)

if __name__ == "__main__":
    main()
\$\endgroup\$
  • \$\begingroup\$ What is the point of limitting to the 60 first numbers? Put differently, why would an input of 27000000000000 not give me 27777890035288? \$\endgroup\$ – 301_Moved_Permanently Sep 4 '17 at 11:16
  • 2
    \$\begingroup\$ Also this code does not seem to perform the task described. When running it, all I see is a bunch of 1s, 9s and 22s, out of whom, 9 and 22 aren't fibonacci numbers. Besides, the notion of closest number seems not to be respected in the code, as you are always using >. (I mean, after the second for loop, temp would be 13 [resp. 34] for x = 9 [resp. x = 22] whereas 8 [resp. 21] would be a closer fit.) \$\endgroup\$ – 301_Moved_Permanently Sep 4 '17 at 11:29
  • \$\begingroup\$ The task at hand requires limiting the sequence to first 60 numbers. The function takes an array of integers as input. For each integer, it outputs the next fibonacci number. \$\endgroup\$ – mnemonicj Sep 4 '17 at 12:14
2
\$\begingroup\$

Use a cache to save fibonacci numbers, will improve speed of the program. That way you won't have to compute the numbers again at each loop.

'''
Cached_fib
'''
def memoize(f):
    cache = {}
    return lambda *args: cache[args] if args in cache else cache.update({args: f(*args)}) or cache[args]

@memoize
def fib(n):
    return n if n < 2 else fib(n-2) + fib(n-1)

def find_closest_fib(l):
    for num in l: 
        i = 1
        while 2*num>fib(i)+fib(i+1):
            i += 1
        print ('Nearest fib number = {} \n for num {}\n'.format(fib(i), num))


if __name__ == '__main__':
    l = (60, 234234231, 35342454, 27000000000000)
    start_time = timeit.default_timer()
    find_closest_fib(l)
    print('Elapsed time: ', timeit.default_timer() - start_time)

    start_time = timeit.default_timer()
    find_fib_op(l)
    print('Elapsed time: ', timeit.default_timer() - start_time)

Output new version

Nearest fib number = 55 for num 60
Nearest fib number = 267914296 for num 234234231
Nearest fib number = 39088169 for num 35342454
Nearest fib number = 27777890035288 for num 27000000000000

Timing of implementation

Cached fibonacci

Elapsed time: 0.06364319414684597

OP fibonacci

Elapsed time: 0.23451719927193976

| improve this answer | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.