TAOCP 4.2.2 Exercise 13

Section 4.2.2: Accuracy of Floating Point Arithmetic

Exercise 13. ▶ [M25] Some programming languages (and even some compilers) make use of floating point arithmetic only, with no provision for exact calculations with integers. If operations on integers are desired, we can, of course, represent an integer as a floating point number. When the floating point operations satisfy our basic definitions in (9), we know that all floating point operations will be exact, provided that the operands and the answer can each be represented exactly with $p$ significant digits. Therefore, so long as we know that the numbers aren't too large, we can add, subtract, or multiply integers with no inaccuracy due to rounding errors.

But suppose that a programmer wants to determine if $m$ is an exact multiple of $n$, when $m$ and $n \ne 0$ are integers. Suppose further that a subroutine is available to calculate the quantity $\text{round}(u \bmod 1) = u \ominus \lfloor u \rfloor$ for any given floating point number $u$, as in exercise 4.2.1–15. One good way to determine whether or not $m$ is a multiple of $n$ might be to test whether or not $(m \oslash n) \ominus \lfloor m \oslash n \rfloor = 0$, using the assumed subroutine; but perhaps rounding errors in the floating point calculations will invalidate this test in certain cases.

Find suitable conditions on the range of integer values $n \ne 0$ and $m$, such that $m$ is a multiple of $n$ if and only if $(m \oslash n) \ominus \lfloor m \oslash n \rfloor = 0$. In other words, show that if $m$ and $n$ are not too large, this test is valid.

Verified: no
Solve time: 6m09s

Error in message stream