Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- use std::u32;
- use std::u64;
- type U32DivModResult = (u32, u32);
- type U64DivModResult = (u64, u64);
- fn divmod(dividend: u32, divisor: u32) -> U32DivModResult {
- let quotient = dividend / divisor;
- let remainder = dividend % divisor;
- (quotient, remainder)
- }
- fn div_mod_u64_v9(numerator: u64, divisor: u64) -> U64DivModResult {
- let num_hi = (numerator >> 32) as u32;
- let num_lo = (numerator & u32::MAX as u64) as u32;
- let div_hi = (divisor >> 32) as u32;
- let div_lo = (divisor & u32::MAX as u64) as u32;
- if div_hi == 0 && num_hi == 0 {
- let (quotient, remainder) = divmod(num_lo, div_lo);
- return (quotient as u64, remainder as u64);
- }
- let mut res;
- let mut q1 = 0;
- if div_hi != 0 {
- res = divmod(num_hi, div_hi);
- q1 = res.0 as u64;
- }
- let mut r1_lo = q1 * div_lo as u64;
- let mut r1_hi = q1 * div_hi as u64 + (r1_lo >> 32);
- r1_lo = r1_lo & u32::MAX as u64;
- if r1_hi > num_hi as u64 || (r1_hi == num_hi as u64 && r1_lo > num_lo as u64) {
- q1 -= 1;
- r1_lo = q1 * div_lo as u64;
- r1_hi = q1 * div_hi as u64 + (r1_lo >> 32);
- r1_lo = r1_lo & u32::MAX as u64;
- }
- let rem1_hi = num_hi.wrapping_sub(r1_hi as u32);
- let (rem1_lo, borrow) = num_lo.overflowing_sub(r1_lo as u32);
- let rem2 = ((rem1_hi as u64) << 32) | rem1_lo as u64;
- let rem2 = if borrow {
- rem2.wrapping_sub(1 << 32)
- } else {
- rem2
- };
- res = divmod((rem2 >> 32) as u32, div_hi);
- let mut q2 = res.0 as u64;
- let mut r2_lo = q2 * div_lo as u64;
- let mut r2_hi = q2 * div_hi as u64 + (r2_lo >> 32);
- r2_lo = r2_lo & u32::MAX as u64;
- if r2_hi > rem1_hi as u64 || (r2_hi == rem1_hi as u64 && r2_lo > rem1_lo as u64) {
- q2 -= 1;
- r2_lo = q2 * div_lo as u64;
- r2_hi = q2 * div_hi as u64 + (r2_lo >> 32);
- r2_lo = r2_lo & u32::MAX as u64;
- }
- let remainder = rem2 - ((r2_hi << 32) | r2_lo);
- let quotient = (q1) + q2;
- (quotient, remainder)
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement