RombergIntegration 1.0.0

High-performance Cython implementation of Romberg Integration algorithm

Romberg Integration - 高精度数值积分库

English | 中文

一个基于 Cython 的高性能 Romberg 积分数值库，提供递归和动态规划两种算法实现。

快速开始 • 安装 • API 文档 • 示例 • 单元测试

---

项目简介

Romberg Integration 是一个高精度数值积分库，采用 Cython 实现以获得接近原生 C++ 的性能。提供两种经典算法：

• 递归方法：使用哈希表缓存，支持灵活的精度控制
• 动态规划方法：使用 Romberg 表迭代计算，直观易懂

该项目完全兼容原始 C++ 版本的接口设计，并提供 Pythonic 的使用体验。

核心特性

✨ 高精度计算

• 采用 long double 类型，提供机器级别的数值精度
• 支持自定义精度要求，可达 1e-12 以上

🚀 高性能实现

• 使用 Cython 编译为 C/C++ 代码
• C 级别的循环和数学运算，接近原生 C++ 速度
• 编译指令优化：禁用边界检查、启用 C 风格除法等

🔄 双算法支持

• 递归算法：使用哈希表缓存，灵活可控
• 动态规划：逐步构建 Romberg 表，直观可视化

📊 完整的测试覆盖

• 10 个全面的单元测试
• 涵盖多种函数类型：多项式、三角、指数、对数等
• 与 C++ 版本对标验证，保证数值精度一致

快速开始

最简单的使用方式

from RombergIntegration import RombergIntegration
import math

# 计算 sin(x) 在 [0, π] 的积分
integrator = RombergIntegration(0.0, math.pi, 1e-10, lambda x: math.sin(x))
result = integrator.recursive()
print(f"积分结果: {result}")  # 输出: 2.0

使用动态规划方法

# 使用动态规划方法
result = integrator.dynamic_programming(maximum_step=20)
print(f"积分结果: {result}")  # 输出: 2.0

安装

系统要求

项目	版本
Python	3.6+
Cython	>= 0.29.0
编译器	gcc/clang/MSVC 等（支持 C++11）

安装步骤

方式一：从源代码编译（推荐）

# 1. 克隆或下载项目
git clone <repository-url>
cd romberg

# 2. 创建虚拟环境（可选但推荐）
python -m venv venv
source venv/bin/activate  # Linux/Mac
# 或
venv\Scripts\activate  # Windows

# 3. 安装依赖
pip install -r requirements.txt
# 或手动安装
pip install cython numpy

# 4. 编译并安装
python setup.py build_ext --inplace

# 5. 验证安装
python test_romberg.py

方式二：直接使用（已预编译）

如果已有预编译的 .so 文件：

# 直接导入使用
python -c "from RombergIntegration import RombergIntegration; print('OK')"

API 文档

类：RombergIntegration

Romberg 积分计算器的主类。

构造函数

RombergIntegration(a: float, b: float, precision: float, integrand: Callable[[float], float])

参数说明：

参数	类型	说明
a	float	积分下界
b	float	积分上界
precision	float	精度要求（绝对误差），推荐值 1e-8 ~ 1e-12
integrand	Callable	被积函数，签名为 f(x: float) -> float

示例：

import math
from RombergIntegration import RombergIntegration

# 定义被积函数
def f(x):
    return math.sin(x) * math.cos(x)

# 创建积分器
integrator = RombergIntegration(0, math.pi, 1e-10, f)

# 也可使用 lambda 表达式
integrator = RombergIntegration(0, math.pi, 1e-10, lambda x: math.sin(x) * math.cos(x))

方法

recursive() -> float

使用递归方法计算积分。采用哈希表缓存中间结果，逐步提高精度直至满足要求。

返回值：float - 计算得到的积分结果

算法特点：

• 使用递归分治法
• 自动缓存中间计算结果
• 精度自适应调整

示例：

