Integer points close to a transcendental curve: an algorithmic approach
For developers of correctly rounded mathematical libraries, this work reduces the computational cost of implementing binary128 support, which was previously prohibitive.
The paper presents an algorithmic approach to find integer points near transcendental curves, achieving a significant speedup for the Table Maker's Dilemma problem, enabling correct rounding for binary128 format at a much smaller cost.
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.