crypto_ratio/
lib.rs

1//! Arbitrary-precision rational number arithmetic using crypto-bigint integers.
2//!
3//! This library provides `Ratio<T>`, a generic rational number type supporting
4//! any crypto-bigint unsigned integer from U64 to U16384.
5//!
6//! # Features
7//!
8//! - **Generic over integer width**: Works with U256, U512, U1024, U2048, etc.
9//! - **Performance-focused**: Deferred reduction and smart heuristics
10//! - **Overflow handling**: Automatic fallback to wider types when needed
11//! - **no_std compatible**: Works in embedded and constrained environments
12//!
13//! # Design Philosophy
14//!
15//! Operations like multiplication and addition return **unreduced** results by default.
16//! Call [`Ratio::normalize`] explicitly when reduction is needed. This design
17//! improves performance in loops and chained operations.
18//!
19//! For convenience, [`Ratio::mul_reduced`] provides smart reduction using fast
20//! heuristics that avoid expensive GCD operations when possible.
21//!
22//! # Examples
23//!
24//! ## Basic Usage
25//!
26//! ```
27//! use crypto_ratio::Ratio;
28//! use crypto_bigint::U256;
29//!
30//! // Create rationals
31//! let a = Ratio::<U256>::from_u64(1, 2);  // 1/2
32//! let b = Ratio::<U256>::from_u64(1, 3);  // 1/3
33//!
34//! // Operations return unreduced results
35//! let sum = &a + &b;  // 5/6
36//! assert_eq!(sum.numer, U256::from_u64(5));
37//! assert_eq!(sum.denom, U256::from_u64(6));
38//!
39//! // Explicit reduction when needed
40//! let product = &a * &b;  // 1/6 (unreduced as 2/12)
41//! let mut reduced = product.clone();
42//! reduced.normalize();
43//! assert_eq!(reduced.numer, U256::from_u64(1));
44//! assert_eq!(reduced.denom, U256::from_u64(6));
45//! ```
46//!
47//! ## Type Aliases
48//!
49//! ```
50//! use crypto_ratio::RatioU512;
51//!
52//! let r = RatioU512::from_u64(3, 4);
53//! assert_eq!(r.to_f64_approx(), 0.75);
54//! ```
55//!
56//! ## Deferred Reduction Pattern
57//!
58//! ```
59//! use crypto_ratio::RatioU512;
60//!
61//! // Accumulate without reduction
62//! let mut sum = RatioU512::zero();
63//! let increment = RatioU512::from_u64(1, 100);
64//!
65//! for _ in 0..10 {
66//!     sum = sum.add(&increment);
67//! }
68//!
69//! // Reduce once at the end
70//! sum.normalize();
71//! ```
72
73pub mod ratio_trait;
74
75pub use crate::ratio_trait::{RatioInteger, WideInteger};
76use core::cmp::Ordering;
77
78/// A rational number represented as numerator/denominator with explicit sign.
79///
80/// # Type Parameter
81///
82/// `T` must implement [`RatioInteger`], which includes all crypto-bigint types
83/// from U64 through U16384.
84///
85/// # Invariants
86///
87/// - Denominator is never zero
88/// - Values are not automatically reduced (call [`normalize`](Ratio::normalize) explicitly)
89/// - Sign is stored separately in the `negative` field
90/// - Zero is always represented with `negative = false`
91///
92/// # Examples
93///
94/// ```
95/// use crypto_ratio::Ratio;
96/// use crypto_bigint::U512;
97///
98/// let r = Ratio::<U512>::from_u64(2, 3);
99/// assert_eq!(r.numer, U512::from_u64(2));
100/// assert_eq!(r.denom, U512::from_u64(3));
101/// assert!(!r.negative);
102/// ```
103#[derive(Clone, Debug)]
104pub struct Ratio<T: RatioInteger> {
105    /// The numerator.
106    pub numer: T,
107    /// The denominator.
108    pub denom: T,
109    /// Sign of the rational (true = negative).
110    pub negative: bool,
111}
112
113impl<T: RatioInteger> Ratio<T> {
114    // ========================================================================
115    // CONSTRUCTORS
116    // ========================================================================
117
118    /// Create a ratio without reduction.
119    ///
120    /// The denominator must be non-zero. This method is fast but the caller
121    /// is responsible for calling [`normalize`](Ratio::normalize) if needed.
122    ///
123    /// # Examples
124    ///
125    /// ```
126    /// use crypto_ratio::Ratio;
127    /// use crypto_bigint::U256;
128    ///
129    /// let r = Ratio::new_raw(U256::from_u64(4), U256::from_u64(6), false);
130    /// assert_eq!(r.numer, U256::from_u64(4)); // Not reduced
131    /// assert_eq!(r.denom, U256::from_u64(6));
132    /// ```
133    #[inline(always)]
134    pub fn new_raw(numer: T, denom: T, negative: bool) -> Self {
135        Self {
136            numer,
137            denom,
138            negative,
139        }
140    }
141
142    /// Create a ratio with automatic GCD reduction.
143    ///
144    /// This is slower than [`new_raw`](Ratio::new_raw) but ensures the result
145    /// is in lowest terms.
146    ///
147    /// # Examples
148    ///
149    /// ```
150    /// use crypto_ratio::Ratio;
151    /// use crypto_bigint::U256;
152    ///
153    /// let r = Ratio::new(U256::from_u64(4), U256::from_u64(6));
154    /// assert_eq!(r.numer, U256::from_u64(2)); // Reduced
155    /// assert_eq!(r.denom, U256::from_u64(3));
156    /// ```
157    pub fn new(numer: T, denom: T) -> Self {
158        if numer.is_zero_bool() {
159            return Self::zero();
160        }
161        let g = T::gcd(numer.clone(), denom.clone());
162        Self {
163            numer: numer.wrapping_div(&g),
164            denom: denom.wrapping_div(&g),
165            negative: false,
166        }
167    }
168
169    /// Create from u64 with automatic reduction.
170    ///
171    /// This is the most efficient constructor for small values.
172    ///
173    /// # Examples
174    ///
175    /// ```
176    /// use crypto_ratio::RatioU256;
177    ///
178    /// let r = RatioU256::from_u64(6, 8);
179    /// assert_eq!(r.to_f64_approx(), 0.75);
180    /// ```
181    #[inline]
182    pub fn from_u64(numer: u64, denom: u64) -> Self {
183        let g = gcd_u64(numer, denom);
184        Self {
185            numer: T::from_u64(numer / g),
186            denom: T::from_u64(denom / g),
187            negative: false,
188        }
189    }
190
191    /// Create a ratio representing 1.
192    #[inline(always)]
193    pub fn one() -> Self {
194        Self {
195            numer: T::ONE,
196            denom: T::ONE,
197            negative: false,
198        }
199    }
200
201    /// Create a ratio representing 0.
202    #[inline(always)]
203    pub fn zero() -> Self {
204        Self {
205            numer: T::ZERO,
206            denom: T::ONE,
207            negative: false,
208        }
209    }
210
211    // ========================================================================
212    // BASIC OPERATIONS
213    // ========================================================================
214
215    /// Negate the ratio, flipping its sign.
216    #[allow(clippy::should_implement_trait)] // We do implement Neg trait, clippy doesn't detect it
217    #[inline(always)]
218    pub fn neg(mut self) -> Self {
219        if !self.numer.is_zero_bool() {
220            self.negative = !self.negative;
221        }
222        self
223    }
224
225    /// Get the absolute value.
226    #[inline(always)]
227    pub fn abs(&self) -> Self {
228        Self {
229            numer: self.numer.clone(),
230            denom: self.denom.clone(),
231            negative: false,
232        }
233    }
234
235    /// Check if the ratio is zero.
236    #[inline(always)]
237    pub fn is_zero(&self) -> bool {
238        self.numer.is_zero_bool()
239    }
240
241    /// Check if the ratio is positive.
242    #[inline]
243    pub fn is_positive(&self) -> bool {
244        !self.negative && !self.numer.is_zero_bool()
245    }
246
247    /// Check if the ratio is negative.
248    #[inline]
249    pub fn is_negative(&self) -> bool {
250        self.negative && !self.numer.is_zero_bool()
251    }
252
253    /// Check if the ratio represents an integer (denominator is 1).
254    #[inline]
255    pub fn is_integer(&self) -> bool {
256        self.denom == T::ONE
257    }
258
259    // ========================================================================
260    // REDUCTION
261    // ========================================================================
262
263    /// Check if the ratio should be reduced to prevent overflow.
264    ///
265    /// Returns true if either numerator or denominator exceeds the
266    /// reduction threshold (typically 70% of the type's bit width).
267    #[inline(always)]
268    pub fn needs_reduction(&self) -> bool {
269        self.numer.bits_u32() > T::REDUCTION_THRESHOLD
270            || self.denom.bits_u32() > T::REDUCTION_THRESHOLD
271    }
272
273    /// Normalize only if [`needs_reduction`](Ratio::needs_reduction) returns true.
274    ///
275    /// This is useful in loops to avoid unnecessary GCD operations.
276    #[inline]
277    pub fn normalize_if_needed(&mut self) {
278        if self.needs_reduction() {
279            self.normalize();
280        }
281    }
282
283    /// Reduce the ratio to lowest terms using GCD.
284    ///
285    /// This operation is optimized to:
286    /// - Return immediately if already reduced (GCD = 1)
287    /// - Use bit shifts for power-of-2 factors
288    /// - Normalize zero to 0/1
289    ///
290    /// # Examples
291    ///
292    /// ```
293    /// use crypto_ratio::RatioU256;
294    ///
295    /// let mut r = RatioU256::new_raw(
296    ///     crypto_bigint::U256::from_u64(6),
297    ///     crypto_bigint::U256::from_u64(8),
298    ///     false
299    /// );
300    /// r.normalize();
301    /// assert_eq!(r.numer, crypto_bigint::U256::from_u64(3));
302    /// assert_eq!(r.denom, crypto_bigint::U256::from_u64(4));
303    /// ```
304    #[inline]
305    #[allow(clippy::should_implement_trait)]
306    pub fn normalize(&mut self) {
307        if self.numer.is_zero_bool() {
308            self.denom = T::ONE;
309            self.negative = false;
310            return;
311        }
312
313        let g = T::gcd(self.numer.clone(), self.denom.clone());
314        if g == T::ONE {
315            return;
316        }
317
318        let trailing = g.trailing_zeros_u32();
319        let bits = g.bits_u32();
320
321        if trailing > 0 && bits == trailing + 1 {
322            self.numer = self.numer.shr_vartime_u32(trailing);
323            self.denom = self.denom.shr_vartime_u32(trailing);
324        } else {
325            self.numer = self.numer.wrapping_div(&g);
326            self.denom = self.denom.wrapping_div(&g);
327        }
328    }
329
330    // ========================================================================
331    // FLOAT CONVERSION
332    // ========================================================================
333
334    /// Convert an f64 to a ratio with automatic reduction.
335    ///
336    /// Returns `None` if the input is infinite or NaN.
337    ///
338    /// # Examples
339    ///
340    /// ```
341    /// use crypto_ratio::RatioU512;
342    ///
343    /// let r = RatioU512::from_float(0.75).unwrap();
344    /// assert_eq!(r.numer, crypto_bigint::U512::from_u64(3));
345    /// assert_eq!(r.denom, crypto_bigint::U512::from_u64(4));
346    /// ```
347    pub fn from_float(f: f64) -> Option<Self> {
348        if !f.is_finite() {
349            return None;
350        }
351        let negative = f.is_sign_negative();
352        let abs_f = f.abs();
353
354        const SCALE_POWER: u32 = 52;
355        let scale = 1u64 << SCALE_POWER;
356        let scaled = (abs_f * scale as f64) as u128;
357
358        if scaled == 0 {
359            return Some(Self::zero());
360        }
361
362        if scaled <= u64::MAX as u128 {
363            let n_u64 = scaled as u64;
364            let g = gcd_u64(n_u64, scale);
365            return Some(Self {
366                numer: T::from_u64(n_u64 / g),
367                denom: T::from_u64(scale / g),
368                negative,
369            });
370        }
371
372        let n = T::from_u128(scaled);
373        let d = T::from_u64(scale);
374        let g = T::gcd(n.clone(), d.clone());
375
376        Some(Self {
377            numer: n.wrapping_div(&g),
378            denom: d.wrapping_div(&g),
379            negative,
380        })
381    }
382
383    /// Approximate conversion to f64.
384    ///
385    /// Large values are scaled to fit in f64 range, potentially losing precision.
386    ///
387    /// # Examples
388    ///
389    /// ```
390    /// use crypto_ratio::RatioU256;
391    ///
392    /// let r = RatioU256::from_u64(1, 2);
393    /// assert!((r.to_f64_approx() - 0.5).abs() < 1e-10);
394    /// ```
395    #[inline]
396    pub fn to_f64_approx(&self) -> f64 {
397        let n_bits = self.numer.bits_u32();
398        let d_bits = self.denom.bits_u32();
399
400        if n_bits == 0 {
401            return 0.0;
402        }
403
404        let n_shift = n_bits.saturating_sub(64);
405        let d_shift = d_bits.saturating_sub(64);
406
407        let n_approx = self.numer.shr_vartime_u32(n_shift).first_word() as f64;
408        let d_approx = self.denom.shr_vartime_u32(d_shift).first_word() as f64;
409
410        let exp_diff = (n_shift as i32) - (d_shift as i32);
411        let val = n_approx / d_approx * 2f64.powi(exp_diff);
412
413        if self.negative {
414            -val
415        } else {
416            val
417        }
418    }
419
420    // ========================================================================
421    // ARITHMETIC - ADDITION
422    // ========================================================================
423
424    /// Add two ratios.
425    ///
426    /// Returns an unreduced result. Call [`normalize`](Ratio::normalize) if needed.
427    ///
428    /// # Examples
429    ///
430    /// ```
431    /// use crypto_ratio::RatioU256;
432    ///
433    /// let a = RatioU256::from_u64(1, 2);
434    /// let b = RatioU256::from_u64(1, 3);
435    /// let sum = a.add(&b);
436    /// // Result is 5/6
437    /// ```
438    #[inline]
439    pub fn add(&self, other: &Self) -> Self {
440        if self.denom == other.denom {
441            let (n, neg) = self.add_sub_numer(other);
442            return Self {
443                numer: n,
444                denom: self.denom.clone(),
445                negative: neg,
446            };
447        }
448
449        let (ad, ad_hi) = self.numer.mul_wide(&other.denom);
450        let (bc, bc_hi) = other.numer.mul_wide(&self.denom);
451        let (bd, bd_hi) = self.denom.mul_wide(&other.denom);
452
453        if ad_hi.is_zero_bool() && bc_hi.is_zero_bool() && bd_hi.is_zero_bool() {
454            let (numer, negative) = match (self.negative, other.negative) {
455                (false, false) => (ad.wrapping_add(&bc), false),
456                (true, true) => (ad.wrapping_add(&bc), true),
457                (false, true) if ad >= bc => (ad.wrapping_sub(&bc), false),
458                (false, true) => (bc.wrapping_sub(&ad), true),
459                (true, false) if bc >= ad => (bc.wrapping_sub(&ad), false),
460                (true, false) => (ad.wrapping_sub(&bc), true),
461            };
462
463            return Self {
464                numer,
465                denom: bd,
466                negative,
467            };
468        }
469
470        self.add_wide(other)
471    }
472
473    #[inline(always)]
474    fn add_sub_numer(&self, other: &Self) -> (T, bool) {
475        match (self.negative, other.negative) {
476            (false, false) => (self.numer.wrapping_add(&other.numer), false),
477            (true, true) => (self.numer.wrapping_add(&other.numer), true),
478            (false, true) if self.numer >= other.numer => {
479                (self.numer.wrapping_sub(&other.numer), false)
480            }
481            (false, true) => (other.numer.wrapping_sub(&self.numer), true),
482            (true, false) if other.numer >= self.numer => {
483                (other.numer.wrapping_sub(&self.numer), false)
484            }
485            (true, false) => (self.numer.wrapping_sub(&other.numer), true),
486        }
487    }
488
489    #[cold]
490    #[inline(never)]
491    fn add_wide(&self, other: &Self) -> Self {
492        let a = self.numer.to_wide();
493        let b = self.denom.to_wide();
494        let c = other.numer.to_wide();
495        let d = other.denom.to_wide();
496
497        let ad = a.wrapping_mul(&d);
498        let bc = b.wrapping_mul(&c);
499        let bd = b.wrapping_mul(&d);
500
501        let (numer_wide, negative) = match (self.negative, other.negative) {
502            (false, false) => (ad.wrapping_add(&bc), false),
503            (true, true) => (ad.wrapping_add(&bc), true),
504            (false, true) => {
505                if ad >= bc {
506                    (ad.wrapping_sub(&bc), false)
507                } else {
508                    (bc.wrapping_sub(&ad), true)
509                }
510            }
511            (true, false) => {
512                if bc >= ad {
513                    (bc.wrapping_sub(&ad), false)
514                } else {
515                    (ad.wrapping_sub(&bc), true)
516                }
517            }
518        };
519
520        let g = T::Wide::gcd(numer_wide.clone(), bd.clone());
521        let normalized_numer = numer_wide.wrapping_div(&g);
522        let normalized_denom = bd.wrapping_div(&g);
523
524        let numer =
525            T::from_wide_checked(&normalized_numer).expect("numerator overflow after reduction");
526        let denom =
527            T::from_wide_checked(&normalized_denom).expect("denominator overflow after reduction");
528
529        Self {
530            numer,
531            denom,
532            negative,
533        }
534    }
535
536    // ========================================================================
537    // ARITHMETIC - MULTIPLICATION
538    // ========================================================================
539
540    /// Multiply two ratios without automatic reduction.
541    ///
542    /// For reduced results, use [`mul_reduced`](Ratio::mul_reduced) or call
543    /// [`normalize`](Ratio::normalize) afterward.
544    ///
545    /// # Examples
546    ///
547    /// ```
548    /// use crypto_ratio::RatioU256;
549    ///
550    /// let a = RatioU256::from_u64(2, 3);
551    /// let b = RatioU256::from_u64(3, 4);
552    /// let product = a.mul(&b);
553    /// // Result is 6/12 (unreduced)
554    /// ```
555    #[inline]
556    pub fn mul(&self, other: &Self) -> Self {
557        let negative = self.negative ^ other.negative;
558
559        let self_max_bits = self.numer.bits_u32().max(self.denom.bits_u32());
560        let other_max_bits = other.numer.bits_u32().max(other.denom.bits_u32());
561        let large_threshold = (T::BITS * 6) / 10;
562
563        let (self_work, other_work) =
564            if self_max_bits > large_threshold || other_max_bits > large_threshold {
565                let mut s = self.clone();
566                let mut o = other.clone();
567                if self_max_bits > large_threshold {
568                    s.normalize();
569                }
570                if other_max_bits > large_threshold {
571                    o.normalize();
572                }
573                (s, o)
574            } else {
575                (self.clone(), other.clone())
576            };
577
578        let (ac, ac_hi) = self_work.numer.mul_wide(&other_work.numer);
579        let (bd, bd_hi) = self_work.denom.mul_wide(&other_work.denom);
580
581        if ac_hi.is_zero_bool() && bd_hi.is_zero_bool() {
582            return Self {
583                numer: ac,
584                denom: bd,
585                negative,
586            };
587        }
588
589        let g_ad = T::gcd(self_work.numer.clone(), other_work.denom.clone());
590        let g_bc = T::gcd(self_work.denom.clone(), other_work.numer.clone());
591
592        let a = self_work.numer.wrapping_div(&g_ad);
593        let c = other_work.numer.wrapping_div(&g_bc);
594        let b = self_work.denom.wrapping_div(&g_bc);
595        let d = other_work.denom.wrapping_div(&g_ad);
596
597        let (ac, ac_hi) = a.mul_wide(&c);
598        let (bd, bd_hi) = b.mul_wide(&d);
599
600        if !ac_hi.is_zero_bool() || !bd_hi.is_zero_bool() {
601            panic!("multiplication overflow after cross-cancellation");
602        }
603
604        Self {
605            numer: ac,
606            denom: bd,
607            negative,
608        }
609    }
610
611    /// Multiply with smart reduction using fast heuristics.
612    ///
613    /// This applies cheap reduction techniques:
614    /// - Power-of-2 factors via bit shifts (~10ns)
615    /// - Small value GCD using u64 (~50ns)
616    /// - Skips expensive full GCD for large coprime values
617    ///
618    /// # Examples
619    ///
620    /// ```
621    /// use crypto_ratio::RatioU256;
622    ///
623    /// let a = RatioU256::from_u64(2, 3);
624    /// let b = RatioU256::from_u64(3, 4);
625    /// let product = a.mul_reduced(&b);
626    /// // Result is 1/2 (reduced)
627    /// ```
628    #[inline]
629    pub fn mul_reduced(&self, other: &Self) -> Self {
630        let self_max_bits = self.numer.bits_u32().max(self.denom.bits_u32());
631        let other_max_bits = other.numer.bits_u32().max(other.denom.bits_u32());
632        let large_threshold = (T::BITS * 6) / 10;
633
634        let (self_work, other_work) =
635            if self_max_bits > large_threshold || other_max_bits > large_threshold {
636                let mut s = self.clone();
637                let mut o = other.clone();
638                if self_max_bits > large_threshold {
639                    s.normalize();
640                }
641                if other_max_bits > large_threshold {
642                    o.normalize();
643                }
644                (s, o)
645            } else {
646                (self.clone(), other.clone())
647            };
648
649        let negative = self.negative ^ other.negative;
650
651        let (ac, ac_hi) = self_work.numer.mul_wide(&other_work.numer);
652        let (bd, bd_hi) = self_work.denom.mul_wide(&other_work.denom);
653
654        if ac_hi.is_zero_bool() && bd_hi.is_zero_bool() {
655            let mut numer = ac;
656            let mut denom = bd;
657
658            let trailing_n = numer.trailing_zeros_u32();
659            let trailing_d = denom.trailing_zeros_u32();
660            let common_trailing = trailing_n.min(trailing_d);
661
662            if common_trailing > 0 {
663                numer = numer.shr_vartime_u32(common_trailing);
664                denom = denom.shr_vartime_u32(common_trailing);
665            }
666
667            let numer_bits = numer.bits_u32();
668            let denom_bits = denom.bits_u32();
669
670            if numer_bits <= 64 && denom_bits <= 64 {
671                if let (Some(n_u64), Some(d_u64)) = (numer.try_to_u64(), denom.try_to_u64()) {
672                    let g = gcd_u64(n_u64, d_u64);
673                    if g > 1 {
674                        return Self {
675                            numer: T::from_u64(n_u64 / g),
676                            denom: T::from_u64(d_u64 / g),
677                            negative,
678                        };
679                    }
680                    return Self {
681                        numer,
682                        denom,
683                        negative,
684                    };
685                }
686            }
687
688            if numer_bits <= 128 && denom_bits <= 128 {
689                let g = T::gcd(numer.clone(), denom.clone());
690                if g != T::ONE {
691                    return Self {
692                        numer: numer.wrapping_div(&g),
693                        denom: denom.wrapping_div(&g),
694                        negative,
695                    };
696                }
697            }
698
699            return Self {
700                numer,
701                denom,
702                negative,
703            };
704        }
705
706        let g_ad = T::gcd(self_work.numer.clone(), other_work.denom.clone());
707        let g_bc = T::gcd(self_work.denom.clone(), other_work.numer.clone());
708
709        let a = self_work.numer.wrapping_div(&g_ad);
710        let c = other_work.numer.wrapping_div(&g_bc);
711        let b = self_work.denom.wrapping_div(&g_bc);
712        let d = other_work.denom.wrapping_div(&g_ad);
713
714        let (ac, ac_hi) = a.mul_wide(&c);
715        let (bd, bd_hi) = b.mul_wide(&d);
716
717        if !ac_hi.is_zero_bool() || !bd_hi.is_zero_bool() {
718            panic!("multiplication overflow after cross-cancellation");
719        }
720
721        Self {
722            numer: ac,
723            denom: bd,
724            negative,
725        }
726    }
727
728    /// Divide by an unsigned integer.
729    ///
730    /// Multiplies the denominator by the divisor.
731    #[inline]
732    pub fn div_by_uint(&self, divisor: &T) -> Self {
733        let (bd, bd_hi) = self.denom.mul_wide(divisor);
734
735        if !bd_hi.is_zero_bool() {
736            panic!("denominator overflow in div_by_uint");
737        }
738
739        Self {
740            numer: self.numer.clone(),
741            denom: bd,
742            negative: self.negative,
743        }
744    }
745
746    /// Subtract another ratio.
747    ///
748    /// Equivalent to `self.add(&other.neg())`.
749    #[inline]
750    pub fn sub(&self, other: &Self) -> Self {
751        self.add(&other.clone().neg())
752    }
753
754    /// Divide by another ratio.
755    ///
756    /// # Panics
757    ///
758    /// Panics if `other` is zero.
759    #[inline]
760    pub fn div(&self, other: &Self) -> Self {
761        if other.numer.is_zero_bool() {
762            panic!("division by zero");
763        }
764
765        let reciprocal = Self {
766            numer: other.denom.clone(),
767            denom: other.numer.clone(),
768            negative: other.negative,
769        };
770        self.mul(&reciprocal)
771    }
772
773    /// Get the reciprocal (1/x).
774    ///
775    /// # Panics
776    ///
777    /// Panics if the ratio is zero.
778    #[inline]
779    pub fn recip(&self) -> Self {
780        if self.numer.is_zero_bool() {
781            panic!("reciprocal of zero");
782        }
783        Self {
784            numer: self.denom.clone(),
785            denom: self.numer.clone(),
786            negative: self.negative,
787        }
788    }
789
790    // ========================================================================
791    // COMPARISONS
792    // ========================================================================
793
794    /// Less-than comparison optimized for both small and large values.
795    ///
796    /// Uses fast paths for:
797    /// - Sign differences
798    /// - Large magnitude differences
799    /// - Small values (≤64 bits)
800    #[inline]
801    pub fn lt(&self, other: &Self) -> bool {
802        if self.negative != other.negative {
803            return self.negative;
804        }
805
806        let self_numer_bits = self.numer.bits_u32();
807        let self_denom_bits = self.denom.bits_u32();
808        let other_numer_bits = other.numer.bits_u32();
809        let other_denom_bits = other.denom.bits_u32();
810
811        let self_mag = self_numer_bits as i32 - self_denom_bits as i32;
812        let other_mag = other_numer_bits as i32 - other_denom_bits as i32;
813        let mag_diff = self_mag - other_mag;
814
815        if mag_diff < -2 {
816            return !self.negative;
817        }
818        if mag_diff > 2 {
819            return self.negative;
820        }
821
822        if self_numer_bits <= 64
823            && self_denom_bits <= 64
824            && other_numer_bits <= 64
825            && other_denom_bits <= 64
826        {
827            if let (Some(self_n), Some(self_d), Some(other_n), Some(other_d)) = (
828                self.numer.try_to_u64(),
829                self.denom.try_to_u64(),
830                other.numer.try_to_u64(),
831                other.denom.try_to_u64(),
832            ) {
833                let ad = (self_n as u128) * (other_d as u128);
834                let bc = (other_n as u128) * (self_d as u128);
835                return if self.negative { ad > bc } else { ad < bc };
836            }
837        }
838
839        let (ad, ad_hi) = self.numer.mul_wide(&other.denom);
840        let (bc, bc_hi) = self.denom.mul_wide(&other.numer);
841
842        match (ad_hi.cmp(&bc_hi), ad.cmp(&bc)) {
843            (Ordering::Less, _) => !self.negative,
844            (Ordering::Greater, _) => self.negative,
845            (Ordering::Equal, ord) => {
846                if self.negative {
847                    ord == Ordering::Greater
848                } else {
849                    ord == Ordering::Less
850                }
851            }
852        }
853    }
854
855    /// Greater-than comparison optimized for both small and large values.
856    ///
857    /// Uses fast paths for:
858    /// - Sign differences
859    /// - Large magnitude differences
860    /// - Small values (≤64 bits)
861    #[inline]
862    pub fn gt(&self, other: &Self) -> bool {
863        if self.negative != other.negative {
864            return !self.negative && other.negative;
865        }
866
867        let self_numer_bits = self.numer.bits_u32();
868        let self_denom_bits = self.denom.bits_u32();
869        let other_numer_bits = other.numer.bits_u32();
870        let other_denom_bits = other.denom.bits_u32();
871
872        let self_mag = self_numer_bits as i32 - self_denom_bits as i32;
873        let other_mag = other_numer_bits as i32 - other_denom_bits as i32;
874        let mag_diff = self_mag - other_mag;
875
876        if mag_diff > 2 {
877            return !self.negative;
878        }
879        if mag_diff < -2 {
880            return self.negative;
881        }
882
883        if self_numer_bits <= 64
884            && self_denom_bits <= 64
885            && other_numer_bits <= 64
886            && other_denom_bits <= 64
887        {
888            if let (Some(self_n), Some(self_d), Some(other_n), Some(other_d)) = (
889                self.numer.try_to_u64(),
890                self.denom.try_to_u64(),
891                other.numer.try_to_u64(),
892                other.denom.try_to_u64(),
893            ) {
894                let ad = (self_n as u128) * (other_d as u128);
895                let bc = (other_n as u128) * (self_d as u128);
896                return if self.negative { ad < bc } else { ad > bc };
897            }
898        }
899
900        let (ad, ad_hi) = self.numer.mul_wide(&other.denom);
901        let (bc, bc_hi) = self.denom.mul_wide(&other.numer);
902
903        match (ad_hi.cmp(&bc_hi), ad.cmp(&bc)) {
904            (Ordering::Greater, _) => !self.negative,
905            (Ordering::Less, _) => self.negative,
906            (Ordering::Equal, ord) => {
907                if self.negative {
908                    ord == Ordering::Less
909                } else {
910                    ord == Ordering::Greater
911                }
912            }
913        }
914    }
915}
916
917// ============================================================================
918// HELPERS
919// ============================================================================
920
921/// Fast u64 GCD using the Euclidean algorithm.
922#[inline]
923fn gcd_u64(mut a: u64, mut b: u64) -> u64 {
924    while b != 0 {
925        let temp = b;
926        b = a % b;
927        a = temp;
928    }
929    a
930}
931
932// ============================================================================
933// TRAIT IMPLEMENTATIONS
934// ============================================================================
935
936use core::ops::{Add, Div, Mul, Neg, Sub};
937
938impl<T: RatioInteger> Add for Ratio<T> {
939    type Output = Self;
940    #[inline(always)]
941    fn add(self, other: Self) -> Self {
942        Ratio::add(&self, &other)
943    }
944}
945
946impl<T: RatioInteger> Add for &Ratio<T> {
947    type Output = Ratio<T>;
948    #[inline(always)]
949    fn add(self, other: Self) -> Ratio<T> {
950        Ratio::add(self, other)
951    }
952}
953
954impl<T: RatioInteger> Mul for Ratio<T> {
955    type Output = Self;
956    #[inline(always)]
957    fn mul(self, other: Self) -> Self {
958        Ratio::mul(&self, &other)
959    }
960}
961
962impl<T: RatioInteger> Mul for &Ratio<T> {
963    type Output = Ratio<T>;
964    #[inline(always)]
965    fn mul(self, other: Self) -> Ratio<T> {
966        Ratio::mul(self, other)
967    }
968}
969
970impl<T: RatioInteger> Neg for Ratio<T> {
971    type Output = Self;
972    #[inline(always)]
973    fn neg(self) -> Self {
974        Ratio::neg(self)
975    }
976}
977
978impl<T: RatioInteger> Sub for Ratio<T> {
979    type Output = Self;
980    fn sub(self, other: Self) -> Self {
981        Ratio::sub(&self, &other)
982    }
983}
984
985impl<T: RatioInteger> Sub for &Ratio<T> {
986    type Output = Ratio<T>;
987    fn sub(self, other: Self) -> Ratio<T> {
988        Ratio::sub(self, other)
989    }
990}
991
992impl<T: RatioInteger> Div for Ratio<T> {
993    type Output = Self;
994    fn div(self, other: Self) -> Self {
995        Ratio::div(&self, &other)
996    }
997}
998
999impl<T: RatioInteger> Div for &Ratio<T> {
1000    type Output = Ratio<T>;
1001    fn div(self, other: Self) -> Ratio<T> {
1002        Ratio::div(self, other)
1003    }
1004}
1005
1006impl<T: RatioInteger> PartialEq for Ratio<T> {
1007    fn eq(&self, other: &Self) -> bool {
1008        if self.numer.is_zero_bool() && other.numer.is_zero_bool() {
1009            return true;
1010        }
1011        if self.negative != other.negative {
1012            return false;
1013        }
1014
1015        let (ad, ad_hi) = self.numer.mul_wide(&other.denom);
1016        let (bc, bc_hi) = other.numer.mul_wide(&self.denom);
1017
1018        ad == bc && ad_hi == bc_hi
1019    }
1020}
1021
1022impl<T: RatioInteger> Eq for Ratio<T> {}
1023
1024impl<T: RatioInteger> PartialOrd for Ratio<T> {
1025    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1026        Some(self.cmp(other))
1027    }
1028}
1029
1030impl<T: RatioInteger> Ord for Ratio<T> {
1031    fn cmp(&self, other: &Self) -> Ordering {
1032        if self.gt(other) {
1033            Ordering::Greater
1034        } else if self.lt(other) {
1035            Ordering::Less
1036        } else {
1037            Ordering::Equal
1038        }
1039    }
1040}
1041
1042// ============================================================================
1043// TYPE ALIASES
1044// ============================================================================
1045
1046/// Ratio using 64-bit integers.
1047pub type RatioU64 = Ratio<crypto_bigint::U64>;
1048
1049/// Ratio using 128-bit integers.
1050pub type RatioU128 = Ratio<crypto_bigint::U128>;
1051
1052/// Ratio using 256-bit integers.
1053pub type RatioU256 = Ratio<crypto_bigint::U256>;
1054
1055/// Ratio using 512-bit integers (recommended for most use cases).
1056pub type RatioU512 = Ratio<crypto_bigint::U512>;
1057
1058/// Ratio using 1024-bit integers.
1059pub type RatioU1024 = Ratio<crypto_bigint::U1024>;
1060
1061/// Ratio using 2048-bit integers.
1062pub type RatioU2048 = Ratio<crypto_bigint::U2048>;
1063
1064/// Ratio using 4096-bit integers.
1065pub type RatioU4096 = Ratio<crypto_bigint::U4096>;
1066
1067/// Ratio using 8192-bit integers.
1068pub type RatioU8192 = Ratio<crypto_bigint::U8192>;
1069
1070/// Ratio using 16384-bit integers.
1071pub type RatioU16384 = Ratio<crypto_bigint::U16384>;
1072
1073#[cfg(test)]
1074mod tests {
1075    use super::*;
1076    use crypto_bigint::*;
1077
1078    #[test]
1079    fn test_basic_u512() {
1080        let r = Ratio::<U512>::from_u64(3, 4);
1081        assert_eq!(r.numer, U512::from_u64(3));
1082        assert_eq!(r.denom, U512::from_u64(4));
1083    }
1084
1085    #[test]
1086    fn test_basic_u256() {
1087        let r = Ratio::<U256>::from_u64(5, 10);
1088        assert_eq!(r.numer, U256::from_u64(1));
1089        assert_eq!(r.denom, U256::from_u64(2));
1090    }
1091
1092    #[test]
1093    fn test_add_same_denom() {
1094        let r1 = Ratio::<U512>::from_u64(1, 4);
1095        let r2 = Ratio::<U512>::from_u64(1, 4);
1096        let sum = &r1 + &r2;
1097        assert_eq!(sum.numer, U512::from_u64(2));
1098        assert_eq!(sum.denom, U512::from_u64(4));
1099    }
1100
1101    #[test]
1102    fn test_mul_unreduced() {
1103        let r1 = Ratio::<U256>::from_u64(2, 3);
1104        let r2 = Ratio::<U256>::from_u64(3, 4);
1105        let prod = &r1 * &r2;
1106
1107        assert_eq!(prod.numer, U256::from_u64(6));
1108        assert_eq!(prod.denom, U256::from_u64(12));
1109    }
1110
1111    #[test]
1112    fn test_mul_reduced() {
1113        let r1 = Ratio::<U256>::from_u64(2, 3);
1114        let r2 = Ratio::<U256>::from_u64(3, 4);
1115        let prod = r1.mul_reduced(&r2);
1116
1117        assert_eq!(prod.numer, U256::from_u64(1));
1118        assert_eq!(prod.denom, U256::from_u64(2));
1119    }
1120
1121    #[test]
1122    fn test_mul_reduced_power_of_2() {
1123        let r1 = Ratio::<U256>::from_u64(4, 8);
1124        let r2 = Ratio::<U256>::from_u64(2, 6);
1125        let prod = r1.mul_reduced(&r2);
1126
1127        assert_eq!(prod.numer, U256::from_u64(1));
1128        assert_eq!(prod.denom, U256::from_u64(6));
1129    }
1130
1131    #[test]
1132    fn test_flexible_wide_types() {
1133        let r576 = Ratio::<U576>::from_u64(1, 2);
1134        assert_eq!(r576.numer, U576::from_u64(1));
1135
1136        let r640 = Ratio::<U640>::from_u64(3, 4);
1137        assert_eq!(r640.numer, U640::from_u64(3));
1138    }
1139}
crypto_ratio/lib.rs

crypto_ratio/
lib.rs