result = integrator.recursive()
print(f"递归方法结果: {result}")

dynamic_programming(maximum_step: int = 20) -> float

使用动态规划方法计算积分。逐行构建 Romberg 表，每次迭代都改进精度。

参数说明：

参数	类型	默认值	说明
maximum_step	int	20	最大迭代步数，值越大精度越高但计算时间越长

返回值：float - 计算得到的积分结果

算法特点：

• 逐步构建 Romberg 表
• 结果可视化：可查看 romberg_table 和 precision_table
• 控制更细致

示例：

# 使用默认步数
result = integrator.dynamic_programming()

# 使用更多迭代步数以获得更高精度
result = integrator.dynamic_programming(maximum_step=25)

属性

romberg_table

返回动态规划方法中构建的 Romberg 表。

类型：list[list[float]]

说明：

• 二维列表，其中 romberg_table[m][k] 表示第 m 行第 k 列的值
• 仅在调用 dynamic_programming() 后有效
• 用于观察积分精度的逐步改进过程

示例：

integrator = RombergIntegration(0, 1, 1e-10, lambda x: x**2)
result = integrator.dynamic_programming(maximum_step=10)

# 查看完整的 Romberg 表
print("Romberg Table:")
for row in integrator.romberg_table:
    print([f"{val:.10f}" for val in row])

precision_table

返回每次迭代的精度改进情况。

类型：list[float]

说明：

• 记录每一步与前一步的误差差值
• 用于评估收敛速度
• 仅在调用 dynamic_programming() 后有效

示例：

integrator.dynamic_programming(maximum_step=10)
print("精度改进序列:", integrator.precision_table)

romberg_map

返回递归方法中使用的缓存字典。

类型：dict[str, float]

说明：

• 键格式为 "m-k" (例如 "3-2")
• 值为该位置的 Romberg 表计算结果
• 仅在调用 recursive() 后有效

示例：

integrator.recursive()
print("缓存大小:", len(integrator.romberg_map))
print("缓存内容:", integrator.romberg_map)

使用示例

示例 1：基础积分计算

计算 $\int_0^1 x^2 dx = \frac{1}{3}$

from RombergIntegration import RombergIntegration

# 创建积分器
integrator = RombergIntegration(0.0, 1.0, 1e-10, lambda x: x * x)

# 计算积分
result = integrator.recursive()
expected = 1.0 / 3.0

print(f"计算结果: {result:.10f}")
print(f"理论值:   {expected:.10f}")
print(f"误差:     {abs(result - expected):.2e}")

输出：

计算结果: 0.3333333333
理论值:   0.3333333333
误差:     1.23e-10

示例 2：三角函数积分

计算 $\int_0^{\pi} \sin(x) dx = 2$

import math
from RombergIntegration import RombergIntegration

integrator = RombergIntegration(0.0, math.pi, 1e-12, lambda x: math.sin(x))
result = integrator.dynamic_programming(maximum_step=15)

print(f"∫₀^π sin(x)dx = {result:.12f}")  # 输出: 2.000000000000

示例 3：指数函数积分

计算 $\int_0^1 e^x dx = e - 1$

import math
from RombergIntegration import RombergIntegration

integrator = RombergIntegration(0.0, 1.0, 1e-10, lambda x: math.exp(x))
result = integrator.recursive()
expected = math.e - 1.0

print(f"计算值: {result:.10f}")
print(f"期望值: {expected:.10f}")

示例 4：复杂多项式积分

计算 $\int_0^1 (x^4 + 2x^2 + 1) dx = \frac{28}{15}$

from RombergIntegration import RombergIntegration

def f(x):
    return x**4 + 2*x**2 + 1

integrator = RombergIntegration(0.0, 1.0, 1e-10, f)
result = integrator.dynamic_programming(maximum_step=20)
expected = 28.0 / 15.0  # ≈ 1.8666666667

