Hardware for arbitrary-precision iterative numerical algorithms

Abstract

Many algorithms feature an iterative loop that converges to the result of interest. The numerical operations in such algorithms are generally implemented using finite-precision arithmetic, either fixed- or floating-point, most of which operate least-significant digit first. This results in a fundamental problem: if, after some time, the result has not converged, is this because we have not run the algorithm for enough iterations or because the arithmetic in some iterations was insufficiently precise? There is no easy way to answer this question, so users will often over-budget precision in the hope that the answer will always be to run for a few more iterations. I propose a fundamentally new approach: with the appropriate arithmetic able to generate results from most-significant digit first, this work shows that fixed compute-area hardware can be used to calculate an arbitrary number of algorithmic iterations to arbitrary precision, with both precision and approximant index increasing in lockstep. Consequently, datapaths constructed following my principles demonstrate efficiency over their traditional arithmetic equivalents where the latter's precisions are either under- or over-budgeted for the computation of a result to a particular accuracy. Further efficiency gains are realisable by inferring the superfluous digits within iterative calculations. Use of forward error analysis allows us to infer insignificant least-significant digits for stationary iterative methods. Their lack of computation is guaranteed not to affect the ability to reach a solution of any accuracy. Exploitation of most-significant digit-first arithmetic additionally enables us to declare certain digits to be identical at runtime for any iterative methods. Specific to stationary iterative methods, digit stability is inferred by combining the knowledge of identical digits shared between successive approximants with matrix conditioning. Both allow the skipping of MSD calculation. Versus arbitrary-precision iterative solvers without the optimisations I detail herein, up-to 470x performance speedups and 22x memory savings are achieved for the evaluated benchmarks.