wheel/
fraction.rs

1//! Wheel implementation for fractions.
2
3use crate::Wheel;
4
5use core::ops::{Add, Sub, Mul, Div, Neg, Rem};
6use core::fmt::Debug;
7
8pub trait Ring: Add<Output=Self> + Mul<Output=Self> + Neg<Output=Self> + Copy + Clone + PartialEq + Eq + PartialOrd + Debug {
9    const ZERO: Self;
10    const ONE: Self;
11
12    fn compare_pairs(a: (Self, Self), b: (Self, Self)) -> bool {
13        let a0_is_zero = a.0 == Self::ZERO;
14        let b0_is_zero = b.0 == Self::ZERO;
15        let a1_is_zero = a.1 == Self::ZERO;
16        let b1_is_zero = b.1 == Self::ZERO;
17        match (a0_is_zero, b0_is_zero, a1_is_zero, b1_is_zero) {
18            (true, true, false, false) => true,
19            (false, false, true, true) => true,
20            (true, true, true, true) => true,
21            (false, false, false, false) => a.0 * b.1 == a.1 * b.0,
22            _ => false,
23        }
24    }
25
26    fn normalize_pair(pair: (Self, Self)) -> (Self, Self) {
27        let first_is_zero = pair.0 == Self::ZERO;
28        let second_is_zero = pair.1 == Self::ZERO;
29        match (first_is_zero, second_is_zero) {
30            (true, true) => (Self::ZERO, Self::ZERO),
31            (true, false) => (Self::ZERO, Self::ONE),
32            (false, true) => (Self::ONE, Self::ZERO),
33            (false, false) => {
34                (pair.0, pair.1)
35            }
36        }
37    }
38}
39
40trait Gcd: Ring + Rem<Output=Self> + Ord {
41    fn abs(&self) -> Self {
42        if *self < Self::ZERO {
43            -*self
44        } else {
45            *self
46        }
47    }
48
49    fn gcd(a: Self, b: Self) -> Self {
50        let mut a = a.abs();
51        let mut b = b.abs();
52        while b != Self::ZERO {
53            let t = b;
54            b = a % b;
55            a = t;
56        }
57        if a == Self::ZERO {
58            Self::ONE
59        } else {
60            a
61        }
62    }
63}
64
65impl Gcd for i8 {}
66impl Gcd for i16 {}
67impl Gcd for i32 {}
68impl Gcd for i64 {}
69impl Gcd for i128 {}
70
71impl Ring for i8 {
72    const ZERO: i8 = 0;
73    const ONE: i8 = 1;
74
75    fn normalize_pair((a, b): (Self, Self)) -> (Self, Self) {
76        let gcd = Self::gcd(a, b);
77        (a / gcd, b / gcd)
78    }
79}
80
81impl Ring for i16 {
82    const ZERO: i16 = 0;
83    const ONE: i16 = 1;
84
85    fn normalize_pair((a, b): (Self, Self)) -> (Self, Self) {
86        let gcd = Self::gcd(a, b);
87        (a / gcd, b / gcd)
88    }
89}
90
91impl Ring for i32 {
92    const ZERO: i32 = 0;
93    const ONE: i32 = 1;
94
95    fn normalize_pair((a, b): (Self, Self)) -> (Self, Self) {
96        let gcd = Self::gcd(a, b);
97        (a / gcd, b / gcd)
98    }
99}
100
101impl Ring for i64 {
102    const ZERO: i64 = 0;
103    const ONE: i64 = 1;
104
105    fn normalize_pair((a, b): (Self, Self)) -> (Self, Self) {
106        let gcd = Self::gcd(a, b);
107        (a / gcd, b / gcd)
108    }
109}
110
111impl Ring for i128 {
112    const ZERO: i128 = 0;
113    const ONE: i128 = 1;
114
115    fn normalize_pair((a, b): (Self, Self)) -> (Self, Self) {
116        let gcd = Self::gcd(a, b);
117        (a / gcd, b / gcd)
118    }
119}
120
121#[derive(Debug, Clone, Copy)]
122pub struct FractionWheel<T: Ring> (T, T);
123
124impl<T: Ring> FractionWheel<T> {
125    pub const ZERO: Self = FractionWheel(T::ZERO, T::ONE);
126    pub const ONE: Self = FractionWheel(T::ONE, T::ONE);
127
128    /// There is only one infinity (no signed infinity)
129    pub const INFINITY: Self = FractionWheel(T::ONE, T::ZERO);
130
131    /// 0/0
132    pub const BOTTOM: Self = FractionWheel(T::ZERO, T::ZERO);
133
134    pub fn new(numerator: T, denominator: T) -> Self {
135        let value = FractionWheel(numerator, denominator);
136        value.normalize()
137    }
138
139    fn normalize(&self) -> Self {
140        let (numerator, denominator) = T::normalize_pair((self.0, self.1));
141        if denominator < T::ZERO {
142            FractionWheel(-numerator, -denominator)
143        } else if denominator == T::ZERO && numerator < T::ZERO {
144            FractionWheel(T::ONE, T::ZERO)
145        } else {
146            FractionWheel(numerator, denominator)
147        }
148    }
149
150    fn add(&self, other: Self) -> Self {
151        let a = self.0 * other.1;
152        let b = self.1 * other.0;
153        let c = self.1 * other.1;
154        FractionWheel(a + b, c).normalize()
155    }
156
157    fn neg(&self) -> Self {
158        FractionWheel(-self.0, self.1).normalize()
159    }
160
161    /// Defined as `self + other.neg()`.
162    /// `x - x` is not always zero.
163    fn sub(&self, other: Self) -> Self {
164        self.add(other.neg())
165    }
166
167    /// `0 * x` is not always zero.
168    fn mul(&self, other: Self) -> Self {
169        let a = self.0 * other.0;
170        let b = self.1 * other.1;
171        FractionWheel(a, b).normalize()
172    }
173
174    /// Always defined. Not the same as the multiplicative inverse.
175    pub fn inv(&self) -> Self {
176        FractionWheel(self.1, self.0).normalize()
177    }
178
179    /// Always defined as `self * other.inv()`.
180    /// `x / x` is not always one
181    fn div(&self, other: Self) -> Self {
182        self.mul(other.inv())
183    }
184
185    fn eq(&self, other: Self) -> bool {
186        T::compare_pairs((self.0, self.1), (other.0, other.1))
187    }
188}
189
190impl<T: Ring> Wheel for FractionWheel<T> {
191    const ZERO: Self = FractionWheel::ZERO;
192    const ONE: Self = FractionWheel::ONE;
193    const INFINITY: Self = FractionWheel::INFINITY;
194    const BOTTOM: Self = FractionWheel::BOTTOM;
195
196    fn add(&self, other: &Self) -> Self {
197        FractionWheel::add(self, *other)
198    }
199
200    fn neg(&self) -> Self {
201        FractionWheel::neg(self)
202    }
203
204    fn mul(&self, other: &Self) -> Self {
205        FractionWheel::mul(self, *other)
206    }
207
208    fn inv(&self) -> Self {
209        FractionWheel::inv(self)
210    }
211}
212
213
214// Conversion from integers
215
216impl From<i8> for FractionWheel<i8> {
217    fn from(value: i8) -> Self {
218        FractionWheel(value, 1)
219    }
220}
221
222impl From<i16> for FractionWheel<i16> {
223    fn from(value: i16) -> Self {
224        FractionWheel(value, 1)
225    }
226}
227
228impl From<i32> for FractionWheel<i32> {
229    fn from(value: i32) -> Self {
230        FractionWheel(value, 1)
231    }
232}
233
234impl From<i64> for FractionWheel<i64> {
235    fn from(value: i64) -> Self {
236        FractionWheel(value, 1)
237    }
238}
239
240impl From<i128> for FractionWheel<i128> {
241    fn from(value: i128) -> Self {
242        FractionWheel(value, 1)
243    }
244}
245
246
247// Arithmetic operators
248
249// Add
250
251impl<T: Ring> Add for FractionWheel<T> {
252    type Output = Self;
253
254    fn add(self, other: Self) -> Self {
255        Self::add(&self, other)
256    }
257}
258
259impl<T: Ring> Add<&FractionWheel<T>> for FractionWheel<T> {
260    type Output = FractionWheel<T>;
261
262    fn add(self, other: &Self) -> Self {
263        Self::add(&self, *other)
264    }
265}
266
267impl<T: Ring> Add<FractionWheel<T>> for &FractionWheel<T> {
268    type Output = FractionWheel<T>;
269
270    fn add(self, other: FractionWheel<T>) -> FractionWheel<T> {
271        FractionWheel::add(self, other)
272    }
273}
274
275impl<T: Ring> Add<&FractionWheel<T>> for &FractionWheel<T> {
276    type Output = FractionWheel<T>;
277
278    fn add(self, other: &FractionWheel<T>) -> FractionWheel<T> {
279        FractionWheel::add(self, *other)
280    }
281}
282
283// Sub
284
285impl<T: Ring> Sub for FractionWheel<T> {
286    type Output = Self;
287
288    fn sub(self, other: Self) -> Self {
289        Self::sub(&self, other)
290    }
291}
292
293impl<T: Ring> Sub<&FractionWheel<T>> for FractionWheel<T> {
294    type Output = FractionWheel<T>;
295
296    fn sub(self, other: &Self) -> Self {
297        Self::sub(&self, *other)
298    }
299}
300
301impl<T: Ring> Sub<FractionWheel<T>> for &FractionWheel<T> {
302    type Output = FractionWheel<T>;
303
304    fn sub(self, other: FractionWheel<T>) -> FractionWheel<T> {
305        FractionWheel::sub(self, other)
306    }
307}
308
309impl<T: Ring> Sub<&FractionWheel<T>> for &FractionWheel<T> {
310    type Output = FractionWheel<T>;
311
312    fn sub(self, other: &FractionWheel<T>) -> FractionWheel<T> {
313        FractionWheel::sub(self, *other)
314    }
315}
316
317// Mul
318
319impl<T: Ring> Mul for FractionWheel<T> {
320    type Output = Self;
321
322    fn mul(self, other: Self) -> Self {
323        Self::mul(&self, other)
324    }
325}
326
327impl<T: Ring> Mul<&FractionWheel<T>> for FractionWheel<T> {
328    type Output = FractionWheel<T>;
329
330    fn mul(self, other: &Self) -> Self {
331        Self::mul(&self, *other)
332    }
333}
334
335impl<T: Ring> Mul<FractionWheel<T>> for &FractionWheel<T> {
336    type Output = FractionWheel<T>;
337
338    fn mul(self, other: FractionWheel<T>) -> FractionWheel<T> {
339        FractionWheel::mul(self, other)
340    }
341}
342
343impl<T: Ring> Mul<&FractionWheel<T>> for &FractionWheel<T> {
344    type Output = FractionWheel<T>;
345
346    fn mul(self, other: &FractionWheel<T>) -> FractionWheel<T> {
347        FractionWheel::mul(self, *other)
348    }
349}
350
351// Div
352
353impl<T: Ring> Div for FractionWheel<T> {
354    type Output = Self;
355
356    fn div(self, other: Self) -> Self {
357        Self::div(&self, other)
358    }
359}
360
361impl<T: Ring> Div<&FractionWheel<T>> for FractionWheel<T> {
362    type Output = FractionWheel<T>;
363
364    fn div(self, other: &Self) -> Self {
365        Self::div(&self, *other)
366    }
367}
368
369impl<T: Ring> Div<FractionWheel<T>> for &FractionWheel<T> {
370    type Output = FractionWheel<T>;
371
372    fn div(self, other: FractionWheel<T>) -> FractionWheel<T> {
373        FractionWheel::div(self, other)
374    }
375}
376
377impl<T: Ring> Div<&FractionWheel<T>> for &FractionWheel<T> {
378    type Output = FractionWheel<T>;
379
380    fn div(self, other: &FractionWheel<T>) -> FractionWheel<T> {
381        FractionWheel::div(self, *other)
382    }
383}
384
385// Neg
386
387impl<T: Ring> Neg for FractionWheel<T> {
388    type Output = Self;
389
390    fn neg(self) -> Self {
391        Self::neg(&self)
392    }
393}
394
395impl<T: Ring> Neg for &FractionWheel<T> {
396    type Output = FractionWheel<T>;
397
398    fn neg(self) -> FractionWheel<T> {
399        FractionWheel::neg(self)
400    }
401}
402
403
404// Comparison operators
405
406impl<T: Ring> PartialEq for FractionWheel<T> {
407    fn eq(&self, other: &Self) -> bool {
408        self.eq(*other)
409    }
410}
411
412impl<T: Ring> Eq for FractionWheel<T> {}
413
414pub type FractionWheel8 = FractionWheel<i8>;
415pub type FractionWheel16 = FractionWheel<i16>;
416pub type FractionWheel32 = FractionWheel<i32>;
417pub type FractionWheel64 = FractionWheel<i64>;
418pub type FractionWheel128 = FractionWheel<i128>;
419
420pub use FractionWheel8 as qw8;
421pub use FractionWheel16 as qw16;
422pub use FractionWheel32 as qw32;
423pub use FractionWheel64 as qw64;
424pub use FractionWheel128 as qw128;
425
426
427#[cfg(test)]
428mod test {
429    use super::*;
430    type MyWheel = FractionWheel<i32>;
431
432    const ZERO: MyWheel = MyWheel::ZERO;
433    const ONE: MyWheel = MyWheel::ONE;
434    const INFINITY: MyWheel = MyWheel::INFINITY;
435    const BOTTOM: MyWheel = MyWheel::BOTTOM;
436
437    #[inline]
438    fn negative_one() -> MyWheel {
439        -ONE
440    }
441
442    #[inline]
443    fn three() -> MyWheel {
444        ONE + ONE + ONE
445    }
446
447    #[inline]
448    fn negative_two() -> MyWheel {
449        -ONE - ONE
450    }
451
452    #[inline]
453    fn three_halves() -> MyWheel {
454        MyWheel::new(3, 2)
455    }
456
457    #[inline]
458    fn negative_two_fifths() -> MyWheel {
459        MyWheel::new(-2, 5)
460    }
461
462    #[inline]
463    fn any_numbers() -> [MyWheel; 9] {
464        [
465            ZERO, ONE, INFINITY, BOTTOM,
466            negative_one(), three(), negative_two(),
467            three_halves(), negative_two_fifths()
468        ]
469    }
470
471    #[test]
472    fn inv_is_involution() {
473        for &x in any_numbers().iter() {
474            println!("{:?} == {:?}", x.inv().inv(), x);
475            assert_eq!(x.inv().inv(), x);
476        }
477    }
478
479    #[test]
480    fn inv_is_multicative() {
481        for &x in any_numbers().iter() {
482            for &y in any_numbers().iter() {
483                println!("{:?} == {:?}", (x * y).inv(), y.inv() * x.inv());
484                assert_eq!((x * y).inv(), y.inv() * x.inv());
485            }
486        }
487    }
488
489    /// `(x + y) * z + 0 * z = x * z + y * z`
490    #[test]
491    fn add_is_distributive() {
492        for &x in any_numbers().iter() {
493            for &y in any_numbers().iter() {
494                for &z in any_numbers().iter() {
495                    println!("{:?} == {:?}", (x + y) * z + ZERO * z, x * z + y * z);
496                    assert_eq!((x + y) * z + ZERO * z, x * z + y * z);
497                }
498            }
499        }
500    }
501
502    /// `(x + y * z) / y = x / y + z + 0 * y`
503    #[test]
504    fn add_is_distributive_div() {
505        for &x in any_numbers().iter() {
506            for &y in any_numbers().iter() {
507                for &z in any_numbers().iter() {
508                    println!("{:?} == {:?}", (x + y * z) / y, x / y + z + ZERO * y);
509                    assert_eq!((x + y * z) / y, x / y + z + ZERO * y);
510                }
511            }
512        }
513    }
514
515    /// `0 * 0 = 0`
516    #[test]
517    fn zero_times_zero() {
518        assert_eq!(ZERO * ZERO, ZERO);
519    }
520
521    /// `(x + 0 * y) * z = x * z + 0 * y`
522    #[test]
523    fn zero_times_y() {
524        for &x in any_numbers().iter() {
525            for &y in any_numbers().iter() {
526                for &z in any_numbers().iter() {
527                    println!("{:?} == {:?}", (x + ZERO * y) * z, x * z + ZERO * y);
528                    assert_eq!((x + ZERO * y) * z, x * z + ZERO * y);
529                }
530            }
531        }
532    }
533
534    /// `inv(x + 0 * y) = inv(x) + 0 * y`
535    #[test]
536    fn zero_times_y_inv() {
537        for &x in any_numbers().iter() {
538            for &y in any_numbers().iter() {
539                println!("{:?} == {:?}", (x + ZERO * y).inv(), x.inv() + ZERO * y);
540                assert_eq!((x + ZERO * y).inv(), x.inv() + ZERO * y);
541            }
542        }
543    }
544
545    /// `0 / 0 + x = 0 / 0`
546    #[test]
547    fn bottom_addition() {
548        for &x in any_numbers().iter() {
549            println!("{:?} == {:?}", BOTTOM + x, BOTTOM);
550            assert_eq!(BOTTOM + x, BOTTOM);
551        }
552    }
553
554    /// `0 * x + 0 * y = 0 * x * y`
555    #[test]
556    fn zero_times_x_plus_zero_times_y() {
557        for &x in any_numbers().iter() {
558            for &y in any_numbers().iter() {
559                println!("{:?} == {:?}", ZERO * x + ZERO * y, ZERO * x * y);
560                assert_eq!(ZERO * x + ZERO * y, ZERO * x * y);
561            }
562        }
563    }
564
565    /// `x / x = 1 + 0 * x / x`
566    #[test]
567    fn x_div_x() {
568        for &x in any_numbers().iter() {
569            println!("{:?} == {:?}", x / x, ONE + ZERO * x / x);
570            assert_eq!(x / x, ONE + ZERO * x / x);
571        }
572    }
573
574    /// `x - x = 0 * x * x`
575    #[test]
576    fn x_minus_x() {
577        for &x in any_numbers().iter() {
578            println!("{:?} == {:?}", x - x, ZERO * x * x);
579            assert_eq!(x - x, ZERO * x * x);
580        }
581    }
582}
wheel/fraction.rs

wheel/
fraction.rs