print(f"计算结果: {result:.10f}")
print(f"理论值:   {expected:.10f}")

示例 5：观察 Romberg 表的收敛过程

import math
from RombergIntegration import RombergIntegration

integrator = RombergIntegration(0, math.pi, 1e-10, lambda x: math.sin(x))
result = integrator.dynamic_programming(maximum_step=8)

print("Romberg 表的收敛过程:")
print("=" * 70)
for i, row in enumerate(integrator.romberg_table):
    print(f"第 {i} 行: ", end="")
    for j, val in enumerate(row):
        if j < len(integrator.romberg_table[i]):
            print(f"{val:.10f}  ", end="")
    print()

print("\n精度改进序列:")
for i, prec in enumerate(integrator.precision_table):
    print(f"步骤 {i}: 误差 = {prec:.2e}")

单元测试

本项目包含 10 个全面的单元测试，覆盖多种场景。

运行测试

# 运行所有测试
python test_romberg.py

# 预期输出
============================================================
Running Cython Romberg Integration Tests
============================================================
✓ Test 1 passed: constant function (recursive) = 1.0
✓ Test 2 passed: linear function (recursive) = 0.5
✓ Test 3 passed: quadratic function (recursive) = 0.3333333333333333
✓ Test 4 passed: cubic function (recursive) = 0.25
✓ Test 5 passed: sine function (recursive) = 2.0
✓ Test 6 passed: cosine function (recursive) = 1.0
✓ Test 7 passed: exponential function (recursive) = 1.7182818284590444
✓ Test 8 passed: reciprocal function (recursive) = 0.693147180559947
✓ Test 9 passed: polynomial function (dynamic programming) = 1.8666666666666667
✓ Test 10 passed: trigonometric function (dynamic programming) = 2.041077998578922e-17
============================================================
Results: 10/10 tests passed
============================================================
✓ All tests passed!

测试详情

递归方法测试 (Tests 1-8)

测试	函数	积分区间	理论值	说明
1	f(x) = 1	[0, 1]	1.0	常函数
2	f(x) = x	[0, 1]	0.5	线性函数
3	f(x) = x²	[0, 1]	1/3 ≈ 0.3333	二次多项式
4	f(x) = x³	[0, 1]	0.25	三次多项式
5	f(x) = sin(x)	[0, π]	2.0	正弦函数
6	f(x) = cos(x)	[0, π/2]	1.0	余弦函数
7	f(x) = eˣ	[0, 1]	e-1 ≈ 1.7183	指数函数
8	f(x) = 1/x	[1, 2]	ln(2) ≈ 0.6931	对数函数

动态规划方法测试 (Tests 9-10)

测试	函数	积分区间	理论值	说明
9	f(x) = x⁴ + 2x² + 1	[0, 1]	28/15 ≈ 1.8667	复杂多项式
10	f(x) = sin(x)cos(x)	[0, π]	0.0	三角组合函数

性能特点

优化措施

1. 静态类型

   • 使用 long double 进行高精度计算
   • 避免 Python 对象的开销

2. 编译指令

   # cython: language_level=3, boundscheck=False, wraparound=False, cdivision=True
   

   • boundscheck=False: 禁用边界检查
   • wraparound=False: 禁用负索引包装
   • cdivision=True: 启用 C 风格除法

3. C 库函数

   • 使用 libc.math 的 pow 和 fabs
   • 避免 Python 函数调用开销

4. 编译优化

   • -O3: 最大优化级别
   • -march=native: 利用本地 CPU 特性
   • -ffast-math: 快速数学运算

性能对比

项	C++ 原生版	Cython 版
编译	g++ 直接编译	Cython -> C/C++
运行速度	原生 C++	接近原生 C++
Python 可用性	需额外包装	原生 Python 支持
易用性	中	高
接口一致性	-	✓ 完全兼容

算法说明

Romberg 积分算法

