rug/rational/
arith.rs

1// Copyright © 2016–2025 Trevor Spiteri
2
3// This program is free software: you can redistribute it and/or modify it under
4// the terms of the GNU Lesser General Public License as published by the Free
5// Software Foundation, either version 3 of the License, or (at your option) any
6// later version.
7//
8// This program is distributed in the hope that it will be useful, but WITHOUT
9// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
10// FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
11// details.
12//
13// You should have received a copy of the GNU Lesser General Public License and
14// a copy of the GNU General Public License along with this program. If not, see
15// <https://www.gnu.org/licenses/>.
16
17use crate::ext::xmpq;
18use crate::ext::xmpq::OptRational;
19use crate::integer::MiniInteger;
20use crate::integer::arith::AsLong;
21use crate::ops::{AddFrom, DivFrom, MulFrom, NegAssign, Pow, PowAssign, SubFrom};
22use crate::{Assign, Complete, Integer, Rational};
23use az::{CheckedAs, CheckedCast};
24use core::ffi::{c_long, c_ulong};
25use core::iter::{Product, Sum};
26use core::ops::{
27    Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Shl, ShlAssign, Shr, ShrAssign, Sub,
28    SubAssign,
29};
30
31arith_unary! {
32    Rational;
33    xmpq::neg;
34    Neg { neg }
35    NegAssign { neg_assign }
36    NegIncomplete
37}
38arith_binary_self! {
39    Rational;
40    xmpq::add;
41    Add { add }
42    AddAssign { add_assign }
43    AddFrom { add_from }
44    AddIncomplete;
45    rhs_has_more_alloc
46}
47arith_binary_self! {
48    Rational;
49    xmpq::sub;
50    Sub { sub }
51    SubAssign { sub_assign }
52    SubFrom { sub_from }
53    SubIncomplete;
54    rhs_has_more_alloc
55}
56arith_binary_self! {
57    Rational;
58    xmpq::mul;
59    Mul { mul }
60    MulAssign { mul_assign }
61    MulFrom { mul_from }
62    MulIncomplete;
63    rhs_has_more_alloc
64}
65arith_binary_self! {
66    Rational;
67    xmpq::div;
68    Div { div }
69    DivAssign { div_assign }
70    DivFrom { div_from }
71    DivIncomplete;
72    rhs_has_more_alloc
73}
74
75arith_commut! {
76    Rational;
77    xmpq::add_z;
78    Add { add }
79    AddAssign { add_assign }
80    AddFrom { add_from }
81    Integer;
82    AddIntegerIncomplete, AddOwnedIntegerIncomplete
83}
84arith_noncommut! {
85    Rational;
86    xmpq::sub_z;
87    xmpq::z_sub;
88    Sub { sub }
89    SubAssign { sub_assign }
90    SubFrom { sub_from }
91    Integer;
92    SubIntegerIncomplete, SubOwnedIntegerIncomplete;
93    SubFromIntegerIncomplete, SubFromOwnedIntegerIncomplete
94}
95arith_commut! {
96    Rational;
97    xmpq::mul_z;
98    Mul { mul }
99    MulAssign { mul_assign }
100    MulFrom { mul_from }
101    Integer;
102    MulIntegerIncomplete, MulOwnedIntegerIncomplete
103}
104arith_noncommut! {
105    Rational;
106    xmpq::div_z;
107    xmpq::z_div;
108    Div { div }
109    DivAssign { div_assign }
110    DivFrom { div_from }
111    Integer;
112    DivIntegerIncomplete, DivOwnedIntegerIncomplete;
113    DivFromIntegerIncomplete, DivFromOwnedIntegerIncomplete
114}
115
116arith_prim_commut! {
117    Rational;
118    PrimOps::add;
119    Add { add }
120    AddAssign { add_assign }
121    AddFrom { add_from }
122    i8, AddI8Incomplete;
123    i16, AddI16Incomplete;
124    i32, AddI32Incomplete;
125    i64, AddI64Incomplete;
126    i128, AddI128Incomplete;
127    isize, AddIsizeIncomplete;
128    u8, AddU8Incomplete;
129    u16, AddU16Incomplete;
130    u32, AddU32Incomplete;
131    u64, AddU64Incomplete;
132    u128, AddU128Incomplete;
133    usize, AddUsizeIncomplete;
134}
135arith_prim_noncommut! {
136    Rational;
137    PrimOps::sub, PrimOps::sub_from;
138    Sub { sub }
139    SubAssign { sub_assign }
140    SubFrom { sub_from }
141    i8, SubI8Incomplete, SubFromI8Incomplete;
142    i16, SubI16Incomplete, SubFromI16Incomplete;
143    i32, SubI32Incomplete, SubFromI32Incomplete;
144    i64, SubI64Incomplete, SubFromI64Incomplete;
145    i128, SubI128Incomplete, SubFromI128Incomplete;
146    isize, SubIsizeIncomplete, SubFromIsizeIncomplete;
147    u8, SubU8Incomplete, SubFromU8Incomplete;
148    u16, SubU16Incomplete, SubFromU16Incomplete;
149    u32, SubU32Incomplete, SubFromU32Incomplete;
150    u64, SubU64Incomplete, SubFromU64Incomplete;
151    u128, SubU128Incomplete, SubFromU128Incomplete;
152    usize, SubUsizeIncomplete, SubFromUsizeIncomplete;
153}
154arith_prim_commut! {
155    Rational;
156    PrimOps::mul;
157    Mul { mul }
158    MulAssign { mul_assign }
159    MulFrom { mul_from }
160    i8, MulI8Incomplete;
161    i16, MulI16Incomplete;
162    i32, MulI32Incomplete;
163    i64, MulI64Incomplete;
164    i128, MulI128Incomplete;
165    isize, MulIsizeIncomplete;
166    u8, MulU8Incomplete;
167    u16, MulU16Incomplete;
168    u32, MulU32Incomplete;
169    u64, MulU64Incomplete;
170    u128, MulU128Incomplete;
171    usize, MulUsizeIncomplete;
172}
173arith_prim_noncommut! {
174    Rational;
175    PrimOps::div, PrimOps::div_from;
176    Div { div }
177    DivAssign { div_assign }
178    DivFrom { div_from }
179    i8, DivI8Incomplete, DivFromI8Incomplete;
180    i16, DivI16Incomplete, DivFromI16Incomplete;
181    i32, DivI32Incomplete, DivFromI32Incomplete;
182    i64, DivI64Incomplete, DivFromI64Incomplete;
183    i128, DivI128Incomplete, DivFromI128Incomplete;
184    isize, DivIsizeIncomplete, DivFromIsizeIncomplete;
185    u8, DivU8Incomplete, DivFromU8Incomplete;
186    u16, DivU16Incomplete, DivFromU16Incomplete;
187    u32, DivU32Incomplete, DivFromU32Incomplete;
188    u64, DivU64Incomplete, DivFromU64Incomplete;
189    u128, DivU128Incomplete, DivFromU128Incomplete;
190    usize, DivUsizeIncomplete, DivFromUsizeIncomplete;
191}
192
193arith_prim! {
194    Rational;
195    xmpq::shl_i32;
196    Shl { shl }
197    ShlAssign { shl_assign }
198    i32, ShlI32Incomplete;
199}
200arith_prim! {
201    Rational;
202    xmpq::shr_i32;
203    Shr { shr }
204    ShrAssign { shr_assign }
205    i32, ShrI32Incomplete;
206}
207arith_prim! {
208    Rational;
209    xmpq::shl_u32;
210    Shl { shl }
211    ShlAssign { shl_assign }
212    u32, ShlU32Incomplete;
213}
214arith_prim! {
215    Rational;
216    xmpq::shr_u32;
217    Shr { shr }
218    ShrAssign { shr_assign }
219    u32, ShrU32Incomplete;
220}
221arith_prim! {
222    Rational;
223    xmpq::shl_isize;
224    Shl { shl }
225    ShlAssign { shl_assign }
226    isize, ShlIsizeIncomplete;
227}
228arith_prim! {
229    Rational;
230    xmpq::shr_isize;
231    Shr { shr }
232    ShrAssign { shr_assign }
233    isize, ShrIsizeIncomplete;
234}
235arith_prim! {
236    Rational;
237    xmpq::shl_usize;
238    Shl { shl }
239    ShlAssign { shl_assign }
240    usize, ShlUsizeIncomplete;
241}
242arith_prim! {
243    Rational;
244    xmpq::shr_usize;
245    Shr { shr }
246    ShrAssign { shr_assign }
247    usize, ShrUsizeIncomplete;
248}
249arith_prim! {
250    Rational;
251    xmpq::pow_i32;
252    Pow { pow }
253    PowAssign { pow_assign }
254    i32, PowI32Incomplete;
255}
256arith_prim! {
257    Rational;
258    xmpq::pow_u32;
259    Pow { pow }
260    PowAssign { pow_assign }
261    u32, PowU32Incomplete;
262}
263
264trait PrimOps<Long>: AsLong {
265    fn add<O: OptRational>(rop: &mut Rational, op1: O, op2: Self);
266    fn sub<O: OptRational>(rop: &mut Rational, op1: O, op2: Self);
267    fn sub_from<O: OptRational>(rop: &mut Rational, op1: Self, op2: O);
268    fn mul<O: OptRational>(rop: &mut Rational, op1: O, op2: Self);
269    fn div<O: OptRational>(rop: &mut Rational, op1: O, op2: Self);
270    fn div_from<O: OptRational>(rop: &mut Rational, op1: Self, op2: O);
271}
272
273macro_rules! forward {
274    (fn $fn:ident() -> $deleg_long:path, $deleg:path) => {
275        #[inline]
276        fn $fn<O: OptRational>(rop: &mut Rational, op1: O, op2: Self) {
277            if let Some(op2) = op2.checked_as() {
278                $deleg_long(rop, op1, op2);
279            } else {
280                let mut small: MiniInteger = op2.into();
281                $deleg(rop, op1, &*small.borrow_excl());
282            }
283        }
284    };
285}
286macro_rules! reverse {
287    (fn $fn:ident() -> $deleg_long:path, $deleg:path) => {
288        #[inline]
289        fn $fn<O: OptRational>(rop: &mut Rational, op1: Self, op2: O) {
290            if let Some(op1) = op1.checked_as() {
291                $deleg_long(rop, op1, op2);
292            } else {
293                let mut small: MiniInteger = op1.into();
294                $deleg(rop, &*small.borrow_excl(), op2);
295            }
296        }
297    };
298}
299
300impl<T> PrimOps<c_long> for T
301where
302    T: AsLong<Long = c_long> + CheckedCast<c_long> + Into<MiniInteger>,
303{
304    forward! { fn add() -> xmpq::add_si, xmpq::add_z }
305    forward! { fn sub() -> xmpq::sub_si, xmpq::sub_z }
306    reverse! { fn sub_from() -> xmpq::si_sub, xmpq::z_sub }
307    forward! { fn mul() -> xmpq::mul_si, xmpq::mul_z }
308    forward! { fn div() -> xmpq::div_si, xmpq::div_z }
309    reverse! { fn div_from() -> xmpq::si_div, xmpq::z_div }
310}
311
312impl<T> PrimOps<c_ulong> for T
313where
314    T: AsLong<Long = c_ulong> + CheckedCast<c_ulong> + Into<MiniInteger>,
315{
316    forward! { fn add() -> xmpq::add_ui, xmpq::add_z }
317    forward! { fn sub() -> xmpq::sub_ui, xmpq::sub_z }
318    reverse! { fn sub_from() -> xmpq::ui_sub, xmpq::z_sub }
319    forward! { fn mul() -> xmpq::mul_ui, xmpq::mul_z }
320    forward! { fn div() -> xmpq::div_ui, xmpq::div_z }
321    reverse! { fn div_from() -> xmpq::ui_div, xmpq::z_div }
322}
323
324impl<T> Sum<T> for Rational
325where
326    Rational: AddAssign<T>,
327{
328    fn sum<I>(iter: I) -> Rational
329    where
330        I: Iterator<Item = T>,
331    {
332        let mut ret = Rational::new();
333        for i in iter {
334            ret.add_assign(i);
335        }
336        ret
337    }
338}
339
340impl<T> Product<T> for Rational
341where
342    Rational: MulAssign<T>,
343{
344    fn product<I>(iter: I) -> Rational
345    where
346        I: Iterator<Item = T>,
347    {
348        let mut ret = Rational::from(1);
349        for i in iter {
350            ret.mul_assign(i);
351        }
352        ret
353    }
354}
355
356#[inline]
357fn rhs_has_more_alloc(lhs: &Rational, rhs: &Rational) -> bool {
358    // This can overflow:
359    //     lhs.num.alloc + lhs.den.alloc < rhs.num.alloc + rhs.den.alloc
360    // Since all alloc are non-negative signed integers (c_int), this
361    // cannot overflow:
362    //     lhs.num.alloc - rhs.den.alloc < rhs.num.alloc - lhs.den.alloc
363    lhs.numer().inner().alloc - rhs.denom().inner().alloc
364        < rhs.numer().inner().alloc - lhs.denom().inner().alloc
365}
366
367#[cfg(test)]
368mod tests {
369    use crate::ops::Pow;
370    use crate::rational::MiniRational;
371    use crate::{Integer, Rational};
372
373    macro_rules! test_ref_op {
374        ($first:expr, $second:expr) => {
375            assert_eq!(
376                Rational::from($first),
377                $second,
378                "({}) != ({})",
379                stringify!($first),
380                stringify!($second)
381            );
382        };
383    }
384
385    #[test]
386    fn check_ref_op() {
387        let lhs = Rational::from((-13, 27));
388        let rhs = Rational::from((15, 101));
389        let pu = 30_u32;
390        let pi = -15_i32;
391        test_ref_op!(-&lhs, -lhs.clone());
392        test_ref_op!(&lhs + &rhs, lhs.clone() + &rhs);
393        test_ref_op!(&lhs - &rhs, lhs.clone() - &rhs);
394        test_ref_op!(&lhs * &rhs, lhs.clone() * &rhs);
395        test_ref_op!(&lhs / &rhs, lhs.clone() / &rhs);
396
397        test_ref_op!(&lhs << pu, lhs.clone() << pu);
398        test_ref_op!(&lhs >> pu, lhs.clone() >> pu);
399        test_ref_op!((&lhs).pow(pu), lhs.clone().pow(pu));
400
401        test_ref_op!(&lhs << pi, lhs.clone() << pi);
402        test_ref_op!(&lhs >> pi, lhs.clone() >> pi);
403        test_ref_op!((&lhs).pow(pi), lhs.clone().pow(pi));
404    }
405
406    macro_rules! test_numer_denom {
407        ($first:expr, $second:expr) => {{
408            let a = $first;
409            let b = $second;
410            assert_eq!(
411                a.numer(),
412                b.numer(),
413                "({}).numer() != ({}).numer()",
414                stringify!($first),
415                stringify!($second)
416            );
417            assert_eq!(
418                a.denom(),
419                b.denom(),
420                "({}).denom() != ({}).denom()",
421                stringify!($first),
422                stringify!($second)
423            );
424        }};
425    }
426
427    #[test]
428    fn check_arith_int() {
429        let r = &Rational::from((-15, 128));
430        let zero = &Integer::new();
431        let minus_100 = &Integer::from(-100);
432
433        test_numer_denom!(r.clone() + zero, r + Rational::from(zero));
434        test_numer_denom!(r.clone() - zero, r - Rational::from(zero));
435        test_numer_denom!(r.clone() * zero, r * Rational::from(zero));
436        test_numer_denom!(r.clone() + minus_100, r + Rational::from(minus_100));
437        test_numer_denom!(r.clone() - minus_100, r - Rational::from(minus_100));
438        test_numer_denom!(r.clone() * minus_100, r * Rational::from(minus_100));
439        test_numer_denom!(r.clone() / minus_100, r / Rational::from(minus_100));
440
441        test_numer_denom!(zero + r.clone(), Rational::from(zero) + r);
442        test_numer_denom!(zero - r.clone(), Rational::from(zero) - r);
443        test_numer_denom!(zero * r.clone(), Rational::from(zero) * r);
444        test_numer_denom!(zero / r.clone(), Rational::from(zero) / r);
445        test_numer_denom!(minus_100 + r.clone(), Rational::from(minus_100) + r);
446        test_numer_denom!(minus_100 - r.clone(), Rational::from(minus_100) - r);
447        test_numer_denom!(minus_100 * r.clone(), Rational::from(minus_100) * r);
448        test_numer_denom!(minus_100 / r.clone(), Rational::from(minus_100) / r);
449    }
450
451    #[test]
452    fn check_neg_pow() {
453        let a = Rational::from((-12, 7));
454        let pow_pos = a.clone().pow(3i32);
455        assert_eq!(
456            pow_pos,
457            MiniRational::from(((-12i32).pow(3), 7i32.pow(3u32)))
458        );
459        let pow_neg = a.pow(-3i32);
460        assert_eq!(pow_neg, MiniRational::from(((-7i32).pow(3), 12i32.pow(3))));
461    }
462
463    macro_rules! check_u_s {
464        ($list:expr, $against:expr) => {
465            for &op in $list {
466                let rat_op = Rational::from(op);
467                for b in &$against {
468                    test_numer_denom!(b.clone() + op, b.clone() + &rat_op);
469                    test_numer_denom!(b.clone() - op, b.clone() - &rat_op);
470                    test_numer_denom!(b.clone() * op, b.clone() * &rat_op);
471                    if op != 0 {
472                        test_numer_denom!(b.clone() / op, b.clone() / &rat_op);
473                    }
474                    test_numer_denom!(op + b.clone(), rat_op.clone() + b);
475                    test_numer_denom!(op - b.clone(), rat_op.clone() - b);
476                    test_numer_denom!(op * b.clone(), rat_op.clone() * b);
477                    if !b.is_zero() {
478                        test_numer_denom!(op / b.clone(), rat_op.clone() / b);
479                    }
480                }
481            }
482        };
483    }
484
485    fn num_den<T>(s: &[T]) -> impl Iterator<Item = Rational> + '_
486    where
487        T: Copy + Eq + From<bool>,
488        Rational: From<(T, T)>,
489    {
490        let zero = T::from(false);
491        let one = T::from(true);
492        s.iter()
493            .map(move |&den| if den == zero { one } else { den })
494            .flat_map(move |den| s.iter().map(move |&num| Rational::from((num, den))))
495    }
496
497    #[test]
498    fn check_arith_u_s() {
499        use crate::tests::{I8, I16, I32, I64, I128, ISIZE, U8, U16, U32, U64, U128, USIZE};
500        let large = [(1, 3, 100), (-11, 5, 200), (33, 79, -150)];
501        let against = (large.iter().map(|&(n, d, s)| Rational::from((n, d)) << s))
502            .chain(num_den(I32))
503            .chain(num_den(U32))
504            .chain(num_den(I64))
505            .chain(num_den(U64))
506            .chain(num_den(I128))
507            .chain(num_den(U128))
508            .chain(num_den(ISIZE))
509            .chain(num_den(USIZE))
510            .collect::<Vec<Rational>>();
511
512        check_u_s!(I8, against);
513        check_u_s!(I16, against);
514        check_u_s!(I32, against);
515        check_u_s!(I64, against);
516        check_u_s!(I128, against);
517        check_u_s!(ISIZE, against);
518        check_u_s!(U8, against);
519        check_u_s!(U16, against);
520        check_u_s!(U32, against);
521        check_u_s!(U64, against);
522        check_u_s!(USIZE, against);
523    }
524
525    #[test]
526    fn check_shift_u_s() {
527        let pos = &(Rational::from((13, 7)) >> 100u32);
528        let neg = &(Rational::from((19, 101)) << 200u32);
529
530        assert_eq!(pos.clone() << 10u32, pos.clone() << 10i32);
531        assert_eq!(pos.clone() << 10u32, pos.clone() >> -10i32);
532        assert_eq!(pos.clone() >> 10u32, pos.clone() >> 10i32);
533        assert_eq!(pos.clone() >> 10u32, pos.clone() << -10i32);
534
535        assert_eq!(neg.clone() << 10u32, neg.clone() << 10i32);
536        assert_eq!(neg.clone() << 10u32, neg.clone() >> -10i32);
537        assert_eq!(neg.clone() >> 10u32, neg.clone() >> 10i32);
538        assert_eq!(neg.clone() >> 10u32, neg.clone() << -10i32);
539
540        assert_eq!(pos.clone() << 10u32, pos.clone() << 10usize);
541        assert_eq!(pos.clone() << 10u32, pos.clone() << 10isize);
542        assert_eq!(pos.clone() << 10u32, pos.clone() >> -10isize);
543        assert_eq!(pos.clone() >> 10u32, pos.clone() >> 10usize);
544        assert_eq!(pos.clone() >> 10u32, pos.clone() >> 10isize);
545        assert_eq!(pos.clone() >> 10u32, pos.clone() << -10isize);
546
547        assert_eq!(neg.clone() << 10u32, neg.clone() << 10usize);
548        assert_eq!(neg.clone() << 10u32, neg.clone() << 10isize);
549        assert_eq!(neg.clone() << 10u32, neg.clone() >> -10isize);
550        assert_eq!(neg.clone() >> 10u32, neg.clone() >> 10usize);
551        assert_eq!(neg.clone() >> 10u32, neg.clone() >> 10isize);
552        assert_eq!(neg.clone() >> 10u32, neg.clone() << -10isize);
553    }
554}
rug/rational/arith.rs

rug/rational/
arith.rs
