Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Wrapper newtypes for f32 and f64 implementing Ord #1249

Open
glaebhoerl opened this issue Aug 11, 2015 · 9 comments
Open

Wrapper newtypes for f32 and f64 implementing Ord #1249

glaebhoerl opened this issue Aug 11, 2015 · 9 comments
Labels

Comments

@glaebhoerl
Copy link
Contributor

@glaebhoerl glaebhoerl commented Aug 11, 2015

The Rust standard library (rightly, in my view) distinguishes PartialOrd (resp. -Eq) from Ord, primarily because according to their usual semantics, IEEE754 floating-point numbers do not have a total ordering, and therefore implement only the Partial traits. So far, so good. However, beyond this point, when faced with common tasks involving floating-point types which would in fact require an implementation of Eq or Ord - such as sorting, minimum/maximum, binary search, using them as keys in a data structure, etc. - users are currently, to a large degree, left to figure things out on their own, often leading to pain and frustration on their part.

We could do something about this, and make their lives easier, by providing wrapper newtypes (single-field structs) over the floating-point types which do in fact implement Eq and Ord, according to various policies. I can think of several different possibilities off the top of my head, any of which may be useful:

  • The IEEE standard allegedly does specify a total ordering which may be used, even if it is not the ordering which is implemented in hardware. A newtype could be used to select this alternative (total) ordering.
  • Another newtype could simply guarantee the absence of NaNs via a smart constructor, and implement Eq and Ord on this basis. (This is based on a suggestion by @shepmaster in an answer on StackOverflow.)
  • Another pair of newtypes could be used to specify that NaNs are to be treated as always less than, or always greater than any other number.
  • Another newtype could implement comparison simply based on the two numbers' bit-patterns as if they were u32 and u64. This ordering is likely to bear no relationship to the numerical one, but may be appropriate if one wishes to use floating-point types as keys in a data structure, provided that it doesn't really matter what the ordering (resp. equality) is, as long as it's total and fast.

If these were available, the options for bridging the gap between f{32,64} and Ord would be more apparent to users, and they could select the appropriate policy for dealing with NaNs based on their needs.

(Of course, such functionality would likely benefit from prototyping on crates.io beforehand, but I don't think it's unreasonable to consider it a candidate for eventual inclusion in std.)

@steveklabnik
Copy link
Member

@steveklabnik steveklabnik commented Aug 12, 2015

I swear we had some sort of issue like this somewhere, but cannot find it.

@glaebhoerl
Copy link
Contributor Author

@glaebhoerl glaebhoerl commented Aug 12, 2015

There's #675 and #852 which are related in some sense but not really the same.

@nixpulvis
Copy link

@nixpulvis nixpulvis commented Aug 26, 2015

Could this be the right place to implement a Number type?

@oberien
Copy link

@oberien oberien commented Aug 26, 2015

+5000 ;)

It's just such a common thing to compare floats, where NaN and Infinity are not a problem. But you still need to implement custom Wrappers which IMHO just sucks...

@shepmaster
Copy link
Member

@shepmaster shepmaster commented Aug 27, 2015

such functionality would likely benefit from prototyping on crates.io beforehand,

I think this is the key. There's nothing stopping someone from doing this right now and starting to gather feedback on how much it is used. That, in turn, could help suggest the importance of including it in the standard library.

@jfager
Copy link

@jfager jfager commented Dec 14, 2016

This ordering is likely to bear no relationship to the numerical one

