1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
//! Schoolbook division of a [`U320`] by a `u64`, returning the remainder.
use super::U320;
impl U320 {
/// Divides `self` by a `u64` divisor in place using schoolbook long
/// division and returns the remainder.
///
/// Processes limbs from most significant (index 4) to least significant
/// (index 0), carrying the remainder from each step into the next as
/// the high half of a `u128` dividend. This is the standard single-word
/// divisor algorithm.
///
/// Used internally by [`Display`](core::fmt::Display) formatting to
/// extract groups of decimal digits via repeated division by `10^19`.
///
/// # Panics
///
/// Panics if `d` is zero (division by zero).
///
/// # Examples
///
/// ```
/// use cnfy_uint::u320::U320;
///
/// let mut v = U320::from_be_limbs([0, 0, 0, 0, 100]);
/// let rem = v.div_u64(7);
/// assert_eq!(v, U320::from_be_limbs([0, 0, 0, 0, 14]));
/// assert_eq!(rem, 2);
/// ```
#[inline]
pub fn div_u64(&mut self, d: u64) -> u64 {
let mut rem: u128 = 0;
let divisor = d as u128;
let mut i = 4;
loop {
let dividend = (rem << 64) | (self.0[i] as u128);
self.0[i] = (dividend / divisor) as u64;
rem = dividend % divisor;
if i == 0 {
break;
}
i -= 1;
}
rem as u64
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
/// Division of a small value by a small divisor.
#[test]
fn small_division() {
let mut v = U320::from_be_limbs([0, 0, 0, 0, 100]);
let rem = v.div_u64(7);
assert_eq!(v, U320::from_be_limbs([0, 0, 0, 0, 14]));
assert_eq!(rem, 2);
}
/// Division with zero remainder.
#[test]
fn exact_division() {
let mut v = U320::from_be_limbs([0, 0, 0, 0, 21]);
let rem = v.div_u64(7);
assert_eq!(v, U320::from_be_limbs([0, 0, 0, 0, 3]));
assert_eq!(rem, 0);
}
/// Division of zero by any non-zero value yields zero.
#[test]
fn zero_dividend() {
let mut v = U320::ZERO;
let rem = v.div_u64(42);
assert_eq!(v, U320::ZERO);
assert_eq!(rem, 0);
}
/// Division by 1 is identity.
#[test]
fn divide_by_one() {
let original = U320::from_be_limbs([0xAA, 0xBB, 0xCC, 0xDD, 0xEE]);
let mut v = original;
let rem = v.div_u64(1);
assert_eq!(v, original);
assert_eq!(rem, 0);
}
/// Division across multiple limbs.
#[test]
fn multi_limb_division() {
// 2^64 / 3 = 6148914691236517205 rem 1
let mut v = U320::from_be_limbs([0, 0, 0, 1, 0]);
let rem = v.div_u64(3);
assert_eq!(rem, 1);
// Verify: quotient * 3 + 1 should equal 2^64
let q = v.to_be_limbs();
let reconstructed = (q[4] as u128) * 3 + 1;
assert_eq!(reconstructed, 1u128 << 64);
}
/// Division of MAX by u64::MAX.
#[test]
fn max_by_max_u64() {
let mut v = U320::MAX;
let rem = v.div_u64(u64::MAX);
// (2^320 - 1) / (2^64 - 1) = 2^256 + 2^192 + 2^128 + 2^64 + 1
assert_eq!(v, U320::from_be_limbs([1, 1, 1, 1, 1]));
assert_eq!(rem, 0);
}
}