bigdecimal/arithmetic/
mod.rs

Help
1//! arithmetic routines
2
3use crate::*;
4use num_traits::CheckedSub;
5
6pub(crate) mod addition;
7pub(crate) mod sqrt;
8pub(crate) mod cbrt;
9pub(crate) mod inverse;
10
11/// Return 10^pow
12///
13/// Try to calculate this with fewest number of allocations
14///
15pub(crate) fn ten_to_the(pow: u64) -> BigInt {
16    ten_to_the_uint(pow).into()
17}
18
19/// Return 10^{pow} as u64
20pub(crate) fn ten_to_the_u64(pow: u8) -> u64 {
21    debug_assert!(pow < 20);
22    10u64.pow(pow as u32)
23}
24
25/// Return 10^pow
26pub(crate) fn ten_to_the_uint(pow: u64) -> BigUint {
27    if pow < 20 {
28        return BigUint::from(10u64.pow(pow as u32));
29    }
30
31    // linear case of 10^pow = 10^(19 * count + rem)
32    if pow < 590 {
33        let ten_to_nineteen = 10u64.pow(19);
34
35        // count factors of 19
36        let (count, rem) = pow.div_rem(&19);
37
38        let mut res = BigUint::from(ten_to_nineteen);
39        for _ in 1..count {
40            res *= ten_to_nineteen;
41        }
42        if rem != 0 {
43            res *= 10u64.pow(rem as u32);
44        }
45
46        return res;
47    }
48
49    // use recursive algorithm where linear case might be too slow
50    let (quotient, rem) = pow.div_rem(&16);
51    let x = ten_to_the_uint(quotient);
52
53    let x2 = &x * &x;
54    let x4 = &x2 * &x2;
55    let x8 = &x4 * &x4;
56    let res = &x8 * &x8;
57
58    if rem == 0 {
59        res
60    } else {
61        res * 10u64.pow(rem as u32)
62    }
63}
64
65pub(crate) fn multiply_by_ten_to_the_uint<T, P>(n: &mut T, pow: P)
66    where T: MulAssign<u64> + MulAssign<BigUint>,
67          P: ToPrimitive
68{
69    let pow = pow.to_u64().expect("exponent overflow error");
70    if pow < 20 {
71        *n *= 10u64.pow(pow as u32);
72    } else {
73        *n *= ten_to_the_uint(pow);
74    }
75
76}
77
78/// Return number of decimal digits in integer
79pub(crate) fn count_decimal_digits(int: &BigInt) -> u64 {
80    count_decimal_digits_uint(int.magnitude())
81}
82
83/// Return number of decimal digits in unsigned integer
84pub(crate) fn count_decimal_digits_uint(uint: &BigUint) -> u64 {
85    if uint.is_zero() {
86        return 1;
87    }
88    let mut digits = (uint.bits() as f64 / LOG2_10) as u64;
89    // guess number of digits based on number of bits in UInt
90    let mut num = ten_to_the_uint(digits);
91    while *uint >= num {
92        num *= 10u8;
93        digits += 1;
94    }
95    digits
96}
97
98
99/// Return difference of two numbers, returning diff as u64
100pub(crate) fn diff<T>(a: T, b: T) -> (Ordering, u64)
101where
102    T: ToPrimitive + CheckedSub + stdlib::cmp::Ord
103{
104    use stdlib::cmp::Ordering::*;
105
106    let (ord, diff) = checked_diff(a, b);
107
108    (ord, diff.expect("subtraction overflow"))
109}
110
111/// Return difference of two numbers. If num doesn't fit in u64, return None
112pub(crate) fn checked_diff<T>(a: T, b: T) -> (Ordering, Option<u64>)
113where
114    T: ToPrimitive + CheckedSub + stdlib::cmp::Ord
115{
116    use stdlib::cmp::Ordering::*;
117
118    let _try_subtracting = |x:T, y:T| x.checked_sub(&y).and_then(|diff| diff.to_u64());
119
120    match a.cmp(&b) {
121        Less => (Less, _try_subtracting(b, a)),
122        Greater => (Greater, _try_subtracting(a, b)),
123        Equal => (Equal, Some(0)),
124    }
125}
126
127/// Return difference of two numbers, returning diff as usize
128#[allow(dead_code)]
129pub(crate) fn diff_usize(a: usize, b: usize) -> (Ordering, usize) {
130    use stdlib::cmp::Ordering::*;
131
132    match a.cmp(&b) {
133        Less => (Less, b - a),
134        Greater => (Greater, a - b),
135        Equal => (Equal, 0),
136    }
137}
138
139/// Return absolute difference between two numbers
140#[cfg(rustc_1_60)]
141#[allow(clippy::incompatible_msrv)]
142#[allow(dead_code)]
143pub(crate) fn abs_diff(x: i64, y: i64) -> u64 {
144    x.abs_diff(y)
145}
146
147#[cfg(not(rustc_1_60))]
148#[allow(dead_code)]
149pub(crate) fn abs_diff(x: i64, y: i64) -> u64 {
150    (x as i128 - y as i128).to_u64().unwrap_or(0)
151}
152
153
154/// Add carry to given number, returning trimmed value and storing overflow back in carry
155///
156pub(crate) fn add_carry(n: u8, carry: &mut u8) -> u8 {
157    let s = n + *carry;
158    if s < 10 {
159        *carry = 0;
160        s
161    } else {
162        debug_assert!(s < 20);
163        *carry = 1;
164        s - 10
165    }
166}
167
168
169/// If n is greater than 10, split and store overflow in carry
170///
171/// No action if n is less than 10.
172///
173/// Carry is not allowed to be 1 if n is two digits
174///
175pub(crate) fn store_carry(n: u8, carry: &mut u8) -> u8 {
176    if n < 10 {
177        n
178    } else {
179        debug_assert!(n < 20);
180        debug_assert_eq!(carry, &0);
181        *carry = 1;
182        n - 10
183    }
184}
185
186
187/// Extend destination vector with values in D, adding carry while carry is not zero
188///
189/// If carry overflows, it is NOT pushed into the destination vector.
190///
191pub(crate) fn extend_adding_with_carry<D: Iterator<Item=u8>>(
192    dest: &mut Vec<u8>,
193    mut digits: D,
194    carry: &mut u8,
195) {
196    while *carry != 0 {
197        match digits.next() {
198            Some(d) => {
199                dest.push(add_carry(d, carry))
200            }
201            None => {
202                return;
203            }
204        }
205    }
206    dest.extend(digits);
207}
bigdecimal/arithmetic/mod.rs

bigdecimal/arithmetic/
mod.rs
