1pub fn div_rem<const N: usize>(numerator: &[u64; N], divisor: &[u64; N]) -> ([u64; N], [u64; N]) {
17 let numerator_bits = bits(numerator);
18 let divisor_bits = bits(divisor);
19 assert_ne!(divisor_bits, 0, "division by zero");
20
21 if numerator_bits < divisor_bits {
22 return ([0; N], *numerator);
23 }
24
25 if divisor_bits <= 64 {
26 return div_rem_small(numerator, divisor[0]);
27 }
28
29 let numerator_words = numerator_bits.div_ceil(64);
30 let divisor_words = divisor_bits.div_ceil(64);
31 let n = divisor_words;
32 let m = numerator_words - divisor_words;
33
34 div_rem_knuth(numerator, divisor, n, m)
35}
36
37fn bits(arr: &[u64]) -> usize {
39 for (idx, v) in arr.iter().enumerate().rev() {
40 if *v > 0 {
41 return 64 - v.leading_zeros() as usize + 64 * idx;
42 }
43 }
44 0
45}
46
47fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N], [u64; N]) {
49 #[cfg(all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri)))]
53 {
54 div_rem_small_reciprocal(numerator, divisor)
55 }
56
57 #[cfg(not(all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))))]
60 {
61 div_rem_small_word(numerator, divisor)
62 }
63}
64
65#[cfg(any(
66 test,
67 not(all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri)))
68))]
69fn div_rem_small_word<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N], [u64; N]) {
70 let mut rem = 0u64;
71 let mut numerator = *numerator;
72 numerator.iter_mut().rev().for_each(|d| {
73 let (q, r) = div_rem_word(rem, *d, divisor);
74 *d = q;
75 rem = r;
76 });
77
78 let mut rem_padded = [0; N];
79 rem_padded[0] = rem;
80 (numerator, rem_padded)
81}
82
83#[cfg(any(
86 test,
87 all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
88))]
89fn div_rem_small_reciprocal<const N: usize>(
90 numerator: &[u64; N],
91 divisor: u64,
92) -> ([u64; N], [u64; N]) {
93 let shift = divisor.leading_zeros();
95 let divisor = divisor << shift;
96 let reciprocal = reciprocal_word(divisor);
97 let numerator = full_shl(numerator, shift);
98
99 let mut rem = numerator[N];
101 let mut quotient = [0; N];
102 for i in (0..N).rev() {
103 let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
104 quotient[i] = q;
105 rem = r;
106 }
107
108 let mut rem_padded = [0; N];
109 rem_padded[0] = rem >> shift;
110 (quotient, rem_padded)
111}
112
113#[cfg(any(
121 test,
122 all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
123))]
124fn reciprocal_word(divisor: u64) -> u64 {
125 debug_assert_eq!(divisor >> 63, 1);
126
127 const TABLE: [u16; 256] = {
130 let mut table = [0; 256];
131 let mut i = 0;
132 while i < 256 {
133 table[i] = (((1 << 19) - 3 * (1 << 8)) / (i as u32 + 256)) as u16;
134 i += 1;
135 }
136 table
137 };
138
139 let d0 = divisor & 1; let d9 = divisor >> 55; let d40 = (divisor >> 24) + 1; let d63 = (divisor >> 1) + d0; let v0 = u64::from(TABLE[(d9 & 0xff) as usize]);
147 let v1 = (v0 << 11) - ((v0 * v0 * d40) >> 40) - 1;
152 let v2 = (v1 << 13) + ((v1 * ((1 << 60) - v1 * d40)) >> 47);
153 let e = ((v2 >> 1) & d0.wrapping_neg()).wrapping_sub(v2.wrapping_mul(d63));
157 let v3 = (v2 << 31).wrapping_add(((u128::from(v2) * u128::from(e)) >> 65) as u64);
159 let p = (((u128::from(v3) + 1) * u128::from(divisor)) >> 64) as u64;
163 v3.wrapping_sub(p.wrapping_add(divisor))
164}
165
166#[cfg(any(
170 test,
171 all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
172))]
173#[inline]
174fn div_rem_word_reciprocal(hi: u64, lo: u64, divisor: u64, reciprocal: u64) -> (u64, u64) {
175 debug_assert!(hi < divisor);
176 debug_assert_eq!(divisor >> 63, 1);
177
178 let p = u128::from(reciprocal) * u128::from(hi) + ((u128::from(hi) << 64) | u128::from(lo));
180 let mut q = ((p >> 64) as u64).wrapping_add(1);
182 let mut r = lo.wrapping_sub(q.wrapping_mul(divisor));
183 if r > p as u64 {
185 q = q.wrapping_sub(1);
186 r = r.wrapping_add(divisor);
187 }
188 if r >= divisor {
190 q += 1;
191 r -= divisor;
192 }
193 (q, r)
194}
195
196fn div_rem_knuth<const N: usize>(
205 numerator: &[u64; N],
206 divisor: &[u64; N],
207 n: usize,
208 m: usize,
209) -> ([u64; N], [u64; N]) {
210 assert!(n + m <= N);
211
212 let shift = divisor[n - 1].leading_zeros();
230 let divisor = shl_word(divisor, shift);
232 let mut numerator = full_shl(numerator, shift);
234
235 let b0 = divisor[n - 1];
237 let b1 = divisor[n - 2];
238
239 let mut q = [0; N];
240
241 for j in (0..=m).rev() {
242 let a0 = numerator[j + n];
243 let a1 = numerator[j + n - 1];
244
245 let mut q_hat = if a0 < b0 {
246 let (mut q_hat, mut r_hat) = div_rem_word(a0, a1, b0);
248
249 let a2 = numerator[j + n - 2];
258 loop {
259 let r = u128::from(q_hat) * u128::from(b1);
260 let (lo, hi) = (r as u64, (r >> 64) as u64);
261 if (hi, lo) <= (r_hat, a2) {
262 break;
263 }
264
265 q_hat -= 1;
266 let (new_r_hat, overflow) = r_hat.overflowing_add(b0);
267 r_hat = new_r_hat;
268
269 if overflow {
270 break;
271 }
272 }
273 q_hat
274 } else {
275 u64::MAX
276 };
277
278 let q_hat_v = full_mul_u64(&divisor, q_hat);
282 let c = sub_assign(&mut numerator[j..], &q_hat_v[..n + 1]);
283
284 if c {
286 q_hat -= 1;
288
289 let c = add_assign(&mut numerator[j..], &divisor[..n]);
291 numerator[j + n] = numerator[j + n].wrapping_add(u64::from(c));
292 }
293
294 q[j] = q_hat;
296 }
297
298 let remainder = full_shr(&numerator, shift);
300 (q, remainder)
301}
302
303fn div_rem_word(hi: u64, lo: u64, divisor: u64) -> (u64, u64) {
308 debug_assert!(hi < divisor);
309 debug_assert_ne!(divisor, 0);
310
311 #[cfg(all(target_arch = "x86_64", not(miri)))]
314 unsafe {
315 let mut quot = lo;
316 let mut rem = hi;
317 std::arch::asm!(
318 "div {divisor}",
319 divisor = in(reg) divisor,
320 inout("rax") quot,
321 inout("rdx") rem,
322 options(pure, nomem, nostack)
323 );
324 (quot, rem)
325 }
326 #[cfg(any(not(target_arch = "x86_64"), miri))]
327 {
328 let x = (u128::from(hi) << 64) + u128::from(lo);
329 let y = u128::from(divisor);
330 ((x / y) as u64, (x % y) as u64)
331 }
332}
333
334fn add_assign(a: &mut [u64], b: &[u64]) -> bool {
336 binop_slice(a, b, u64::overflowing_add)
337}
338
339fn sub_assign(a: &mut [u64], b: &[u64]) -> bool {
341 binop_slice(a, b, u64::overflowing_sub)
342}
343
344fn binop_slice(a: &mut [u64], b: &[u64], binop: impl Fn(u64, u64) -> (u64, bool) + Copy) -> bool {
346 let mut c = false;
347 a.iter_mut().zip(b.iter()).for_each(|(x, y)| {
348 let (res1, overflow1) = y.overflowing_add(u64::from(c));
349 let (res2, overflow2) = binop(*x, res1);
350 *x = res2;
351 c = overflow1 || overflow2;
352 });
353 c
354}
355
356fn full_mul_u64<const N: usize>(a: &[u64; N], b: u64) -> ArrayPlusOne<u64, N> {
358 let mut carry = 0;
359 let mut out = [0; N];
360 out.iter_mut().zip(a).for_each(|(o, v)| {
361 let r = *v as u128 * b as u128 + carry as u128;
362 *o = r as u64;
363 carry = (r >> 64) as u64;
364 });
365 ArrayPlusOne(out, carry)
366}
367
368fn shl_word<const N: usize>(v: &[u64; N], shift: u32) -> [u64; N] {
370 full_shl(v, shift).0
371}
372
373fn full_shl<const N: usize>(v: &[u64; N], shift: u32) -> ArrayPlusOne<u64, N> {
375 debug_assert!(shift < 64);
376 if shift == 0 {
377 return ArrayPlusOne(*v, 0);
378 }
379 let mut out = [0u64; N];
380 out[0] = v[0] << shift;
381 for i in 1..N {
382 out[i] = (v[i - 1] >> (64 - shift)) | (v[i] << shift)
383 }
384 let carry = v[N - 1] >> (64 - shift);
385 ArrayPlusOne(out, carry)
386}
387
388fn full_shr<const N: usize>(a: &ArrayPlusOne<u64, N>, shift: u32) -> [u64; N] {
390 debug_assert!(shift < 64);
391 if shift == 0 {
392 return a.0;
393 }
394 let mut out = [0; N];
395 for i in 0..N - 1 {
396 out[i] = (a[i] >> shift) | (a[i + 1] << (64 - shift))
397 }
398 out[N - 1] = a[N - 1] >> shift;
399 out
400}
401
402#[repr(C)]
406struct ArrayPlusOne<T, const N: usize>([T; N], T);
407
408impl<T, const N: usize> std::ops::Deref for ArrayPlusOne<T, N> {
409 type Target = [T];
410
411 #[inline]
412 fn deref(&self) -> &Self::Target {
413 let x = std::ptr::from_ref::<Self>(self);
414 unsafe { std::slice::from_raw_parts(x.cast::<T>(), N + 1) }
415 }
416}
417
418impl<T, const N: usize> std::ops::DerefMut for ArrayPlusOne<T, N> {
419 fn deref_mut(&mut self) -> &mut Self::Target {
420 let x = std::ptr::from_mut::<Self>(self);
421 unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
422 }
423}
424
425#[cfg(test)]
426mod tests {
427 use super::*;
428 use rand::{RngExt, SeedableRng, rngs::StdRng};
429
430 fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
431 let expected = div_rem_small_word(&numerator, divisor);
432 assert_eq!(
433 div_rem_small_reciprocal(&numerator, divisor),
434 expected,
435 "{numerator:?} / {divisor}"
436 );
437 }
438
439 #[test]
440 fn test_reciprocal_word() {
441 let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
442 for i in 257..512u64 {
444 divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
445 }
446 let mut rng = StdRng::seed_from_u64(42);
447 divisors.extend((0..100_000).map(|_| rng.random::<u64>() | (1 << 63)));
448 for divisor in divisors {
449 let n = (u128::from(!divisor) << 64) | u128::from(u64::MAX);
450 let expected = (n / u128::from(divisor)) as u64;
451 assert_eq!(reciprocal_word(divisor), expected, "{divisor}");
452 }
453 }
454
455 #[test]
456 fn test_div_rem_word_reciprocal() {
457 let (hi, lo, divisor) = (1 << 63, u64::MAX, (1 << 63) + 2);
461 assert_eq!(reciprocal_word(divisor), u64::MAX - 7);
462 let n = (u128::from(hi) << 64) | u128::from(lo);
463 let d = u128::from(divisor);
464 assert_eq!(
465 div_rem_word_reciprocal(hi, lo, divisor, reciprocal_word(divisor)),
466 ((n / d) as u64, (n % d) as u64)
467 );
468
469 let mut rng = StdRng::seed_from_u64(42);
470 let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
471 divisors.extend((0..100).map(|_| rng.random::<u64>() | (1 << 63)));
472 for divisor in divisors {
473 let reciprocal = reciprocal_word(divisor);
474 let mut his = vec![0, 1, divisor / 2, divisor - 1];
475 his.extend((0..20).map(|_| rng.random_range(0..divisor)));
476 for hi in his {
477 let mut los = vec![0, 1, divisor - 1, divisor, u64::MAX];
478 los.extend((0..20).map(|_| rng.random::<u64>()));
479 for lo in los {
480 let n = (u128::from(hi) << 64) | u128::from(lo);
481 let d = u128::from(divisor);
482 let expected = ((n / d) as u64, (n % d) as u64);
483 assert_eq!(
484 div_rem_word_reciprocal(hi, lo, divisor, reciprocal),
485 expected,
486 "{n} / {divisor}"
487 );
488 }
489 }
490 }
491 }
492
493 #[test]
494 fn test_div_rem_small_reciprocal() {
495 let mut rng = StdRng::seed_from_u64(42);
496 let numerators = [
497 [0; 4],
498 [1, 0, 0, 0],
499 [0, 0, 0, 1],
500 [u64::MAX; 4],
501 [0, 0, 0, u64::MAX],
502 [u64::MAX, 0, 0, 0],
503 rng.random(),
504 ];
505 for shift in 0..64 {
507 let p = 1u64 << shift;
508 let mut divisors = vec![p, p.wrapping_mul(2).wrapping_sub(1)];
509 divisors.extend(p.checked_add(1));
510 divisors.extend(p.checked_sub(1).filter(|d| *d != 0));
511 for divisor in divisors {
512 for numerator in numerators {
513 check_div_rem_small(numerator, divisor);
514 check_div_rem_small([numerator[0], numerator[1]], divisor);
515 check_div_rem_small([numerator[0]], divisor);
516 }
517 }
518 }
519 for k in 0..=19 {
521 let p = 10u64.pow(k);
522 for divisor in [p - 1, p, p + 1].into_iter().filter(|d| *d != 0) {
523 for numerator in numerators {
524 check_div_rem_small(numerator, divisor);
525 }
526 }
527 }
528 for _ in 0..1000 {
529 let divisor = rng.random::<u64>() >> rng.random_range(0..64);
530 if divisor != 0 {
531 check_div_rem_small(rng.random::<[u64; 4]>(), divisor);
532 }
533 }
534 }
535}