Metadata-Version: 2.1
Name: RombergIntegration
Version: 1.0.0
Summary: High-performance Cython implementation of Romberg Integration algorithm
Author-email: wangheng <wangfaofao@gmail.com>
License: MIT License
        
        Copyright (c) 2025 Your Name/Organization
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to deal
        in the Software without restriction, including without limitation the rights
        to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
        copies of the Software, and to permit persons to whom the Software is
        furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all
        copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
        AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
        LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
        OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
        SOFTWARE.
        
Project-URL: Homepage, https://github.com/wangheng/romberg-integration
Project-URL: Documentation, https://github.com/wangheng/romberg-integration/blob/main/README.md
Project-URL: Repository, https://github.com/wangheng/romberg-integration.git
Project-URL: Issues, https://github.com/wangheng/romberg-integration/issues
Keywords: numerical-integration,romberg,calculus,cython,numerical-methods
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Cython
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Provides-Extra: dev
Requires-Dist: pytest>=7.0.0; extra == "dev"
Requires-Dist: pytest-cov>=4.0.0; extra == "dev"
Requires-Dist: black>=23.0.0; extra == "dev"
Requires-Dist: isort>=5.12.0; extra == "dev"
Requires-Dist: mypy>=1.0.0; extra == "dev"
Provides-Extra: docs
Requires-Dist: sphinx>=5.0.0; extra == "docs"
Requires-Dist: sphinx-rtd-theme>=1.0.0; extra == "docs"

<!-- 中文版本 -->

# Romberg Integration - 高精度数值积分库

[English](#english-version) | 中文

<div align="center">

![License](https://img.shields.io/badge/License-MIT-green.svg)
![Python](https://img.shields.io/badge/Python-3.6+-blue.svg)
![Cython](https://img.shields.io/badge/Cython-0.29+-blue.svg)

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

[快速开始](#快速开始) • [安装](#安装) • [API 文档](#api-文档) • [示例](#使用示例) • [单元测试](#单元测试)

</div>

---

## 项目简介

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

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

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

## 核心特性

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

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

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

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

## 快速开始

### 最简单的使用方式

```python
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
```

### 使用动态规划方法

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

## 安装

### 系统要求

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

### 安装步骤

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

```bash
# 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` 文件：

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

## API 文档

### 类：`RombergIntegration`

Romberg 积分计算器的主类。

#### 构造函数

```python
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` |

**示例**：

```python
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` - 计算得到的积分结果

**算法特点**：
- 使用递归分治法
- 自动缓存中间计算结果
- 精度自适应调整

**示例**：

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

##### `dynamic_programming(maximum_step: int = 20) -> float`

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

**参数说明**：

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

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

**算法特点**：
- 逐步构建 Romberg 表
- 结果可视化：可查看 `romberg_table` 和 `precision_table`
- 控制更细致

**示例**：

```python
# 使用默认步数
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()` 后有效
- 用于观察积分精度的逐步改进过程

**示例**：

```python
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()` 后有效

**示例**：

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

##### `romberg_map`

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

**类型**：`dict[str, float]`

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

**示例**：

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

## 使用示例

### 示例 1：基础积分计算

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

```python
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$

```python
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$

```python
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}$

```python
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 表的收敛过程

```python
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 个全面的单元测试，覆盖多种场景。

### 运行测试

```bash
# 运行所有测试
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
   # 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**: 精度参数应根据应用需求选择：

```python
# 一般工程应用 (相对误差 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**: 目前版本不抛出异常，但可能返回不准确的结果。建议：

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

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

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

**A**: 有两种方式：

**方式一**：直接复制文件
```bash
cp RombergIntegration.pyx your_project/
# 在 your_project 的 setup.py 中添加该模块
```

**方式二**：安装为依赖
```bash
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
# cython: language_level=3, boundscheck=False, wraparound=True, cdivision=True
```

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

### 关键数据结构

```python
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](LICENSE) 文件。

## 作者

- **原始版本**（C++）：wangheng <wangfaofao@gmail.com>
- **Cython 移植版**：wangheng <wangfaofao@gmail.com>

## 更新日志

### v1.0.0 (2026-01-27)

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

## 相关资源

- [Romberg 积分法 - Wikipedia](https://en.wikipedia.org/wiki/Romberg%27s_method)
- [数值分析 - 外推方法](https://en.wikipedia.org/wiki/Richardson_extrapolation)
- [Cython 文档](https://cython.readthedocs.io/)

---

<a id="english-version"></a>

# Romberg Integration - High-Precision Numerical Integration Library

[中文](#项目简介) | English

<div align="center">

![License](https://img.shields.io/badge/License-MIT-green.svg)
![Python](https://img.shields.io/badge/Python-3.6+-blue.svg)
![Cython](https://img.shields.io/badge/Cython-0.29+-blue.svg)

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

[Quick Start](#quick-start) • [Installation](#installation) • [API Reference](#api-reference) • [Examples](#usage-examples) • [Tests](#unit-tests)

</div>

---

## 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

```python
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

```python
# 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)

```bash
# 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:

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

## API Reference

### Class: `RombergIntegration`

Main class for Romberg integration computation.

#### Constructor

```python
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**:

```python
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**:

```python
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**:

```python
# 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**:

```python
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**:

```python
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**:

```python
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}$

```python
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$

```python
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$

```python
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}$

```python
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

```python
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

```bash
# 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
   # 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:

```python
# 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:

```python
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
```bash
cp RombergIntegration.pyx your_project/
# Add this module to your_project's setup.py
```

**Method 2**: Install as dependency
```bash
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
# 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

```python
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](LICENSE) file for details.

## Author

- **Original Version** (C++): wangheng <wangfaofao@gmail.com>
- **Cython Port**: wangheng <wangfaofao@gmail.com>

## 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](https://en.wikipedia.org/wiki/Romberg%27s_method)
- [Numerical Analysis - Extrapolation Methods](https://en.wikipedia.org/wiki/Richardson_extrapolation)
- [Cython Documentation](https://cython.readthedocs.io/)
