Search code examples
floating-pointieee-754

IEEE754: guarantees on division results

Consider:

\x/10^y = z.5

x is a positive integer with a maximum value which is unlikely to be above about 10,000,000.

y is a small integer which is >=0, with a maximum value of about 5; I can set an upper limit if necessary.

z is calculated and then rounded to the nearest integer, with halfway cases rounded upwards. I'm interested in cases where the numerically correct answer is rounded upwards, but double-precision 754 gives the 'wrong' answer, which will then be rounded downwards. So, in other words, the numerically-correct result has a fractional part which is >=0.5, but the fractional part of the actual result is <0.5.

The language I'm using doesn't give me access to the FPU setup, so I can only use default settings (primarily x86_64, Linux and Windows).

Do I just have to accept that some answers will be 'wrong', or can I put some limits on x and y which are guaranteed to give the required answer? Or is there an alternative calculation which will give the correct answer after rounding? If necessary, I can also change the definition of how z will be rounded if I can actually make guarantees about the result.

Solution

  • Assuming:

    • x ≤ 10,000,000.
    • 0 ≤ y ≤ 5.
    • IEEE-754 basic 64-bit binary floating-point is used, with round-to-nearest-ties-to-even.

    Then the result of the division is never a number whose fraction part is less than ½ but that rounds to ½.

    The greatest result occurs when x = 10,000,000 and y = 0, in which case z = 10,000,000. Then z has 24 bits in its integer part. The floating-point format has 53 bits in the significand, so 29 remain available for the fraction part. This means that any fraction part less than ½ − 2−30 will be rounded to ½ − 2−29 or less (because the bits available for the fraction are capable of making distinctions that fine—if the mathematical result is less than ½ − 2−30, there is a representable value closer to it than ½, so the lower value is used).

    Therefore, only an exact mathematical result with a fraction in [½ − 2−30, ½) could be less than ½ but rounded up to ½. Let z be such a value, and let t be its fraction part.

    From the statement of the problem, we know that z • 10y is an integer (x). Therefore t • 10y is an integer, and, even if y is less than 5, t • 105 is an integer.

    Since t is in [½ − 2−30, ½), t • 105 is in [(½ − 2−30) • 105, ½ • 105) = [50,000 − 2−30 • 105, 50,000) = [50,000 - 0.0000931322574615478515625, 50,000).

    Obviously, there are no integers in this interval, so no such z exists.