47 for (
u64 m = 1; m <= 200; ++m) {
48 for (
u64 u = 1; u <= 200; ++u) {
66 u64 seed = 0x51ce1b7ea4df7c21ull;
67 for (
int i = 0; i < 20000; ++i) {
68 u64 m = xorshift64(&seed);
69 u64 u = xorshift64(&seed);
88 u64 seed = 0x2b44ae9d4d6c8f13ull;
89 const mp_size_t mn_values[] = {2, 3, 5, 9, 17, 33, 60};
90 for (
size_t mn_index = 0; mn_index <
ARRAY_SIZE(mn_values); ++mn_index) {
92 for (
int iter = 0; iter < 7; ++iter) {
93 mp_ptr m = alloc_limbs(mn);
94 random_limbs(m, mn, &seed);
100 un = mn / 2 > 0 ? mn / 2 : 1;
102 random_limbs(u, un, &seed);
104 }
else if (iter % 2 == 0) {
107 u = alloc_limbs(mn + 1);
110 add_small_inplace(u, mn + 1, 1);
111 un = norm_len(u, mn + 1);
115 random_limbs(u, un, &seed);
118 mp_ptr dst = alloc_limbs(mn);
121 mp_ptr gr = alloc_limbs(un > mn ? un : mn);
123 if (gn == 1 && gr[0] == 1) {
125 mp_ptr prod = alloc_limbs(mn + un + 1), q = alloc_limbs(mn + un + 1),
130 TEST_CHECK_MSG(norm_len(r, mn) == 1 && r[0] == 1,
"inv*u mod m == 1");
138 mp_ptr u2 = alloc_limbs(un > mn ? un : mn);
141 TEST_CHECK_MSG(rn2 == rn && (rn == 0 || mpn_cmp(u2, rn2, dst, rn) == 0),
149 TEST_RUN(
"numth/modinv", modinv_ulong);
150 TEST_RUN(
"numth/modinv", modinv_big);
#define lmmp_copy(dst, src, n)
#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_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]
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
ulong lmmp_modinv_ulong_(ulong u, ulong m)
模逆元(单 limb):求 u^{-1} mod m
mp_size_t lmmp_modinv_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr mp, mp_size_t mn)
模逆元(任意长度):求 [up,un]^{-1} mod [mp,mn]
mp_size_t lmmp_gcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(通用分发入口)
#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 gcd_u64(u64 a, u64 b)
Copyright (C) 2026 HJimmyK (Jericho Knox)