RE: [Python-Dev] Comparing heterogeneous types
Armin Rigo writes:
Is it really what we want? It seems to me that the precision of a float gives roughly the magnitude of "uncertainty" of the value that it represents. If a float is large enough, then the same float can represent several long integer values. It should then probably be considered equal to any of these integers, instead of just equal to the one arbitrarily returned by casting it to long.
I think that what you describe is NOT the behavior that we want, and I'll try to give an explanation of why. But please bear with me... I'm still a beginner at understanding some of the theory behind numerical computing, so I may make some mistakes. Hopefully those who understand it better will correct me. It's a fact that only certain numbers can be represented exactly when using numbers of finite precision. For instance, floating point numbers where the exponent is larger than the number of digits of precision can represent certain integers but not others. The same situation arises in the use of floating (or fixed) point decimals -- only certain fractions can be expressed exactly. There are (at least) two different mental models we can use to deal with this limitation of finite precision. One (which you are espousing above) is to treat each limited-precision number as if it had an inherent uncertainty, and it represented all those numbers which are closer to that representable number than any other. The other mental model is to suppose that each limited-precision number represents just one specific value and that the other values simply cannot be represented. I always understand things better when I have concrete examples, so let me use numbers in base 10 with a precision of 3 to illustrate these two viewpoints. With a precision of 3 we can write out the values 2.34x10^4 for the number 23,400 and 2.35x10^4 for the number 23,500. But 23,401, 23,402, and all the others in between can't be represented. So by the "Error bar" mental model, we think of "2.34x10^4" as shorthand for "some number from 23,350 to 23,450". By the "Exact values" mental model we think of "2.34x10^4" as meaning "The exact value 23,340". Now that we know there are two different mental models, we have to wonder whether one is inherently better than the other (and whether it makes any difference). I maintain that it DOES make a difference, and that the "Exact values" mental model is BETTER than the "Error bar" model. The reason why it is better doesn't come into play until you start performing operations on the numbers, so let's examine that. Suppose that you are adding two numbers under the "Exact values" mental model. Adding 1.23x10^4 and 3.55x10^4 is quite easy... the exact sum of 12,300 and 35,500 is 47,800 or 4.78x10^4. But if we add 1.23x10^4 and 8.55x10^2, then the "real" sum is 12,300 + 855 = 13,155. That CAN'T be represented in the "exact values" mental model, so we have to ROUND IT OFF and store "1.32x10^4" instead. In general, the values are quite clear in the "Exact values" model, but OPERATIONS may require rounding to express the result. Proponents of the "Error bar" mental model are now thinking "yes, well our model trades complexity of VALUES for simplicity in OPERATIONS". But unfortunately that's just not true. Again, let us try to add 1.23x10^4 and 3.55x10^4. What that REALLY means (in the "Error bar" mental model) is that we are adding SOME number in the range 12,250..12,350 to SOME number in the range 35,450..35,550. The result must be some number in the range 47,700..47,900. That is LIKELY to belong to the range 47,750..47,850 (ie 4.78x10^4), but it MIGHT also come out to something in the 4.77x10^4 range or the 4.79x10^4 range. We intent to return a result of 1.78x10^4, so operations in the "Error bar" mental model aren't simple, but contain some sort of "rounding off" as well, only the exact rules for how THIS "rounding off" works are a bit more confusing -- I'm not sure I could express them very well. (Side Note: You might think to fix this problem by saying that instead of perfect ranges, the numbers represent probability curves centered around the given number. By using gaussian curves, you might even be able to make addition "simple" (at the cost of a very complex idea of "values"). But whatever distribution worked for addition would NOT work for multiplication or other operations, so this trick is doomed to failure.) So it turns out that WHATEVER you do, operations on finite- precision numbers are going to require some sort of a "rounding off" step to keep the results within the domain. That being said, the "Exact values" mental model is superior. Not only does it allow a very simple interpretation of the "values", but it *also* allows the definition of "rounding off" to be part of the definition of the operations and not be linked to the values themselves. (For instance, I prefer a simple "round-to-nearest" rule, but someone else may have a different rule and that only affects how they perform operations.) It is for this reason that (I think) most serious specifications for the behavior of finite-precision numbers prefer to use the "Exact value" mental model. (Another side note: You will notice that the argument here is strikingly similar to the behavior of PEP 327's Decimal type. That's because I learned just about everything I'm saying here from following the discussions (and doing the recommended reading) about Facundo's work there.) Okay, in my long-winded fashion, I may have shown that the "Exact values" mental model is superior to the "Error bars" model. But does it really make any difference to anyone other than writers of numerical arithmetic specifications? It does, and one of the best examples is the one that started this conversation... comparing instances of different numerical types. I maintain that when comparing a long with a float where the exponent is larger than the precision, that the float should be treated as if it were EXACTLY EQUAL TO <coefficient>*2^<exponent>, instead of trying to treat it as some sort of a range. Similarly, if we implemented a Rational type, I would suggest that instances of float (or of Facundo's Decimal) where <exponent> is LESS than the digits of <coefficient> should be treated as if they were EXACTLY EQUAL TO the corresponding fraction-over-a-power-of-two. All right, those who ACTUALLY understand this stuff (rather than having learned it from this newsgroup) can go ahead and correct me now. Once-a-teacher,-always-trying-to-give-a-lecture-lly yours, -- Michael Chermside This email may contain confidential or privileged information. If you believe you have received the message in error, please notify the sender and delete the message without copying or disclosing it.
Michael Chermside cites Armin Rigo:
Armin Rigo writes:
Is it really what we want? It seems to me that the precision of a float gives roughly the magnitude of "uncertainty" of the value that it represents. If a float is large enough, then the same float can represent several long integer values. It should then probably be considered equal to any of these integers, instead of just equal to the one arbitrarily returned by casting it to long.
I think that what you describe is NOT the behavior that we want, and I'll try to give an explanation of why. But please bear with me... I'm still a beginner at understanding some of the theory behind numerical computing, so I may make some mistakes. Hopefully those who understand it better will correct me.
I'm not going to correct you--rather, I'd like to amplify what you're saying by noting that you don't even need to resort to numerical computing to make the argument. There's a much simpler line of reasoning: Sort and other related algorithms can be made to work reliably only if they have recourse to a total order relation over the elements being sorted. A total order relation is one for which exactly one of x<y, x==y, y<x holds for any x and y, and for which <, ==, and > are transitive, == is reflexive and symmetric, and < and > are irreflexive and antisymmetric. In other words, x==y if and only if y==x, x==y and y==z implies x==z, x<y and y<z implies x<z, and x>y and y>z implies x>z. If a float is considered equal to more than one integer, then these requirements fail, because if x is such a float, there are two integers m and n such that x==m, x==n, and m!=n. In other words, equality is not transitive. You can't sort numbers reliably under such circumstances.
There are (at least) two different mental models we can use to deal with this limitation of finite precision. One (which you are espousing above) is to treat each limited-precision number as if it had an inherent uncertainty, and it represented all those numbers which are closer to that representable number than any other. The other mental model is to suppose that each limited-precision number represents just one specific value and that the other values simply cannot be represented.
Yes. And as I understand it, that is the school of thought that computational numerical analysts are more likely to adopt these days. Such thinking, for example, gives rise to the requirement in IEEE floating-point that the primitive operations (+, -, /, *, and square root) must give results that are exactly equal to the infinite-precision results after rounding.
I maintain that when comparing a long with a float where the exponent is larger than the precision, that the float should be treated as if it were EXACTLY EQUAL TO <coefficient>*2^<exponent>, instead of trying to treat it as some sort of a range. Similarly, if we implemented a Rational type, I would suggest that instances of float (or of Facundo's Decimal) where <exponent> is LESS than the digits of <coefficient> should be treated as if they were EXACTLY EQUAL TO the corresponding fraction-over-a-power-of-two.
Right. I'm an amateur in this field too, but I've now been convinced many times over this is what comparisons *should* do, rather than converting the long (or int) to float and doing the comparison as float (what they currenttly do). Anyone feel like implementing this for 2.4? (Andrew Koenig posted an algorithm here a few weeks or so ago.) (For other operations, I still want to see e.g. long+float to return a float rather than a long -- you *have* to do it this way for obvious reasons when the values are relatively small, e.g. consider 1 + 0.5.) --Guido van Rossum (home page: http://www.python.org/~guido/)
Hello Guido, On Tue, Jun 22, 2004 at 10:49:51PM -0700, Guido van Rossum wrote:
(For other operations, I still want to see e.g. long+float to return a float rather than a long -- you *have* to do it this way for obvious reasons when the values are relatively small, e.g. consider 1 + 0.5.)
Well, just for quick consideration (and probably rejection :-) : If "a <= b" is to mean we convert a and b to either float or long depending on their magnitude, would it make any sense at all if other operators like "a + b" would do the same, to maximize precision?
1L + 0.5 1.5 L = 100000000000000000000000L float(L) 9.9999999999999992e+22 float(L+1) 9.9999999999999992e+22 L + 1.0 9.9999999999999992e+22 # currently 100000000000000000000001L # suggested
Armin
Well, just for quick consideration (and probably rejection :-) :
If "a <= b" is to mean we convert a and b to either float or long depending on their magnitude, would it make any sense at all if other operators like "a + b" would do the same, to maximize precision?
1L + 0.5 1.5 L = 100000000000000000000000L float(L) 9.9999999999999992e+22 float(L+1) 9.9999999999999992e+22 L + 1.0 9.9999999999999992e+22 # currently 100000000000000000000001L # suggested
No, the return type shouldn't depend on the input values. (This isn't an issue for comparisons, since those always return a bool.) --Guido van Rossum (home page: http://www.python.org/~guido/)
On Thu, Jun 24, 2004, Andrew Koenig wrote:
Guido:
No, the return type shouldn't depend on the input values.
It does already:
1000000000 + 1000000000 2000000000 2000000000 + 2000000000 4000000000L
Yes, and that's strictly a transitional wart. -- Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/ "Typing is cheap. Thinking is expensive." --Roy Smith, c.l.py
(For other operations, I still want to see e.g. long+float to return a float rather than a long -- you *have* to do it this way for obvious reasons when the values are relatively small, e.g. consider 1 + 0.5.)
That is not unreasonable behavior. However, I wonder if it might be possible to do better by yielding a long in those cases where the value is so large that the LSB of a float would be >=1. By doing so, it might be possible to guarantee that no precision is needlessly lost--analogously to having the result of int addition yield a long when an int cannot contain the result exactly. Please understand that I am not advocating this strategy for arithmetic the way I am for comparison, because I am not sure about its formal properties. I'm going to think about it for a while; depending on my conclusions, I may change my opinion later.
[Resending -- I got a weird bounce about this]
(For other operations, I still want to see e.g. long+float to return a float rather than a long -- you *have* to do it this way for obvious reasons when the values are relatively small, e.g. consider 1 + 0.5.)
That is not unreasonable behavior. However, I wonder if it might be possible to do better by yielding a long in those cases where the value is so large that the LSB of a float would be >=1. By doing so, it might be possible to guarantee that no precision is needlessly lost--analogously to having the result of int addition yield a long when an int cannot contain the result exactly.
Please understand that I am not advocating this strategy for arithmetic the way I am for comparison, because I am not sure about its formal properties. I'm going to think about it for a while; depending on my conclusions, I may change my opinion later.
Well, even if for comparisons we treat floats as if they were exact, for other purposes I want to keep the association of "float" with "inexact" and "int/long" with "exact", and I'd rather not return an "exact" result from an operation involvin an "inexact" operand. (The alternative, introducing exactness as a separate concept from representation, is better in theory but in practice just complicates matters needlessly.) --Guido van Rossum (home page: http://www.python.org/~guido/)
Well, even if for comparisons we treat floats as if they were exact, for other purposes I want to keep the association of "float" with "inexact" and "int/long" with "exact", and I'd rather not return an "exact" result from an operation involvin an "inexact" operand.
Agreed.
(The alternative, introducing exactness as a separate concept from representation, is better in theory but in practice just complicates matters needlessly.)
Also agreed. However, I'm thinking less about exactness than I am about choosing the more accurate of two possible representations for the result. For example, in principle it should be possible to guarantee that x+0.0 == x for all numeric values of x. The unanswered question in my mind is whether such a guarantee carries other undesirable properties along with it. Incidentally, right now I am leaning toward the believe that such a guarantee *does* carry other undesirable properties along with it. For example, consider 0L + 1e300. It is clear that in principle, no accuracy is lost by returning the result of this addition as a long. It is equally clear that in practice, it would be very slow.
Chermside, Michael wrote:
... [a generally great explanation] ... All right, those who ACTUALLY understand this stuff (rather than having learned it from this newsgroup) can go ahead and correct me now.
You missed the killer example, subtraction: Compare 2.34x10^4 - 2.34x10^4 and 2.34x10^40 - 2.34x10^40 These are obviously the same value in exact-mode, but no ranged system should treat them identically. Addition/subtraction is _more_ problematic than multiplication/division in error range stuff. You could even use 2.35x10^4 - 2.34x10^4 but I find the zeros more dramatic. - Scott David Daniels Scott.Daniels@Acm.Org
participants (7)
-
Aahz -
Andrew Koenig -
Andrew Koenig -
Armin Rigo -
Chermside, Michael -
Guido van Rossum -
Scott David Daniels