arXiv:2410.07468v4 Announce Type: replace-cross Abstract: Evaluating real numbers to high precision is important in computational science, numerical computing, and in hardware and software design. Efficient algorithms exist for computing arithmetic operations and common elementary functions, but composing these primitives into larger expressions remains a challenge. The typical expression-evaluation algorithm computes all primitives in the expression to a uniform precision, doubling that precision until a sufficiently-accurate result is achieved. This is wasteful: usually only a few operations really need to be performed at high precision, and the bulk of the expression could be computed at a much lower, faster precision. However, no rigorous algorithm currently exists to compute these non-uniform precision assignments, nor to leverage non-uniform precision to reduce the number of primitive computations needed to evaluate an expression. We propose a new algorithm for deriving such rigorous precision assignments and reducing the number of primitive computations needed. This algorithm can leverage results computed at lower precisions to analytically determine a precision for each primitive that will result in a sufficiently-accurate evaluation. It can also use information from constant subexpressions, movability flags, and repeat flags to skip the computation of certain primitives, further reducing the time to evaluate real expressions. Our implementation, Reval, achieves an average speed-up of 3.97x compared to the widely-used Sollya tool, with the speed-up increasing to 9.26x on the most difficult inputs. A detailed evaluation shows that this speed-up results from both assigning lower precisions to the majority of primitives and from computing fewer primitives overall.