Here are some timings using three different approaches using Cython, and also numba: https://share.cocalc.com/share/df81e09e5b8f16f28b3a2e818dcdd4560e7818ae/su

Here are some timings using three different approaches using Cython, and also numba: https://share.cocalc.com/share/df81e09e5b8f16f28b3a2e818dcdd4560e7818ae/support/2021-02-09-fib-cython.sagews?viewer=share https://share.cocalc.com/share/df81e09e5b8f16f28b3a2e818dcdd... Numba wins and is about twice as fast as my most clever Cython code. Naive Cython is pretty bad, but more clever Cython is reasonably good (though not as good as numba).