Romberg 积分是一种外推加速方法，通过组合不同步长的梯形法则结果来提高精度。

基本原理：

1. 使用梯形法则计算初值：$T(m, 0)$
2. 使用 Richardson 外推公式逐步改进：

$$T(m, k) = \frac{4^k T(m, k-1) - T(m-1, k-1)}{4^k - 1}$$

3. 当 $|T(m, k) - T(m, k-1)| < \text{precision}$ 时停止

两种实现方式：

• 递归方法：按需计算，使用哈希表缓存中间结果
• 动态规划方法：从下往上逐行构建完整的 Romberg 表

常见问题 (FAQ)

Q1: 如何选择精度参数？

A: 精度参数应根据应用需求选择：

# 一般工程应用 (相对误差 1e-6)
integrator = RombergIntegration(a, b, 1e-8, f)

# 科学计算 (相对误差 1e-10)
integrator = RombergIntegration(a, b, 1e-12, f)

# 高精度计算 (相对误差 1e-14)
integrator = RombergIntegration(a, b, 1e-14, f)

Q2: 递归方法和动态规划方法有什么区别？

A:

特性	递归方法	动态规划方法
计算策略	按需计算	逐行计算
中间结果	用哈希表缓存	构建完整表
内存占用	可能更少	固定的二维表
可视化	不直观	可查看完整表
控制粒度	自动	手动指定步数

选择建议：

• 快速计算：使用递归方法
• 观察收敛过程：使用动态规划方法

Q3: 如何处理积分失败的情况？

A: 目前版本不抛出异常，但可能返回不准确的结果。建议：

integrator = RombergIntegration(a, b, 1e-10, f)
result = integrator.recursive()

# 验证结果的可信度
if abs(result) > 1e10:
    print("警告：结果可能不可信，请检查函数或参数")

Q4: 如何集成到自己的项目中？

A: 有两种方式：

方式一：直接复制文件

cp RombergIntegration.pyx your_project/
# 在 your_project 的 setup.py 中添加该模块

方式二：安装为依赖

pip install -e .  # 在项目目录执行

文件结构

romberg/
├── README.md                      # 项目说明（本文件）
├── LICENSE                        # MIT 许可证
├── pyproject.toml                 # 现代 Python 项目配置
├── setup.py                       # 构建脚本
├── MANIFEST.in                    # 源码包文件清单
├── RombergIntegration.pyx         # Cython 核心实现
├── test_romberg.py                # 单元测试
├── test_romberg_compare.py        # 与 C++ 版本对标测试
└── .github/
    └── workflows/
        └── ci.yml                 # GitHub Actions CI/CD

技术细节

Cython 编译指令

# cython: language_level=3, boundscheck=False, wraparound=True, cdivision=True

• language_level=3: 使用 Python 3 语法
• boundscheck=False: 关闭边界检查（提高性能）
• wraparound=True: 保留负索引支持
• cdivision=True: C 风格整数除法

关键数据结构

class RombergIntegration:
    cdef:
        object _integrand              # Python 可调用对象
        long double _lower_bound       # 积分下界
        long double _upper_bound       # 积分上界
        long double _precision         # 精度要求
        dict romberg_map               # 递归方法缓存 (m-k -> value)
        list romberg_table             # 动态规划方法表
        list precision_table           # 精度改进序列

许可证

本项目采用 MIT 许可证。详见 LICENSE 文件。

作者

• 原始版本（C++）：wangheng [e-mail]
• Cython 移植版：wangheng [e-mail]

更新日志

v1.0.0 (2026-01-27)

• ✨ 初始发布
• ✓ 实现递归方法
• ✓ 实现动态规划方法
• ✓ 完整的单元测试（10/10）
• ✓ 详细的 API 文档
• ✓ GitHub Actions CI/CD

相关资源

• Romberg 积分法 - Wikipedia
• 数值分析 - 外推方法
• Cython 文档

---

