stv_rs/arithmetic/
fixed_big.rs

1// Copyright 2023 Google LLC
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//! Module for fixed-point arithmetic, defined in terms of *decimal* places.
16//! For now, it only implements 9 decimal places (i.e. with a factor `10^-9`).
17//! This implementation is backed by a [`BigInt`].
18
19use super::{Rational, RationalRef};
20use num::bigint::Sign;
21use num::traits::{One, Zero};
22use num::{BigInt, BigRational, Integer, Signed};
23use std::fmt::{Debug, Display};
24use std::iter::{Product, Sum};
25use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};
26
27/// A fixed-point decimal arithmetic for 9 decimal places. This type represents
28/// a number `x` by the integer `x * 10^9`, backed by a [`BigInt`].
29#[derive(Clone, Debug, PartialEq, Eq, PartialOrd)]
30pub struct BigFixedDecimal9(BigInt);
31
32impl BigFixedDecimal9 {
33    const FACTOR: i64 = 1_000_000_000;
34}
35
36impl Display for BigFixedDecimal9 {
37    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
38        let sign = match self.0.sign() {
39            Sign::Plus | Sign::NoSign => "",
40            Sign::Minus => "-",
41        };
42        let (i, rem) = self.0.abs().div_rem(&BigInt::from(Self::FACTOR));
43        write!(f, "{sign}{i}.{rem:09}")
44    }
45}
46
47impl Zero for BigFixedDecimal9 {
48    fn zero() -> Self {
49        BigFixedDecimal9(BigInt::zero())
50    }
51    fn is_zero(&self) -> bool {
52        self.0.is_zero()
53    }
54}
55impl One for BigFixedDecimal9 {
56    fn one() -> Self {
57        BigFixedDecimal9(BigInt::from(Self::FACTOR))
58    }
59}
60
61impl Add for BigFixedDecimal9 {
62    type Output = Self;
63    fn add(self, rhs: Self) -> Self {
64        BigFixedDecimal9(self.0 + rhs.0)
65    }
66}
67impl Sub for BigFixedDecimal9 {
68    type Output = Self;
69    fn sub(self, rhs: Self) -> Self {
70        BigFixedDecimal9(self.0 - rhs.0)
71    }
72}
73impl Mul for BigFixedDecimal9 {
74    type Output = Self;
75    fn mul(self, rhs: Self) -> Self {
76        BigFixedDecimal9((self.0 * rhs.0) / Self::FACTOR)
77    }
78}
79impl Mul<BigInt> for BigFixedDecimal9 {
80    type Output = Self;
81    fn mul(self, rhs: BigInt) -> Self {
82        BigFixedDecimal9(self.0 * rhs)
83    }
84}
85impl Div<BigInt> for BigFixedDecimal9 {
86    type Output = Self;
87    fn div(self, rhs: BigInt) -> Self {
88        BigFixedDecimal9(self.0 / rhs)
89    }
90}
91
92impl Add<&'_ Self> for BigFixedDecimal9 {
93    type Output = Self;
94    fn add(self, rhs: &'_ Self) -> Self {
95        BigFixedDecimal9(self.0 + &rhs.0)
96    }
97}
98impl Sub<&'_ Self> for BigFixedDecimal9 {
99    type Output = Self;
100    fn sub(self, rhs: &'_ Self) -> Self {
101        BigFixedDecimal9(self.0 - &rhs.0)
102    }
103}
104impl Mul<&'_ Self> for BigFixedDecimal9 {
105    type Output = Self;
106    fn mul(self, rhs: &'_ Self) -> Self {
107        BigFixedDecimal9((self.0 * &rhs.0) / Self::FACTOR)
108    }
109}
110
111impl Add<&'_ BigFixedDecimal9> for &'_ BigFixedDecimal9 {
112    type Output = BigFixedDecimal9;
113    fn add(self, rhs: &'_ BigFixedDecimal9) -> BigFixedDecimal9 {
114        BigFixedDecimal9(&self.0 + &rhs.0)
115    }
116}
117impl Sub<&'_ BigFixedDecimal9> for &'_ BigFixedDecimal9 {
118    type Output = BigFixedDecimal9;
119    fn sub(self, rhs: &'_ BigFixedDecimal9) -> BigFixedDecimal9 {
120        BigFixedDecimal9(&self.0 - &rhs.0)
121    }
122}
123impl Mul<&'_ BigFixedDecimal9> for &'_ BigFixedDecimal9 {
124    type Output = BigFixedDecimal9;
125    fn mul(self, rhs: &'_ BigFixedDecimal9) -> BigFixedDecimal9 {
126        BigFixedDecimal9((&self.0 * &rhs.0) / BigFixedDecimal9::FACTOR)
127    }
128}
129impl Mul<&'_ BigInt> for &'_ BigFixedDecimal9 {
130    type Output = BigFixedDecimal9;
131    fn mul(self, rhs: &'_ BigInt) -> BigFixedDecimal9 {
132        BigFixedDecimal9(&self.0 * rhs)
133    }
134}
135impl Div<&'_ BigInt> for &'_ BigFixedDecimal9 {
136    type Output = BigFixedDecimal9;
137    fn div(self, rhs: &'_ BigInt) -> BigFixedDecimal9 {
138        BigFixedDecimal9(&self.0 / rhs)
139    }
140}
141
142impl AddAssign for BigFixedDecimal9 {
143    fn add_assign(&mut self, rhs: Self) {
144        self.0 += rhs.0
145    }
146}
147impl SubAssign for BigFixedDecimal9 {
148    fn sub_assign(&mut self, rhs: Self) {
149        self.0 -= rhs.0
150    }
151}
152impl MulAssign for BigFixedDecimal9 {
153    fn mul_assign(&mut self, rhs: Self) {
154        self.0 *= rhs.0;
155        self.0 /= Self::FACTOR;
156    }
157}
158
159impl AddAssign<&'_ Self> for BigFixedDecimal9 {
160    fn add_assign(&mut self, rhs: &'_ Self) {
161        self.0 += &rhs.0
162    }
163}
164impl SubAssign<&'_ Self> for BigFixedDecimal9 {
165    fn sub_assign(&mut self, rhs: &'_ Self) {
166        self.0 -= &rhs.0
167    }
168}
169impl MulAssign<&'_ Self> for BigFixedDecimal9 {
170    fn mul_assign(&mut self, rhs: &'_ Self) {
171        self.0 *= &rhs.0;
172        self.0 /= Self::FACTOR;
173    }
174}
175impl DivAssign<&'_ BigInt> for BigFixedDecimal9 {
176    fn div_assign(&mut self, rhs: &'_ BigInt) {
177        self.0 /= rhs;
178    }
179}
180
181impl Sum for BigFixedDecimal9 {
182    fn sum<I>(iter: I) -> Self
183    where
184        I: Iterator<Item = Self>,
185    {
186        BigFixedDecimal9(iter.map(|item| item.0).sum())
187    }
188}
189
190impl Product for BigFixedDecimal9 {
191    fn product<I>(iter: I) -> Self
192    where
193        I: Iterator<Item = Self>,
194    {
195        iter.fold(Self::one(), |acc, x| acc * x)
196    }
197}
198
199impl<'a> Sum<&'a Self> for BigFixedDecimal9 {
200    fn sum<I>(iter: I) -> Self
201    where
202        I: Iterator<Item = &'a Self>,
203    {
204        BigFixedDecimal9(iter.map(|item| &item.0).sum())
205    }
206}
207
208impl RationalRef<&BigInt, BigFixedDecimal9> for &BigFixedDecimal9 {}
209
210impl Rational<BigInt> for BigFixedDecimal9 {
211    fn from_int(i: BigInt) -> Self {
212        BigFixedDecimal9(i * Self::FACTOR)
213    }
214
215    fn ratio_i(num: BigInt, denom: BigInt) -> Self {
216        BigFixedDecimal9((num * Self::FACTOR) / denom)
217    }
218
219    fn to_f64(&self) -> f64 {
220        Rational::to_f64(&BigRational::new(
221            self.0.clone(),
222            BigInt::from(Self::FACTOR),
223        ))
224    }
225
226    fn epsilon() -> Self {
227        BigFixedDecimal9(BigInt::from(1))
228    }
229
230    fn is_exact() -> bool {
231        false
232    }
233
234    fn description() -> &'static str {
235        "fixed-point decimal arithmetic (9 places)"
236    }
237
238    fn mul_up(&self, rhs: &Self) -> Self {
239        BigFixedDecimal9((&self.0 * &rhs.0 + Self::FACTOR - 1) / Self::FACTOR)
240    }
241
242    fn div_up_as_keep_factor(&self, rhs: &Self) -> Self {
243        BigFixedDecimal9((&self.0 * Self::FACTOR + &rhs.0 - 1) / &rhs.0)
244    }
245
246    #[cfg(test)]
247    fn get_positive_test_values() -> Vec<Self> {
248        let mut result = Vec::new();
249        for i in 0..=62 {
250            result.push(BigFixedDecimal9(BigInt::from(1i64 << i)));
251        }
252        for i in 0..=62 {
253            result.push(BigFixedDecimal9(BigInt::from(
254                0x7FFF_FFFF_FFFF_FFFF_i64 - (1 << i),
255            )));
256        }
257        result
258    }
259}
260
261#[cfg(test)]
262mod test {
263    use super::*;
264    use crate::{big_numeric_tests, numeric_benchmarks, numeric_tests};
265
266    numeric_tests!(
267        BigInt,
268        BigFixedDecimal9,
269        test_values_are_positive,
270        test_is_exact,
271        test_ratio,
272        test_ratio_invert => fail(r"assertion `left == right` failed: R::ratio(1, a) * a != 1 for 3
273  left: BigFixedDecimal9(999999999)
274 right: BigFixedDecimal9(1000000000)"),
275        test_is_zero,
276        test_zero_is_add_neutral,
277        test_add_is_commutative,
278        test_opposite,
279        test_sub_self,
280        test_add_sub,
281        test_sub_add,
282        test_one_is_mul_neutral,
283        test_mul_is_commutative,
284        test_mul_up_is_commutative,
285        test_mul_up_integers,
286        test_mul_up_wrt_mul,
287        test_one_is_div_up_neutral,
288        test_div_up_self,
289        test_mul_div_up => fail(r"assertion `left == right` failed: div_up(a * b, b) != a for 0.000000001, 0.000000001
290  left: BigFixedDecimal9(0)
291 right: BigFixedDecimal9(1)"),
292        test_mul_by_int,
293        test_mul_div_by_int,
294        test_references,
295        test_assign,
296    );
297
298    big_numeric_tests!(
299        BigInt,
300        BigFixedDecimal9,
301        None,
302        test_add_is_associative,
303        test_mul_is_associative => fail(r"assertion `left == right` failed: (a * b) * c != a * (b * c) for 0.000000001, 0.000000001, 1152921504.606846976
304  left: BigFixedDecimal9(0)
305 right: BigFixedDecimal9(1)"),
306        test_mul_is_distributive => fail(r"assertion `left == right` failed: a * (b + c) != (a * b) + (a * c) for 0.000000001, 0.033554432, 281474.976710656
307  left: BigFixedDecimal9(281475)
308 right: BigFixedDecimal9(281474)"),
309        test_mul_by_int_is_associative,
310        test_mul_by_int_is_distributive,
311        test_div_by_int_is_associative,
312        test_div_by_int_is_distributive => fail(r"assertion `left == right` failed: (a + b) / c != (a / c) + (b / c) for 0.000000001, 0.000000001, 2
313  left: BigFixedDecimal9(1)
314 right: BigFixedDecimal9(0)"),
315        test_sum,
316        test_product,
317    );
318
319    numeric_benchmarks!(
320        BigInt,
321        BigFixedDecimal9,
322        bench_add,
323        bench_sub,
324        bench_mul,
325        bench_div_up,
326    );
327
328    #[test]
329    fn test_description() {
330        assert_eq!(
331            BigFixedDecimal9::description(),
332            "fixed-point decimal arithmetic (9 places)"
333        );
334    }
335
336    #[test]
337    fn test_display() {
338        assert_eq!(format!("{}", BigFixedDecimal9::zero()), "0.000000000");
339        assert_eq!(format!("{}", BigFixedDecimal9::one()), "1.000000000");
340        assert_eq!(
341            format!("{}", BigFixedDecimal9(BigInt::from(0))),
342            "0.000000000"
343        );
344        assert_eq!(
345            format!("{}", BigFixedDecimal9(BigInt::from(1))),
346            "0.000000001"
347        );
348        assert_eq!(
349            format!("{}", BigFixedDecimal9(BigInt::from(1_000_000_000))),
350            "1.000000000"
351        );
352        assert_eq!(
353            format!("{}", BigFixedDecimal9(BigInt::from(1_234_567_890))),
354            "1.234567890"
355        );
356        assert_eq!(
357            format!("{}", BigFixedDecimal9(BigInt::from(-1))),
358            "-0.000000001"
359        );
360        assert_eq!(
361            format!("{}", BigFixedDecimal9(BigInt::from(-1_000_000_000))),
362            "-1.000000000"
363        );
364        assert_eq!(
365            format!("{}", BigFixedDecimal9(BigInt::from(10).pow(20))),
366            "100000000000.000000000"
367        );
368    }
369
370    #[test]
371    fn test_display_test_values() {
372        #[rustfmt::skip]
373        let expected_displays = [
374            "0.000000001", "0.000000002", "0.000000004", "0.000000008",
375            "0.000000016", "0.000000032", "0.000000064", "0.000000128",
376            "0.000000256", "0.000000512", "0.000001024", "0.000002048",
377            "0.000004096", "0.000008192", "0.000016384", "0.000032768",
378            "0.000065536", "0.000131072", "0.000262144", "0.000524288",
379            "0.001048576", "0.002097152", "0.004194304", "0.008388608",
380            "0.016777216", "0.033554432", "0.067108864", "0.134217728",
381            "0.268435456", "0.536870912", "1.073741824", "2.147483648",
382            "4.294967296", "8.589934592", "17.179869184", "34.359738368",
383            "68.719476736", "137.438953472", "274.877906944", "549.755813888",
384            "1099.511627776", "2199.023255552", "4398.046511104", "8796.093022208",
385            "17592.186044416", "35184.372088832", "70368.744177664", "140737.488355328",
386            "281474.976710656", "562949.953421312", "1125899.906842624", "2251799.813685248",
387            "4503599.627370496", "9007199.254740992", "18014398.509481984", "36028797.018963968",
388            "72057594.037927936", "144115188.075855872", "288230376.151711744",
389            "576460752.303423488", "1152921504.606846976", "2305843009.213693952",
390            "4611686018.427387904",
391            "9223372036.854775806", "9223372036.854775805", "9223372036.854775803",
392            "9223372036.854775799", "9223372036.854775791", "9223372036.854775775",
393            "9223372036.854775743", "9223372036.854775679", "9223372036.854775551",
394            "9223372036.854775295", "9223372036.854774783", "9223372036.854773759",
395            "9223372036.854771711", "9223372036.854767615", "9223372036.854759423",
396            "9223372036.854743039", "9223372036.854710271", "9223372036.854644735",
397            "9223372036.854513663", "9223372036.854251519", "9223372036.853727231",
398            "9223372036.852678655", "9223372036.850581503", "9223372036.846387199",
399            "9223372036.837998591", "9223372036.821221375", "9223372036.787666943",
400            "9223372036.720558079", "9223372036.586340351", "9223372036.317904895",
401            "9223372035.781033983", "9223372034.707292159", "9223372032.559808511",
402            "9223372028.264841215", "9223372019.674906623", "9223372002.495037439",
403            "9223371968.135299071", "9223371899.415822335", "9223371761.976868863",
404            "9223371487.098961919", "9223370937.343148031", "9223369837.831520255",
405            "9223367638.808264703", "9223363240.761753599", "9223354444.668731391",
406            "9223336852.482686975", "9223301668.110598143", "9223231299.366420479",
407            "9223090561.878065151", "9222809086.901354495", "9222246136.947933183",
408            "9221120237.041090559", "9218868437.227405311", "9214364837.600034815",
409            "9205357638.345293823", "9187343239.835811839", "9151314442.816847871",
410            "9079256848.778919935", "8935141660.703064063", "8646911284.551352319",
411            "8070450532.247928831", "6917529027.641081855", "4611686018.427387903"
412        ];
413        let actual_displays: Vec<String> = BigFixedDecimal9::get_positive_test_values()
414            .iter()
415            .map(|x| format!("{x}"))
416            .collect();
417        assert_eq!(actual_displays, expected_displays);
418    }
419
420    /// Check that [`BigFixedDecimal9`] correctly handles inputs that would
421    /// overflow with [`FixedDecimal9`], which is backed by [`i64`].
422    #[test]
423    fn test_i64_overflow() {
424        // The intermediate result of 10^19 is just between 2^63 and 2^64.
425        assert_eq!(
426            BigFixedDecimal9::from_int(5.into()) * BigFixedDecimal9::from_int(2.into()),
427            BigFixedDecimal9::from_int(10.into())
428        );
429        // The intermediate result is above 2^64.
430        assert_eq!(
431            BigFixedDecimal9::from_int(1_000.into()) * BigFixedDecimal9::from_int(1_000.into()),
432            BigFixedDecimal9::from_int(1_000_000.into())
433        );
434        // The final result exceeds 2^64.
435        assert_eq!(
436            BigFixedDecimal9::from_int(1_000_000.into())
437                * BigFixedDecimal9::from_int(1_000_000.into()),
438            BigFixedDecimal9::from_int(1_000_000_000_000_i64.into())
439        );
440    }
441}
stv_rs/arithmetic/fixed_big.rs

stv_rs/arithmetic/
fixed_big.rs
