Figure out a good convention for normalizing rational numbers

[cuviper]

From @rust-highfive on September 28, 2014 22:43

Issue by thestinger Friday Apr 05, 2013 at 08:48 GMT

For earlier discussion, see https://github.com/rust-lang/rust/issues/5738

This issue was labelled with: A-libs in the Rust repository

---

The gmp Mpq type does does it after each operation, and then exposes a raw interface for doing a few operations without normalizing. It only guarantees that operations are valid when the type is normalized. This leads to the most predictable performance with big integers, and avoids avoidable overflows for fixed size ones.

This would probably involve making the fields priv and using scary names for raw manipulation methods.

Copied from original issue: rust-num/num#6

[maxbla]

I think normalizing after each operation is the way to go here. Also, is this a good definition of normalized?

• positive denominator
• fully reduced (p/q)
  • p and q have no factors in common, i.e. gcd(p,q) = 1
  • if p is zero, q must be 1

using scary names for raw manipulation methods.

This makes sense to me - you will generally get worse performance (bignums) or a higher chance of overflow (constant size numbers) from not reducing rationals during operations. What do we think is the use case for raw manipulation, and what might these raw manipulation methods look like?

[cuviper]

Yes, normalized Ratio should be reduced with a positive denominator. I think the status quo is that everything operation already normalizes this way, and new_raw is the only exception.

[maxbla]

Thumbing through the code, it indeed appears as if every ratio is reduced after an operation on it. If this is the desired behavior, and I think it should be, we should probably add tests specifically for it, and document somewhere that that's how this crate works.

[maxbla]

Now that #42 is merged, for any operation, if input Ratios are reduced and the result of an operation is in range for the underlying type, no overflow will occur during that operation. (possibly with an exception related to negating the min value in two's compliment). This is not true if we allow un-reduced Ratios. There isn't really a corresponding guarantee for the un-reduced way of dealing with this. I see only one advantage to being able to work with un-reduced ratios -- minimized overhead of reducing all over the place. But even this argument breaks down because in #42 I left in a bunch of otherwise unnecessary calls to reduce so that un-reduced inputs would produce reduced outputs. By not reducing, we trade one call to reduce when calling Ratio::new for one call to reduce after every operation.

In this change I'm suggesting, we would make new_raw() either unsafe or ~remove it entirely~ remove it from the public api (make it no longer pub). I think I would prefer to ~remove new_raw() entirely~ make it no longer pub. Before making a breaking API change like that, I would want to go around looking at crates that depend on this one to see if any use new_raw() and if they do, what they're using it for (because I can't think of a single good use-case).

Preliminary research: The most popular dependent crate (image-rs) uses Ratios sparingly. It only constructs them using new and from_integer. The second most downloaded crate, (wasmi) appears to use BigRationals to safely convert from float to int, returning an err Result if that conversion fails. That actually seems like misuse -- I think it should use rust-num to convert from f32/f64 to various integer types directly with ToPrimitive. Maybe I'm missing something though. The third most popular crate, (gstreamer) wraps Rational32 to implement its own Fraction type. None of these use new_raw().