AxiomeLab  ·  Michel Jean

Romberg–Kahan Integrator

A C++ implementation of W. Kahan's algorithm for HP calculators
March 2026  ·  Source code release
· · ·
🇫🇷 Français

L'algorithme secret des HP

Depuis 1979, les calculatrices scientifiques HP — HP-34C, HP-15C, HP-42S — intègrent un algorithme de quadrature numérique développé par William Kahan, mathématicien chez HP et futur lauréat du prix Turing (1989).

L'idée centrale : une substitution cubique transforme l'intervalle [a, b] de sorte que la dérivé disparait aux bornes. La fonction n'est donc jamais évaluée aux points singuliers — ce qui permet d'intégrer des fonctions comme 1/√x ou ln(x) sans traitement spécial.

Sur la variable substituée, on construit le tableau de trapèzes en réutilisant les points des niveaux précédents, puis on applique l'extrapolation de Richardson (Romberg) pour une convergence extrêmement rapide sur les fonctions régulières.

Ce fichier C++ est une implémentation autonome, documentée et compilable directement. Modifiez simplement f(x) et les bornes, compilez, exécutez.

🇬🇧 English

The secret behind HP's ∫ key

Since 1979, HP scientific calculators — HP-34C, HP-15C, HP-42S — have used a numerical quadrature algorithm designed by William Kahan, HP mathematician and future Turing Award laureate (1989).

The core idea: a cubic substitution remaps the interval [a, b] so that the derivative vanishes exactly at the endpoints. The function is therefore never evaluated at singular points — allowing integration of functions like 1/√x or ln(x) with no special handling.

On the substituted variable, a trapezoid table is built by reusing points from previous levels, then Richardson extrapolation (Romberg) is applied for extremely fast convergence on smooth functions.

This C++ file is a self-contained, documented, directly compilable implementation. Simply edit f(x) and the bounds, compile, and run.

Output preview — 4/(1+x²) on [0,1] → π
kahan — integrator output
Terminal output of Romberg-Kahan integrator showing convergence to π
kahan.cpp
⬇ Download source

Compile : g++ kahan.cpp -o kahan    Run : ./kahan

References
  1. W. Kahan, "Handheld Calculator Evaluates Integrals", HP Journal, vol. 31 no. 8, August 1980, pp. 23–32. Original description of the algorithm used in the HP-34C.
  2. HP-15C Advanced Functions Handbook, Hewlett-Packard Co., 1982. Documents the integration algorithm inherited from the HP-34C.
  3. HP-42S RPN Scientific Calculator Owner's Manual, Hewlett-Packard Co., 1988. Continued use of the Kahan algorithm in the HP-42S.
  4. J.-F. Garnier, "The Math ROM for the HP-71B", jeffcalc.hp41.eu, 2019. Analysis of Kahan's implementation across the HP-71B math ROM.
  5. W. H. Press et al., Numerical Recipes in C++, 3rd ed., Cambridge University Press, 2007. §4.3 — Romberg integration and Richardson extrapolation.