Cython Fibonacci Sequence

Question

For my current job, I've been told that soon I'm going to be porting our Python code to Cython, with the intent of performance upgrades. In preparation of that, I've been learning as much about Cython as I can. I've decided that tackling the Fibonacci sequence would be a good start. I've implemented a Cython + Iterative version of the Fibonacci sequence. Are there any more performance upgrades I can squeeze out of this? Thanks!

fibonacci.pyx

cpdef fib(int n):
 return fib_c(n)
cdef int fib_c(int n):
 cdef int a = 0
 cdef int b = 1
 cdef int c = n
 while n > 1:
 c = a + b
 a = b
 b = c
 n -= 1
 return c

And how I test this code:

testing.py

import pyximport ; pyximport.install() # So I can run .pyx without needing a setup.py file #
import time
from fibonacci import fib
start = time.time()
for i in range(100_000):
 fib(i)
end = time.time()
print(f"Finonacci Sequence: {(end - start):0.10f}s (i=100,000)") # ~2.2s for 100k iterations

• vnp: Yes you can; there is a \$O(\log n)\$ algorithm, but it has nothing to do with Cython.
• EngrStudent: memoize goes a long way here. youtube.com/watch?v=Qk0zUZW-U_M&t=240s Sometimes you get better speedup by not using Cython. Numpy is strongly optimized. So is Numba.

Answer 1

Using one less variable seems faster:

cdef int fib_c(int n):
 if n == 0:
 return 0
 cdef int a = 0
 cdef int b = 1
 for _ in range(n - 1):
 a, b = b, a + b
 return b

Running your test on my machine:

Original = 2.934 s
Improved = 1.522 s

• Manuel: I wonder whether it's because of the multi-assignment or because of the loop-kind...

Answer 2

How about unrolling the loop a bit, doing two steps per iteration so you don't need to "swap" a and b? (I'm not familiar with Cython, so didn't benchmark):

cdef int fib_c(int n):
 cdef int a = 0
 cdef int b = 1
 while n > 1:
 a += b
 b += a
 n -= 2
 return b if n > 0 else a