Comment

Comment on A Linear Algebra Trick for Computing Fibonacci Numbers Fast

The article is comparing to the dynamic programming algorithm, which requires reading and writing to an array or hash table (the article uses a hash table, which is slower).

The naive algorithm is way faster than the DP algorithm.

source

Sort:hotnew top

t_veor@sopuli.xyz ⁨1⁩ ⁨year⁩ ago

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 &lt; 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

source

cbarrick@lemmy.world ⁨1⁩ ⁨year⁩ ago
Nice.

I have successfully stuck my foot in my own mouth.

source