47 u64 r = 1 % p, a = base % p;
49 if (exp & 1) r = r * a % p;
57 for (
mp_size_t i = 0; i <
n; ++i) p[i] = xorshift64(&seed);
58 if (
n > 0) p[
n - 1] |= (
u64)1 << 63;
63 mp_ptr a = alloc_limbs(
n), b = alloc_limbs(
n), d = alloc_limbs(2 *
n + 2),
64 ref = alloc_limbs(2 *
n + 2);
70 bool ok = memcmp(d, ref, (
size_t)(2 *
n) * 8) == 0;
71 ok = ok && mod_is_product(d, 2 *
n, a,
n, b,
n);
96 u64 seed = 0xabcddcba12344321ull;
97 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(sizes); ++n_index) {
99 mp_ptr a = alloc_limbs(
n), b = alloc_limbs(
n),
lo = alloc_limbs(
n),
100 full = alloc_limbs(2 *
n + 2);
107 "mullo low limbs match full product at threshold");
119 u64 seed = 0x0123456789abcdefull;
120 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(ns); ++n_index) {
123 mp_ptr num = alloc_limbs(na), den = alloc_limbs(
n), q = alloc_limbs(
n + 2),
124 r = alloc_limbs(
n + 2),
t = alloc_limbs(2 *
n + 4), qd = alloc_limbs(na + 2),
125 sum = alloc_limbs(2 *
n + 4);
128 num[na - 1] &= ~((
u64)1 << 63);
134 memcpy(sum, qd, (
size_t)(2 *
n + 1) * 8);
136 memcpy(
t, r, (
size_t)
n * 8);
138 TEST_CHECK_MSG(mpn_eq(sum, 2 *
n + 4, num, na),
"div q*d+r rebuild at boundary");
152TEST_CASE(
"threshold/divexact", divexact_two_threshold_boundaries) {
153 u64 seed = 0x0fedcba987654321ull;
157 const Case cases[] = {
165 for (
size_t c_index = 0; c_index <
ARRAY_SIZE(cases); ++c_index) {
166 const Case c = cases[c_index];
168 mp_ptr q0 = alloc_limbs(qn), dp = alloc_limbs(c.dn), np = alloc_limbs(c.nn + 2),
169 dst = alloc_limbs(c.nn + 2);
173 dp[c.dn - 1] |= (
u64)1 << 63;
183 "divexact boundary recovers original quotient");
194 mp_ptr b = alloc_limbs(1);
199 for (
size_t e_index = 0; e_index <
ARRAY_SIZE(exps); ++e_index) {
200 ulong e = exps[e_index];
202 mp_ptr dst = alloc_limbs(rn + 2), dst1 = alloc_limbs(rn + 2);
206 TEST_CHECK_MSG(got == got1 && memcmp(dst, dst1, (
size_t)got * 8) == 0,
207 "pow_ vs pow_1_ at exp boundary");
210 for (
int i = 0; i < MOD_P_CNT && ok; ++i)
211 ok = mod32(dst, got, MOD_P[i]) ==
modpow32(base, e, MOD_P[i]);
220 TEST_RUN(
"threshold/mul", mul_n_toom_boundaries);
221 TEST_RUN(
"threshold/mullo", mullo_dc_boundary);
222 TEST_RUN(
"threshold/div", divide_threshold_boundary);
223 TEST_RUN(
"threshold/divexact", divexact_two_threshold_boundaries);
224 TEST_RUN(
"threshold/pow", pow_1_exp_boundary);
#define lmmp_zero(dst, n)
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define DIV_DIVIDE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define MUL_TOOM22_THRESHOLD
#define MUL_TOOM33_THRESHOLD
#define MULLO_DC_THRESHOLD
#define MUL_TOOM44_THRESHOLD
void test_threshold_boundaries(void)
void lmmp_mul_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
基础乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
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]
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_mullo_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
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 DIVEXACT_NN_THRESHOLD
#define POW_1_EXP_THRESHOLD
#define DIVEXACT_BASECASE_THRESHOLD
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)
mp_size_t lmmp_pow_1_(mp_ptr dst, mp_size_t rn, mp_limb_t base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_pow_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算大整数幂 [dst,rn] = [base,n] ^ exp
mp_size_t lmmp_pow_size_(mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEST_CHECK_MSG(cond, msg)
#define TEST_CASE(category, name)
#define TEST_RUN(category, name)
static u64 modpow32(u64 base, u64 exp, u32 p)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void check_mul_n(mp_size_t n, u64 seed)
static void fill_deterministic(mp_ptr p, mp_size_t n, u64 seed)