37 u64 seed = 0x1111222233334444ull;
39 for (
int iter = 0; iter < 8; ++iter) {
40 u64 d = xorshift64(&seed) | 1;
48 mp_ptr q = alloc_limbs(
n), np = alloc_limbs(
n + 1), dst = alloc_limbs(
n + 1);
49 random_limbs_with_top(q,
n, &seed,
false);
50 if (iter % 2 == 0) q[
n - 1] >>= 1;
53 if (hi) np[
n] = hi, nn =
n + 1;
56 const mp_limb_t sent = UINT64_C(0x5a5af00dcafebeef);
83 u64 seed = 0x5555666677778888ull;
85 for (
int iter = 0; iter < 8; ++iter) {
87 mp_ptr q = alloc_limbs(
n - 2), d = alloc_limbs(2), np = alloc_limbs(
n),
88 dst = alloc_limbs(
n - 1), dinv = alloc_limbs(2);
89 random_limbs_with_top(q,
n - 2, &seed,
false);
90 random_limbs(d, 2, &seed);
107TEST_CASE(
"numth/divexact", divexact_basecase_divide_cross) {
108 u64 seed = 0x1234432187655678ull;
110 const Case cases[] = {
111 {2, 1}, {3, 1}, {5, 2}, {10, 3}, {20, 5}, {40, 10},
112 {60, 20}, {100, 30}, {150, 40}, {250, 60}, {400, 80},
114 {9, 8}, {12, 10}, {61, 41}, {100, 60}, {200, 120}
116 for (
size_t c_index = 0; c_index <
ARRAY_SIZE(cases); ++c_index) {
117 const Case c = cases[c_index];
119 for (
int iter = 0; iter < 5; ++iter) {
120 mp_ptr d = alloc_limbs(dn);
121 random_limbs(d, dn, &seed);
127 mp_ptr q = alloc_limbs(q_actual > 0 ? q_actual : 1);
128 random_limbs_with_top(q, q_actual, &seed,
false);
129 mp_ptr np = alloc_limbs(nn);
130 mul_sorted(np, q, q_actual, d, dn);
133 mp_ptr dst1 = alloc_limbs(qn + 1), np1 = alloc_limbs(nn);
134 memcpy(np1, np, nn * 8);
140 mp_ptr dst2 = alloc_limbs(qn + 1), np2 = alloc_limbs(nn);
141 memcpy(np2, np, nn * 8);
149 mp_ptr dst3 = alloc_limbs(qn + 1), np3 = alloc_limbs(nn);
150 memcpy(np3, np, nn * 8);
156 mp_ptr dst4 = alloc_limbs(qn + 1), np4 = alloc_limbs(nn);
157 memcpy(np4, np, nn * 8);
163 mp_ptr qd = alloc_limbs(nn - dn + 2), rd = alloc_limbs(dn);
167 TEST_CHECK(mpn_eq(qd, nn - dn + 2, q, q_actual));
177TEST_CASE(
"numth/divexact", divexact_unbalanced_preinv) {
178 u64 seed = 0x0a0b0c0d0e0f0102ull;
179 const mp_size_t dn_values[] = {1, 2, 3, 10, 30};
180 for (
size_t dn_index = 0; dn_index <
ARRAY_SIZE(dn_values); ++dn_index) {
182 for (
mp_size_t nn = dn + 1; nn <= dn + 40; ++nn) {
183 mp_ptr d = alloc_limbs(dn);
184 random_limbs(d, dn, &seed);
188 mp_ptr q = alloc_limbs(q_actual > 0 ? q_actual : 1);
189 random_limbs_with_top(q, q_actual, &seed,
false);
190 mp_ptr np = alloc_limbs(nn);
191 if (q_actual >= dn)
lmmp_mul_(np, q, q_actual, d, dn);
194 mp_ptr dinv = alloc_limbs(dn + 1);
196 mp_ptr dst = alloc_limbs(qn + 1), np2 = alloc_limbs(nn);
197 memcpy(np2, np, nn * 8);
209 TEST_RUN(
"numth/divexact", divexact_1);
210 TEST_RUN(
"numth/divexact", divexact_2);
211 TEST_RUN(
"numth/divexact", divexact_basecase_divide_cross);
212 TEST_RUN(
"numth/divexact", divexact_unbalanced_preinv);
#define lmmp_zero(dst, n)
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
void lmmp_divexact_unbalance_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_ptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
void lmmp_divexact_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
void lmmp_divexact_basecase_(mp_ptr dst, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn-dn+1]=[np,nn]/[dp,dn],且余数必须为0),朴素算法
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
void lmmp_divexact_1_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_limb_t d, mp_limb_t dinv)
精确除法([dst,nn]=[np,nn]/d,且余数必须为0)
void lmmp_divexact_2_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_srcptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,2],且余数必须为0)
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元
void lmmp_divexact_divide_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0),分治算法
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEST_CASE(category, name)
#define TEST_CHECK_EQ(a, b)
#define TEST_RUN(category, name)