Romberg Integration - High-Precision Numerical Integration Library

中文 | English

A high-performance Romberg numerical integration library built with Cython, offering both recursive and dynamic programming algorithm implementations.

Quick Start • Installation • API Reference • Examples • Tests

---

Overview

Romberg Integration is a high-precision numerical integration library implemented in Cython for near-native C++ performance. It provides two classical algorithms:

• Recursive Method: Uses hash table caching for flexible precision control
• Dynamic Programming Method: Iteratively builds the Romberg table for transparent convergence visualization

Fully compatible with the original C++ interface design while providing a Pythonic user experience.

Features

✨ High-Precision Computation

• Uses long double type for machine-level numerical precision
• Supports custom precision requirements, achievable to 1e-12 and beyond

🚀 High-Performance Implementation

• Compiled from Cython to C/C++ code
• C-level loops and mathematical operations for near-native C++ speed
• Optimized compilation directives: disabled bounds checking, enabled C-style division, etc.

🔄 Dual Algorithm Support

• Recursive algorithm: Uses hash table caching for flexible control
• Dynamic programming: Stepwise Romberg table construction for intuitive visualization

📊 Comprehensive Test Coverage

• 10 complete unit tests
• Covers multiple function types: polynomials, trigonometric, exponential, logarithmic, etc.
• Validated against C++ version for numerical consistency

Quick Start

Simplest Usage

from RombergIntegration import RombergIntegration
import math

# Compute integral of sin(x) over [0, π]
integrator = RombergIntegration(0.0, math.pi, 1e-10, lambda x: math.sin(x))
result = integrator.recursive()
print(f"Integration result: {result}")  # Output: 2.0

Using Dynamic Programming Method

# Use dynamic programming method
result = integrator.dynamic_programming(maximum_step=20)
print(f"Integration result: {result}")  # Output: 2.0

Installation

System Requirements

Item	Version
Python	3.6+
Cython	>= 0.29.0
Compiler	gcc/clang/MSVC etc. (C++11 support)

Installation Steps

Method 1: Build from Source (Recommended)

# 1. Clone or download the repository
git clone <repository-url>
cd romberg

# 2. Create virtual environment (optional but recommended)
python -m venv venv
source venv/bin/activate  # Linux/Mac
# or
venv\Scripts\activate  # Windows

# 3. Install dependencies
pip install -r requirements.txt
# or manually install
pip install cython numpy

# 4. Build and install
python setup.py build_ext --inplace

# 5. Verify installation
python test_romberg.py

Method 2: Direct Usage (Pre-compiled)

If pre-compiled .so files are available:

# Direct import
python -c "from RombergIntegration import RombergIntegration; print('OK')"

API Reference

Class: RombergIntegration

Main class for Romberg integration computation.

Constructor

RombergIntegration(a: float, b: float, precision: float, integrand: Callable[[float], float])

Parameter Description:

Parameter	Type	Description
a	float	Lower integration bound
b	float	Upper integration bound
precision	float	Required precision (absolute error), recommended 1e-8 ~ 1e-12
integrand	Callable	Integrand function, signature f(x: float) -> float

Example:

import math
from RombergIntegration import RombergIntegration

# Define integrand
def f(x):
    return math.sin(x) * math.cos(x)

# Create integrator
integrator = RombergIntegration(0, math.pi, 1e-10, f)

# Or use lambda
integrator = RombergIntegration(0, math.pi, 1e-10, lambda x: math.sin(x) * math.cos(x))

Methods

recursive() -> float

Compute the integral using the recursive method. Uses hash table caching of intermediate results, progressively increasing precision until the requirement is met.

Return Value: float - The computed integral result

Algorithm Characteristics:

• Uses recursive divide-and-conquer approach
• Automatically caches intermediate computation results
• Adaptive precision adjustment

Example:

result = integrator.recursive()
print(f"Recursive method result: {result}")

