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