Skip to content

README.md

Latest commit

 

History

History
160 lines (106 loc) · 4.45 KB

README.md

File metadata and controls

160 lines (106 loc) · 4.45 KB
Raw

Fibonacci Python Extension

English | 中文 | 日本語 | Français | Deutsch

This project demonstrates how to implement Fibonacci calculation in C++ and call it from Python as a native extension module.

After building the extension, Python can use it like this:

import fibonacci_cpp

print(fibonacci_cpp.fibonacci(10))  # 55

Demo picture

Requirements

  • Python 3.x
  • CMake 3.18 or later
  • A C++17 compiler, such as MinGW, MSVC, or Clang

Check that the required commands are available:

python --version
cmake --version
g++ --version

The Python extension must be built and run with the same Python version. This project's CMake configuration prefers the python executable found in the current command-line PATH, so the module generated by cmake --build build can be imported directly by python main.py.

To select a specific Python interpreter, configure CMake like this:

cmake -S . -B build -DPython_EXECUTABLE="C:\Users\YourName\miniconda3\python.exe"

Build

Run these commands from the project root:

cmake -S . -B build
cmake --build build

After a successful build, the build directory will contain a file similar to:

fibonacci_cpp.cp313-win_amd64.pyd

The Python version tag in the filename may be different. For example, cp313 means CPython 3.13.

The core CMake configuration is:

find_package(Python REQUIRED COMPONENTS Interpreter Development.Module)

add_library(fibonacci_cpp MODULE
    src/fibonacci.cpp
)

target_link_libraries(fibonacci_cpp PRIVATE Python::Module)

The generated module is named fibonacci_cpp, so Python imports it with import fibonacci_cpp.

Usage

src/fibonacci.cpp exposes one function through the Python C API:

fibonacci_cpp.fibonacci(n)

Notes:

  • n must be a non-negative integer.
  • The return value is a Python int, so large results are supported.
  • The C++ side currently parses n as unsigned long long, so the maximum accepted index is 18446744073709551615. Practical limits still depend on memory and runtime.

Run the demo:

python main.py

Run a larger benchmark:

python main.py 1000000

Wall Time Benchmark

main.py does two things:

  • Prints small examples from fibonacci_cpp.fibonacci(0) to fibonacci_cpp.fibonacci(10).
  • Compares the wall time of a pure Python implementation and the C++ extension for the same large n.

Default benchmark:

python main.py

Example result:

Benchmark n = 100,000
Result decimal digits : 20,899
Python Wall Time     : 0.052376 s
C++ Wall Time        : 0.000816 s
Speedup              : 64.18x

Benchmark with n = 1000000:

python main.py 1000000

Example result:

Benchmark n = 1,000,000
Result decimal digits : 208,988
Python Wall Time     : 4.540529 s
C++ Wall Time        : 0.033997 s
Speedup              : 133.56x

Wall time depends on the machine, Python version, compiler, and background load. Treat these numbers as reference results only. For stricter benchmarking, run several iterations and average them, or use a dedicated tool such as pyperf.

Why C++ Helps Here

C++ extensions are useful for compute-heavy hot paths. In this project:

  • The Python version uses a straightforward loop, so every step goes through Python bytecode execution and variable binding.
  • The C++ extension moves the hot calculation into a compiled module, reducing Python-level loop overhead.
  • The C++ implementation uses fast doubling, calculating Fibonacci numbers with about O(log n) big-integer operations instead of O(n) loop iterations.
  • Python still handles the entry point and output, while C++ handles the expensive calculation.

Not every Python program becomes faster by moving code to C++. Cross-language calls have overhead, so this approach works best for stable, compute-intensive logic with controlled call frequency.

Learning Resources