Finding the “discrete” difference between close fl

Question

Suppose I have two floating point numbers, x and y, with their values being very close.

There's a discrete number of floating point numbers representable on a computer, so we can enumerate them in increasing order: f_1, f_2, f_3, .... I wish to find the distance of x and y in this list (i.e. are they 1, 2, 3, ... or n discrete steps apart?)

Is it possible to do this by only using arithmetic operations (+-*/), and not looking at the binary representation? I'm primarily interested in how this works on x86.

Is the following approximation correct, assuming that y > x and that x and y are only a few steps (say, < 100) apart? (Probably not ...)

(y-x) / x / eps

Here eps denotes the machine epsilon. (The machine epsilon is the difference between 1.0 and the next smallest floating point number.)

Answer 1

Floats are lexicographically ordered, therefore:

int steps(float a, float b){

  int ai = *(int*)&a;  // reinterpret as integer
  int bi = *(int*)&b;  // reinterpret as integer
  return bi - ai;
}

steps(5.0e-1, 5.0000054e-1);  // returns 9

Such a technique is used when comparing floating point numbers.

Answer 2

You do not have to examine the binary representation directly, but you do have to rely on it to get an exact answer, I think.

Start by using frexp() to break x into exponent exp and mantissa. I believe the next float bigger than x is x + eps * 2^(exp-1). (The "-1" is because frexp returns a mantissa in the range [1/2, 1) and not [1, 2).)

If x and y have the same exponent, you are basically done. Otherwise you need to count how many steps there are per power of 2, which is just 1.0/eps. In other words, the number of steps between 2^n and 2^(n+1) is 1.0/eps.

So, for y > x, count how many steps there are from x to the next power of two; then count how many more steps it takes to get to the largest power of 2 less than y; then count how many more steps it takes to get from there up to y. All of these are pretty easily expressible in terms of eps, I think.