Gap between numbers in fixed-point vs. floating point arithmetic

Question

If $r$ is a machine-representable number and $f(r)$ is the next larger machine representable number, are the following true or false?

1. In fixed-point arithmetic, the distance between $r$ and $f(r)$ is constant.

2. In floating-point arithmetic, the relative distance $|(f(r)-r)/r|$ is constant.

I believe that (1) is true, but I'm not sure about (2). I am new to the world of numerical analysis and I'm just trying to hang on for dear life. Could anybody point me to a resource that does a good job of explaining the basic introductory topics of machine mathematics?

Answer 1

1. Yes, the difference is constant.

2. It is not really constant, but approximately, yes. With exceptions.

With binary floating point numbers, the expression $(f(r)−r)/r$ is constant within a factor of $2$. It is between $1 \over 2^m$ and $1 \over 2^{m-1}$ where m is the number of bits in the mantissa. For rounding error calculations, you can assume it is constant.

A note on 0:
Obviously, you cannot apply the formula when $r=0$. But it is important to know that while $f(r)-r$ decreases when $r$ becomes small, $f(0)-0$ is much larger than, for instance, $f(f(r))-f(r)$. There is a huge non-representable gap around $0$.

Answer 2

(1) Yes, the numbers in fixed point arithmetic are just scaled integers.

(2) No, by a short counterexample. The floating-point arithmetic represents numbers as $r = i \times b^j$. Let us pick a random base, e.g. $b = 10$ and create the smallest positive number $r = 1 \times 10^m$. Let $m < 0$ be the minimal possible exponent (its size depends on the number of bits assigned to the exponent).

Now the next two numbers are $f(r) = 2 \times 10^m$ and $f(f(r)) = 3 \times 10^m$. After inserting them into your equation $$|(2 \times 10^m - 1 \times 10^m) / 10^m| = 1$$ however $$|(3 \times 10^m - 2 \times 10^m) / (2 \times 10^m)| = 0.5$$

Answer 3

For ieee754 floating point numbers (the most common) we have abs(f(r) - r) <= c with a rather small c as long as r is in the range of normalised numbers. For tiny numbers (denormalised) it behaves like fixed point.

You get better bounds if you assume that $2^k <= x < 2 \cdot 2^k$ with an error <= $c \cdot 2^k$, especially if x is slightly smaller than some power of two - you can often improve the precision of an algorithm if you can arrange things so intermediate results are slightly smaller than powers of two.