1
$\begingroup$

In the article http://floating-point-gui.de/errors/comparison/, a method for comparing floating-point numbers is suggested:

There is an alternative to heaping conceptual complexity onto such an apparently simple task: instead of comparing a and b as real numbers, we can think about them as discrete steps and define the error margin as the maximum number of possible floating-point values between the two values.

This is conceptually very clear and easy and has the advantage of implicitly scaling the relative error margin with the magnitude of the values. Technically, it’s a bit more complex, but not as much as you might think, because IEEE 754 floats are designed to maintain their order when their bit patterns are interpreted as integers.

So instead of some complex variant of abs(b - a) < ε, we interpret a and b as integers and find abs(b - a) < ε(steps(a, b)) where ε is somehow variable with regards to the density of floating-point numbers in the vicinity of a and b. But how exactly?

Also, does this method really alleviate checking for NaNs and Infs? Or are some of these "heaps of conceptual complexity" inevitable if you want a solid, generic method of floating-point comparison?

The following C code produces 1677722:

#include <stdio.h>

int main(int argc, char *argv[])
{
    double x, y, z, a, b;
    int steps;

    sscanf("0.1", "%f", &x);
    sscanf("0.2", "%f", &y);
    sscanf("0.15", "%f", &z);

    a = x + y;
    b = z + z;
    steps = *(int*)&b - *(int*)&a;

    printf("%d\n", steps);
}

Edit: Rephrased so the word "discrete" is not misused. Rewrote "steps(a, b) < ε(a, b)" into "abs(b - a) < ε(steps(a, b))" to indicate that it may still just be floating-point operations, but that ε is chosen variably.

$\endgroup$
  • $\begingroup$ @aka.nice wrote on Stack Overflow before I moved the question here: "floating points are sign-magnitude rather than 2-complement so beware what happens near zero. Of course all this is technically implementation defined, and pointer aliasing should be replaced by a more robust technic in above code" $\endgroup$ – Simon Shine Jan 4 '17 at 12:28
  • 1
    $\begingroup$ Computers are discrete, any effective method to do anything is discrete in nature. However, it seems rather pointless to me to perform the kind of operations you mention in an high-level programming language when a floating point subtraction does the same in hardware, efficiently, Verilog-checked, and already handling exceptions for you. Detailed procedures to compare machine numbers avoiding precision errors are not trivial, and are studied by numerical analysts. $\endgroup$ – quicksort Jan 4 '17 at 14:25
  • $\begingroup$ @quicksort: Thanks for your points. I rewrote the question slightly. $\endgroup$ – Simon Shine Jan 4 '17 at 15:09
  • 2
    $\begingroup$ I'm pretty sure there is no such thing as "a solid, generic method of floating-point comparison". How you compare floating point numbers (for equality, anyway) almost always depends on what the numbers mean and how you got them. $\endgroup$ – Pseudonym Jan 5 '17 at 6:00
  • 1
    $\begingroup$ Re-interpreting IEEEE-754 binary floating-point operands as integers, then subtracting yields the difference in ulp, a useful and commonly used way of stating floating-point error. There are a few caveats: In general, comparing two floating-point operands via their bit pattern requires the operands to have the same sign; ulp error is not defined if one operand is zero, infinity, or NaN; there are differences in ulp error definitions if two values fall in two different binades. But generally, ulp-error comparison is good for ε-comparison $\endgroup$ – njuffa Jan 6 '17 at 18:18
4
$\begingroup$

There are a few fine tricks in the IEEE P754 format, which allows the use of integer operations for comparisons, or for rounding... It is useful for hardware implementations, for CPUs without an FPU, for some optimized libraries that need fast comparisons...

Caveats: - The sign bit (MSB) must be handled separately. - NaNs must be checked.

When comparing 0, denormals, normals or infinites of the same sign, integer comparisons work for floating point numbers.

$\endgroup$
  • 2
    $\begingroup$ I don't see how this answers the question. This seems like some generic comments about IEEE P754, but it's not clear it relates or connects to the specific question that was asked. As a reminder, the question was "But how exactly?" Can you edit your answer to be more explicit about answering the question that was asked? $\endgroup$ – D.W. Jan 4 '17 at 23:27
  • 1
    $\begingroup$ It does answer parts of the sub-question, "does this method really alleviate checking for NaNs and Infs?" But naturally, as the original paragraph that I'm citing was not being very elaborate, I'd enjoy more elaboration. :) $\endgroup$ – Simon Shine Jan 5 '17 at 9:05
  • 1
    $\begingroup$ I completed this answer yesterday with all the different bit patterns. I was about to post it then thought it was pointless. The answer to your question is "ask Wikipedia", take a bit of paper and write down the bit patterns and everything will become obvious. I once made an FPU in hardware, the way the carry can be propagated between the mantissa and exponent between denormals, normal, to infinite, show how cleverly this damn standard was invented. $\endgroup$ – TEMLIB Jan 5 '17 at 21:09
3
$\begingroup$

If you graph $y = float(x)$, that is, the float value obtained by interpreting/casting the integer x bitwise as a float, you get an exponential curve approximated by a piecewise linear function, as the value of y increases in fixed steps of $2^{exponent}$ for each range where $exponent$ is constant. So the density of values undergoes discontinuous jumps as you move along x, but it approximates an exponential ($1/y$) decline in density as x increases.

So what the author is suggesting is to scale the acceptable error approximately by using a fixed difference $dx$ in x, ie the number of discrete values between two comparands. If $dx$ falls within one line segment, this allowed error is exactly $dx * 2^{exponent}$ for the local exponent (it's slightly more complex if it crosses two or more segments), and it scales up as $exponent$ increases. So we get a kind of auto-adapting error that scales approximately with the inverse of the local density.

$\endgroup$
-1
$\begingroup$

Answer:

I think what this is describing is a matter of scaling.

Say you are comparing two floating-pointnumbers with a precision to two decimal places.

If you multiply both by 100 you have raised their values by two orders of magnitude, and end up with integers to compare.

This can be computationally more efficient, since every flop takes more time than an intop.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.