I provide an answer to this question below (I did not find an 'answer own question' button)
In Java, we have floating point type double which is encoded as 64 bits in memory. From this we know that it can take on at most 2^64 possible values, minus some special values. We could enumerate all of them.
The routines Math.nextUp(d) and Math.nextDown(d), given a double value d, will compute the one next larger and smaller double, respectively. Now I wonder how I can compute the number of double steps from one double a to b, i.e., my method difference(a,b) should work as follows:
assume a fixed, given a.
b = .... | difference(a, b)
===========================================================
a | 0
Math.nextUp(a) | 1
Math.nextDown(a) | 1
Math.nextUp(Math.nextUp(a)) | 2
Math.nextDown(Math.nextDown(a)) | 2
...and so on.
In the Java OpenJDK, the two mentioned methods are implemented as follows:
public static double nextUp(double d) {
if( Double.isNaN(d) || d == Double.POSITIVE_INFINITY)
return d;
else {
d += 0.0d;
return Double.longBitsToDouble(Double.doubleToRawLongBits(d) +
((d >= 0.0d)?+1L:-1L));
}
}
and
public static double nextDown(double d) {
if (Double.isNaN(d) || d == Double.NEGATIVE_INFINITY)
return d;
else {
if (d == 0.0)
return -Double.MIN_VALUE;
else
return Double.longBitsToDouble(Double.doubleToRawLongBits(d) +
((d > 0.0d)?-1L:+1L));
}
}
Can I safely do something similar, or does this only work because they only consider increments and decrements of 1, i.e., may I run into trouble with the exponent? I strongly assume the latter case, and wonder what would be the right method to achieve my goal?
Again: I want this to work for arbitrary doubles, i.e., difference(1e-3,3.442e201) should return the number Math.nextUp steps I would need to get from 1e-3 to 3.44e201. Obviously, just iterating and counting Math.nextUp would not do in this scenario.
Many thanks, Thomas.
Thanks to the comments of @Thilo, it turns out that it actually is that easy to calculate the difference. Well, at least it sems to be that easy.
Here is the Java code:
/** Some mathematical utilities */
public final class MathUtils {
/**
* The number of unique {@code double} values between {@code a} and
* {@code b}.
*
* @param a
* the first {@code double}
* @param b
* the second {@code double}
* @return the steps between them, or {@code -1} if either value is
* {@link Double#NaN} or both are infinities of different signs
*/
public static final long difference(final double a, final double b) {
final long bitsA;
double useA, useB, temp;
if ((a != a) || (b != b)) { // take are of NaN
return -1L;
}
useA = (a + 0d);
useB = (b + 0d);
if (useA > useB) {
temp = useB;
useB = useA;
useA = temp;
}
if (useA == useB) {
return 0L;
}
if (useA <= Double.NEGATIVE_INFINITY) {
return -1L;
}
if (useB >= Double.POSITIVE_INFINITY) {
return -1L;
}
if (useA < 0d) {
bitsA = Double.doubleToRawLongBits(-useA);
if (useB < 0d) {
return (bitsA - Double.doubleToRawLongBits(-useB));
}
return (bitsA + Double.doubleToRawLongBits(useB));
}
return (Double.doubleToRawLongBits(useB)
- Double.doubleToRawLongBits(useA));
}
}
and here some rudimentary JUnit test to confirm whether the results are what they should be:
import java.util.Random;
import org.junit.Assert;
import org.junit.Test;
/**
* A test for math utils
*/
public class MathUtilsTest {
/** the constructor */
public MathUtilsTest() {
super();
}
/** test step difference between two values */
@Test(timeout = 3600000)
public void testDifferenceBetweenTwoValues() {
final Random random;
double start, end;
int starts, iteration;
random = new Random();
for (starts = 333; (--starts) >= 0;) {
end = start = -(1d / Math.log(1d - random.nextDouble()));
for (iteration = 0; iteration < 3333; iteration++) {
Assert.assertEquals(iteration, MathUtils.difference(start, end));
Assert.assertEquals(iteration, MathUtils.difference(end, start));
end = Math.nextUp(end);
}
}
}
/**
* test the "step" difference of two values, one of which is negative,
* the other one being positive
*/
@Test(timeout = 3600000)
public void testDifferenceBetweenTwoValuesOfDifferentSign() {
double start, end;
int iteration;
end = start = 0d;
for (iteration = 0; iteration < 333333; iteration++) {
Assert.assertEquals(
(MathUtils.difference(start, 0d) + //
MathUtils.difference(0d, end)),
MathUtils.difference(start, end));
Assert.assertEquals(
(MathUtils.difference(start, 0d) + //
MathUtils.difference(0d, end)),
MathUtils.difference(end, start));
start = Math.nextAfter(start, Double.NEGATIVE_INFINITY);
end = Math.nextUp(end);
}
}
/** test the border cases of the step difference */
@Test(timeout = 3600000)
public void testDifferenceBetweenTwoValuesBorderCases() {
Assert.assertEquals(0L, MathUtils.difference(0d, 0d));
Assert.assertEquals(0L, MathUtils.difference(0d, -0d));
Assert.assertEquals(0L, MathUtils.difference(-0d, 0d));
Assert.assertEquals(0L, MathUtils.difference(-0d, -0d));
Assert.assertEquals(1L, MathUtils.difference(0d, Double.MIN_VALUE));
Assert.assertEquals(1L, MathUtils.difference(Double.MIN_VALUE, 0d));
Assert.assertEquals(1L, MathUtils.difference(-0d, Double.MIN_VALUE));
Assert.assertEquals(1L, MathUtils.difference(Double.MIN_VALUE, -0d));
Assert.assertEquals(1L, MathUtils.difference(0d, -Double.MIN_VALUE));
Assert.assertEquals(1L, MathUtils.difference(-Double.MIN_VALUE, 0d));
Assert.assertEquals(1L, MathUtils.difference(-0d, -Double.MIN_VALUE));
Assert.assertEquals(1L, MathUtils.difference(-Double.MIN_VALUE, -0d));
Assert.assertEquals(2L,
MathUtils.difference(Double.MIN_VALUE, -Double.MIN_VALUE));
Assert.assertEquals(2L,
MathUtils.difference(-Double.MIN_VALUE, Double.MIN_VALUE));
Assert.assertEquals((1L << 52L),
MathUtils.difference(0d, Double.MIN_NORMAL));
Assert.assertEquals((1L << 52L),
MathUtils.difference(Double.MIN_NORMAL, 0d));
Assert.assertEquals((1L << 52L),
MathUtils.difference(-0d, Double.MIN_NORMAL));
Assert.assertEquals((1L << 52L),
MathUtils.difference(Double.MIN_NORMAL, -0d));
Assert.assertEquals((1L << 52L),
MathUtils.difference(0d, -Double.MIN_NORMAL));
Assert.assertEquals((1L << 52L),
MathUtils.difference(-Double.MIN_NORMAL, 0d));
Assert.assertEquals((1L << 52L),
MathUtils.difference(-0d, -Double.MIN_NORMAL));
Assert.assertEquals((1L << 52L),
MathUtils.difference(-Double.MIN_NORMAL, -0d));
Assert.assertEquals((2L << 52L),
MathUtils.difference(Double.MIN_NORMAL, -Double.MIN_NORMAL));
Assert.assertEquals((2L << 52L),
MathUtils.difference(-Double.MIN_NORMAL, Double.MIN_NORMAL));
Assert.assertEquals(0L, MathUtils.difference(Double.POSITIVE_INFINITY,
Double.POSITIVE_INFINITY));
Assert.assertEquals(0L, MathUtils.difference(Double.NEGATIVE_INFINITY,
Double.NEGATIVE_INFINITY));
Assert.assertEquals(-1L, MathUtils.difference(Double.POSITIVE_INFINITY,
Double.NEGATIVE_INFINITY));
Assert.assertEquals(-1L, MathUtils.difference(Double.NEGATIVE_INFINITY,
Double.POSITIVE_INFINITY));
Assert.assertEquals(-1L, MathUtils.difference(Double.NaN, Double.NaN));
Assert.assertEquals(-1L,
MathUtils.difference(Double.POSITIVE_INFINITY, Double.NaN));
Assert.assertEquals(-1L,
MathUtils.difference(Double.NEGATIVE_INFINITY, Double.NaN));
Assert.assertEquals(-1L,
MathUtils.difference(Double.NaN, Double.POSITIVE_INFINITY));
Assert.assertEquals(-1L,
MathUtils.difference(Double.NaN, Double.NEGATIVE_INFINITY));
Assert.assertEquals(-1L,
MathUtils.difference(0d, Double.NEGATIVE_INFINITY));
Assert.assertEquals(-1L,
MathUtils.difference(0d, Double.POSITIVE_INFINITY));
Assert.assertEquals(-1L, MathUtils.difference(0d, Double.NaN));
Assert.assertEquals(-1L,
MathUtils.difference(Double.POSITIVE_INFINITY, 0d));
Assert.assertEquals(-1L,
MathUtils.difference(Double.NEGATIVE_INFINITY, 0d));
Assert.assertEquals(-1L, MathUtils.difference(Double.NaN, 0d));
Assert.assertEquals(-1L,
MathUtils.difference(1d, Double.NEGATIVE_INFINITY));
Assert.assertEquals(-1L,
MathUtils.difference(1d, Double.POSITIVE_INFINITY));
Assert.assertEquals(-1L, MathUtils.difference(1d, Double.NaN));
Assert.assertEquals(-1L,
MathUtils.difference(Double.POSITIVE_INFINITY, 1d));
Assert.assertEquals(-1L,
MathUtils.difference(Double.NEGATIVE_INFINITY, 1d));
Assert.assertEquals(-1L, MathUtils.difference(Double.NaN, 1d));
Assert.assertEquals(-1L,
MathUtils.difference(-1d, Double.NEGATIVE_INFINITY));
Assert.assertEquals(-1L,
MathUtils.difference(-1d, Double.POSITIVE_INFINITY));
Assert.assertEquals(-1L, MathUtils.difference(-1d, Double.NaN));
Assert.assertEquals(-1L,
MathUtils.difference(Double.POSITIVE_INFINITY, -1d));
Assert.assertEquals(-1L,
MathUtils.difference(Double.NEGATIVE_INFINITY, -1d));
Assert.assertEquals(-1L, MathUtils.difference(Double.NaN, -1d));
}
}
I'd be thankful for any counter-indications or issues not yet covered by the code.
Cheers, Thomas.
It seems you could just take the doubleToRawLongBits of the two values and subtract them (plus some extra logic to take care of the sign, crossing zero, and Inf/NaN).
Since all nextUp does is add one, the results of a subtraction should be consistent with the number of steps.