1 | #[cfg (feature = "no-panic" )] |
2 | use no_panic::no_panic; |
3 | |
4 | /// Multiply unsigned 128 bit integers, return upper 128 bits of the result |
5 | #[inline ] |
6 | #[cfg_attr (feature = "no-panic" , no_panic)] |
7 | fn u128_mulhi(x: u128, y: u128) -> u128 { |
8 | let x_lo: u64 = x as u64; |
9 | let x_hi: u64 = (x >> 64) as u64; |
10 | let y_lo: u64 = y as u64; |
11 | let y_hi: u64 = (y >> 64) as u64; |
12 | |
13 | // handle possibility of overflow |
14 | let carry: u128 = (x_lo as u128 * y_lo as u128) >> 64; |
15 | let m: u128 = x_lo as u128 * y_hi as u128 + carry; |
16 | let high1: u128 = m >> 64; |
17 | |
18 | let m_lo: u64 = m as u64; |
19 | let high2: u128 = (x_hi as u128 * y_lo as u128 + m_lo as u128) >> 64; |
20 | |
21 | x_hi as u128 * y_hi as u128 + high1 + high2 |
22 | } |
23 | |
24 | /// Divide `n` by 1e19 and return quotient and remainder |
25 | /// |
26 | /// Integer division algorithm is based on the following paper: |
27 | /// |
28 | /// T. Granlund and P. Montgomery, “Division by Invariant Integers Using Multiplication” |
29 | /// in Proc. of the SIGPLAN94 Conference on Programming Language Design and |
30 | /// Implementation, 1994, pp. 61–72 |
31 | /// |
32 | #[inline ] |
33 | #[cfg_attr (feature = "no-panic" , no_panic)] |
34 | pub fn udivmod_1e19(n: u128) -> (u128, u64) { |
35 | let d: u64 = 10_000_000_000_000_000_000_u64; // 10^19 |
36 | |
37 | let quot: u128 = if n < 1 << 83 { |
38 | ((n >> 19) as u64 / (d >> 19)) as u128 |
39 | } else { |
40 | u128_mulhi(x:n, y:156927543384667019095894735580191660403) >> 62 |
41 | }; |
42 | |
43 | let rem: u64 = (n - quot * d as u128) as u64; |
44 | debug_assert_eq!(quot, n / d as u128); |
45 | debug_assert_eq!(rem as u128, n % d as u128); |
46 | |
47 | (quot, rem) |
48 | } |
49 | |