Relative error and wobble

Question

The full context of the below is on page 8 of What Every Computer Scientist Should Know About Floating-Point Arithmetic. In the below it is stated "In general, when the base is b, a fixed relative error expressed in ulps can wobble by a factor of up to b."

Can someone give a detailed proof of this? And what exactly does it mean by "a fixed relative error expressed in ulps can wobble by a factor of up to b."; if the relative error is fixed then how can it wobble or change?

the relative error is always bounded by e, which is referred to as machine epsilon.

...

To illustrate the difference between ulps and relative error, consider the real number x = 12.35. It is approximated by = 1.24 x 10^1. The error is 0.5 ulps; the relative error is 0.8 e. Next consider the computation 8x. The exact value is 8 x = 98.8, whereas, the computed value is 8 = 9.92 x 10^1. The error is now 4.0 ulps, but the relative error is still 0.8 e. The error measured in ulps is eight times larger, even though the relative error is the same. In general, when the base is b, a fixed relative error expressed in ulps can wobble by a factor of up to b. Conversely, as eq. (2) shows, a fixed error of 1/2 ulps results in a relative error that can wobble by b.

Answer 1

It is demonstrated on the same page as the quotes you give, in the paragraph before “In general, when the base is b, a fixed relative error expressed in ulps can wobble by a factor of up to b.”

That paragraph explains that numbers from 1.0000…0 • b^e to d.dddd…d • b^e, where d is, as I use it here, the digit b-1, have the same ULP, because the ULP is the value of the last digit, and that value of the last digit is determined by the exponent of b (and the number of digits in the significand, which is fixed for the format).

These numbers span a ratio of (almost) b, because d.dddd…d is almost b, so d.dddd…d / 1 is almost b. But they have the same ULP. Therefore, the magnitude of one ULP relative to the number spans a ratio of b.

Addressing the October 30, 2013, edit:

And what exactly does it mean by "a fixed relative error expressed in ulps can wobble by a factor of up to b."; if the relative error is fixed then how can it wobble or change?

The error is said to be a fixed number of ULP. But the value of an ULP is not fixed or constant truly fixed or constant relative to floating-point values.

There is just a language issue here. It is not accurate to speak of an ULP as a “fixed relative error”. However, people sometimes express error bounds or error amounts in ULPs because the nature of floating-point quantizes values, and those quanta are ULPs.

ULP is approximately a relative error. It stays in the same range throughout the entire scale of a floating-point format. Consider a three-digit decimal format:

• In the interval from 1.00 to 9.99, the absolute value of the ULP is .005. Its value relative to numbers in the interval ranges from .005 to (almost) .0005.
• In the interval from 1,000,000 to 9,990,000, the absolute value of the ULP is 5,000. Its value relative to numbers in the interval ranges from .005 to (almost) .0005.
• In the interval from 1.00•10^-100 to 9.99•10^-100, the absolute value of the ULP is .005•10^-100. Its value relative to numbers in the interval ranges from .005 to (almost) .0005.

As you see, the value of the ULP relative to floating-point numbers always stays within a small interval. Thus, it serves as an approximation of a relative error.

The fact that our expressions of relative errors in floating-point arithmetic wobble by a factor of b comes from two mathematical facts:

• When you work with floating-point arithmetic and calculate or derive a proof about the errors that may occur, you will find yourself expressing errors in units of ULP, because the quantization of the floating-point format causes bounds to be in ULPs or half-ULPs.
• For floating-point values x, the value of an ULP of x divided by x changes by a factor of b as x changes within a single exponent interval of the floating-point format. When the exponent changes, the value ULP(x)/x resets.