• 0 Posts
  • 1 Comment
Joined 2 years ago
cake
Cake day: June 11th, 2023

help-circle
  • It’s not that hard to check yourself. Running the following code on my machine, I get that the linear algebra algorithm is already faster than the naive algorithm at around n = 100 or so. I’ve written a more optimised version of the naive algorithm, which is beaten somewhere between n = 200 and n = 500.

    Try running this Python code on your machine and see what you get:

    import timeit
    
    def fib_naive(n):
        a = 0
        b = 1
        while 0 < n:
            b = a + b
            a = b - a
            n = n - 1
        return a
    
    def fib_naive_opt(n):
        a, b = 0, 1
        for _ in range(n):
            a, b = b + a, b
        return a
    
    def matmul(a, b):
        return (
            (a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]),
            (a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]),
        )
    
    def fib_linear_alg(n):
        z = ((1, 1), (1, 0))
        y = ((1, 0), (0, 1))
        while n > 0:
            if n % 2 == 1:
                y = matmul(y, z)
            z = matmul(z, z)
            n //= 2
    
        return y[0][0]
    
    def time(func, n):
        times = timeit.Timer(lambda: func(n)).repeat(repeat=5, number=10000)
        return min(times)
    
    for n in (50, 100, 200, 500, 1000):
        print("========")
        print(f"n = {n}")
        print(f"fib_naive:\t{time(fib_naive, n):.3g}")
        print(f"fib_naive_opt:\t{time(fib_naive_opt, n):.3g}")
        print(f"fib_linear_alg:\t{time(fib_linear_alg, n):.3g}")
    

    Here’s what it prints on my machine:

    ========
    n = 50
    fib_naive:      0.0296
    fib_naive_opt:  0.0145
    fib_linear_alg: 0.0701
    ========
    n = 100
    fib_naive:      0.0652
    fib_naive_opt:  0.0263
    fib_linear_alg: 0.0609
    ========
    n = 200
    fib_naive:      0.135
    fib_naive_opt:  0.0507
    fib_linear_alg: 0.0734
    ========
    n = 500
    fib_naive:      0.384
    fib_naive_opt:  0.156
    fib_linear_alg: 0.112
    ========
    n = 1000
    fib_naive:      0.9
    fib_naive_opt:  0.347
    fib_linear_alg: 0.152