Arithmetic with ULPs

[John C. Bollinger]

Basic question: if d is a finite positive double value, is
d - Math.ulp(d)
guaranteed to be the next representable double value smaller than d? Is
there any finite value of d for which the result would be d, or for
which there is another double value between the result and d?

The docs for Math.ulp(double) describe it in terms of the opposite
direction -- the distance to the next value _larger_ than the argument.
I'm out of my league when it comes to this level of minutiae of
floating point representation and arithmetic.

Thanks,

 

[D Jensen]

This is not authoritative! But it seems to me (without having tested)
that the answer to your question is a resounding NO.
The reason is that the distribution of doubles is not uniform over the
field of (0.0D , MAX]. This necessarily implies that for most (all?)
values the distance to the next higher double and the distance to the
next lower double is NOT the same. I dont know if rounding would take
care of this. I would try a simple test program :
//PSEUDO CODE
boolean testHypothesis(){
for (int i=0;i<50000;i++)
{
d1= Random.nextDouble();
diff1=ulp(d1);
d2=d1-diff1;
if (d1 == d2) return false;
if (d2+ulp(d2) != d1) return false;
}
return true;
}

or something similar should show you quite quickly

I may be wrong though... let me know,

David Jensen

 

[D Jensen]

beware if testing this though, as it's most probably near-uniform for
doubles between 0 and 1, try getting the random double up near 100000
for what i think will be a quick failure. Even better might be to do
the step down 100 times, and then the step up 100 times, and compare
the starting and final results only, to see if they match (which i
don't think they will)

 

[Patricia Shanahan]

Basic question: if d is a finite positive double value,
is d - Math.ulp(d) guaranteed to be the next
representable double value smaller than d? Is there any
finite value of d for which the result would be d, or
for which there is another double value between the
result and d?

There will be a double between d and d-Math.ulp(d) if d is a
finite integer power of two greater than
Double.valueOf(2.0E-323). Specifically, the next smaller
double if d is a normalized positive power of two is d -
Math.ulp(d)/2

Given a fixed mantissa width, the ulp value depends on the
exponent. For normalized doubles (all finite doubles except
the very small ones) the exponent changes at each power of
two. The gap to the next smaller magnitude double is half
the gap to the next larger magnitude double, because the
smaller magnitude double's exponent is one less.

For finite positive double d, the next smaller double is
Double.longBitsToDouble(Double.doubleToLongBits(d)-1).

Patricia

 

[Patricia Shanahan]

beware if testing this though, as it's most probably
near-uniform for doubles between 0 and 1, try getting the
random double up near 100000 for what i think will be a
quick failure. Even better might be to do the step down
100 times, and then the step up 100 times, and compare
the starting and final results only, to see if they match
(which i don't think they will)

I agree with "beware if testing this".

For each exponent in the finite normalized range, there is a
double for each distinct value of the 52-bit mantissa field.
Exactly one of those 2^52 doubles, the one with the all zero
mantissa, has the problem.

For the 100 times down and up test, you would see the
problem if the random choice were a power of two or one of
the next 99 representable numbers, so if the random numbers
are uniformly distributed over the representable numbers
there is about a 1 in 45E12 probability of a hit.

Despite the low random probability, it is an issue for many
interesting numbers, such as 0.25, 0.5, 1.0, 2.0, and 4.0.

Patricia

 

[John C. Bollinger]

There will be a double between d and d-Math.ulp(d) if d is a
finite integer power of two greater than
Double.valueOf(2.0E-323). Specifically, the next smaller
double if d is a normalized positive power of two is d -
Math.ulp(d)/2
OK.

Given a fixed mantissa width, the ulp value depends on the
exponent. For normalized doubles (all finite doubles except
the very small ones) the exponent changes at each power of
two. The gap to the next smaller magnitude double is half
the gap to the next larger magnitude double, because the
smaller magnitude double's exponent is one less.

Got it.

For finite positive double d, the next smaller double is
Double.longBitsToDouble(Double.doubleToLongBits(d)-1).

Thanks, Patricia, that's exactly what I needed. Not only that, but it
makes sense, too.

 

[John C. Bollinger]

This is not authoritative! But it seems to me (without having tested)
that the answer to your question is a resounding NO.
The reason is that the distribution of doubles is not uniform over the
field of (0.0D , MAX].

Yes, I already recognized this property of exactly representable
doubles, which is why the question arose at all (and why there is a use
for Math.ulp(double)).

This necessarily implies that for most (all?)
values the distance to the next higher double and the distance to the
next lower double is NOT the same. I dont know if rounding would take
care of this.

THAT was one of the keys to the question. I hadn't adequately
internalized the details of IEEE floating point representations to
understand what the magnitude of the difference in ULP might be, and it
seemed to me that rounding might fix up the difference. Having digested
Patricia's response, it is now clear to me that that is not the case.

I would try a simple test program :

I appreciate your suggestion, though I prefer to rely on specifications
when they are sufficiently precise to provide an answer.

Thanks for your response.