Integer points close to a transcendental curve: an algorithmic approach
2026-06-03 • Symbolic Computation
Symbolic Computation
AI summaryⓘ
The authors present a new algorithm to find whole number points close to a certain kind of curved line, called a transcendental curve. Their method builds on earlier mathematical techniques but adds new theoretical backing and practical tests, showing it works faster than older methods. They apply this approach to a problem known as the Table Maker's Dilemma, which is about making sure computer calculations are very accurate when rounding numbers. Their experiments suggest it's now easier and cheaper to create precise math software for high-precision number formats. Overall, the authors offer a promising way to improve exact rounding in computer math libraries.
transcendental curveinteger pointsBombieri-Pila methodCoppersmith's methodalgorithm complexityTable Maker's Dilemmacorrect roundingbinary128 formatmathematical librarycomputational number theory
Authors
Nicolas Brisebarre, Guillaume Hanrot
Abstract
In this article, we propose an algorithmic approach to determine the integer points located near a transcendental curve. This approach is closely related to a celebrated work by Bombieri and Pila and to the so-called Coppersmith's method. We establish the underlying theoretical foundations, prove the algorithms, study their complexity and present practical experiments; we also compare our approach with previously existing ones. From a practical point of view, we focus on an instance of our general problem, called the Table Maker's Dilemma, whose solving makes it possible to evaluate a given function with correct rounding. Our experiments show a significant speedup. In particular, our results show that the development of a correctly rounded mathematical library for the binary128 format is now possible at a much smaller cost than with previously existing approaches.