dynamic_programming(maximum_step: int = 20) -> float

Compute the integral using the dynamic programming method. Builds the Romberg table row by row, improving precision with each iteration.

Parameter Description:

Parameter	Type	Default	Description
maximum_step	int	20	Maximum iteration steps; larger values yield higher precision but longer computation time

Return Value: float - The computed integral result

Algorithm Characteristics:

• Stepwise Romberg table construction
• Visualizable results: inspect romberg_table and precision_table
• Finer control

Example:

# Use default steps
result = integrator.dynamic_programming()

# Use more iteration steps for higher precision
result = integrator.dynamic_programming(maximum_step=25)

Properties

romberg_table

Returns the Romberg table built by the dynamic programming method.

Type: list[list[float]]

Description:

• 2D list where romberg_table[m][k] represents the value at row m, column k
• Valid only after calling dynamic_programming()
• Useful for observing the stepwise improvement of integration precision

Example:

integrator = RombergIntegration(0, 1, 1e-10, lambda x: x**2)
result = integrator.dynamic_programming(maximum_step=10)

# View the complete Romberg table
print("Romberg Table:")
for row in integrator.romberg_table:
    print([f"{val:.10f}" for val in row])

precision_table

Returns the precision improvement at each iteration.

Type: list[float]

Description:

• Records error differences between consecutive steps
• Used to assess convergence rate
• Valid only after calling dynamic_programming()

Example:

integrator.dynamic_programming(maximum_step=10)
print("Precision improvement sequence:", integrator.precision_table)

romberg_map

Returns the cache dictionary used in the recursive method.

Type: dict[str, float]

Description:

• Key format is "m-k" (e.g., "3-2")
• Value is the Romberg table computation result at that position
• Valid only after calling recursive()

Example:

integrator.recursive()
print("Cache size:", len(integrator.romberg_map))
print("Cache contents:", integrator.romberg_map)

Usage Examples

Example 1: Basic Integration

Compute $\int_0^1 x^2 dx = \frac{1}{3}$

from RombergIntegration import RombergIntegration

# Create integrator
integrator = RombergIntegration(0.0, 1.0, 1e-10, lambda x: x * x)

# Compute integration
result = integrator.recursive()
expected = 1.0 / 3.0

print(f"Computed result: {result:.10f}")
print(f"Theoretical value:   {expected:.10f}")
print(f"Error:     {abs(result - expected):.2e}")

Output:

Computed result: 0.3333333333
Theoretical value:   0.3333333333
Error:     1.23e-10

Example 2: Trigonometric Function Integration

Compute $\int_0^{\pi} \sin(x) dx = 2$

import math
from RombergIntegration import RombergIntegration

integrator = RombergIntegration(0.0, math.pi, 1e-12, lambda x: math.sin(x))
result = integrator.dynamic_programming(maximum_step=15)

print(f"∫₀^π sin(x)dx = {result:.12f}")  # Output: 2.000000000000

Example 3: Exponential Function Integration

Compute $\int_0^1 e^x dx = e - 1$

import math
from RombergIntegration import RombergIntegration

integrator = RombergIntegration(0.0, 1.0, 1e-10, lambda x: math.exp(x))
result = integrator.recursive()
expected = math.e - 1.0

print(f"Computed value: {result:.10f}")
print(f"Expected value: {expected:.10f}")

Example 4: Complex Polynomial Integration

Compute $\int_0^1 (x^4 + 2x^2 + 1) dx = \frac{28}{15}$

from RombergIntegration import RombergIntegration

def f(x):
    return x**4 + 2*x**2 + 1

integrator = RombergIntegration(0.0, 1.0, 1e-10, f)
result = integrator.dynamic_programming(maximum_step=20)
expected = 28.0 / 15.0  # ≈ 1.8666666667

print(f"Computed result: {result:.10f}")
print(f"Theoretical value:   {expected:.10f}")

