import time, math, socket

def fib1(n):
    if n <= 1: return 1
    return fib1(n-1)+fib1(n-2)

def fib2(n, a=1, b=1):
    if n == 0: return a
    elif n == 1: return b
    else: return fib2(n-1, b, a+b)

print 'Timings for %s' % socket.gethostname()
print '------------------------'

for i in range(4,18):
    before = time.time()
    for r in range(10000): fib1(i)
    after = time.time()
    t1 = int((after-before)/10000*1.0e9)

    before = time.time()
    for r in range(100000): fib2(i)
    after = time.time()
    t2 = int((after-before)/100000*1.0e9)

    # Diese Zeile soll so veraendert werden, dass sie die Zeilen fuer
    # die LaTeX-Tabelle erzeugt
    print 'N=%d\tfib=%d\tt1=%dns\tt2=%dns' % (i, fib2(i), t1, t2)