eval.in

Paste #989203

Python — CPython 2.7.8, pasted 1 year ago (json)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import collections

calls = collections.Counter()

def fib(n):
    calls[n] = calls.get(n, 0) + 1
    i = abs(n)
    if i in (0,1): o = i
    elif i&1: o = fib((i-1)/2)**2 + fib((i+1)/2)**2
    else: o = fib(i/2) * (fib(i/2-1)*2 + fib(i/2))
    return -o if not n&1 and o<0 else o

fib(128)
print(calls.most_common(10))

Program Output

[(1, 610), (2, 233), (0, 233), (4, 89), (3, 55), (8, 34), (7, 21), (16, 13), (15, 8), (32, 5)]

OK (0.036 sec real, 0.054 sec wall, 6 MB, 215 syscalls)

Fork