A firmware organization for minimal error evaluation in numerical computations
S. S. Hyder, V. Ung, J. Vignes · 1974
The use of numerical arithmetic developed for general use in continuous space, on computers where numerical values are represented by a finite number of significant digits leads to errors that tend degenerate as computing progresses. The principle of the permutation-perturbation method is that, while in algebra a given algorithm provides a single result r, the same algorithm carried out on a computer provides a set R of numerical results that are all representative of the exact algebraic result r. The perturbation procedure acts on the data and result of each elementary operation, and the permutation acts on the order on which operations are carried out. A statistical procedure is used to generate r and its accuracy from a few elements of the set R. In practice the method consists in adding (or not adding) a bit in low order position of each operand and the partial and final results of a computation. The permutation procedure consists in permuting (or not) the non-associative operators in the algorithm. The software simulation of the P-P algorithm has given excellent results. We describe in this paper our approach towards incorporating this concept as a microprogrammed module. It is expected that the study will be a step towards a machine structure that will yield an evaluation of the error together with the numerical results of an algorithm.