smart_big_rational/
lib.rs

1// Copyright 2023-2026 The SmartBigRational Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! This crate implements a big rational type that is optimized for addition,
16//! subtraction and multiplication.
17//!
18//! Unlike the vanilla [`BigRational`] type, the [`SmartBigRational`] doesn't
19//! perform a full GCD reduction upon addition and subtraction, and doesn't
20//! perform any reduction upon multiplication.
21
22#![forbid(missing_docs, unsafe_code)]
23
24mod denom;
25mod denom_array;
26mod denom_sparse;
27mod primes;
28mod util;
29
30pub use denom::{Denom, DenomRef};
31pub use denom_array::{DenomArray, DenomArray24};
32pub use denom_sparse::{DenomSparse6542, DenomSparseU16};
33use num_bigint::{BigInt, BigUint, Sign};
34use num_rational::BigRational;
35use num_traits::{One, Pow, Zero};
36use std::cmp::Ordering;
37use std::fmt::Display;
38use std::iter::{Product, Sum};
39use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
40
41/// A big rational type optimized for addition, subtraction and multiplication.
42///
43/// This is achieved by representing the denominator with a [`Denom`] type, and
44/// performing only partial GCD reductions during arithmetic operations.
45#[derive(Clone, Debug)]
46pub struct SmartBigRational<D> {
47    num: BigInt,
48    denom: D,
49}
50
51impl<D: Denom> SmartBigRational<D> {
52    /// Constant value of 0.
53    pub const ZERO: Self = Self {
54        num: BigInt::ZERO,
55        denom: D::ONE,
56    };
57
58    /// Constant value of 1.
59    pub const ONE: Self = Self {
60        num: BigInt::ONE,
61        denom: D::ONE,
62    };
63
64    /// Creates a new rational number by dividing the given numerator by the
65    /// denominator.
66    ///
67    /// ```
68    /// # use num_bigint::BigInt;
69    /// # use num_rational::BigRational;
70    /// # use smart_big_rational::{DenomArray24, SmartBigRational};
71    /// let x = SmartBigRational::<DenomArray24>::ratio(2, 3u32);
72    ///
73    /// assert_eq!(
74    ///     BigRational::from(x),
75    ///     BigRational::new(BigInt::from(2), BigInt::from(3))
76    /// );
77    /// ```
78    pub fn ratio(num: impl Into<BigInt>, denom: impl Into<D>) -> Self {
79        Self {
80            num: num.into(),
81            denom: denom.into(),
82        }
83    }
84
85    /// Returns the current numerator and denominator as is, without reduction.
86    pub fn into_raw(self) -> (BigInt, D) {
87        (self.num, self.denom)
88    }
89
90    /// Returns the current numerator as is, without reduction.
91    pub fn numer(&self) -> &BigInt {
92        &self.num
93    }
94
95    /// Returns the current denominator as is, without reduction.
96    pub fn denom(&self) -> &D {
97        &self.denom
98    }
99
100    /// Converts this value to a [`BigRational`].
101    pub fn into_big_rational(self) -> BigRational {
102        self.into()
103    }
104
105    /// Converts this value to a [`BigRational`].
106    pub fn to_big_rational(&self) -> BigRational {
107        self.into()
108    }
109
110    /// Reduces the current value.
111    ///
112    /// After reduction, the GCD of the numerator and denominator is one.
113    ///
114    /// This is a slow operation, but may be beneficial in some cases (for
115    /// example if this value is then used many times) as the representation
116    /// becomes smaller if the numerator and denominator had many common
117    /// factors. This may however be detrimental if you then add/subtract values
118    /// that contain the same common factors that were reduced. Therefore,
119    /// there is no rule of thumb: benchmark your concrete code to see if
120    /// this brings any performance improvement.
121    pub fn reduce(&mut self) {
122        self.denom.gcd_reduce(&mut self.num);
123    }
124}
125
126impl<D: Denom> From<BigRational> for SmartBigRational<D> {
127    fn from(value: BigRational) -> Self {
128        let (num, denom) = value.into_raw();
129        let (sign, denom) = denom.into_parts();
130        assert_eq!(sign, Sign::Plus);
131        Self {
132            num,
133            denom: denom.into(),
134        }
135    }
136}
137
138impl<D: Denom> From<&BigRational> for SmartBigRational<D> {
139    fn from(value: &BigRational) -> Self {
140        let denom = value.denom();
141        assert_eq!(denom.sign(), Sign::Plus);
142        Self {
143            num: value.numer().clone(),
144            denom: denom.magnitude().into(),
145        }
146    }
147}
148
149impl<D: Denom> From<BigInt> for SmartBigRational<D> {
150    fn from(value: BigInt) -> Self {
151        Self {
152            num: value,
153            denom: D::ONE,
154        }
155    }
156}
157
158impl<D: Denom> From<SmartBigRational<D>> for BigRational {
159    fn from(value: SmartBigRational<D>) -> BigRational {
160        BigRational::new(value.num, value.denom.to_biguint().into())
161    }
162}
163
164impl<D: Denom> From<&SmartBigRational<D>> for BigRational {
165    fn from(value: &SmartBigRational<D>) -> BigRational {
166        BigRational::new(value.num.clone(), value.denom.to_biguint().into())
167    }
168}
169
170impl<D: Denom> PartialEq for SmartBigRational<D> {
171    fn eq(&self, rhs: &Self) -> bool {
172        self.num.sign() == rhs.num.sign()
173            && self.num.magnitude() * rhs.denom.to_biguint()
174                == rhs.num.magnitude() * self.denom.to_biguint()
175    }
176}
177
178impl<D: Denom> Eq for SmartBigRational<D> {}
179
180impl<D: Denom> PartialOrd for SmartBigRational<D> {
181    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
182        Some(self.cmp(rhs))
183    }
184}
185
186impl<D: Denom> Ord for SmartBigRational<D> {
187    fn cmp(&self, rhs: &Self) -> Ordering {
188        match (self.num.sign(), rhs.num.sign()) {
189            (Sign::Plus, Sign::Plus) => (self.num.magnitude() * rhs.denom.to_biguint())
190                .cmp(&(rhs.num.magnitude() * self.denom.to_biguint())),
191            (Sign::Plus, Sign::NoSign) => Ordering::Greater,
192            (Sign::Plus, Sign::Minus) => Ordering::Greater,
193            (Sign::NoSign, Sign::Plus) => Ordering::Less,
194            (Sign::NoSign, Sign::NoSign) => Ordering::Equal,
195            (Sign::NoSign, Sign::Minus) => Ordering::Greater,
196            (Sign::Minus, Sign::Plus) => Ordering::Less,
197            (Sign::Minus, Sign::NoSign) => Ordering::Less,
198            (Sign::Minus, Sign::Minus) => (rhs.num.magnitude() * self.denom.to_biguint())
199                .cmp(&(self.num.magnitude() * rhs.denom.to_biguint())),
200        }
201    }
202}
203
204impl<D: Denom> Display for SmartBigRational<D> {
205    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
206        Display::fmt(&self.to_big_rational(), f)
207    }
208}
209
210impl<D: Denom> Zero for SmartBigRational<D> {
211    fn zero() -> Self {
212        Self::ZERO
213    }
214
215    fn is_zero(&self) -> bool {
216        self.num.is_zero()
217    }
218}
219
220impl<D: Denom> One for SmartBigRational<D> {
221    fn one() -> Self {
222        Self::ONE
223    }
224}
225
226impl<D: Denom> Neg for SmartBigRational<D> {
227    type Output = Self;
228
229    fn neg(self) -> Self {
230        Self {
231            num: -self.num,
232            denom: self.denom,
233        }
234    }
235}
236
237impl<D: Denom> Neg for &SmartBigRational<D> {
238    type Output = SmartBigRational<D>;
239
240    fn neg(self) -> SmartBigRational<D> {
241        SmartBigRational {
242            num: -&self.num,
243            denom: self.denom.clone(),
244        }
245    }
246}
247
248impl<D: Denom> Pow<u32> for SmartBigRational<D> {
249    type Output = Self;
250
251    fn pow(self, rhs: u32) -> Self {
252        Self {
253            num: self.num.pow(rhs),
254            denom: self.denom.pow(rhs),
255        }
256    }
257}
258
259impl<D: Denom> Pow<u32> for &SmartBigRational<D>
260where
261    for<'a> &'a D: DenomRef<D>,
262{
263    type Output = SmartBigRational<D>;
264
265    fn pow(self, rhs: u32) -> SmartBigRational<D> {
266        SmartBigRational {
267            num: Pow::pow(&self.num, rhs),
268            denom: Pow::pow(&self.denom, rhs),
269        }
270    }
271}
272
273impl<D: Denom> Add for SmartBigRational<D> {
274    type Output = Self;
275
276    fn add(mut self, mut rhs: Self) -> Self {
277        let denom = D::normalize(&mut self.num, &mut rhs.num, &self.denom, &rhs.denom);
278        Self {
279            num: self.num + rhs.num,
280            denom,
281        }
282    }
283}
284
285impl<D: Denom> Add<&Self> for SmartBigRational<D> {
286    type Output = Self;
287
288    fn add(mut self, rhs: &Self) -> Self {
289        let mut rhs_num = rhs.num.clone();
290        let denom = D::normalize(&mut self.num, &mut rhs_num, &self.denom, &rhs.denom);
291        Self {
292            num: self.num + rhs_num,
293            denom,
294        }
295    }
296}
297
298impl<D: Denom> Add for &SmartBigRational<D> {
299    type Output = SmartBigRational<D>;
300
301    fn add(self, rhs: Self) -> SmartBigRational<D> {
302        let mut num = self.num.clone();
303        let mut rhs_num = rhs.num.clone();
304        let denom = D::normalize(&mut num, &mut rhs_num, &self.denom, &rhs.denom);
305        SmartBigRational {
306            num: num + rhs_num,
307            denom,
308        }
309    }
310}
311
312impl<D: Denom> Add<SmartBigRational<D>> for &SmartBigRational<D> {
313    type Output = SmartBigRational<D>;
314
315    fn add(self, mut rhs: SmartBigRational<D>) -> SmartBigRational<D> {
316        let mut num = self.num.clone();
317        let denom = D::normalize(&mut num, &mut rhs.num, &self.denom, &rhs.denom);
318        SmartBigRational {
319            num: num + rhs.num,
320            denom,
321        }
322    }
323}
324
325impl<D: Denom> AddAssign for SmartBigRational<D> {
326    fn add_assign(&mut self, mut rhs: Self) {
327        self.denom = D::normalize(&mut self.num, &mut rhs.num, &self.denom, &rhs.denom);
328        self.num += rhs.num;
329    }
330}
331
332impl<D: Denom> AddAssign<&Self> for SmartBigRational<D> {
333    fn add_assign(&mut self, rhs: &Self) {
334        let mut rhs_num = rhs.num.clone();
335        self.denom = D::normalize(&mut self.num, &mut rhs_num, &self.denom, &rhs.denom);
336        self.num += rhs_num;
337    }
338}
339
340impl<D: Denom> Add<BigInt> for SmartBigRational<D>
341where
342    BigInt: for<'a> MulAssign<&'a D>,
343{
344    type Output = Self;
345
346    fn add(self, mut rhs: BigInt) -> Self {
347        rhs *= &self.denom;
348        Self {
349            num: self.num + rhs,
350            denom: self.denom,
351        }
352    }
353}
354
355impl<D: Denom> Add<&BigInt> for SmartBigRational<D>
356where
357    for<'a> &'a D: DenomRef<D>,
358{
359    type Output = Self;
360
361    fn add(self, rhs: &BigInt) -> Self {
362        Self {
363            num: self.num + &self.denom * rhs,
364            denom: self.denom,
365        }
366    }
367}
368
369impl<D: Denom> Add<BigInt> for &SmartBigRational<D>
370where
371    BigInt: for<'a> MulAssign<&'a D>,
372{
373    type Output = SmartBigRational<D>;
374
375    fn add(self, mut rhs: BigInt) -> SmartBigRational<D> {
376        rhs *= &self.denom;
377        SmartBigRational {
378            num: &self.num + rhs,
379            denom: self.denom.clone(),
380        }
381    }
382}
383
384impl<D: Denom> Add<&BigInt> for &SmartBigRational<D>
385where
386    for<'a> &'a D: DenomRef<D>,
387{
388    type Output = SmartBigRational<D>;
389
390    fn add(self, rhs: &BigInt) -> SmartBigRational<D> {
391        SmartBigRational {
392            num: &self.num + &self.denom * rhs,
393            denom: self.denom.clone(),
394        }
395    }
396}
397
398impl<D: Denom> AddAssign<BigInt> for SmartBigRational<D>
399where
400    BigInt: for<'a> MulAssign<&'a D>,
401{
402    fn add_assign(&mut self, mut rhs: BigInt) {
403        rhs *= &self.denom;
404        self.num += rhs;
405    }
406}
407
408impl<D: Denom> AddAssign<&BigInt> for SmartBigRational<D>
409where
410    for<'a> &'a D: DenomRef<D>,
411{
412    fn add_assign(&mut self, rhs: &BigInt) {
413        self.num += &self.denom * rhs;
414    }
415}
416
417impl<D: Denom> Sub for SmartBigRational<D> {
418    type Output = Self;
419
420    fn sub(mut self, mut rhs: Self) -> Self {
421        let denom = D::normalize(&mut self.num, &mut rhs.num, &self.denom, &rhs.denom);
422        Self {
423            num: self.num - rhs.num,
424            denom,
425        }
426    }
427}
428
429impl<D: Denom> Sub<&Self> for SmartBigRational<D> {
430    type Output = Self;
431
432    fn sub(mut self, rhs: &Self) -> Self {
433        let mut rhs_num = rhs.num.clone();
434        let denom = D::normalize(&mut self.num, &mut rhs_num, &self.denom, &rhs.denom);
435        Self {
436            num: self.num - rhs_num,
437            denom,
438        }
439    }
440}
441
442impl<D: Denom> Sub for &SmartBigRational<D> {
443    type Output = SmartBigRational<D>;
444
445    fn sub(self, rhs: Self) -> SmartBigRational<D> {
446        let mut num = self.num.clone();
447        let mut rhs_num = rhs.num.clone();
448        let denom = D::normalize(&mut num, &mut rhs_num, &self.denom, &rhs.denom);
449        SmartBigRational {
450            num: num - rhs_num,
451            denom,
452        }
453    }
454}
455
456impl<D: Denom> Sub<SmartBigRational<D>> for &SmartBigRational<D> {
457    type Output = SmartBigRational<D>;
458
459    fn sub(self, mut rhs: SmartBigRational<D>) -> SmartBigRational<D> {
460        let mut num = self.num.clone();
461        let denom = D::normalize(&mut num, &mut rhs.num, &self.denom, &rhs.denom);
462        SmartBigRational {
463            num: num - rhs.num,
464            denom,
465        }
466    }
467}
468
469impl<D: Denom> SubAssign for SmartBigRational<D> {
470    fn sub_assign(&mut self, mut rhs: Self) {
471        self.denom = D::normalize(&mut self.num, &mut rhs.num, &self.denom, &rhs.denom);
472        self.num -= rhs.num;
473    }
474}
475
476impl<D: Denom> SubAssign<&Self> for SmartBigRational<D> {
477    fn sub_assign(&mut self, rhs: &Self) {
478        let mut rhs_num = rhs.num.clone();
479        self.denom = D::normalize(&mut self.num, &mut rhs_num, &self.denom, &rhs.denom);
480        self.num -= rhs_num;
481    }
482}
483
484impl<D: Denom> Sub<BigInt> for SmartBigRational<D>
485where
486    BigInt: for<'a> MulAssign<&'a D>,
487{
488    type Output = Self;
489
490    fn sub(self, mut rhs: BigInt) -> Self {
491        rhs *= &self.denom;
492        Self {
493            num: self.num - rhs,
494            denom: self.denom,
495        }
496    }
497}
498
499impl<D: Denom> Sub<&BigInt> for SmartBigRational<D>
500where
501    for<'a> &'a D: DenomRef<D>,
502{
503    type Output = Self;
504
505    fn sub(self, rhs: &BigInt) -> Self {
506        Self {
507            num: self.num - &self.denom * rhs,
508            denom: self.denom,
509        }
510    }
511}
512
513impl<D: Denom> Sub<BigInt> for &SmartBigRational<D>
514where
515    BigInt: for<'a> MulAssign<&'a D>,
516{
517    type Output = SmartBigRational<D>;
518
519    fn sub(self, mut rhs: BigInt) -> SmartBigRational<D> {
520        rhs *= &self.denom;
521        SmartBigRational {
522            num: &self.num - rhs,
523            denom: self.denom.clone(),
524        }
525    }
526}
527
528impl<D: Denom> Sub<&BigInt> for &SmartBigRational<D>
529where
530    for<'a> &'a D: DenomRef<D>,
531{
532    type Output = SmartBigRational<D>;
533
534    fn sub(self, rhs: &BigInt) -> SmartBigRational<D> {
535        SmartBigRational {
536            num: &self.num - &self.denom * rhs,
537            denom: self.denom.clone(),
538        }
539    }
540}
541
542impl<D: Denom> SubAssign<BigInt> for SmartBigRational<D>
543where
544    BigInt: for<'a> MulAssign<&'a D>,
545{
546    fn sub_assign(&mut self, mut rhs: BigInt) {
547        rhs *= &self.denom;
548        self.num -= rhs;
549    }
550}
551
552impl<D: Denom> SubAssign<&BigInt> for SmartBigRational<D>
553where
554    for<'a> &'a D: DenomRef<D>,
555{
556    fn sub_assign(&mut self, rhs: &BigInt) {
557        self.num -= &self.denom * rhs;
558    }
559}
560
561impl<D: Denom> Mul for SmartBigRational<D> {
562    type Output = Self;
563
564    fn mul(self, rhs: Self) -> Self {
565        Self {
566            num: self.num * rhs.num,
567            denom: self.denom * rhs.denom,
568        }
569    }
570}
571
572impl<D: Denom> Mul<&Self> for SmartBigRational<D> {
573    type Output = Self;
574
575    fn mul(self, rhs: &Self) -> Self {
576        Self {
577            num: self.num * &rhs.num,
578            denom: self.denom * &rhs.denom,
579        }
580    }
581}
582
583impl<D: Denom> Mul for &SmartBigRational<D>
584where
585    for<'a> &'a D: DenomRef<D>,
586{
587    type Output = SmartBigRational<D>;
588
589    fn mul(self, rhs: Self) -> SmartBigRational<D> {
590        SmartBigRational {
591            num: &self.num * &rhs.num,
592            denom: &self.denom * &rhs.denom,
593        }
594    }
595}
596
597impl<D: Denom> Mul<SmartBigRational<D>> for &SmartBigRational<D>
598where
599    for<'a> &'a D: DenomRef<D>,
600{
601    type Output = SmartBigRational<D>;
602
603    fn mul(self, rhs: SmartBigRational<D>) -> SmartBigRational<D> {
604        SmartBigRational {
605            num: &self.num * rhs.num,
606            denom: &self.denom * rhs.denom,
607        }
608    }
609}
610
611impl<D: Denom> MulAssign for SmartBigRational<D> {
612    fn mul_assign(&mut self, rhs: Self) {
613        self.num *= rhs.num;
614        self.denom *= rhs.denom;
615    }
616}
617
618impl<D: Denom> MulAssign<&Self> for SmartBigRational<D> {
619    fn mul_assign(&mut self, rhs: &Self) {
620        self.num *= &rhs.num;
621        self.denom *= &rhs.denom;
622    }
623}
624
625impl<D: Denom> Mul<BigInt> for SmartBigRational<D> {
626    type Output = Self;
627
628    fn mul(self, rhs: BigInt) -> Self {
629        Self {
630            num: self.num * rhs,
631            denom: self.denom,
632        }
633    }
634}
635
636impl<D: Denom> Mul<&BigInt> for SmartBigRational<D> {
637    type Output = Self;
638
639    fn mul(self, rhs: &BigInt) -> Self {
640        Self {
641            num: self.num * rhs,
642            denom: self.denom,
643        }
644    }
645}
646
647impl<D: Denom> Mul<BigInt> for &SmartBigRational<D> {
648    type Output = SmartBigRational<D>;
649
650    fn mul(self, rhs: BigInt) -> SmartBigRational<D> {
651        SmartBigRational {
652            num: &self.num * rhs,
653            denom: self.denom.clone(),
654        }
655    }
656}
657
658impl<D: Denom> Mul<&BigInt> for &SmartBigRational<D> {
659    type Output = SmartBigRational<D>;
660
661    fn mul(self, rhs: &BigInt) -> SmartBigRational<D> {
662        SmartBigRational {
663            num: &self.num * rhs,
664            denom: self.denom.clone(),
665        }
666    }
667}
668
669impl<D: Denom> MulAssign<BigInt> for SmartBigRational<D> {
670    fn mul_assign(&mut self, rhs: BigInt) {
671        self.num *= rhs;
672    }
673}
674
675impl<D: Denom> MulAssign<&BigInt> for SmartBigRational<D> {
676    fn mul_assign(&mut self, rhs: &BigInt) {
677        self.num *= rhs;
678    }
679}
680
681impl<D: Denom> Div for SmartBigRational<D> {
682    type Output = Self;
683
684    fn div(self, rhs: Self) -> Self {
685        let (rhs_sign, rhs_num) = rhs.num.into_parts();
686        let rhs_denom = BigInt::from_biguint(rhs_sign, rhs.denom.into());
687        Self {
688            num: self.num * rhs_denom,
689            denom: self.denom * D::from(rhs_num),
690        }
691    }
692}
693
694impl<D: Denom> Div<&Self> for SmartBigRational<D>
695where
696    for<'a> &'a D: DenomRef<D>,
697{
698    type Output = Self;
699
700    fn div(self, rhs: &Self) -> Self {
701        let rhs_denom = BigInt::from_biguint(rhs.num.sign(), (&rhs.denom).into());
702        Self {
703            num: self.num * rhs_denom,
704            denom: self.denom * D::from(rhs.num.magnitude()),
705        }
706    }
707}
708
709impl<D: Denom> Div for &SmartBigRational<D>
710where
711    for<'a> &'a D: DenomRef<D>,
712{
713    type Output = SmartBigRational<D>;
714
715    fn div(self, rhs: Self) -> SmartBigRational<D> {
716        let rhs_denom = BigInt::from_biguint(rhs.num.sign(), (&rhs.denom).into());
717        SmartBigRational {
718            num: &self.num * rhs_denom,
719            denom: &self.denom * D::from(rhs.num.magnitude()),
720        }
721    }
722}
723
724impl<D: Denom> Div<SmartBigRational<D>> for &SmartBigRational<D>
725where
726    for<'a> &'a D: DenomRef<D>,
727{
728    type Output = SmartBigRational<D>;
729
730    fn div(self, rhs: SmartBigRational<D>) -> SmartBigRational<D> {
731        let (rhs_sign, rhs_num) = rhs.num.into_parts();
732        let rhs_denom = BigInt::from_biguint(rhs_sign, rhs.denom.into());
733        SmartBigRational {
734            num: &self.num * rhs_denom,
735            denom: &self.denom * D::from(rhs_num),
736        }
737    }
738}
739
740impl<D: Denom> DivAssign for SmartBigRational<D> {
741    fn div_assign(&mut self, rhs: Self) {
742        let (rhs_sign, rhs_num) = rhs.num.into_parts();
743        let rhs_denom = BigInt::from_biguint(rhs_sign, rhs.denom.into());
744        self.num *= rhs_denom;
745        self.denom *= D::from(rhs_num);
746    }
747}
748
749impl<D: Denom> DivAssign<&Self> for SmartBigRational<D>
750where
751    for<'a> &'a D: DenomRef<D>,
752{
753    fn div_assign(&mut self, rhs: &Self) {
754        let rhs_denom = BigInt::from_biguint(rhs.num.sign(), (&rhs.denom).into());
755        self.num *= rhs_denom;
756        self.denom *= D::from(rhs.num.magnitude());
757    }
758}
759
760impl<D: Denom> Div<BigUint> for SmartBigRational<D> {
761    type Output = Self;
762
763    #[expect(clippy::suspicious_arithmetic_impl)]
764    fn div(self, rhs: BigUint) -> Self {
765        Self {
766            num: self.num,
767            denom: self.denom * D::from(rhs),
768        }
769    }
770}
771
772impl<D: Denom> Div<&BigUint> for SmartBigRational<D> {
773    type Output = Self;
774
775    #[expect(clippy::suspicious_arithmetic_impl)]
776    fn div(self, rhs: &BigUint) -> Self {
777        Self {
778            num: self.num,
779            denom: self.denom * D::from(rhs),
780        }
781    }
782}
783
784impl<D: Denom> Div<BigUint> for &SmartBigRational<D>
785where
786    for<'a> &'a D: DenomRef<D>,
787{
788    type Output = SmartBigRational<D>;
789
790    #[expect(clippy::suspicious_arithmetic_impl)]
791    fn div(self, rhs: BigUint) -> SmartBigRational<D> {
792        SmartBigRational {
793            num: self.num.clone(),
794            denom: &self.denom * D::from(rhs),
795        }
796    }
797}
798
799impl<D: Denom> Div<&BigUint> for &SmartBigRational<D>
800where
801    for<'a> &'a D: DenomRef<D>,
802{
803    type Output = SmartBigRational<D>;
804
805    #[expect(clippy::suspicious_arithmetic_impl)]
806    fn div(self, rhs: &BigUint) -> SmartBigRational<D> {
807        SmartBigRational {
808            num: self.num.clone(),
809            denom: &self.denom * D::from(rhs),
810        }
811    }
812}
813
814impl<D: Denom> DivAssign<BigUint> for SmartBigRational<D> {
815    #[expect(clippy::suspicious_op_assign_impl)]
816    fn div_assign(&mut self, rhs: BigUint) {
817        self.denom *= D::from(rhs);
818    }
819}
820
821impl<D: Denom> DivAssign<&BigUint> for SmartBigRational<D> {
822    #[expect(clippy::suspicious_op_assign_impl)]
823    fn div_assign(&mut self, rhs: &BigUint) {
824        self.denom *= D::from(rhs);
825    }
826}
827
828impl<D: Denom> Sum for SmartBigRational<D> {
829    fn sum<I>(iter: I) -> Self
830    where
831        I: Iterator<Item = Self>,
832    {
833        iter.fold(Self::ZERO, |acc, x| acc + x)
834    }
835}
836
837impl<'a, D: Denom> Sum<&'a Self> for SmartBigRational<D> {
838    fn sum<I>(iter: I) -> Self
839    where
840        I: Iterator<Item = &'a Self>,
841    {
842        iter.fold(Self::ZERO, |acc, x| acc + x)
843    }
844}
845
846impl<D: Denom> Product for SmartBigRational<D> {
847    fn product<I>(iter: I) -> Self
848    where
849        I: Iterator<Item = Self>,
850    {
851        iter.fold(Self::ONE, |acc, x| acc * x)
852    }
853}
854
855impl<'a, D: Denom> Product<&'a Self> for SmartBigRational<D> {
856    fn product<I>(iter: I) -> Self
857    where
858        I: Iterator<Item = &'a Self>,
859    {
860        iter.fold(Self::ONE, |acc, x| acc * x)
861    }
862}
863
864#[cfg(test)]
865mod tests {
866    use super::*;
867    use primes::ODD_PRIMES;
868    use rand::seq::IndexedRandom;
869    use std::fmt::Debug;
870
871    fn get_positive_test_values<D: Denom>() -> Vec<SmartBigRational<D>> {
872        let mut result = Vec::new();
873        for i in 0..=30 {
874            result.push(SmartBigRational::ratio(1 << i, 1u32));
875        }
876        for i in 0..=30 {
877            result.push(SmartBigRational::ratio(1, 1u32 << i));
878        }
879        for i in 0..=30 {
880            result.push(SmartBigRational::ratio(0x7FFF_FFFF - (1 << i), 1u32));
881        }
882        for i in 0..=30 {
883            result.push(SmartBigRational::ratio(1, 0x7FFF_FFFF - (1u32 << i)));
884        }
885        for &p in ODD_PRIMES.iter().take(30) {
886            result.push(SmartBigRational::ratio(1, p));
887        }
888        let prime_product = (0..=30)
889            .map(|i| ODD_PRIMES[i])
890            .fold(BigUint::ONE, |acc, x| acc * x);
891        result.push(SmartBigRational::ratio(1, prime_product));
892        result
893    }
894
895    fn loop_check1<T>(test_values: &[T], f: impl Fn(&T)) {
896        for a in test_values {
897            f(a);
898        }
899    }
900
901    fn loop_check2<T>(test_values: &[T], f: impl Fn(&T, &T)) {
902        for a in test_values {
903            for b in test_values {
904                f(a, b);
905            }
906        }
907    }
908
909    fn loop_check3<T>(test_values: &[T], num_samples: Option<usize>, f: impl Fn(&T, &T, &T)) {
910        match num_samples {
911            None => {
912                // Exhaustive check.
913                for a in test_values {
914                    for b in test_values {
915                        for c in test_values {
916                            f(a, b, c);
917                        }
918                    }
919                }
920            }
921            Some(n) => {
922                // Randomly sample values rather than conducting an exhaustive O(n^3) search on
923                // the test values.
924                let mut rng = rand::rng();
925
926                for _ in 0..n {
927                    let a = test_values.choose(&mut rng).unwrap();
928                    let b = test_values.choose(&mut rng).unwrap();
929                    let c = test_values.choose(&mut rng).unwrap();
930                    f(a, b, c);
931                }
932            }
933        }
934    }
935
936    macro_rules! tests {
937        (
938            $mod:ident,
939            $denom:ty,
940            $( $case:ident ,)*
941        ) => {
942            mod $mod {
943                use super::*;
944
945                $(
946                    #[test]
947                    fn $case() {
948                        $crate::tests::$case::<$denom>();
949                    }
950                )*
951            }
952        };
953    }
954
955    macro_rules! all_tests {
956        (
957            $mod:ident,
958            $denom:ty
959        ) => {
960            tests!(
961                $mod,
962                $denom,
963                test_is_zero,
964                test_zero_is_add_neutral,
965                test_add_is_commutative,
966                test_add_is_associative,
967                test_opposite,
968                test_sub_self,
969                test_add_sub,
970                test_sub_add,
971                test_one_is_mul_neutral,
972                test_mul_is_commutative,
973                test_mul_is_associative,
974                test_mul_is_distributive,
975                test_one_is_div_neutral,
976                test_div_self,
977                test_mul_div,
978                test_sum,
979                test_product,
980            );
981        };
982    }
983
984    all_tests!(denom_array24, DenomArray<24>);
985    all_tests!(denom_array200, DenomArray<200>);
986    all_tests!(denom_sparse24, DenomSparseU16<24, 8>);
987    all_tests!(denom_sparse6542, DenomSparseU16<6542, 8>);
988
989    fn test_is_zero<D: Denom + Debug>()
990    where
991        for<'a> &'a D: DenomRef<D>,
992    {
993        let test_values = get_positive_test_values::<D>();
994        assert!(SmartBigRational::<DenomArray24>::ZERO.is_zero());
995        assert!(!SmartBigRational::<DenomArray24>::ONE.is_zero());
996        loop_check1(&test_values, |a| {
997            assert!(!a.is_zero(), "{a} is zero");
998        });
999    }
1000
1001    fn test_zero_is_add_neutral<D: Denom + Debug>()
1002    where
1003        for<'a> &'a D: DenomRef<D>,
1004    {
1005        let test_values = get_positive_test_values::<D>();
1006        loop_check1(&test_values, |a| {
1007            assert_eq!(&(a + SmartBigRational::ZERO), a, "a + 0 != a for {a}");
1008            assert_eq!(&(SmartBigRational::ZERO + a), a, "0 + a != a for {a}");
1009            assert_eq!(&(a - SmartBigRational::ZERO), a, "a - 0 != a for {a}");
1010        })
1011    }
1012
1013    fn test_add_is_commutative<D: Denom + Debug>()
1014    where
1015        for<'a> &'a D: DenomRef<D>,
1016    {
1017        let test_values = get_positive_test_values::<D>();
1018        loop_check2(&test_values, |a, b| {
1019            assert_eq!(a + b, b + a, "a + b != b + a for {a}, {b}");
1020        })
1021    }
1022
1023    fn test_add_is_associative<D: Denom + Debug>()
1024    where
1025        for<'a> &'a D: DenomRef<D>,
1026    {
1027        let test_values = get_positive_test_values::<D>();
1028        loop_check3(&test_values, None, |a, b, c| {
1029            assert_eq!(
1030                (a + b) + c,
1031                a + (b + c),
1032                "(a + b) + c != a + (b + c) for {a}, {b}, {c}"
1033            );
1034        })
1035    }
1036
1037    fn test_opposite<D: Denom + Debug>()
1038    where
1039        for<'a> &'a D: DenomRef<D>,
1040    {
1041        let test_values = get_positive_test_values::<D>();
1042        loop_check1(&test_values, |a| {
1043            assert_eq!(&-(-a), a, "-(-a) != a for {a}");
1044            assert_eq!(
1045                &(SmartBigRational::ZERO - (SmartBigRational::ZERO - a)),
1046                a,
1047                "0 - (0 - a) != a for {a}"
1048            );
1049        });
1050    }
1051
1052    #[expect(clippy::eq_op)]
1053    fn test_sub_self<D: Denom + Debug>()
1054    where
1055        for<'a> &'a D: DenomRef<D>,
1056    {
1057        let test_values = get_positive_test_values::<D>();
1058        loop_check1(&test_values, |a| {
1059            assert_eq!(a - a, SmartBigRational::ZERO, "a - a != 0 for {a}");
1060        });
1061    }
1062
1063    fn test_add_sub<D: Denom + Debug>()
1064    where
1065        for<'a> &'a D: DenomRef<D>,
1066    {
1067        let test_values = get_positive_test_values::<D>();
1068        loop_check2(&test_values, |a, b| {
1069            assert_eq!(&((a + b) - b), a, "(a + b) - b != a for {a}, {b}");
1070        });
1071    }
1072
1073    fn test_sub_add<D: Denom + Debug>()
1074    where
1075        for<'a> &'a D: DenomRef<D>,
1076    {
1077        let test_values = get_positive_test_values::<D>();
1078        loop_check2(&test_values, |a, b| {
1079            assert_eq!(&((a - b) + b), a, "(a - b) + b != a for {a}, {b}");
1080        });
1081    }
1082
1083    fn test_one_is_mul_neutral<D: Denom + Debug>()
1084    where
1085        for<'a> &'a D: DenomRef<D>,
1086    {
1087        let test_values = get_positive_test_values::<D>();
1088        loop_check1(&test_values, |a| {
1089            assert_eq!(&(a * SmartBigRational::ONE), a, "a * 1 != a for {a}");
1090            assert_eq!(&(SmartBigRational::ONE * a), a, "1 * a != a for {a}");
1091        })
1092    }
1093
1094    fn test_mul_is_commutative<D: Denom + Debug>()
1095    where
1096        for<'a> &'a D: DenomRef<D>,
1097    {
1098        let test_values = get_positive_test_values::<D>();
1099        loop_check2(&test_values, |a, b| {
1100            assert_eq!(a * b, b * a, "a * b != b * a for {a}, {b}");
1101        })
1102    }
1103
1104    fn test_mul_is_associative<D: Denom + Debug>()
1105    where
1106        for<'a> &'a D: DenomRef<D>,
1107    {
1108        let test_values = get_positive_test_values::<D>();
1109        loop_check3(&test_values, None, |a, b, c| {
1110            assert_eq!(
1111                (a * b) * c,
1112                a * (b * c),
1113                "(a * b) * c != a * (b * c) for {a}, {b}, {c}"
1114            );
1115        })
1116    }
1117
1118    fn test_mul_is_distributive<D: Denom + Debug>()
1119    where
1120        for<'a> &'a D: DenomRef<D>,
1121    {
1122        let test_values = get_positive_test_values::<D>();
1123        loop_check3(&test_values, None, |a, b, c| {
1124            assert_eq!(
1125                a * (b + c),
1126                (a * b) + (a * c),
1127                "a * (b + c) != (a * b) + (a * c) for {a}, {b}, {c}"
1128            );
1129        })
1130    }
1131
1132    fn test_one_is_div_neutral<D: Denom + Debug>()
1133    where
1134        for<'a> &'a D: DenomRef<D>,
1135    {
1136        let test_values = get_positive_test_values::<D>();
1137        loop_check1(&test_values, |a| {
1138            assert_eq!(&(a / SmartBigRational::ONE), a, "a / 1 != a for {a}");
1139        })
1140    }
1141
1142    #[expect(clippy::eq_op)]
1143    fn test_div_self<D: Denom + Debug>()
1144    where
1145        for<'a> &'a D: DenomRef<D>,
1146    {
1147        let test_values = get_positive_test_values::<D>();
1148        loop_check1(&test_values, |a| {
1149            assert_eq!(a / a, SmartBigRational::ONE, "a / a != 1 for {a}");
1150        });
1151    }
1152
1153    fn test_mul_div<D: Denom + Debug>()
1154    where
1155        for<'a> &'a D: DenomRef<D>,
1156    {
1157        let test_values = get_positive_test_values::<D>();
1158        loop_check2(&test_values, |a, b| {
1159            assert_eq!(&((a * b) / b), a, "(a * b) / b != a for {a}, {b}");
1160        });
1161    }
1162
1163    fn test_sum<D: Denom + Debug>()
1164    where
1165        for<'a> &'a D: DenomRef<D>,
1166    {
1167        let test_values = get_positive_test_values::<D>();
1168        let mut expected = SmartBigRational::ZERO;
1169        for x in &test_values {
1170            expected += x;
1171        }
1172        assert_eq!(
1173            test_values.iter().sum::<SmartBigRational<_>>(),
1174            expected,
1175            "[x, ..., y].sum() != x + ... + y for {test_values:?}"
1176        );
1177    }
1178
1179    fn test_product<D: Denom + Debug>()
1180    where
1181        for<'a> &'a D: DenomRef<D>,
1182    {
1183        let test_values = get_positive_test_values::<D>();
1184        let mut expected = SmartBigRational::ONE;
1185        for x in &test_values {
1186            expected *= x;
1187        }
1188        assert_eq!(
1189            test_values.iter().product::<SmartBigRational<_>>(),
1190            expected,
1191            "[x, ..., y].product() != x * ... * y for {test_values:?}"
1192        );
1193    }
1194}
smart_big_rational/lib.rs

smart_big_rational/
lib.rs
