relp_num/traits/
gcd.rs

1//! # The greatest common divisor of two numbers
2//!
3//! For a field the usual notion is empty: every non-zero element divides every other one, so any
4//! two values have every value as a common divisor. What is meant here is the divisor in the
5//! *integer* sense, which a field of fractions still has: the largest `g >= 0` for which both
6//! values are integer multiples of `g`. For two integers that is the ordinary greatest common
7//! divisor, and for two fractions in lowest terms it is
8//!
9//! ```text
10//! gcd(p1 / q1, p2 / q2) = gcd(p1, p2) / lcm(q1, q2)
11//! ```
12//!
13//! which is again in lowest terms: a prime dividing both `gcd(p1, p2)` and `lcm(q1, q2)` would
14//! divide one of the `p` and the `q` beside it, and those are coprime.
15//!
16//! # What it is for
17//!
18//! Dividing a set of fractions by their greatest common divisor leaves integers with no common
19//! factor. That is the canonical form of a linear constraint, and it is what an exact solver wants
20//! from scaling: a floating point solver scales a row for conditioning, which exact arithmetic
21//! gives for free, but the encoding of the numbers is a cost that does not go away, and clearing
22//! the denominators of a row is what removes it.
23
24/// The greatest common divisor of two numbers, in the integer sense.
25///
26/// The result is the largest `g >= 0` for which both values are integer multiples of `g`. It is
27/// zero exactly when both values are, and it is never negative: the sign of the operands says
28/// nothing about what divides them.
29///
30/// # What implements it
31///
32/// The rational types of this crate, and only those.
33///
34/// A row whose coefficients are integers wants the same operation, and the routines for it are
35/// already in the crate: a binary gcd per machine word, and one over the words of an arbitrary
36/// precision integer. Implementing this for the primitive integers and for
37/// [`Ubig`](crate::Ubig) is left for when a caller needs it, so a bound of `T: Gcd` means a
38/// rational today.
39pub trait Gcd: Sized {
40    /// The greatest common divisor of two numbers.
41    ///
42    /// `None` when the result is not representable in this type, which a fixed width type can
43    /// run into: the denominator of the result is the least common multiple of the two
44    /// denominators, and that is larger than either of them.
45    #[must_use]
46    fn gcd(&self, other: &Self) -> Option<Self>;
47}
relp_num/traits/gcd.rs

relp_num/traits/
gcd.rs
