DeepCausality Rational Numbers
Summary
Rational<T> is ℚ, the field of fractions of an integral domain. It is exact: 1/3 is the pair
(1, 3), never an approximation of it, so (1/3) * 3 is exactly 1 and 0.1 + 0.2 is exactly
0.3; a binary float manages neither.
use Rational;
let third = new;
assert_eq!;
assert_eq!; // reduced on construction
assert_eq!; // sign lives in the numerator
Canonical form
Every value is held in canonical form, and the fields are private to keep it so:
- The denominator is strictly positive. A sign lives in the numerator, never the denominator.
- Numerator and denominator are coprime.
- Zero is exactly
0/1. - The numerator is never
T::MIN.
The first three make the representation unique, and therefore make equality structural: two rationals are equal exactly when their components match, with no cross-multiplication.
The fourth concerns the machine, not ℚ. T::MIN has no representable negation (-i64::MIN is
2⁶³, one past the top of the range), so a numerator holding it would make Neg partial, and with
it subtraction and the AbelianGroup law a + (-a) = 0. Construction refuses that one value per
width instead. This costs Rational::<i64>::from_integer(i64::MIN) and buys a negation that cannot
fail. The represented set stays symmetric, so the field laws hold.
Ordering does not cross-multiply. a·d against c·b overflows for large scalars, and in
release wraps rather than aborting: i64::MAX/1 would compare as less than 1/2. Ord instead
descends the continued fraction (compare the floor quotients, then recurse on the remainders),
which is exact, total, and multiplies nothing.
Where it sits in the tower
Rational<T> is built over T: EuclideanDomain + SignedInt. The Euclidean domain supplies the
gcd that reduction to lowest terms needs. SignedInt supplies the rest of canonical form: a
total order, because Ord cannot answer "incomparable"; a sign, because invariant 1 moves it
into the numerator; and the end of the range, because T::MIN is the one value whose negation does
not fit, and the type must detect it. Every signed width qualifies: i8–i128, isize.
It is a Field and not a Real. Real is the
analytic axis (sqrt, exp, ln, sin), and ℚ is closed under none of them. ℚ is
arithmetically complete and analytically empty, the mirror of Dual, which is analytic without
being a field.
ℤ cannot take this step on its own. Integer / truncates rather than inverts, so the integers
stop at CommutativeRing; constructing ℚ supplies the missing inverses.
Overflow
T is fixed-width, so not every exact result is representable. The lists below state exactly
which operations can fail.
Total (cannot overflow on any input):
- Construction.
try_newreturns a correct value orNone, never a wrong one. It reduces by the gcd before moving a sign out of the denominator, sotry_new(i64::MIN, -2)is2⁶²rather than an overflow on an intermediate-i64::MINthat was never needed. - Comparison.
Orddescends the continued fraction and multiplies nothing. - Negation and
recip. Guaranteed by invariant 4.
Partial (can overflow under these conditions):
- Addition and subtraction. Each operand is split into an integer part and a proper fraction,
a/b = q + r/b, and the two are carried separately, so a sum with a large integer part does not overflow on the numerator:MAX/2 + MAX/2is exactlyMAX, where formingMAX + MAXwould not fit. It overflows whenlcm(b, d)does not fit, whenq₁ + q₂does not, or when the fractional numerator (bounded by2·lcm(b, d)) does not. Two coprime denominators near√T::MAXstill overflow, and so does any chain whose intermediate needs a numerator wider thanT, even where the final answer would fit. - Multiplication and division. Each numerator is cross-cancelled against the other's
denominator before either product is formed, so
2/3 · 3/2never builds6/6. What survives the cancelling must fit.
When an operation overflows, the behaviour is T's (a panic in debug builds, wrapping in
release), except where the type detects the failure itself; there it panics with a message naming
the cause. Choose T with headroom (i128 where denominators are unpredictable), and
prefer accumulating over a common denominator where the problem admits one.
Verification
The field laws, canonical-form invariants 1 and 2, and density are machine-checked in Lean 4 against
Mathlib's ℚ, with one Rust witness test per theorem. See
LEAN_NUM_RATIONAL.md.
Build configurations
| Configuration | Cargo features | Supported |
|---|---|---|
std, hosted |
default | ✓ |
no-std with a heap |
default-features = false, features = ["no-std"] |
✓ |
no-std on core alone, no heap |
default-features = false, features = ["no-std"] |
✓ |
The crate needs only core: with no-std it links into a program that defines no #[global_allocator].
CI builds every supported bare-metal configuration for thumbv7em-none-eabihf and links the core configuration without an allocator.
README_NO_STD.md describes the build configuration of every crate in the workspace.
Contribution
Contributions are welcomed especially related to documentation, example code, and fixes. If unsure where to start, just open an issue and ask.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in deep_causality by you, shall be licensed under the MIT licence, without any additional terms or conditions.
Licence
This project is licensed under the MIT license.
Security
For details about security, please read the security policy.