ckb_rational/
lib.rs

1//! Rational numbers.
2#[cfg(test)]
3mod tests;
4
5use numext_fixed_uint::U256;
6use serde::{Deserialize, Serialize};
7use std::cmp::Ordering;
8use std::fmt;
9use std::ops::{Add, Div, Mul, Sub};
10
11/// Represents the ratio `numerator / denominator`, where `numerator` and `denominator` are both
12/// unsigned 256-bit integers.
13#[derive(Clone, Debug, PartialEq, Eq, Deserialize, Serialize)]
14pub struct RationalU256 {
15    /// Numerator.
16    numer: U256,
17    /// Denominator.
18    denom: U256,
19}
20
21impl fmt::Display for RationalU256 {
22    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
23        write!(f, "{}/{}", self.numer, self.denom)
24    }
25}
26
27impl RationalU256 {
28    /// Creates a new ratio `numer / denom`.
29    ///
30    /// ## Panics
31    ///
32    /// Panics when `denom` is zero.
33    #[inline]
34    pub fn new(numer: U256, denom: U256) -> RationalU256 {
35        if denom.is_zero() {
36            panic!("denominator == 0");
37        }
38        let mut ret = RationalU256::new_raw(numer, denom);
39        ret.reduce();
40        ret
41    }
42
43    /// Creates a new ratio `numer / denom` without checking whether `denom` is zero.
44    #[inline]
45    pub const fn new_raw(numer: U256, denom: U256) -> RationalU256 {
46        RationalU256 { numer, denom }
47    }
48
49    /// Creates a new ratio `t / 1`.
50    #[inline]
51    pub const fn from_u256(t: U256) -> RationalU256 {
52        RationalU256::new_raw(t, U256::one())
53    }
54
55    /// Tells whether the numerator is zero.
56    #[inline]
57    pub fn is_zero(&self) -> bool {
58        self.numer.is_zero()
59    }
60
61    /// Creates a new ratio `0 / 1`.
62    #[inline]
63    pub const fn zero() -> RationalU256 {
64        RationalU256::new_raw(U256::zero(), U256::one())
65    }
66
67    /// Creates a new ratio `1 / 1`.
68    #[inline]
69    pub const fn one() -> RationalU256 {
70        RationalU256::new_raw(U256::one(), U256::one())
71    }
72
73    /// Rounds down the ratio into an unsigned 256-bit integer.
74    #[inline]
75    pub fn into_u256(self) -> U256 {
76        self.numer / self.denom
77    }
78
79    /// Computes `self - rhs` and saturates the result to zero when `self` is less than `rhs`.
80    ///
81    /// Returns `self - rhs` when `self > rhs`, returns zero otherwise.
82    #[inline]
83    pub fn saturating_sub(self, rhs: RationalU256) -> Self {
84        if self.denom == rhs.denom {
85            let (numer, overflowing) = self.numer.overflowing_sub(&rhs.numer);
86            return if overflowing {
87                RationalU256::zero()
88            } else {
89                RationalU256::new(numer, self.denom)
90            };
91        }
92
93        let gcd = self.denom.gcd(&rhs.denom);
94        let lcm = &self.denom * (&rhs.denom / gcd);
95        let lhs_numer = &self.numer * (&lcm / self.denom);
96        let rhs_numer = &rhs.numer * (&lcm / &rhs.denom);
97
98        let (numer, overflowing) = lhs_numer.overflowing_sub(&rhs_numer);
99        if overflowing {
100            RationalU256::zero()
101        } else {
102            RationalU256::new(numer, lcm)
103        }
104    }
105
106    /// Computes `self - rhs` and saturates the result to zero when `self` is less than `rhs`.
107    ///
108    /// Returns `self - rhs` when `self > rhs`, returns zero otherwise.
109    #[inline]
110    pub fn saturating_sub_u256(self, rhs: U256) -> Self {
111        let (numer, overflowing) = self.numer.overflowing_sub(&(&self.denom * rhs));
112        if overflowing {
113            RationalU256::zero()
114        } else {
115            RationalU256::new_raw(numer, self.denom)
116        }
117    }
118
119    /// Puts self into lowest terms, with denom > 0.
120    fn reduce(&mut self) {
121        let g = self.numer.gcd(&self.denom);
122        self.numer = &self.numer / &g;
123        self.denom = &self.denom / &g;
124    }
125}
126
127// a/b * c/d = (a/gcd_ad)*(c/gcd_bc) / ((d/gcd_ad)*(b/gcd_bc))
128impl Mul<&RationalU256> for &RationalU256 {
129    type Output = RationalU256;
130    #[inline]
131    fn mul(self, rhs: &RationalU256) -> RationalU256 {
132        let gcd_ad = self.numer.gcd(&rhs.denom);
133        let gcd_bc = self.denom.gcd(&rhs.numer);
134
135        RationalU256::new_raw(
136            (&self.numer / &gcd_ad) * (&rhs.numer / &gcd_bc),
137            (&self.denom / gcd_bc) * (&rhs.denom / gcd_ad),
138        )
139    }
140}
141
142impl Mul<RationalU256> for &RationalU256 {
143    type Output = RationalU256;
144    #[inline]
145    fn mul(self, rhs: RationalU256) -> RationalU256 {
146        self.mul(&rhs)
147    }
148}
149
150impl Mul<&RationalU256> for RationalU256 {
151    type Output = RationalU256;
152    #[inline]
153    fn mul(self, rhs: &RationalU256) -> RationalU256 {
154        (&self).mul(rhs)
155    }
156}
157
158impl Mul<RationalU256> for RationalU256 {
159    type Output = RationalU256;
160    #[inline]
161    fn mul(self, rhs: RationalU256) -> RationalU256 {
162        (&self).mul(&rhs)
163    }
164}
165
166// a/b * c/1 = (a*c) / (b*1) = (a*c) / b
167impl Mul<&U256> for &RationalU256 {
168    type Output = RationalU256;
169    #[inline]
170    fn mul(self, rhs: &U256) -> RationalU256 {
171        let gcd = self.denom.gcd(rhs);
172        RationalU256::new_raw(&self.numer * (rhs.div(&gcd)), (&self.denom).div(gcd))
173    }
174}
175
176impl Mul<U256> for &RationalU256 {
177    type Output = RationalU256;
178    #[inline]
179    fn mul(self, rhs: U256) -> RationalU256 {
180        self.mul(&rhs)
181    }
182}
183
184impl Mul<U256> for RationalU256 {
185    type Output = RationalU256;
186    #[inline]
187    fn mul(self, rhs: U256) -> RationalU256 {
188        (&self).mul(&rhs)
189    }
190}
191
192impl Mul<&U256> for RationalU256 {
193    type Output = RationalU256;
194    #[inline]
195    fn mul(self, rhs: &U256) -> RationalU256 {
196        (&self).mul(rhs)
197    }
198}
199
200// (a/b) / (c/d) = (a/gcd_ac)*(d/gcd_bd) / ((c/gcd_ac)*(b/gcd_bd))
201impl Div<&RationalU256> for &RationalU256 {
202    type Output = RationalU256;
203    #[inline]
204    fn div(self, rhs: &RationalU256) -> RationalU256 {
205        let gcd_ac = self.numer.gcd(&rhs.numer);
206        let gcd_bd = self.denom.gcd(&rhs.denom);
207        RationalU256::new_raw(
208            (&self.numer / &gcd_ac) * (&rhs.denom / &gcd_bd),
209            (&self.denom / gcd_bd) * (&rhs.numer / gcd_ac),
210        )
211    }
212}
213
214impl Div<RationalU256> for RationalU256 {
215    type Output = RationalU256;
216
217    #[inline]
218    fn div(self, rhs: RationalU256) -> RationalU256 {
219        (&self).div(&rhs)
220    }
221}
222
223impl Div<RationalU256> for &RationalU256 {
224    type Output = RationalU256;
225
226    #[inline]
227    fn div(self, rhs: RationalU256) -> RationalU256 {
228        self.div(&rhs)
229    }
230}
231
232impl Div<&RationalU256> for RationalU256 {
233    type Output = RationalU256;
234
235    #[inline]
236    fn div(self, rhs: &RationalU256) -> RationalU256 {
237        (&self).div(rhs)
238    }
239}
240
241// (a/b) / (c/1) = (a*1) / (b*c) = a / (b*c)
242impl Div<&U256> for &RationalU256 {
243    type Output = RationalU256;
244
245    #[inline]
246    fn div(self, rhs: &U256) -> RationalU256 {
247        let gcd = self.numer.gcd(rhs);
248        RationalU256::new_raw(&self.numer / &gcd, &self.denom * (rhs / gcd))
249    }
250}
251
252impl Div<U256> for RationalU256 {
253    type Output = RationalU256;
254
255    #[inline]
256    fn div(self, rhs: U256) -> RationalU256 {
257        (&self).div(&rhs)
258    }
259}
260
261impl Div<&U256> for RationalU256 {
262    type Output = RationalU256;
263
264    #[inline]
265    fn div(self, rhs: &U256) -> RationalU256 {
266        (&self).div(rhs)
267    }
268}
269
270impl Div<U256> for &RationalU256 {
271    type Output = RationalU256;
272
273    #[inline]
274    fn div(self, rhs: U256) -> RationalU256 {
275        (self).div(&rhs)
276    }
277}
278
279impl Add<&RationalU256> for &RationalU256 {
280    type Output = RationalU256;
281    #[inline]
282    fn add(self, rhs: &RationalU256) -> RationalU256 {
283        if self.denom == rhs.denom {
284            RationalU256::new(&self.numer + &rhs.numer, self.denom.clone())
285        } else {
286            let gcd = self.denom.gcd(&rhs.denom);
287            let lcm = &self.denom * (&rhs.denom / gcd);
288            let lhs_numer = &self.numer * (&lcm / &self.denom);
289            let rhs_numer = &rhs.numer * (&lcm / &rhs.denom);
290
291            RationalU256::new(lhs_numer + rhs_numer, lcm)
292        }
293    }
294}
295
296impl Add<RationalU256> for RationalU256 {
297    type Output = RationalU256;
298    #[inline]
299    fn add(self, rhs: RationalU256) -> RationalU256 {
300        (&self).add(&rhs)
301    }
302}
303
304impl Add<&RationalU256> for RationalU256 {
305    type Output = RationalU256;
306    #[inline]
307    fn add(self, rhs: &RationalU256) -> RationalU256 {
308        (&self).add(rhs)
309    }
310}
311
312impl Add<RationalU256> for &RationalU256 {
313    type Output = RationalU256;
314    #[inline]
315    fn add(self, rhs: RationalU256) -> RationalU256 {
316        (self).add(&rhs)
317    }
318}
319
320impl Add<&U256> for &RationalU256 {
321    type Output = RationalU256;
322    #[inline]
323    fn add(self, rhs: &U256) -> RationalU256 {
324        RationalU256::new_raw(&self.numer + (&self.denom * rhs), self.denom.clone())
325    }
326}
327
328impl Add<U256> for RationalU256 {
329    type Output = RationalU256;
330    #[inline]
331    fn add(self, rhs: U256) -> RationalU256 {
332        (&self).add(&rhs)
333    }
334}
335
336impl Add<&U256> for RationalU256 {
337    type Output = RationalU256;
338    #[inline]
339    fn add(self, rhs: &U256) -> RationalU256 {
340        (&self).add(rhs)
341    }
342}
343
344impl Add<U256> for &RationalU256 {
345    type Output = RationalU256;
346    #[inline]
347    fn add(self, rhs: U256) -> RationalU256 {
348        self.add(&rhs)
349    }
350}
351
352impl Sub<&RationalU256> for &RationalU256 {
353    type Output = RationalU256;
354    #[inline]
355    fn sub(self, rhs: &RationalU256) -> RationalU256 {
356        if self.denom == rhs.denom {
357            RationalU256::new(&self.numer - &rhs.numer, self.denom.clone())
358        } else {
359            let gcd = self.denom.gcd(&rhs.denom);
360            let lcm = &self.denom * (&rhs.denom / gcd);
361            let lhs_numer = &self.numer * (&lcm / &self.denom);
362            let rhs_numer = &rhs.numer * (&lcm / &rhs.denom);
363
364            RationalU256::new(lhs_numer - rhs_numer, lcm)
365        }
366    }
367}
368
369impl Sub<RationalU256> for RationalU256 {
370    type Output = RationalU256;
371    #[inline]
372    fn sub(self, rhs: RationalU256) -> RationalU256 {
373        (&self).sub(&rhs)
374    }
375}
376
377impl Sub<&RationalU256> for RationalU256 {
378    type Output = RationalU256;
379    #[inline]
380    fn sub(self, rhs: &RationalU256) -> RationalU256 {
381        (&self).sub(rhs)
382    }
383}
384
385impl Sub<RationalU256> for &RationalU256 {
386    type Output = RationalU256;
387    #[inline]
388    fn sub(self, rhs: RationalU256) -> RationalU256 {
389        self.sub(&rhs)
390    }
391}
392
393impl Sub<&U256> for &RationalU256 {
394    type Output = RationalU256;
395    #[inline]
396    fn sub(self, rhs: &U256) -> RationalU256 {
397        RationalU256::new_raw(&self.numer - (&self.denom * rhs), self.denom.clone())
398    }
399}
400
401impl Sub<U256> for RationalU256 {
402    type Output = RationalU256;
403    #[inline]
404    fn sub(self, rhs: U256) -> RationalU256 {
405        (&self).sub(&rhs)
406    }
407}
408
409impl Sub<&U256> for RationalU256 {
410    type Output = RationalU256;
411    #[inline]
412    fn sub(self, rhs: &U256) -> RationalU256 {
413        (&self).sub(rhs)
414    }
415}
416
417impl Sub<U256> for &RationalU256 {
418    type Output = RationalU256;
419    #[inline]
420    fn sub(self, rhs: U256) -> RationalU256 {
421        self.sub(&rhs)
422    }
423}
424
425impl PartialOrd for RationalU256 {
426    fn partial_cmp(&self, other: &RationalU256) -> Option<Ordering> {
427        Some(self.cmp(other))
428    }
429}
430
431impl Ord for RationalU256 {
432    fn cmp(&self, other: &RationalU256) -> Ordering {
433        let gcd = self.denom.gcd(&other.denom);
434        let lhs = &self.numer * (&other.denom / &gcd);
435        let rhs = &other.numer * (&self.denom / &gcd);
436        lhs.cmp(&rhs)
437    }
438}
ckb_rational/lib.rs

ckb_rational/
lib.rs
