38 mp_ptr rpad = alloc_limbs(na + 1);
39 memset(rpad, 0, (
size_t)(na + 1) * 8);
40 memcpy(rpad, r, (
size_t)rn * 8);
48 u64 seed = 0x3141592653589793ull;
49 for (
size_t n = 1;
n <= 80; ++
n) {
50 for (
int iter = 0; iter < 10; ++iter) {
51 mp_ptr a = alloc_limbs(
n), q = alloc_limbs(
n + 1),
t = alloc_limbs(
n + 1),
52 acopy = alloc_limbs(
n);
53 random_limbs(a,
n, &seed);
54 u64 x = xorshift64(&seed) | 1;
70 add_small_inplace(
t,
n + 1, rem);
75 memcpy(acopy, a,
n * 8);
93 const u64 divisors[] = {
94 1, 2, 3, 5, 7, 0xFFFF, 0x100000001ull,
95 1ull << 62, (1ull << 62) + 1, (1ull << 62) - 1,
96 1ull << 63, (1ull << 63) + 1, (1ull << 63) - 1,
97 ~0ull, ~0ull - 1ull, ~0ull - 2ull, 0x123456789ABCDEFFull,
99 u64 seed = 0x89ABCDEF01234567ull;
100 for (
size_t x_index = 0; x_index <
ARRAY_SIZE(divisors); ++x_index) {
101 u64 x = divisors[x_index];
104 for (
size_t n = 1;
n <= 34; ++
n) {
105 for (
int iter = 0; iter < 6; ++iter) {
107 random_limbs(a,
n, &seed);
125 u64 seed = 0x2718281828459045ull;
127 {2, 1}, {3, 1}, {5, 2}, {10, 3}, {20, 5}, {30, 10},
128 {50, 10}, {80, 20}, {120, 30}, {200, 50}, {350, 80},
129 {600, 120}, {900, 200}, {1400, 300}, {1900, 400}, {2500, 500}
131 for (
size_t c_index = 0; c_index <
ARRAY_SIZE(sizes); ++c_index) {
134 mp_ptr n = alloc_limbs(na), d = alloc_limbs(nb);
135 mp_ptr q = alloc_limbs(na - nb + 1), r = alloc_limbs(nb);
136 random_limbs(
n, na, &seed);
137 random_limbs(d, nb, &seed);
147 u64 seed = 0x0badcafef00dfaceull;
149 {3, 1}, {4, 2}, {10, 3}, {30, 10}, {60, 20}, {120, 40},
150 {300, 80}, {700, 150}, {1200, 300}, {1900, 400}
152 for (
size_t c_index = 0; c_index <
ARRAY_SIZE(sizes); ++c_index) {
155 mp_ptr numa = alloc_limbs(na),
numb = alloc_limbs(nb), nsave = alloc_limbs(na);
156 mp_ptr q = alloc_limbs(na - nb + 2);
157 random_limbs(numa, na, &seed);
158 random_limbs(
numb, nb, &seed);
159 memcpy(nsave, numa, (
size_t)na * 8);
170TEST_CASE(
"div/basecase_divide", div_basecase_vs_divide) {
171 u64 seed = 0x1020304050607080ull;
173 {6, 3}, {10, 4}, {20, 6}, {40, 10}, {60, 20}, {100, 30}, {160, 40}, {220, 50}
175 for (
size_t c_index = 0; c_index <
ARRAY_SIZE(sizes); ++c_index) {
178 if (na < nb + 1)
continue;
179 mp_ptr numa1 = alloc_limbs(na);
180 mp_ptr numa2 = alloc_limbs(na);
182 mp_ptr q1 = alloc_limbs(na - nb + 1);
183 mp_ptr q2 = alloc_limbs(na - nb + 1);
184 random_limbs(numa1, na, &seed);
185 random_limbs(
numb, nb, &seed);
186 memcpy(numa2, numa1, na * 8);
198 if (nb >= 6 && na >= 2 * nb) {
214 u64 seed = 0x0f0e0d0c0b0a0908ull;
216 for (
int i = 0; i < 500; ++i) {
228 for (
int i = 0; i < 200; ++i) {
230 u64 xl = xorshift64(&seed);
237 TEST_RUN(
"div/single", div_1_mod_1);
238 TEST_RUN(
"div/single", mod_preinv_1_boundary);
239 TEST_RUN(
"div/general", div_general_relation);
240 TEST_RUN(
"div/normalized", div_s_normalized_relation);
241 TEST_RUN(
"div/basecase_divide", div_basecase_vs_divide);
#define lmmp_leading_zeros_
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_div_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法运算
mp_limb_t lmmp_div_1_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_limb_t x)
单精度数除法(除数为1个limb)
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
mp_limb_t lmmp_mod_preinv_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x, mp_limb_t inv, mp_limb_t k)
单精度数取余(预备逆元版) [numa,na] mod x,同 lmmp_mod_1_
mp_limb_t lmmp_mod_1_(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)
除法和取模操作
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
mp_limb_t lmmp_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
mp_limb_t lmmp_div_basecase_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
基础除法运算
mp_limb_t lmmp_div_divide_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
分治除法运算
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEST_CHECK_MSG(cond, msg)
#define TEST_CASE(category, name)
#define TEST_CHECK_EQ(a, b)
#define TEST_RUN(category, name)
static void verify_div_relation(const mp_limb_t *n, mp_size_t na, const mp_limb_t *d, mp_size_t nb, const mp_limb_t *q, mp_size_t qn, const mp_limb_t *r, mp_size_t rn)
Copyright (C) 2026 HJimmyK (Jericho Knox)