stv_rs/arithmetic/
exact.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 providing exact arithmetic, implementing the [`Integer`] trait for
16//! [`i64`] and [`BigInt`], and the [`Rational`] trait for [`Ratio<I>`].
17
18use super::{Integer, IntegerRef, Rational, RationalRef};
19use num::bigint::ToBigInt;
20use num::rational::Ratio;
21use num::traits::{NumAssign, ToPrimitive, Zero};
22use num::BigInt;
23use std::fmt::{Debug, Display};
24
25#[cfg(test)]
26impl Integer for i64 {
27    #[inline(always)]
28    fn from_usize(i: usize) -> Self {
29        i as i64
30    }
31
32    fn get_positive_test_values() -> Vec<Self> {
33        let mut result = Vec::new();
34        for i in 0..=30 {
35            result.push(1 << i);
36            result.push(0x7FFF_FFFF ^ (1 << i));
37        }
38        result
39    }
40}
41
42#[cfg(test)]
43impl IntegerRef<i64> for &i64 {}
44
45impl Integer for BigInt {
46    fn from_usize(i: usize) -> Self {
47        BigInt::from(i)
48    }
49
50    #[cfg(test)]
51    fn get_positive_test_values() -> Vec<Self> {
52        let mut result = Vec::new();
53        for i in 0..64 {
54            result.push(BigInt::from(1u64 << i));
55            result.push(BigInt::from(!(1u64 << i)));
56        }
57        result
58    }
59}
60
61impl IntegerRef<BigInt> for &BigInt {}
62
63impl<I> RationalRef<&I, Ratio<I>> for &Ratio<I> where I: Clone + num::Integer {}
64
65impl<I> Rational<I> for Ratio<I>
66where
67    I: Display + Debug,
68    I: num::Integer,
69    I: ToPrimitive + ToBigInt,
70    I: Integer + NumAssign,
71    for<'a> &'a I: IntegerRef<I>,
72{
73    fn from_int(i: I) -> Self {
74        Ratio::from_integer(i)
75    }
76
77    fn ratio_i(num: I, denom: I) -> Self {
78        Ratio::new(num, denom)
79    }
80
81    fn to_f64(&self) -> f64 {
82        ToPrimitive::to_f64(self).unwrap()
83    }
84
85    fn epsilon() -> Self {
86        Self::zero()
87    }
88
89    fn is_exact() -> bool {
90        true
91    }
92
93    fn description() -> &'static str {
94        "exact rational arithmetic"
95    }
96
97    fn div_up_as_keep_factor(&self, rhs: &Self) -> Self {
98        self / rhs
99    }
100
101    #[cfg(test)]
102    fn get_positive_test_values() -> Vec<Self> {
103        let mut result = Vec::new();
104        for i in 0..=30 {
105            result.push(Self::ratio(1 << i, 1));
106        }
107        for i in 0..=30 {
108            result.push(Self::ratio(1, 1 << i));
109        }
110        for i in 0..=30 {
111            result.push(Self::ratio(0x7FFF_FFFF ^ (1 << i), 1));
112        }
113        for i in 0..=30 {
114            result.push(Self::ratio(1, 0x7FFF_FFFF ^ (1 << i)));
115        }
116        result
117    }
118}
119
120#[cfg(test)]
121mod test {
122    use super::*;
123    use crate::{
124        big_integer_tests, big_numeric_tests, integer_tests, numeric_benchmarks, numeric_tests,
125    };
126    use num::traits::One;
127    use num::BigRational;
128
129    fn make_ratio(num: i64, denom: i64) -> BigRational {
130        BigRational::ratio_i(BigInt::from(num), BigInt::from(denom))
131    }
132
133    integer_tests!(
134        BigInt,
135        testi_values_are_positive,
136        testi_is_zero,
137        testi_zero_is_add_neutral,
138        testi_add_is_commutative,
139        testi_opposite,
140        testi_sub_self,
141        testi_add_sub,
142        testi_sub_add,
143        testi_one_is_mul_neutral,
144        testi_mul_is_commutative,
145    );
146
147    big_integer_tests!(
148        BigInt,
149        Some(100_000),
150        testi_add_is_associative,
151        testi_mul_is_associative,
152        testi_mul_is_distributive,
153        testi_product,
154    );
155
156    numeric_tests!(
157        BigInt,
158        BigRational,
159        test_values_are_positive,
160        test_is_exact,
161        test_ratio,
162        test_ratio_invert,
163        test_is_zero,
164        test_zero_is_add_neutral,
165        test_add_is_commutative,
166        test_opposite,
167        test_sub_self,
168        test_add_sub,
169        test_sub_add,
170        test_one_is_mul_neutral,
171        test_mul_is_commutative,
172        test_mul_up_is_commutative,
173        test_mul_up_integers,
174        test_mul_up_wrt_mul,
175        test_one_is_div_up_neutral,
176        test_div_up_self,
177        test_mul_div_up,
178        test_mul_by_int,
179        test_mul_div_by_int,
180        test_references,
181        test_assign,
182    );
183
184    big_numeric_tests!(
185        BigInt,
186        BigRational,
187        Some(100_000),
188        test_add_is_associative,
189        test_mul_is_associative,
190        test_mul_is_distributive,
191        test_mul_by_int_is_associative,
192        test_mul_by_int_is_distributive,
193        test_div_by_int_is_associative,
194        test_div_by_int_is_distributive,
195        test_sum,
196        test_product,
197    );
198
199    numeric_benchmarks!(
200        BigInt,
201        BigRational,
202        bench_add,
203        bench_sub,
204        bench_mul,
205        bench_div_up,
206    );
207
208    #[test]
209    fn test_description() {
210        assert_eq!(BigRational::description(), "exact rational arithmetic");
211    }
212
213    #[test]
214    fn test_display() {
215        assert_eq!(format!("{}", BigRational::zero()), "0");
216        assert_eq!(format!("{}", BigRational::one()), "1");
217        assert_eq!(format!("{}", make_ratio(0, 1)), "0");
218        assert_eq!(format!("{}", make_ratio(1, 1)), "1");
219        assert_eq!(format!("{}", make_ratio(1, 2)), "1/2");
220        assert_eq!(format!("{}", make_ratio(1, 23456789)), "1/23456789");
221        assert_eq!(format!("{}", make_ratio(123456789, 1)), "123456789");
222        assert_eq!(format!("{}", make_ratio(-1, 1)), "-1");
223        assert_eq!(format!("{}", make_ratio(-1, 2)), "-1/2");
224        assert_eq!(format!("{}", make_ratio(2, 2)), "1");
225        assert_eq!(format!("{}", make_ratio(60, 14)), "30/7");
226    }
227
228    #[test]
229    fn test_display_test_values() {
230        #[rustfmt::skip]
231        let expected_displays = [
232            "1", "2", "4", "8", "16", "32", "64", "128", "256", "512", "1024", "2048", "4096",
233            "8192", "16384", "32768", "65536", "131072", "262144", "524288", "1048576", "2097152",
234            "4194304", "8388608", "16777216", "33554432", "67108864", "134217728", "268435456",
235            "536870912", "1073741824",
236            "1", "1/2", "1/4", "1/8", "1/16", "1/32", "1/64", "1/128", "1/256", "1/512", "1/1024",
237            "1/2048", "1/4096", "1/8192", "1/16384", "1/32768", "1/65536", "1/131072", "1/262144",
238            "1/524288", "1/1048576", "1/2097152", "1/4194304", "1/8388608", "1/16777216",
239            "1/33554432", "1/67108864", "1/134217728", "1/268435456", "1/536870912", "1/1073741824",
240            "2147483646", "2147483645", "2147483643", "2147483639", "2147483631", "2147483615",
241            "2147483583", "2147483519", "2147483391", "2147483135", "2147482623", "2147481599",
242            "2147479551", "2147475455", "2147467263", "2147450879", "2147418111", "2147352575",
243            "2147221503", "2146959359", "2146435071", "2145386495", "2143289343", "2139095039",
244            "2130706431", "2113929215", "2080374783", "2013265919", "1879048191", "1610612735",
245            "1073741823",
246            "1/2147483646", "1/2147483645", "1/2147483643", "1/2147483639", "1/2147483631",
247            "1/2147483615", "1/2147483583", "1/2147483519", "1/2147483391", "1/2147483135",
248            "1/2147482623", "1/2147481599", "1/2147479551", "1/2147475455", "1/2147467263",
249            "1/2147450879", "1/2147418111", "1/2147352575", "1/2147221503", "1/2146959359",
250            "1/2146435071", "1/2145386495", "1/2143289343", "1/2139095039", "1/2130706431",
251            "1/2113929215", "1/2080374783", "1/2013265919", "1/1879048191", "1/1610612735",
252            "1/1073741823",
253        ];
254        let actual_displays: Vec<String> = BigRational::get_positive_test_values()
255            .iter()
256            .map(|x| format!("{x}"))
257            .collect();
258        assert_eq!(actual_displays, expected_displays);
259    }
260}
stv_rs/arithmetic/exact.rs

stv_rs/arithmetic/
exact.rs
