Arithmetic congruences and semantic composition

Abstract

Integer arithmetic as performed in fixed‐length representations sometimes leads to errors, the result obtained being congruent to the desired arithmetic result where the modulus of the congruence is dependent on the representation used. In some cases it is possible to perform a sequence of computations in such a way that the final result is correct even though the execution of each constituent is “incorrect”. (Indeed, it may be that the particular computation in question cannot be performed without causing an intermediate “error”). Put another way, there exist functions f and g such that y = f(x) and z = g(y) are erroneous for some x and yet their composition z=g ∘ f(x)=g(f(x)) is correct. We show how elementary theorems from Number Theory may be applied to verify some such computations.

AMS Classification:

• 10.06