Example 5: Observe Romberg Table Convergence

import math
from RombergIntegration import RombergIntegration

integrator = RombergIntegration(0, math.pi, 1e-10, lambda x: math.sin(x))
result = integrator.dynamic_programming(maximum_step=8)

print("Convergence Process of Romberg Table:")
print("=" * 70)
for i, row in enumerate(integrator.romberg_table):
    print(f"Row {i}: ", end="")
    for j, val in enumerate(row):
        if j < len(integrator.romberg_table[i]):
            print(f"{val:.10f}  ", end="")
    print()

print("\nPrecision Improvement Sequence:")
for i, prec in enumerate(integrator.precision_table):
    print(f"Step {i}: error = {prec:.2e}")

Unit Tests

This project includes 10 comprehensive unit tests covering various scenarios.

Running Tests

# Run all tests
python test_romberg.py

# Expected output
============================================================
Running Cython Romberg Integration Tests
============================================================
✓ Test 1 passed: constant function (recursive) = 1.0
✓ Test 2 passed: linear function (recursive) = 0.5
✓ Test 3 passed: quadratic function (recursive) = 0.3333333333333333
✓ Test 4 passed: cubic function (recursive) = 0.25
✓ Test 5 passed: sine function (recursive) = 2.0
✓ Test 6 passed: cosine function (recursive) = 1.0
✓ Test 7 passed: exponential function (recursive) = 1.7182818284590444
✓ Test 8 passed: reciprocal function (recursive) = 0.693147180559947
✓ Test 9 passed: polynomial function (dynamic programming) = 1.8666666666666667
✓ Test 10 passed: trigonometric function (dynamic programming) = 2.041077998578922e-17
============================================================
Results: 10/10 tests passed
============================================================
✓ All tests passed!

Test Details

Recursive Method Tests (Tests 1-8)

Test	Function	Integration Interval	Theoretical Value	Description
1	f(x) = 1	[0, 1]	1.0	Constant function
2	f(x) = x	[0, 1]	0.5	Linear function
3	f(x) = x²	[0, 1]	1/3 ≈ 0.3333	Quadratic polynomial
4	f(x) = x³	[0, 1]	0.25	Cubic polynomial
5	f(x) = sin(x)	[0, π]	2.0	Sine function
6	f(x) = cos(x)	[0, π/2]	1.0	Cosine function
7	f(x) = eˣ	[0, 1]	e-1 ≈ 1.7183	Exponential function
8	f(x) = 1/x	[1, 2]	ln(2) ≈ 0.6931	Logarithmic function

Dynamic Programming Method Tests (Tests 9-10)

Test	Function	Integration Interval	Theoretical Value	Description
9	f(x) = x⁴ + 2x² + 1	[0, 1]	28/15 ≈ 1.8667	Complex polynomial
10	f(x) = sin(x)cos(x)	[0, π]	0.0	Trigonometric combination

Performance Characteristics

Optimization Measures

1. Static Typing

   • Uses long double for high-precision computation
   • Avoids Python object overhead

2. Compilation Directives

   # cython: language_level=3, boundscheck=False, wraparound=False, cdivision=True
   

   • boundscheck=False: Disables boundary checks
   • wraparound=False: Disables negative index wrapping
   • cdivision=True: Enables C-style division

3. C Library Functions

   • Uses pow and fabs from libc.math
   • Avoids Python function call overhead

4. Compilation Optimization

   • -O3: Maximum optimization level
   • -march=native: Utilizes native CPU features
   • -ffast-math: Fast mathematical operations

Performance Comparison

Item	C++ Native Version	Cython Version
Compilation	Direct g++ compilation	Cython -> C/C++
Runtime Speed	Native C++	Near-native C++
Python Availability	Requires additional wrapping	Native Python support
Ease of Use	Medium	High
Interface Consistency	-	✓ Fully Compatible

Algorithm Description

Romberg Integration Algorithm

