Fewest digits to get floating point that doesn't round trip through string?

user_754254 0
Viewed 76

Given a string s representing a real number in decimal notation, to_float returns the nearest IEEE double-precision float to that number.

Given an IEEE double f, to_string returns the shortest string fs such that to_float(fs) == f. E.g., using the Dragon4 algorithm

My question is: What is the shortest string, which is a valid non-NaN, finite number, such that to_string(to_float(s)) != s?

I've tried brute-forcing this, but only managed to check strings up to 7 digits + a decimal point

def check_numbers_up_to_n_digits(n):
    STR = np.format_float_positional
    FLOAT = float
    rngs = [tuple(range(1, i)) for i in range(n + 1)]
    for x in map(''.join, itertools.product('0123456789', repeat=n)):
        x = x.rstrip('0')
        if x == '': continue
        if x[0] == '0':
            s = '0.' + x[1:]
            if STR(FLOAT(s)) != s:
                print(repr(s))
            continue
        for d in rngs[len(x)]:
            s = x[:d] + '.' + x[d:]
            if s[-1] != '.' and STR(FLOAT(s)) != s:
                print(repr(s))
floating-point
1 Answers

There's a loophole in your question: there are many different strings representing any given numeric value, and to_string can only produce one of those, so to_string(to_float(s)) != s is trivially easy to achieve: just use s = "1.00", or s = "+1", or s = "123_456", or s = "1e-006", etc. For the specific to_string you're using in your search code, even just s = "0" is enough, since that converts back to "0.".

The more interesting question (and the question I think you're really asking) is: rather than simply being unequal on a character-by-character basis, what's the shortest s for which to_string(to_float(s)) and s represent different values? Below, I'll answer that question.

First, the answer: there are many such shortest strings, but they all have 16 significant digits, and hence the string must have length at least 16. s = "9007199254740993" is an example. If you insist on a decimal point being present in s, then we'll need at least 17 characters in the string.

Now to the justification: suppose that s is a decimal numeric string that represents a real number with at most 15 significant digits. Let's make it positive, for simplicity (zeros are boring, and the negative case doesn't introduce anything new or exciting). So in other words, s is a string representation of a real number of the form m * 10**e for some integers m and e, with 0 < m < 10**15.

Now let's convert s to the nearest IEEE 754 binary64 float (rounding ties to even as usual in the case of a tie), and then convert that float back to the nearest precision-15 decimal value, again rounding ties to even where necessary. (This isn't using the "shortest-string" conversion yet; we'll get to that below.)

Then it's a well-known property of floating-point base conversions that in this case, provided that s doesn't lie outside the range of normal binary64 values, we recover the original decimal value.

In other words, the composition of round-ties-to-even correctly-rounded conversions of floating-point numbers:

{precision-15 decimal} -> {precision-53 binary} -> {precision-15 decimal}

round trips, assuming either unbounded exponents, or that we avoid the extremes of the exponent range.

For proofs, see "In-and-out conversions", by David Matula. For an informal, hand-wavy intuitive justification, a key point is that if you compare 15-digit decimal floating-point with 53-bit binary floating-point, then the binary format is everywhere finer on the positive real-number line: if you pick any irrational number x, then the spacing between the two nearest binary floats to x is strictly smaller than the spacing between the two nearest decimal floats to x. The inequality that guarantees this is that 10**15 < 2**(53-1). (FWIW, I also wrote up my own proof here.)

For some evidence, you can try the following in Python:

>>> from random import randrange as rr
>>> from decimal import Decimal as D
>>> while True:
...     s = f"{rr(10**15)}e{rr(-300, 290)}"
...     t = format(float(s), '.15g')
...     assert D(s) == D(t)

Here we're repeatedly constructing a random 15-significant-digit string with random exponent, converting to float, converting back to a string with 15 significant digits, and then converting both numeric strings to Decimal (that conversion is exact) to compare their values. The while True loop should run indefinitely. Note that this assumes a version of Python that uses IEEE 754 binary64 floating-point, and for which float and float formatting are correctly rounded.

Now for the shortest string conversions: it follows from the fact above that the conversion from 15-digit decimal strings to binary64 must be injective: different 15-digit decimal strings must give different binary64 values. (Again, avoiding overflow and underflow; I'll stop mentioning this caveat from now on.) So if there's a 15-digit decimal string that converts to a given float, there's only one such.

So in the case that we started with a 15-digit decimal string s, if fs is the closest binary64 float to it, we already know that s converts to fs, so to_string(fs) must give something equivalent in value to s. So you won't find interesting examples where to_string(to_float(s)) != s unless s has more than 15 significant digits.

But as soon as you start looking for examples with 16 significant digits, there are many. The most obvious is s = "9007199254740993" (9007199254740993 being 2**53 + 1).

user_2709860
Related