RE: [Python-Dev] Expert floats
[Andrew Koenig]
But if you're moving to a wider precision, surely there is an even better decimal approximation to the IEEE-rounded "1.1" than 1.1000000000000001 (with even more digits), so isn't the preceding paragraph a justification for using that approximation instead?
[Tim]
Like Ping, you're picturing typing in "1.1" by hand, so that you *know* decimal 1.1 on-the-nose is the number you "really want".
[Andrew]
No, I don't think so. I said ``the IEEE-rounded "1.1"'', by which I mean the IEEE floating-point number that is closest to (infinite-precision) 1.1.
Oops -- got it.
Let's call that number X. Now, of course X is a rational number, and one that can be exactly represented on any machine with at least as many bits in its floating-point representation as the machine that computed X.
On the original machine, converting 1.1 to floating-point yields exactly X, as does converting 1.1000000000000001.
You claim that on a machine with more precision than the original machine, converting 1.1000000000000001 to floating-point will yield a value closer to X than converting 1.1 to floating-point will yield.
I agree with you. However, I claim that there is probably another decimal number, with even more digits, that when converted to floating-point on that machine will yield even a closer approximation to X, so isn't your line of reasoning an argument for using that decimal number instead?
It is, but it wasn't practical. 754 requires that float->string done to 17 significant digits, then back to float again, will reproduce the original float exactly. It doesn't require perfect rounding (there are different accuracy requirements over different parts of the domain -- it's complicated), and it doesn't require that a conforming float->string operation be able to produce more than 17 meaningful digits. For example, on Windows under 2.3.3:
print "%.50f" % 1.1 1.10000000000000010000000000000000000000000000000000
It's fine by the 754 std that all digits beyond the 17th are 0. It would also be fine if all digits beyond the 17th were 1, 8, or chosen at random. So long as Python relies on the platform C, it can't assume more than that is available. Well, it can't even assume that much, relying on C89, but almost all Python fp behavior is inherited from C, and as a "quality of implementation" issue I believed vendors would, over time, at least try to pay lip service to 754. That prediction was a good one, actually.
Here's another way to look at it. Suppose I want to convert 2**-30 to decimal. On a 64-bit machine, I can represent that value to 17 significant digits as 9.31322574615478516e-10. However, I can also represent it exactly as 9.3132257461547851625e-10.
On Windows (among others), not unless you write your own float->string routines to get those "extra" digits.
print "%.50g" % (2**-30) 9.3132257461547852e-010
BTW, it's actually easy to write perfect-rounding float<->string routines in Python. The drawback is (lack of) speed.
If you are arguing that I can get a better approximation on a machine with more precision if I write the first of these representations, doesn't that argument suggest that the second of these representations is better still?
Yes. The difference is that no standard requires that C be able to produce
the latter, and you only suggest David Gay's code because you haven't tried
to maintain it
Remember that every binary floating-point number has an exact decimal representation (though the reverse, of course, is not true).
Yup.
It is, but it wasn't practical. 754 requires that float->string done to 17 significant digits, then back to float again, will reproduce the original float exactly.
But that rules out those hypothetical machines with greater precision on which you are basing your argument.
It doesn't require perfect rounding (there are different accuracy requirements over different parts of the domain -- it's complicated), and it doesn't require that a conforming float->string operation be able to produce more than 17 meaningful digits.
I thought that 754 requires input and output to be no more than 0.47 LSB away from exact. Surely the spirit of 754 would require more than 17 significant digits on machines with more than 56-bit fractions.
So long as Python relies on the platform C, it can't assume more than that is available. Well, it can't even assume that much, relying on C89, but almost all Python fp behavior is inherited from C, and as a "quality of implementation" issue I believed vendors would, over time, at least try to pay lip service to 754. That prediction was a good one, actually.
Understood. What I meant when I started this thread was that I think things would be better in some ways if Python did not rely on the underlying C library for its floating-point conversions--especially in light of the fact that not all C libraries meet the 754 requirements for conversions.
Here's another way to look at it. Suppose I want to convert 2**-30 to decimal. On a 64-bit machine, I can represent that value to 17 significant digits as 9.31322574615478516e-10. However, I can also represent it exactly as 9.3132257461547851625e-10.
On Windows (among others), not unless you write your own float->string routines to get those "extra" digits.
No -- the representation is exact regardless of whether a particular implementation is capable of producing it :-)
BTW, it's actually easy to write perfect-rounding float<->string routines in Python. The drawback is (lack of) speed.
Agreed. I did it in C many moons ago.
If you are arguing that I can get a better approximation on a machine with more precision if I write the first of these representations, doesn't that argument suggest that the second of these representations is better still?
Yes. The difference is that no standard requires that C be able to produce the latter, and you only suggest David Gay's code because you haven't tried to maintain it
.
Naah - I also suggested it because I like the Scheme style of conversions, and because I happen to know David Gay personally. I have no opinion about how easy his code is to maintain. I completely agree that if you're going to rely on the underlying C implementation for floating-point conversions, there's little point in trying to do anything really good--C implementations are just too variable.
[Tim]
It is, but it wasn't practical. 754 requires that float->string done to 17 significant digits, then back to float again, will reproduce the original float exactly.
[Andrew]
But that rules out those hypothetical machines with greater precision on which you are basing your argument.
Sorry, couldn't follow that one.
It doesn't require perfect rounding (there are different accuracy requirements over different parts of the domain -- it's complicated), and it doesn't require that a conforming float->string operation be able to produce more than 17 meaningful digits.
I thought that 754 requires input and output to be no more than 0.47 LSB away from exact.
No, and no standard can ask for better than 0.5 ULP error (when the true result is halfway between two representable quantities, 0.5 ULP is the smallest possible error "even in theory"). It requires perfect rounding for "suitably small" inputs; outside that range, and excepting underflow/overflow: - for nearest/even rounding, it requires no more than 0.47 ULP error *beyond* that allowed for perfect nearest/even conversion (which has a max error of 0.5 ULP on its own) - for directed rounding, no more than 1.47 ULP error (and with the correct sign)
Surely the spirit of 754 would require more than 17 significant digits on machines with more than 56-bit fractions.
Yes, and the derivation of "17" for IEEE double format isn't hard. Of course the 754 standard doesn't say anything about non-754 architectures; there are generalizations in the related 854 standard. ...
Understood. What I meant when I started this thread was that I think things would be better in some ways if Python did not rely on the underlying C library for its floating-point conversions--especially in light of the fact that not all C libraries meet the 754 requirements for conversions.
No argument there. In fact, it would be better in some ways if Python didn't rely on the platform C libraries for anything.
... Naah - I also suggested it because I like the Scheme style of conversions, and because I happen to know David Gay personally. I have no opinion about how easy his code is to maintain.
It's not "David Gay" at issue, it's that this code is trying to do an extremely delicate and exacting task in a language that offers no native support. So here's a snippet of the #ifdef maze at the top: """ #else /* ifndef IEEE_Arith */ #undef Check_FLT_ROUNDS #undef Honor_FLT_ROUNDS #undef SET_INEXACT #undef Sudden_Underflow #define Sudden_Underflow #ifdef IBM #undef Flt_Rounds #define Flt_Rounds 0 #define Exp_shift 24 #define Exp_shift1 24 #define Exp_msk1 0x1000000 #define Exp_msk11 0x1000000 #define Exp_mask 0x7f000000 #define P 14 #define Bias 65 #define Exp_1 0x41000000 #define Exp_11 0x41000000 #define Ebits 8 /* exponent has 7 bits, but 8 is the right value in b2d */ #define Frac_mask 0xffffff #define Frac_mask1 0xffffff #define Bletch 4 #define Ten_pmax 22 #define Bndry_mask 0xefffff #define Bndry_mask1 0xffffff #define LSB 1 #define Sign_bit 0x80000000 #define Log2P 4 #define Tiny0 0x100000 #define Tiny1 0 #define Quick_max 14 #define Int_max 15 #else /* VAX */ #undef Flt_Rounds #define Flt_Rounds 1 #define Exp_shift 23 #define Exp_shift1 7 #define Exp_msk1 0x80 #define Exp_msk11 0x800000 #define Exp_mask 0x7f80 #define P 56 #define Bias 129 #define Exp_1 0x40800000 #define Exp_11 0x4080 #define Ebits 8 #define Frac_mask 0x7fffff #define Frac_mask1 0xffff007f #define Ten_pmax 24 #define Bletch 2 #define Bndry_mask 0xffff007f #define Bndry_mask1 0xffff007f #define LSB 0x10000 #define Sign_bit 0x8000 #define Log2P 1 #define Tiny0 0x80 #define Tiny1 0 #define Quick_max 15 #define Int_max 15 #endif /* IBM, VAX */ #endif /* IEEE_Arith */ #ifndef IEEE_Arith #define ROUND_BIASED #endif #ifdef RND_PRODQUOT #define rounded_product(a,b) a = rnd_prod(a, b) #define rounded_quotient(a,b) a = rnd_quot(a, b) #ifdef KR_headers extern double rnd_prod(), rnd_quot(); #else extern double rnd_prod(double, double), rnd_quot(double, double); #endif #else #define rounded_product(a,b) a *= b #define rounded_quotient(a,b) a /= b #endif #define Big0 (Frac_mask1 | Exp_msk1*(DBL_MAX_EXP+Bias-1)) #define Big1 0xffffffff #ifndef Pack_32 #define Pack_32 #endif #ifdef KR_headers #define FFFFFFFF ((((unsigned long)0xffff)<<16)|(unsigned long)0xffff) #else #define FFFFFFFF 0xffffffffUL #endif #ifdef NO_LONG_LONG #undef ULLong #ifdef Just_16 #undef Pack_32 /* When Pack_32 is not defined, we store 16 bits per 32-bit Long. * This makes some inner loops simpler and sometimes saves work * during multiplications, but it often seems to make things slightly * slower. Hence the default is now to store 32 bits per Long. */ #endif #else /* long long available */ #ifndef Llong #define Llong long long #endif #ifndef ULLong #define ULLong unsigned Llong """ and a snippet of some #ifdef'ed guts (assuming that it's obvious why Bletch is #define'd to 2 on some platforms but 4 on others <wink>): """ #ifdef Pack_32 if (k < Ebits) { d0 = Exp_1 | y >> Ebits - k; w = xa > xa0 ? *--xa : 0; d1 = y << (32-Ebits) + k | w >> Ebits - k; goto ret_d; } z = xa > xa0 ? *--xa : 0; if (k -= Ebits) { d0 = Exp_1 | y << k | z >> 32 - k; y = xa > xa0 ? *--xa : 0; d1 = z << k | y >> 32 - k; } else { d0 = Exp_1 | y; d1 = z; } #else if (k < Ebits + 16) { z = xa > xa0 ? *--xa : 0; d0 = Exp_1 | y << k - Ebits | z >> Ebits + 16 - k; w = xa > xa0 ? *--xa : 0; y = xa > xa0 ? *--xa : 0; d1 = z << k + 16 - Ebits | w << k - Ebits | y >> 16 + Ebits - k; goto ret_d; } z = xa > xa0 ? *--xa : 0; w = xa > xa0 ? *--xa : 0; k -= Ebits + 16; d0 = Exp_1 | y << k + 16 | z << k | w >> 16 - k; y = xa > xa0 ? *--xa : 0; d1 = w << k + 16 | y << k; #endif ret_d: #ifdef VAX word0(d) = d0 >> 16 | d0 << 16; word1(d) = d1 >> 16 | d1 << 16; #else #undef d0 #undef d1 #endif """ There are over 3,000 lines of code "like that" in dtoa.c alone. "Obviously correct" isn't obvious, and some days I think I'd rather track down a bug in Unicode.
I completely agree that if you're going to rely on the underlying C implementation for floating-point conversions, there's little point in trying to do anything really good--C implementations are just too variable.
Well, so far as marshal goes (storing floats in code objects), we could and should stop trying to use decimal strings at all -- Python's 8-byte binary pickle format for floats is portable and is exact for (finite) IEEE doubles.
But that rules out those hypothetical machines with greater precision on which you are basing your argument.
Sorry, couldn't follow that one.
You argued against applying the Scheme rules because that would make marshalling less accurate when the unmarshalling is done on a machine with longer floats. But on such a machine, 17 digits won't be good enough anyway.
I thought that 754 requires input and output to be no more than 0.47 LSB away from exact.
No, and no standard can ask for better than 0.5 ULP error (when the true result is halfway between two representable quantities, 0.5 ULP is the smallest possible error "even in theory"). It requires perfect rounding for "suitably small" inputs; outside that range, and excepting underflow/overflow:
- for nearest/even rounding, it requires no more than 0.47 ULP error *beyond* that allowed for perfect nearest/even conversion (which has a max error of 0.5 ULP on its own)
That's what I meant. Rather than 0.47 from exact, I meant 0.47 from the best possible.
Surely the spirit of 754 would require more than 17 significant digits on machines with more than 56-bit fractions.
Yes, and the derivation of "17" for IEEE double format isn't hard. Of course the 754 standard doesn't say anything about non-754 architectures; there are generalizations in the related 854 standard.
Yes.
Understood. What I meant when I started this thread was that I think things would be better in some ways if Python did not rely on the underlying C library for its floating-point conversions--especially in light of the fact that not all C libraries meet the 754 requirements for conversions.
No argument there. In fact, it would be better in some ways if Python didn't rely on the platform C libraries for anything.
Hey, I know some people who write C programs that don't rely on the platform C libraries for anything :-)
Naah - I also suggested it because I like the Scheme style of conversions, and because I happen to know David Gay personally. I have no opinion about how easy his code is to maintain.
It's not "David Gay" at issue, it's that this code is trying to do an extremely delicate and exacting task in a language that offers no native support. So here's a snippet of the #ifdef maze at the top:
<snip>
There are over 3,000 lines of code "like that" in dtoa.c alone. "Obviously correct" isn't obvious, and some days I think I'd rather track down a bug in Unicode.
Understood.
I completely agree that if you're going to rely on the underlying C implementation for floating-point conversions, there's little point in trying to do anything really good--C implementations are just too variable.
Well, so far as marshal goes (storing floats in code objects), we could and should stop trying to use decimal strings at all -- Python's 8-byte binary pickle format for floats is portable and is exact for (finite) IEEE doubles.
Gee, then you could go back to rounding to 12 digits and make ?!ng happy :-)
[Andrew Koenig]
You argued against applying the Scheme rules because that would make marshalling less accurate when the unmarshalling is done on a machine with longer floats.
I said the 754 committee had that objection. This was discussed on David Hough's numeric-interest mailing list at the time Clinger and Steele/White published their float<->string papers, and "phooey" was the consensus of the 754 folks on the mailing list at the time. The current incarnation of that committee appears to be in favor of perfect rounding all the time (so was the older incarnation, but it wasn't believed to be practical then), but I don't know what they think about shortest-possible (the older incarnation disliked that one). I personally don't think decimal strings are a sane way to transport binary floats regardless of rounding gimmicks.
But on such a machine, 17 digits won't be good enough anyway.
Doesn't change that 17 digits gets closer then shortest-possible: the art of binary fp is about reducing error, not generally about eliminating error. Shortest-possible does go against the spirit of 754 in that respect.
I thought that 754 requires input and output to be no more than 0.47 LSB away from exact.
No ... - for nearest/even rounding, it requires no more than 0.47 ULP error *beyond* that allowed for perfect nearest/even conversion (which has a max error of 0.5 ULP on its own)
That's what I meant. Rather than 0.47 from exact, I meant 0.47 from the best possible.
Well, you originally said that in response to my saying that the standard doesn't require perfect rounding (and it doesn't), and that the standard has different accuracy requirements for different inputs (and it does). So now I'm left wondering what your original "I thought that ..." was trying to get across. ...
Hey, I know some people who write C programs that don't rely on the platform C libraries for anything :-)
Python would love to grab their I/O implementation then <0.8 wink>.
You argued against applying the Scheme rules because that would make marshalling less accurate when the unmarshalling is done on a machine with longer floats.
I said the 754 committee had that objection.
OK, but either that objection is relevant for Python or it isn't.
This was discussed on David Hough's numeric-interest mailing list at the time Clinger and Steele/White published their float<->string papers, and "phooey" was the consensus of the 754 folks on the mailing list at the time.
Interesting -- I didn't know that. But it would make sense -- they're probably more interested in cross-platform computational accuracy than they are in convenience for casual uses.
I personally don't think decimal strings are a sane way to transport binary floats regardless of rounding gimmicks.
Fair enough.
But on such a machine, 17 digits won't be good enough anyway.
Doesn't change that 17 digits gets closer then shortest-possible: the art of binary fp is about reducing error, not generally about eliminating error. Shortest-possible does go against the spirit of 754 in that respect.
That's a fair criticism. On the other hand, maybe ?!ng is right about the desirable properties of display for people being different from those for marshalling/unmarshalling.
That's what I meant. Rather than 0.47 from exact, I meant 0.47 from the best possible.
Well, you originally said that in response to my saying that the standard doesn't require perfect rounding (and it doesn't), and that the standard has different accuracy requirements for different inputs (and it does). So now I'm left wondering what your original "I thought that ..." was trying to get across.
I don't remember; sorry.
Hey, I know some people who write C programs that don't rely on the platform C libraries for anything :-)
Python would love to grab their I/O implementation then <0.8 wink>.
http://www.research.att.com/sw/tools/sfio/ I think the licensing terms are compatible with Python, if you're serious.
[Andrew Koenig, on the move-to-wider-platform thing]
... OK, but either that objection is relevant for Python or it isn't.
It's not important to me. It may be important to some Python users now; I don't know. It may be more or less important in the future, because things do change.
... On the other hand, maybe ?!ng is right about the desirable properties of display for people being different from those for marshalling/unmarshalling.
There's no necessary connection between the two, as I've granted for all the years this debate has raged <wink>. OTOH, there's no fixed choice for displaying floats that will make everyone happy all the time, or, I think, even most people happy most of the time. You gave a list of 4 different behaviors you sometimes want. I have my own list, including some not on yours: + Display numbers with a comma every third digit. + Display numbers with just a few significant digits, but in "engineering" notation (== exponent always a multiple of 3). Because of this, arguments about repr() and str() are futile, IMO. The flexibility most people want some of the time can't be gotten by changing one fixed behavior for another. This isn't limited to floats, either. ...
Python would love to grab their I/O implementation then <0.8 wink>.
http://www.research.att.com/sw/tools/sfio/
I think the licensing terms are compatible with Python, if you're serious.
It was considered before, but its portablility to non-Unixish system looks poor, and in particular its Windows story appears to require commercial users to buy a UWIN license. Guido started on something different in the Python CVS sandbox/sio. I don't think he wrote a design doc, but the thrust is more to make composable filtering streams (like streams that deal with Unicode gracefully, and that hide differences among the different line end conventions (it's increasingly common to have to deal with a variety of file formats on a single box)).
participants (2)
-
Andrew Koenig
-
Tim Peters