1) Пишем метод (файл myfib.c)

unsigned long fib(unsigned long x)
{
    if(x < 2) return x;
    return fib(x-1) + fib(x-2);
}

2) Компилируем:

gcc -shared -Wl,-soname,myfib.so -o myfib.so -fPIC myfib.c

3) Вызываем из Python и сравниваем с функцией написанной на чистом python:

import ctypes
import timeit

fib = ctypes.CDLL('./myfib.so').fib
fib.restype = ctypes.c_long
fib.argtypes = (ctypes.c_ulong,)

print timeit.timeit('fib(32)', 'from __main__ import fib', number=1)

def pyfib(x):
    if x < 2: return x
    return pyfib(x-1) + pyfib(x-2)

print timeit.timeit('pyfib(32)', 'from __main__ import pyfib', number=1)

Результат:

0.0463268756866
1.08009696007

В итоге, за счет использования ctypes, мы получили ускорение в 23 раза.

Если использовать оптимизацию при компиляции, то можно получить большую производительность, для этого нужно указать ключ оптимизации:

gcc -O3 -shared -Wl,-soname,myfib.so -o myfib.so -fPIC myfib.c

Варианты ключей оптимизации:
-O1 — Базовая оптимизация
-O2 — GCC выполняет почти все поддерживаемые оптимизации, эта опция уменьшает как время компиляции так и время выполнения сгенерированного кода.
-O3 — Более сильная оптимизация, включает -O2 + некоторые дополнительные опции.

С учетом оптимизации -O3, мы получили такой результат:

0.023335695266
1.08294892311

Это быстрее в 46 раз чем на чистом python.

Тестировалось на ubuntu 12.10, python 2.7