In IEEE-754 the lexicographical ordering of the bytes is basically the ordering of the representable floating-point values, with only some minor bit-twiddling required. I have some old java code that does this, and there are a few other implementations online (for instance, https://www.working-software.com/cpp-float-comparisons). I have a good citation explaining the details on my home machine, will post when I get back.

@coriolinus
Copy link

@coriolinus coriolinus commented Nov 8, 2017

Is this issue solved by the noisy_float crate?

@jpetkau
Copy link

@jpetkau jpetkau commented Feb 26, 2018

@coriolinus noisy_float does something different: it prevents NaNs in debug builds via copious debug_asserts, and assumes (without checking) that NaNs do not occur in release builds so that it can implement Ord as a weak ordering, i.e. a total ordering with +0 == -0 comparing equal.

I guess that technically solves the issue as described in the title, but not some of the issues that have been folded into it (e.g. #1367), which want totally-ordered wrappers without overhead.

Another newtype could implement comparison simply based on the two numbers' bit-patterns as if they were u32 and u64. This ordering is likely to bear no relationship to the numerical one

As @jfager pointed out, floats are fortunately much more well-specified than that. Interpreting the bits as a signed integer gives the correct ordering for positive floats, and the reverse ordering for negative floats.

But you can do even better: IEEE754-2008 defined a totalorder predicate, which gives a strong ordering (i.e. equality under the ordering implies bitwise equality). An implementation can be as simple as:

fn f32_bits(a: f32) -> i32 { unsafe { std::mem::transmute(a) } }
fn cmp_total_order(a: f32, b: f32) -> std::cmp::Ordering {
  // ideally this would be replaced by a totalorder primitive when that's available
  let mut a = f32_bits(a);
  let mut b = f32_bits(b);
  if a < 0 { a ^= 0x7fffffff; }
  if b < 0 { b ^= 0x7fffffff; }
  a.cmp(&b)
}

There's an abstract argument why this should be added (better IEEE754-2008 conformance), but it's also much more useful in practice than a partial order. Partial orders violate basic equality axioms like a==a, !(a == b) iff (a != b), and !(a < b || a > b) iff a==b, so almost any generic code that gets one (e.g. a sort function) will do the wrong thing.

Rust fortunately makes it hard to do the wrong thing since floats don't implement Ord, so you can't easily hit yourself with that footgun, but it would also help to make it easier to do the right thing by having a total ordering available when you need it.

Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue May 27, 2020
… r=sfackler

Implement total_cmp for f32, f64

# Overview
* Implements method `total_cmp` on `f32` and `f64`. This method implements a float comparison that, unlike the standard `partial_cmp`, is total (defined on all values) in accordance to the IEEE 754 (rev 2008) §5.10 `totalOrder` predicate.
* The method has an API similar to `cmp`: `pub fn total_cmp(&self, other: &Self) -> crate::cmp::Ordering { ... }`.
* Implements tests.
* Has documentation.

# Justification for the API
* Total ordering for `f32` and `f64` has been discussed many time before:
  * https://internals.rust-lang.org/t/pre-pre-rfc-range-restricting-wrappers-for-floating-point-types/6701
  * rust-lang/rfcs#1249
  * rust-lang#53938
  * rust-lang#5585
* The lack of total ordering leads to frequent complaints, especially from people new to Rust.
  * This is an ergonomics issue that needs to be addressed.
  * However, the default behaviour of implementing only `PartialOrd` is intentional, as relaxing it might lead to correctness issues.
* Most earlier implementations and discussions have been focusing on a wrapper type that implements trait `Ord`. Such a wrapper type is, however not easy to add because of the large API surface added.
* As a minimal step that hopefully proves uncontroversial, we can implement a stand-alone method `total_cmp` on floating point types.
  * I expect adding such methods should be uncontroversial because...
    * Similar methods on `f32` and `f64` would be warranted even in case stdlib would provide a wrapper type that implements `Ord` some day.
    * It implements functionality that is standardised. (IEEE 754, 2008 rev. §5.10 Note, that the 2019 revision relaxes the ordering. The way we do ordering in this method conforms to the stricter 2008 standard.)
* With stdlib APIs such as `slice::sort_by` and `slice::binary_search_by` that allow users to provide a custom ordering criterion, providing additional helper methods is a minimal way of adding ordering functionality.
  * Not also does it allow easily using aforementioned APIs, it also provides an easy and well-tested primitive for the users and library authors to implement an `Ord`-implementing wrapper, if needed.
Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue May 27, 2020
… r=sfackler

Implement total_cmp for f32, f64

# Overview
* Implements method `total_cmp` on `f32` and `f64`. This method implements a float comparison that, unlike the standard `partial_cmp`, is total (defined on all values) in accordance to the IEEE 754 (rev 2008) §5.10 `totalOrder` predicate.
* The method has an API similar to `cmp`: `pub fn total_cmp(&self, other: &Self) -> crate::cmp::Ordering { ... }`.
* Implements tests.
* Has documentation.

# Justification for the API
* Total ordering for `f32` and `f64` has been discussed many time before:
  * https://internals.rust-lang.org/t/pre-pre-rfc-range-restricting-wrappers-for-floating-point-types/6701
  * rust-lang/rfcs#1249
  * rust-lang#53938
  * rust-lang#5585
* The lack of total ordering leads to frequent complaints, especially from people new to Rust.
  * This is an ergonomics issue that needs to be addressed.
  * However, the default behaviour of implementing only `PartialOrd` is intentional, as relaxing it might lead to correctness issues.
* Most earlier implementations and discussions have been focusing on a wrapper type that implements trait `Ord`. Such a wrapper type is, however not easy to add because of the large API surface added.
* As a minimal step that hopefully proves uncontroversial, we can implement a stand-alone method `total_cmp` on floating point types.
  * I expect adding such methods should be uncontroversial because...
    * Similar methods on `f32` and `f64` would be warranted even in case stdlib would provide a wrapper type that implements `Ord` some day.
    * It implements functionality that is standardised. (IEEE 754, 2008 rev. §5.10 Note, that the 2019 revision relaxes the ordering. The way we do ordering in this method conforms to the stricter 2008 standard.)
* With stdlib APIs such as `slice::sort_by` and `slice::binary_search_by` that allow users to provide a custom ordering criterion, providing additional helper methods is a minimal way of adding ordering functionality.
  * Not also does it allow easily using aforementioned APIs, it also provides an easy and well-tested primitive for the users and library authors to implement an `Ord`-implementing wrapper, if needed.
Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue May 29, 2020
… r=sfackler

Implement total_cmp for f32, f64

# Overview
* Implements method `total_cmp` on `f32` and `f64`. This method implements a float comparison that, unlike the standard `partial_cmp`, is total (defined on all values) in accordance to the IEEE 754 (rev 2008) §5.10 `totalOrder` predicate.
* The method has an API similar to `cmp`: `pub fn total_cmp(&self, other: &Self) -> crate::cmp::Ordering { ... }`.
* Implements tests.
* Has documentation.

# Justification for the API
* Total ordering for `f32` and `f64` has been discussed many time before:
  * https://internals.rust-lang.org/t/pre-pre-rfc-range-restricting-wrappers-for-floating-point-types/6701
  * rust-lang/rfcs#1249
  * rust-lang#53938
  * rust-lang#5585
* The lack of total ordering leads to frequent complaints, especially from people new to Rust.
  * This is an ergonomics issue that needs to be addressed.
  * However, the default behaviour of implementing only `PartialOrd` is intentional, as relaxing it might lead to correctness issues.
* Most earlier implementations and discussions have been focusing on a wrapper type that implements trait `Ord`. Such a wrapper type is, however not easy to add because of the large API surface added.
* As a minimal step that hopefully proves uncontroversial, we can implement a stand-alone method `total_cmp` on floating point types.
  * I expect adding such methods should be uncontroversial because...
    * Similar methods on `f32` and `f64` would be warranted even in case stdlib would provide a wrapper type that implements `Ord` some day.
    * It implements functionality that is standardised. (IEEE 754, 2008 rev. §5.10 Note, that the 2019 revision relaxes the ordering. The way we do ordering in this method conforms to the stricter 2008 standard.)
* With stdlib APIs such as `slice::sort_by` and `slice::binary_search_by` that allow users to provide a custom ordering criterion, providing additional helper methods is a minimal way of adding ordering functionality.
  * Not also does it allow easily using aforementioned APIs, it also provides an easy and well-tested primitive for the users and library authors to implement an `Ord`-implementing wrapper, if needed.
Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue May 29, 2020
… r=sfackler

Implement total_cmp for f32, f64

# Overview
* Implements method `total_cmp` on `f32` and `f64`. This method implements a float comparison that, unlike the standard `partial_cmp`, is total (defined on all values) in accordance to the IEEE 754 (rev 2008) §5.10 `totalOrder` predicate.
* The method has an API similar to `cmp`: `pub fn total_cmp(&self, other: &Self) -> crate::cmp::Ordering { ... }`.
* Implements tests.
* Has documentation.

# Justification for the API
* Total ordering for `f32` and `f64` has been discussed many time before:
  * https://internals.rust-lang.org/t/pre-pre-rfc-range-restricting-wrappers-for-floating-point-types/6701
  * rust-lang/rfcs#1249
  * rust-lang#53938
  * rust-lang#5585
* The lack of total ordering leads to frequent complaints, especially from people new to Rust.
  * This is an ergonomics issue that needs to be addressed.
  * However, the default behaviour of implementing only `PartialOrd` is intentional, as relaxing it might lead to correctness issues.
* Most earlier implementations and discussions have been focusing on a wrapper type that implements trait `Ord`. Such a wrapper type is, however not easy to add because of the large API surface added.
* As a minimal step that hopefully proves uncontroversial, we can implement a stand-alone method `total_cmp` on floating point types.
  * I expect adding such methods should be uncontroversial because...
    * Similar methods on `f32` and `f64` would be warranted even in case stdlib would provide a wrapper type that implements `Ord` some day.
    * It implements functionality that is standardised. (IEEE 754, 2008 rev. §5.10 Note, that the 2019 revision relaxes the ordering. The way we do ordering in this method conforms to the stricter 2008 standard.)
* With stdlib APIs such as `slice::sort_by` and `slice::binary_search_by` that allow users to provide a custom ordering criterion, providing additional helper methods is a minimal way of adding ordering functionality.
  * Not also does it allow easily using aforementioned APIs, it also provides an easy and well-tested primitive for the users and library authors to implement an `Ord`-implementing wrapper, if needed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
9 participants