1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
/*
* SPDX-License-Identifier: MIT
* Copyright (c) 2023 - 2026. The DeepCausality Authors and Contributors. All Rights Reserved.
*/
use crate::;
use Div;
/// The scalar a [`Rational`] is built over.
///
/// Mathematically, the field of fractions exists over any integral domain. This crate builds it
/// over the **ordered, fixed-width signed integers**, which is narrower, and deliberately so:
///
/// - [`EuclideanDomain`] — reducing a fraction to lowest terms needs a `gcd`, and the Euclidean
/// algorithm is what provides one.
/// - [`SignedInt`] — canonical form needs three things that a bare `PartialOrd` cannot supply.
/// It needs a **total** order, because [`Ord`] for a `Rational` has no way to answer
/// "incomparable"; it needs a **sign**, because invariant 1 below moves that sign into the
/// numerator; and it needs to know where the range **ends**, because `T::MIN` is the one value
/// whose negation does not fit, and the difference between an honest type and a wrong one is
/// whether that case is detected (`checked_neg`) or silently wrapped.
/// - `Div` — to divide numerator and denominator through by their gcd.
///
/// An earlier form of this bound asked only for `EuclideanDomain + Neg + PartialOrd`. That was
/// too weak to be honest: a Euclidean domain with incomparable elements — the Gaussian integers
/// `ℤ[i]`, say — would have satisfied it, and for such a type "the denominator is positive" is
/// not an invariant but a category error, while `Ord::cmp` would have had to invent an answer.
///
/// Every signed integer width satisfies the bound: `i8`, `i16`, `i32`, `i64`, `i128`, `isize`.
/// The unsigned types do not, and cannot: ℕ is not a ring, so it is not a `EuclideanDomain`, and
/// a field of fractions over it would have nothing to negate.
/// A rational number `n/d` — an element of the field of fractions of `T`.
///
/// `Rational<T>` is **exact**. Unlike a floating-point value, `1/3` is represented as the pair
/// `(1, 3)` and never as an approximation of it, so `(1/3) * 3` is exactly `1`.
///
/// # Invariants
///
/// Every `Rational` is kept in canonical form, which is why the fields are private:
///
/// 1. The denominator is strictly positive. A sign lives in the numerator, never the denominator.
/// 2. The numerator and denominator are coprime — `gcd(n, d) == 1`.
/// 3. Zero is exactly `0/1`.
/// 4. The numerator is never `T::MIN`.
///
/// Canonical form makes equality structural: two `Rational`s are equal exactly when their
/// components match, so `PartialEq` needs no cross-multiplication.
///
/// Invariant 4 is the one that is about the machine rather than about ℚ. `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`](core::ops::Neg) partial, and with it subtraction, and with it
/// the `AbelianGroup` marker this type claims. Excluding it at construction costs one value per
/// width and buys a negation that cannot fail. The excluded set is symmetric, so the field laws
/// are untouched: `Rational<i64>` represents every `p/q` with `|p| ≤ i64::MAX` and
/// `0 < q ≤ i64::MAX`, and that set is closed under negation and reciprocal.
///
/// # Where this sits in the tower
///
/// ℚ is a [`Field`](deep_causality_algebra::Field): every non-zero rational has a multiplicative
/// inverse, `(n/d)⁻¹ = d/n`. It is **not** a [`Real`](deep_causality_algebra::Real), and that is
/// not an omission. `Real` is the analytic axis — `sqrt`, `exp`, `ln`, `sin` — and ℚ is not
/// closed under any of them: `sqrt(2)` is irrational, which is the oldest theorem about this
/// gap. ℚ is arithmetically complete and analytically empty.
///
/// This mirrors ℤ, which reaches [`CommutativeRing`](deep_causality_algebra::CommutativeRing) and
/// stops short of `Field` for the opposite reason — ℤ has no inverses. Passing from ℤ to ℚ buys
/// division and gives up nothing; passing from ℚ to ℝ buys limits and gives up exactness.
///
/// # Overflow
///
/// `T` is fixed-width, so not every exact result of an operation on representable values is
/// itself representable. That much is inherent to fixed-width rational arithmetic. What is not
/// inherent is *which* operations can fail, and this section is precise about it rather than
/// blanket.
///
/// **Total — cannot overflow, on any input:**
///
/// - **Construction.** [`try_new`](Self::try_new) returns `None` for every pair with no canonical
/// form and a correct value for every pair that has one. It reduces by the gcd *before* moving
/// a sign out of the denominator, so `try_new(i64::MIN, -2)` is `2⁶²` rather than an overflow
/// on an intermediate `-i64::MIN` that was never needed.
/// - **Comparison.** [`Ord`] compares by continued fraction — floor quotients, then the
/// remainders — and multiplies nothing. `Rational::new(i64::MAX, 1)` and `Rational::new(1, 2)`
/// compare correctly.
/// - **Negation, and therefore subtraction's use of it, and [`recip`](Self::recip).** Guaranteed
/// by invariant 4.
///
/// **Partial — can overflow, and here is exactly when:**
///
/// - **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. The consequence is that a sum
/// whose *integer* part is large no longer overflows on the numerator: `MAX/2 + MAX/2` is
/// exactly `MAX`, where forming `MAX + MAX` would not fit. It overflows when the least common
/// denominator `lcm(b, d)` does not fit, when `q₁ + q₂` does not fit, or when the fractional
/// numerators `r₁·(d/g) + r₂·(b/g)` — bounded by `2·lcm(b, d)` — do not. Two coprime
/// denominators near `√T::MAX` will therefore still overflow, and no arrangement of the
/// arithmetic can prevent it: the answer itself is not representable.
/// - **Multiplication and division.** Each numerator is cross-cancelled against the *other*
/// denominator before either product is formed, so `2/3 · 3/2` never builds `6/6`. What is left
/// after cancelling must fit: the product of two coprime numerators, and of two coprime
/// denominators.
/// - **Anything whose exact answer needs a numerator of `T::MIN`,** which invariant 4 excludes.
///
/// When an operation does overflow, the behaviour is `T`'s — a panic in debug builds, wrapping in
/// release — except where the type can see the failure itself, which is when it panics with a
/// message naming the cause. Choose `T` with headroom (`i128` where the denominators are
/// unpredictable), and prefer accumulating over a common denominator where the problem admits
/// one.
///
/// # Examples
///
/// ```
/// use deep_causality_num_rational::Rational;
///
/// let third = Rational::new(1_i64, 3);
/// let sum = third + third + third;
/// assert_eq!(sum, Rational::from_integer(1)); // exact, unlike 0.1 + 0.2 in binary floats
///
/// // Fractions are reduced on construction.
/// assert_eq!(Rational::new(6_i64, 8), Rational::new(3, 4));
///
/// // A sign never survives in the denominator.
/// let r = Rational::new(1_i64, -2);
/// assert_eq!(*r.numer(), -1);
/// assert_eq!(*r.denom(), 2);
///
/// // Reduction happens before the sign moves, so this is +2⁶² and not an overflow.
/// assert_eq!(Rational::try_new(i64::MIN, -2), Rational::try_new(4_611_686_018_427_387_904, 1));
/// ```