Romberg integration is an extrapolation acceleration method that combines trapezoid rule results with different step sizes to improve precision.

Basic Principle:

1. Use trapezoid rule for initial values: $T(m, 0)$
2. Progressively improve using Richardson extrapolation formula:

$$T(m, k) = \frac{4^k T(m, k-1) - T(m-1, k-1)}{4^k - 1}$$

3. Stop when $|T(m, k) - T(m, k-1)| < \text{precision}$

Two Implementation Approaches:

• Recursive Method: On-demand computation with hash table caching of intermediate results
• Dynamic Programming Method: Build complete Romberg table row by row from bottom to top

FAQ

Q1: How to choose the precision parameter?

A: Choose based on application requirements:

# General engineering applications (relative error 1e-6)
integrator = RombergIntegration(a, b, 1e-8, f)

# Scientific computing (relative error 1e-10)
integrator = RombergIntegration(a, b, 1e-12, f)

# High-precision computing (relative error 1e-14)
integrator = RombergIntegration(a, b, 1e-14, f)

Q2: What's the difference between recursive and dynamic programming methods?

A:

Feature	Recursive Method	Dynamic Programming Method
Computation Strategy	On-demand	Row-by-row
Intermediate Results	Hash table caching	Complete table
Memory Usage	Potentially less	Fixed 2D table
Visualization	Not intuitive	Complete table visible
Control Granularity	Automatic	Manual step specification

Selection Recommendation:

• Fast computation: Use recursive method
• Observe convergence process: Use dynamic programming method

Q3: How to handle integration failures?

A: Current version doesn't throw exceptions, but may return inaccurate results. Recommendations:

integrator = RombergIntegration(a, b, 1e-10, f)
result = integrator.recursive()

# Verify result reliability
if abs(result) > 1e10:
    print("Warning: Result may be unreliable, please check function or parameters")

Q4: How to integrate into my project?

A: Two methods available:

Method 1: Copy files directly

cp RombergIntegration.pyx your_project/
# Add this module to your_project's setup.py

Method 2: Install as dependency

pip install -e .  # Run in project directory

File Structure

romberg/
├── README.md                      # Project documentation (this file)
├── LICENSE                        # MIT License
├── pyproject.toml                 # Modern Python project configuration
├── setup.py                       # Build script
├── MANIFEST.in                    # Source distribution manifest
├── RombergIntegration.pyx         # Cython core implementation
├── test_romberg.py                # Unit tests
├── test_romberg_compare.py        # Comparison tests with C++ version
└── .github/
    └── workflows/
        └── ci.yml                 # GitHub Actions CI/CD

Technical Details

Cython Compilation Directives

# cython: language_level=3, boundscheck=False, wraparound=True, cdivision=True

• language_level=3: Use Python 3 syntax
• boundscheck=False: Disable bounds checking (improves performance)
• wraparound=True: Retain negative index support
• cdivision=True: C-style integer division

Key Data Structures

class RombergIntegration:
    cdef:
        object _integrand              # Python callable object
        long double _lower_bound       # Lower integration bound
        long double _upper_bound       # Upper integration bound
        long double _precision         # Required precision
        dict romberg_map               # Recursive method cache (m-k -> value)
        list romberg_table             # Dynamic programming method table
        list precision_table           # Precision improvement sequence

License

This project is licensed under the MIT License. See the LICENSE file for details.

Author

• Original Version (C++): wangheng [e-mail]
• Cython Port: wangheng [e-mail]

Changelog

v1.0.0 (2026-01-27)

• ✨ Initial release
• ✓ Recursive method implementation
• ✓ Dynamic programming method implementation
• ✓ Comprehensive unit tests (10/10)
• ✓ Complete API documentation
• ✓ GitHub Actions CI/CD

Related Resources

• Romberg's Method - Wikipedia
• Numerical Analysis - Extrapolation Methods
• Cython Documentation