NaN Is Weird
brassnet.biz
brassnet.biz
There are so many discussions about "X language is so weird about it handles numbers!" and it's just IEEE 754 floats.
See: https://docs.python.org/3/library/stdtypes.html#hashing-of-n...
There are a variety of problems here:
- floats can't represent whole numbers exactly as they get further from zero.
- error accumulates in floating point arithmetic, so calculated keys may not match constant keys
- Do you really want 2.0 and 2.00001 to refer to different objects?
>error accumulates in floating point arithmetic, so calculated keys may not match constant keys
Yes, but the parent used a toy example. It's a programming fundamental that you shouldn't be converting magic numbers to floats or doing math with floats without considering inaccuracy. These problems apply everywhere programmers use floats - they must understand them, regardless of whether they are using them as hash keys or any other purpose.
>Do you really want 2.0 and 2.00001 to refer to different objects?
Yes, very much so. They are different values. (Assuming you are using 2.00001 as shorthand for "a float close to 2")
The advantage of common primitives being hashable is theoretically very high. In Swift (where NaN hashes to a different value every time, since that makes sense), hashable primitives makes hashability composable, so anything composed of hashable parts is hashable. And hashability is important not just for storage in maps, but all sorts of things (e.g. set membership, comparison for diffs, etc).
The upsides of floats being hashable is potentially much higher than the downsides, which mostly stem from a programmer not understanding floats, not from floats being hashable.
This is all well and good in a language that makes you declare distinct floating point types, but in python things are maybe not so clear cut - the language uses arbitrary precision integers by default, and it's not always crystal clear when they are going to be converted to a (lossy) floating point representation
Yeah, the programmer should probably be aware of the ins and out here, but python folks often aren't all that in the weeds with the bits and the bytes
The real surprise to me is that Python can index NaN keys sometimes, at least by reference to the original NaN. I knew CPython does some Weird Shit with primitive values, so I assume it's because the hashmap is comparing by reference first and then by value.
Although you shouldn't put nonsense in a HashMap, HashMap::drain will give you (an iterator to get) back everything you put into the HashMap even if it's nonsense and HashMap::retain will let you provide a predicate to throw away the nonsense if you want to keep everything else, while HashMap::extract_if even allows you to get the nonsense back out again to put that somewhere more sensible.
These work because they don't need to find your nonsense in particular using hashing, which may now be impossible, they're just looking at everything.
I'll add that, if I recall correctly, in R, the statement NaN == NaN evaluates to NA which basicall means "it is not known whether these numbers equal each other" which is a more reasonable result than False.
If you do a (signed) integer operation, the hardware does not fit the result in a register of the size expected in a HLL, but the result has some bits elsewhere, typically in a "flags" register.
So the result of an integer arithmetic operation has an extra bit, usually named as the "overflow" bit. That bit is used to encode a not-a-number value, i.e. if the overflow bit is set, the result of the operation is an integer NaN.
For correct results, one should check whether the result is a NaN, which is called checking for integer overflow (unlike for FP, the integer execution units do not distinguish between true overflow and undefined operations, i.e. there are no distinct encodings for infinity and for NaN). After checking that the result is not a NaN, the extra bit can be stripped from the result.
If you serialize an integer number for sending it elsewhere, that implicitly assumes that wherever your number was produced, someone has tested for overflow, i.e. that the value is not a NaN, so the extra bit was correctly stripped from the value. If nobody has tested, your serialized value can be bogus, the same as when serializing a FP NaN and not checking later that it is a NaN, before using one of the 6 relational operators intended for total orders, which may be wrong for partial orders.
Equality, among other operations, are not defined for these inputs. NaN's really are a separate type of object embedded inside another objects value space. So you get the rare programmers gift of being able to construct a statement that is not always realizable based solely on the values of your inputs.
When you define an order relation on a set, the order may be either a total order or a partial order.
In a totally ordered set, there are 3 values for a comparison operation: equal, less and greater. In a partially ordered set, there are 4 values for a comparison operation: equal, less, greater and unordered.
For a totally ordered set you can define 6 relational operators (6 = 2^3 - 2, where you subtract 2 for the always false and always true predicates), while for a partially ordered set you can define 14 relational operators (14 = 2^4 - 2).
For some weird reason, many programmers have not been taught properly about partially-ordered sets and also most programming languages do not define the 14 relational operators needed for partially ordered sets, but only the 6 relational operators that are sufficient for a totally ordered set.
It is easy to write all 14 relational operators by combinations of the symbols for not, less, greater and equal, so parsing this in a programming language would be easy.
This lack of awareness about partial order relations and the lack of support in most programming languages is very bad, because practical applications need very frequently partial orders instead of total orders.
For the floating-point numbers, the IEEE standard specifies 2 choices. You can either use them as a totally-ordered set, or as a partially-ordered set.
When you encounter NaNs as a programmer, that is because you have made the choice to have partially-ordered FP numbers, so you are not allowed to complain that this is an odd behavior, when you have chosen it. Most programmers do not make this choice consciously, because they just use the default configuration of the standard library, but it is still their fault if the default does not do what they like, but nonetheless they have not changed the default settings.
If you do not want NaNs, you must not mask the invalid operation exception. This is actually what the IEEE standard recommends as the default behavior, but lazy programmers do not want to handle exceptions, so most libraries choose to mask all exceptions in their default configurations.
When invalid operations generate exceptions, there are no NaNs and the FP numbers are totally ordered, so the 6 relational operators behave as naive programmers expect them to behave.
If you do not want to handle the invalid operation exception and you mask it, there is no other option for the CPU than to use a special value that reports an invalid operation, and which is indeed not-a-number. With not-numbers added to the set of FP numbers, the set becomes a partially-ordered set and all relational operators must be interpreted accordingly.
If you use something like C/C++, with only 6 relational operators, then you must do before any comparison tests to detect any NaN operand, because otherwise the relational operators do not do what you expect them to do.
In a language with 14 relational operators, you do not need to check for NaNs, but you must choose carefully the relational operator, because for a partially-ordered set, for example not-less is not the same with greater-or-equal (because not-less is the same with greater-or-equal-or-unordered).
If you do not expect to do invalid operations frequently, it may be simpler to unmask the exception, so that you will never have to do any test for NaN detection.
The same not-number, produced by the same computation, occupying the same memory, is still not equal to itself. It is true that I haven't been able to brush up my knowledge on partial ordering, but isn't being identical is the same as being equal in math?
If you test if a not-a-number is not equal to itself, the result is also false.
The reason is that the result of comparing a not-number with itself is neither "equal" nor "not equal", but "unordered".
This should make perfect intuitive sense, because a NaN encodes the fact that "an undefined operation has happened".
For instance, you have 2 instances of the same NaN, both having been obtained by multiplying zero with infinity.
However it may happen that one was obtained while computing values of a sequence that converges to 10 and the other may have been obtained by computing values of a sequence that converges to 100.
Then there is no doubt that equality is not true for this 2 NaNs.
However, those 2 NaNs may have been generated while computing values of sequences that both converge to 10, which shows that neither non-equality may be trued for these 2 NaNs.
When you have NaNs, that means that it is unknown which value, if any, the invalid operations should have produced.
When comparing 2 unknown values, you cannot know whether they are equal or not equal, so both testing for equality and for non-equality must fail.
Or the argument is that NaNs are not actually the values themselves, but the representations of the facts of different failures, and because we can't compare the facts, we shouldn't compare NaNs? Well, I guess one could say that numbers in general are also such incomplete representations; 2 is 2, I could get 2 by adding one crayon to another crayon, or by taking 10 crayons and removing 8 of them. That doesn't stop me from comparing these 2s.
NaN means either an unknown number or that no number can satisfy the condition of being the result of the computed function.
When you compare unknown numbers, you cannot know if they are equal and you cannot know if they are not equal.
That is why both the equality operator and the non-equality operator must be false when comparing a NaN with itself.
When you see a binary FP number, the encoding no longer has any memory about where the number has been generated.
For deciding that a NaN is equal to itself, it is not enough to examine the encoding, you must know the history of the 2 instances of the same NaN value, where they had been generated. Only if the 2 instances are duplicates of a single value, i.e. they had been generated by the same operation, then you could say that they are equal.
If you would want such a facility in a program, then it is not enough to propagate just a floating-point value. You would have to define a custom data type and accompany the FP value by another value that encodes its provenance.
Then you could make custom equality and non-equality operators, which when comparing identical NaNs also compare their provenances, and they decide whether the NaNs are equal or non-equal based on the provenances.
Such a use case is extremely rare. In decades of experience I have never seen a situation when such a feature would be desirable. Nevertheless, if someone wants it, it would be easy to implement it, but it will add considerable overhead.
For example, the provenance could be encoded as a pointer to strings of the form "File ... Line ...", produced using the normal compiler facility for this, which will refer to the source line where the result of a function is tested for being a NaN, and if so the provenance pointer is stored, instead of a null pointer.
Even this encoding of the provenance may not be foolproof, because some functions may generate NaNs with different meanings. For a complete provenance encoding, one would need not only a pointer identifying the function that had generated the NaN, but also the value of a static counter that is incremented at each function invocation.
The provenance could be encoded compactly by storing the string pointers in an array and storing in the provenance an index into that array together with the value of the invocation counter.
So it can be done, but I am pretty sure that this would never be worthwhile.
> If you would want such a facility in a program, then it is not enough to propagate just a floating-point value. You would have to define a custom data type and accompany the FP value by another value that encodes its provenance.
IEEE 754 was way ahead of you. The entire rationale for the existing of NaN payloads was to be able to encode the diagnostic details about operation failure. And this suggests that you really want is the rule that NaNs are equal only to other NaNs with the same payload but are unordered with respect to everything else.
From the research I've done, it seems that the main reason that x != x for NaNs isn't some deep theoretical aspect about the properties of NaNs, but rather because IEEE 754 wanted a cheap way to test for NaN without having to call a function.
IEEE-754 does remainder(5, 3) = -1, whereas Python does 5 % 3 = 2.
There's no reason to expect exact equivalence between operators.
[1] https://stackoverflow.com/questions/18291620/why-will-stdsor...
Rust's standard sorts not only lack the API footgun which causes so many C++ programmers to blow their feet off this way, but even if you go out of your way to provide a nonsensical comparison both sorts are safe anyway because it's a safe language and yet they're also faster than any popular implementation of std::sort / std::stable_sort as appropriate.
It's kinda silly, as late as the Biden administration one of the popular C++ stdlib implementations wasn't even O(n log n) because apparently twenty years was not enough for them to have introduced an introsort yet... That one isn't the standard's fault, the C++ 11 standard does say you should provide an O(n log n) sort at least.
>>> my_dict[nan] = 3
>>> my_dict[nan]
3
>>> class Evil:
... def __init__(self, hash_value): self.hash_value = hash_value
... def __eq__(self, other): return False
... def __hash__(self): return self.hash_value
...
>>> e1, e2 = Evil(1), Evil(2)
>>> {e1:1, e2:2}
{<__main__.Evil object at ...>: 1, <__main__.Evil object at ...>: 2}
>>> {e1:1, e2:2}[Evil(1)]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: <__main__.Evil object at ...>
>>> {e1:1, e2:2}[e1]
1
(But it does have to find the instance via the hash lookup first. This won't work if you e.g. return a random number from `__hash__`.)
elm repl
---- Elm 0.19.1 ----------------------------------------------------------------
Say :help for help and :exit to exit! More at <https://elm-lang.org/0.19.1/repl>
--------------------------------------------------------------------------------
> import Dict exposing (Dict)
> nan = 0/0
NaN : Float
> nan
NaN : Float
> nan == nan
False : Bool
> naan = 0/0
NaN : Float
> d = Dict.fromList [(nan, "a"), (naan, "b")]
Dict.fromList [(NaN,"a"),(NaN,"b")]
: Dict Float String
> Dict.toList d
[(NaN,"a"),(NaN,"b")]
: List ( Float, String )
> Dict.keys d
[NaN,NaN] : List Float
> Dict.get nan d
Nothing : Maybe String
> Dict.get naan d
Nothing : Maybe StringOh, I missed it. But yes, this is more to do with NaN than Python.
> But, of course, you can't actually get to those values by their keys: ... That is, unless you stored the specific instance of nan as a variable:
Worth noting that sets work the same way here, although this was glossed over: you can store multiple NaNs in a set, but not the same NaN instance multiple times. Even though it isn't equal to itself, the insertion process (for both dicts and sets) will consider object identity before object equality:
>>> x = float('nan')
>>> {x for _ in range(10)}
{nan}
In my experience, INF and NaN are almost always an indicator of programming error.
If someone want's to programmatically represent those concepts, they could do it on top of and to the side of the floating point specification, not inside it.
I can also compare infinity to Java's BigDecimal values but I fail to see what I'd want to or need to.
Also: creating an efficient sort key.
Nobody forces you to use NaNs or to have partially-ordered floating-point numbers.
The default settings that have been recommended since the beginning by the standard were to not use NaNs and to have totally-ordered FP numbers.
For this choice, the invalid operation exception must not be masked.
However, it turns out that most programmers are lazy and do not want to bother to write an exception handler, so the standard libraries of C and of most other languages have chosen to mask by default this exception, which causes the generation of NaNs.
This bad default configuration in combination with the bad feature that most programming languages have only the 6 relational operators sufficient for a total order, instead of the 14 operators required for a partial order, makes necessary frequent tests for detecting whether a value is a NaN, to avoid surprising behavior in relational expressions.
I think that in most cases the extra checks for NaNs add up to much more work than writing at exception handler, so the better solution is to unmask the invalid operation exception, which makes the NaN problem go away.
The correct solution for any programming language is to define all the 14 relational operators that are required by any partially-ordered set, instead of defining only the 6 of them that are sufficient for a totally-ordered set.
If the programming language fails to define all 14 operators, then you must always test the operands for NaNs, before using any of the 6 ALGOL relational operators. If you consider this tedious, then you must unmask the invalid operation exception and take care to handle this exception.
If invalid operations generate exceptions, then the floating-point numbers become a totally-ordered set and NaN cannot exist (if a NaN comes from an external source, it will also generate an exception, while internally no NaN will ever be generated).
*This is false, NaN is weird, though maybe it needs to be. It is nowhere written arithmetic on computers must be straightforward.
Although Almost All† Real Numbers are Normal, none of the floats are normal, and nor are most numbers any regular person would think of (possible exceptions Pi and Euler's Number which are conjectured to be Normal although it is unproven)
† Almost All is a term of art in mathematics, remember there are uncountably many real numbers, so the fact the Normals are also uncountable puts them at least in the right ballpark, unlike the rationals.
It makes little sense that 1/0 is SIGFPE, but log(-5) is NaN in C.
And the same is true for higher level languages, and their error facilities.
What a mess.
It would be weird if the behavior of `1 / x` was different depending on whether `0` or `0.0` was passed to a `x: float` parameter -- if `int` is a subtype of `float`, then any operation allowed on `float` (e.g. division) should have the same behavior on both types.
This means Python had to choose at least one:
1. division violates the liskov substitution principle
2. division by zero involving only integer inputs returns NaN
3. division by zero involving only float inputs throws exception
4. It's a type error to pass an int where a float is expected.
They went with option 3, and I think I agree that this is the least harmful/surprising choice. Proper statically typed languages don't have to make this unfortunate tradeoff.
Python is the only language doing this (of the ones I use at least).
I don't think the notation `x: float = 0` existed when it was new by the way so that can't be the design reason?
since python seems to handle integer through integer divisions as float (e.g. 5 / 2 outputs 2.5), 0 / 0 giving nan would seem to be expected there
> liskov substitution principle
that would imply one is a subtype of another, is that really the case here? there are floats that can't be represented as an integer (e.g. 0.5) and integers that can't be represented as a double precision float (e.g. 18446744073709551615)
The rationale is basically that newcomers to Python should see the results that they would expect from grade school mathematics, not the results that an experienced programmer would expect from knowing C. While the PEP above doesn't touch on division by zero, it does point toward the objective being a cohesive, layman-friendly numeric system.
That's true of any "scripting" language types.
E.g. TypeScript
const x: number = 0n; // still is a bigint
IEEE floats should be a base on which more reasonable math semantics are built. Saying that Python should return NaN or inf instead of throwing an error is like saying that Python should return a random value from memory or segfault when reading an out-of-bounds list index.
And the sensible thing will depend on that language.
Not just division by zero.
math.sqrt(-1)
math.log(-2)
I agree that using both errors and float('nan') is odd.
Tbf, C mixes errors (for integers) and NaN (for floats).
NaN is a special type indicating one can't reason about it normal way.
It is an unknown or value that can't be represented.
When comparing, think of it like comparing two bags of unknown amount of apples.
One bag has NaN count of apples
Other bag has NaN count of apples
Do the two bags have equal number of apples?
I wish all languages used nulls the way SQL does.
If NaNs were meant to represent unknown quantities, then they would return false for all comparisons. But NaN != NaN is true. Assuming that two unknowns are always different is just as incorrect as assuming that they're always the same.
I'd also push back on the idea that this behavior makes sense. In my experience it's a consistent source of confusion for anyone learning to program. It's one of the clearest violations of the principle of least astonishment in programming language design.
As others have noted, it makes conscientious languages like Rust do all sorts of gymnastics to accommodate. It's a weird edge case, and imo a design mistake. "Special cases aren't special enough to break the rules."
Also, I think high level languages should avoid exposing programmers to NaN whenever possible. Python gets this right: 0/0 should be an error, not a NaN.
https://people.eecs.berkeley.edu/~wkahan/ieee754status/754st...
1. A value of a given type, either a literal or a value in memory, should represent a single concrete value, semantically (`5` represents the number five).
2. Classical logic (if A = B is true, then A != B is false).
I vote for violating #1, because we control those terms better. Is it weird that we invented a value that represents "unrepresentable" (as opposed to representing "no value")? Yes, but there are practical reasons for why we did it. It would be much more weird/surprising to violate classical logic.
We take for granted that (except for things like x86 extended precision registers) floating point basically works the same everywhere, which was the huge victory of IEEE 754. It easy to lose sight of that huge win, and to be ungrateful, when one's first introduction to IEEE 754 are details like NaN!=NaN.
1/0 is an error (SIGFPE). log(-5) is a value (NaN).
---
I suppose you could have this "no reflexive equality" sentinel, but it applied so randomly in languages as to be eternally violate the principle of least astonishment.
It's a sentinel value for an error. Once you have an error, doing math with the error code isn't sensible.
What should sorted([3, nan, 2, 4, 1]) give you in Python?
A) [1, 2, 3, 4, nan] is an good option
B) [nan, 1, 2, 3, 4] is an good option
C) An error is an good option
D) [3, nan, 1, 2, 4] is a silly, bad option. It's definitely not what you want, and it's quiet enough to slip by unnoticed. This is what you get when Nan != NaN
NaN == NaN is wrong. NaN != NaN is wrong, unintuitive, and breaks the rest of your code. If you want to signal that an operation is invalid, then throw an error. The silently nonsensical semantics of NaN are the worst possible response
And to boot…it’s only floating point numbers
In invalid math op with integers produces an error (or undefined behavior).
Definitely not some self unequal abomination.
>>> hash(float('nan'))
271103401
>>> hash(float('nan'))
271103657Yes and no:
`If an operation has a single NaN input and propagates it to the output, the result NaN's payload should be that of the input NaN (this is not always possible for binary formats when the signaling/quiet state is encoded). If there are multiple NaN inputs, the result NaN's payload should be from one of the input NaNs; the standard does not specify which.'
The IEEE 754 Specification requires that >,<,= evaluate to False.
Saying that two incomparable objects become comparable let alone gain equally would break things.
We use specific exponents and significands to represent NaNs but they have no numerical meaning.
I am actually surprised python got this correct, often NaN behavior is incorrect out of convenience and causes lots of issues and side effects.
nan isn't anything. It's an early attempt at None when no/few (common) languages had that concept.
That python allows nan as an index is just so many kinds of buggy.
> {} + {}
NaN
PS: Wait for it ... Watman! =8-)