Assume I do this operation:
(X / const) * const
with double-precision arguments as defined by IEEE 754-2008, division first, then multiplication.
const is in the range 0 < ABS(const) < 1.
Assuming that the operation succeeds (no overflows occur), are distinct arguments of X to this operation guaranteed to return distinct results?
In other words, are there any X1, X2 and 0 < ABS(const) < 1 so that X1 <> X2, but (X1 / const) * const = (X2 / const) * const?
Does it really matter if you divide first and then multiply? The only difference would be overflows in the exponent, which as you stated would not happen.
According to What Every Computer Scientist must know about Floating Point Arithmetic (see Theorem 7 and 7') division followed by multiplication does not result in rounding errors for very specific denominators, sort of implying that there might be errors due to rounding if you divide and multiply for other denominators (but there is no explicit proof of that).
If you read those theorems, it looks like taking const = 1/n where n is the sum of atleast 3 distinct powers of 2, will probably give you the values you seek.
Yes.
public class TestDoubleDivision
{
public static void main(String[] args)
{
final Random random = new Random();
int i = 0;
while (i < 10)
{
final double c = random.nextDouble();
final double x1 = 10.0 * random.nextDouble();
final double x2 = nextDouble(x1);
if (x1 / c * c == x2 / c * c)
{
System.out.printf("x1 = %.20f, x2 = %.20f, c = %.20f\n", x1, x2, c);
i++;
}
}
}
private static double nextDouble(double d1)
{
return Double.longBitsToDouble(Double.doubleToLongBits(d1) + 1);
}
}
prints
x1 = 5.77383813703796800000, x2 = 5.77383813703796900000, c = 0.15897456707659440000 x1 = 2.97635611350670850000, x2 = 2.97635611350670900000, c = 0.15347615678619309000 x1 = 7.98634439050267450000, x2 = 7.98634439050267500000, c = 0.83202322046715640000 x1 = 0.11618686267768408000, x2 = 0.11618686267768409000, c = 0.09302449134082225000 x1 = 0.98646731978098480000, x2 = 0.98646731978098490000, c = 0.40549842805620606000 x1 = 3.95828649870362700000, x2 = 3.95828649870362750000, c = 0.75526917984495820000 x1 = 1.65404856207794440000, x2 = 1.65404856207794460000, c = 0.14500102367827516000 x1 = 5.72713430182017500000, x2 = 5.72713430182017550000, c = 0.68241935505532810000 x1 = 3.71143195248990980000, x2 = 3.71143195248991000000, c = 0.21294683305890750000 x1 = 5.66441726170857800000, x2 = 5.66441726170857900000, c = 0.69355199625947250000
(I just wanted to add something to starblue's answer -- it's too long to fit into a comment.)
I find it easier to see what's going on -- and I'm hoping you will too -- when I can see the full binary value of a double. I put starblue's examples in a C program and converted the output to binary (using my conversion program at http://www.exploringbinary.com/converting-floating-point-numbers-to-binary-strings-in-c/ ). Here's the output, plus the result of the calculation:
x1 = 101.1100011000011010010000011001001011111001110000111 x2 = 101.11000110000110100100000110010010111110011100001111 c = 0.00101000101100101000111010100110011111010101111100001 r = 100100.01010001101110101101000101101100011111011010101 x1 = 10.111110011111001001111001011010001100001011001111011 x2 = 10.1111100111110010011110010110100011000010110011111 c = 0.0010011101001010001101101010001000011100110010101011 r = 10011.011001001001100010101001001110011100011111011111 x1 = 111.1111110010000001000100001110001111001101010100101 x2 = 111.11111100100000010001000011100011110011010101001011 c = 0.11010100111111110111100101001001011010110100010111011 r = 1001.100110010100010010100101110100000100000110000011 x1 = 0.0001110110111110011011000001011101101100111011010101 x2 = 0.00011101101111100110110000010111011011001110110101010001 c = 0.0001011111010000011100111111110000001001001011101001 r = 1.00111111101111011111001110101010100101010101010101 x1 = 0.1111110010001001000111110100110100001000001101111111 x2 = 0.11111100100010010001111101001101000010000011011111111 c = 0.01100111110011101011111010110111000101001011000000111 r = 10.011011101100011101000000101000110110101011010011111 x1 = 11.1111010101010010010000111001010000100001011000111 x2 = 11.111101010101001001000011100101000010000101100011101 c = 0.110000010101100101010010001010110001110001011111111 r = 101.00111101101010110100110000011111101001010010101111 x1 = 1.1010011101101111101110100000000000011110110111110111 x2 = 1.1010011101101111101110100000000000011110110111111 c = 0.00100101000111101100100101111110100101011010111111001 r = 1011.011010000011101100001011000110000010011111110001 x1 = 101.10111010001001010111100100111110000111100001000011 x2 = 101.101110100010010101111001001111100001111000010001 c = 0.101011101011001100001000111011000001111010111011011 r = 1000.0110010001110100001001010000000101111000011111011 x1 = 11.101101100010000001100111100010010100011000001001111 x2 = 11.10110110001000000110011110001001010001100000101 c = 0.0011011010000011101011110000001111000110010101111111 r = 10001.01101101110011010100011111101110101011001010001 x1 = 101.10101010000101110011111111101001111011111010101111 x2 = 101.1010101000010111001111111110100111101111101011 c = 0.1011000110001100100111111010011000000010100011 r = 1000.0010101011010001010101111000111101110100001000001
(BTW, the "* const" part of the expression is unnecessary: the division by const alone shows that X1 / const == X2 / const.)
You can really see what's going on when you compare the double values with the true, arbitrary precision values. Take the first example, for instance:
x1/c = x2/c (double) = 100100.01010001101110101101000101101100011111011010101 x1/c (true) = 100100.01010001101110101101000101101100011111011010100 1011... x2/c (true) = 100100.01010001101110101101000101101100011111011010101 0111...
I put a space between significant bits 53 and 54, where the rounding occurs in a double. x1/c rounds up, and x2/c rounds down (truncates), becoming the same value.