51 memcpy(out,
s, (
size_t)l * 8);
60 mp_ptr sa = alloc_limbs(cap), ta = alloc_limbs(cap);
63 for (
int i = 0; i < MOD_P_CNT && ok; ++i) {
65 u64 ps = ls ? mulmod32(mod32(sa, ls, (
u32)p), mod32(u, un, (
u32)p), p) : 0;
66 u64 pt = lt ? mulmod32(mod32(ta, lt, (
u32)p), mod32(v, vn, (
u32)p), p) : 0;
67 u64 lhs = (sn < 0) == (tn < 0) ? addmod32(ps, pt, p)
68 : (sn < 0) ? submod32(pt, ps, p) : submod32(ps, pt, p);
69 if ((sn < 0) && (tn < 0)) lhs = (p - lhs) % p;
70 ok = lhs == mod32(g, gn, (
u32)p);
81 mp_ptr sa = alloc_limbs(cap), x = alloc_limbs(cap);
88 if (ls >= gn)
lmmp_mul_(x, sa, ls, g, gn);
93 bool ok = mpn_cmp(x, cap, v, vn) <= 0;
103 for (
int i = 0; i < MOD_P_CNT; ++i) {
105 u64 ps = (sa % p) * (u % p) % p;
106 u64 pt = (ta % p) * (v % p) % p;
107 u64 lhs = (
s < 0) == (
t < 0) ? (ps + pt) % p
108 : (
s < 0) ? submod32(pt, ps, p) : submod32(ps, pt, p);
110 if ((
s < 0) && (
t < 0)) lhs = (p - lhs) % p;
111 if (lhs != g % p)
return false;
121 if (!(mpn_eq(u, un, v, vn)) && !
coeff_bound_l(u, un, g, gn,
t, tn))
128 for (
u64 u = 1; u <= 300; ++u) {
129 for (
u64 v = 1; v <= 300; ++v) {
141 u64 seed = 0x6d2b79f5ull;
142 for (
int i = 0; i < 20000; ++i) {
143 u64 u = xorshift64(&seed), v = xorshift64(&seed);
167 u64 seed = 0x3c6ef372fe94f82bull;
169 for (
int iter = 0; iter < 12; ++iter) {
170 mp_ptr u = alloc_limbs(un);
171 random_limbs(u, un, &seed);
172 u64 v = xorshift64(&seed) | 1;
173 mp_ptr g = alloc_limbs(1),
s = alloc_limbs(1),
t = alloc_limbs(un + 1);
179 TEST_CHECK_MSG(
check_gcdext(g, gn,
s, sn,
t, tn, u, un, &v, 1),
"identity");
188 mp_ptr u = alloc_limbs(5), g = alloc_limbs(5),
s = alloc_limbs(1),
t = alloc_limbs(6);
189 random_limbs(u, 5, &seed);
193 TEST_CHECK_MSG(
check_gcdext(g, 1,
s, sn,
t, tn, u, 5, vp, 1),
"gcdext_1 baseline identity");
202 u64 seed = 0x9e3779b97f4a7c15ull;
204 for (
int iter = 0; iter < 8; ++iter) {
205 mp_ptr u = alloc_limbs(un), v = alloc_limbs(2);
206 random_limbs(u, un, &seed);
207 random_limbs(v, 2, &seed);
208 mp_ptr g = alloc_limbs(2),
s = alloc_limbs(2),
t = alloc_limbs(un + 1);
212 mp_ptr g2 = alloc_limbs(2);
215 TEST_CHECK_MSG(
check_gcdext(g, gn,
s, sn,
t, tn, u, un, v, 2),
"identity");
220 for (
int iter = 0; iter < 10; ++iter) {
221 mp_ptr v = alloc_limbs(2);
222 random_limbs(v, 2, &seed);
223 u64 k = 3 + (xorshift64(&seed) & 0xf);
224 mp_ptr u = alloc_limbs(4);
228 mp_ptr g = alloc_limbs(2),
s = alloc_limbs(2);
239 mp_ptr u = alloc_limbs(un + 2), v = alloc_limbs((un > vn ? un : vn) + 2);
241 random_limbs(u, un, seed);
242 random_limbs(v, vn, seed);
243 }
else if (mode == 1) {
244 random_limbs(v, vn, seed);
246 u64 k = 3 + (xorshift64(seed) & 0xFF);
248 un = hi ? vn + 1 : vn;
250 }
else if (mode == 2) {
251 random_limbs(u, un, seed);
254 sub_small_inplace(v, vn, 1 + (xorshift64(seed) & 0xFF));
255 vn = norm_len(v, vn);
256 }
else if (mode == 4) {
257 random_limbs(u, un, seed);
258 if (u[0] == 0) u[0] = 2;
261 sub_small_inplace(v, vn, 1);
262 vn = norm_len(v, vn);
264 random_limbs(u, un, seed);
265 random_limbs(v, vn, seed);
270 un = norm_len(u, un + 1);
271 vn = norm_len(v, vn + 1);
273 mp_ptr g = alloc_limbs(un + vn);
276 mp_ptr s = alloc_limbs(mx),
t = alloc_limbs(mx);
279 mp_ptr gsave = alloc_limbs(un + vn);
281 memcpy(gsave, g, (
size_t)gn * 8);
283 TEST_CHECK_MSG(mpn_eq(g, gn, v, vn) && sn == 0,
"exact multiple gcd/s");
284 }
else if (mode == 4) {
286 TEST_CHECK_MSG(
check_gcdext(g, gn,
s, sn,
t, tn, u, un, v, vn),
"neighbor-1 identity");
290 mp_ptr gr = alloc_limbs(un + vn);
294 TEST_CHECK_MSG(
check_gcdext(g, gn,
s, sn,
t, tn, u, un, v, vn),
"identity");
301 }
else if (mode == 1) {
304 TEST_CHECK_MSG(mpn_eq(g, gn2, v, vn),
"swapped exact multiple gcd");
305 TEST_CHECK_MSG(sn2 == 1 &&
s[0] == 1 && tn2 == 0,
"swapped exact multiple s=1,t=0");
306 TEST_CHECK_MSG(
check_gcdext(g, gn2,
s, sn2,
t, tn2, v, vn, u, un),
307 "swapped exact multiple identity");
309 TEST_CHECK_MSG(
check_gcdext(g, gn2,
s, sn2,
t, tn2, v, vn, u, un),
"swapped");
316 mp_ptr u2 = alloc_limbs(un + vn);
327 u64 seed = 0x5ac635d8aa3a93e7ull;
329 struct operand_sizes {
mp_size_t un, vn; } sizes[] = {
330 {1, 1}, {2, 1}, {2, 2}, {3, 1}, {3, 2}, {3, 3}, {5, 2}, {5, 4},
331 {9, 3}, {9, 8}, {17, 5}, {17, 16}, {33, 7}, {33, 32}, {60, 3}, {60, 59},
332 {85, 85}, {86, 43}, {87, 2}, {87, 86}, {120, 61}, {200, 3}, {200, 100},
334 for (
size_t sz_index = 0; sz_index <
ARRAY_SIZE(sizes); ++sz_index) {
335 const struct operand_sizes sz = sizes[sz_index];
336 int iters = sz.un > 60 ? 1 : 3;
337 for (
int mode = 0; mode < 5; ++mode) {
338 for (
int iter = 0; iter < iters; ++iter) {
348 const mp_size_t n_values[] = {3, 8, 20, 50, 90};
349 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
356 mp_ptr u = alloc_limbs(rn + 1), v = alloc_limbs(rn + 1);
360 mp_size_t un = norm_len(u, rn + 1), vn = norm_len(v, rn + 1);
361 mp_ptr g = alloc_limbs(rn),
s = alloc_limbs(vn + 1),
t = alloc_limbs(un + 1);
365 TEST_CHECK_MSG(
check_gcdext(g, gn,
s, sn,
t, tn, u, un, v, vn),
"fibonacci identity");
373 u64 seed = 0x9e3779b97f4a7c15ull;
374 struct operand_sizes {
mp_size_t un, vn; } sizes[] = {{200, 100}, {300, 120}, {400, 399}};
375 for (
size_t sz_index = 0; sz_index <
ARRAY_SIZE(sizes); ++sz_index) {
376 const struct operand_sizes sz = sizes[sz_index];
377 mp_ptr u = alloc_limbs(sz.un), v = alloc_limbs(sz.vn);
378 random_limbs(u, sz.un, &seed);
379 random_limbs(v, sz.vn, &seed);
381 if (v[sz.vn - 1] == 0) v[sz.vn - 1] = 1;
382 mp_ptr g = alloc_limbs(sz.vn),
s = alloc_limbs(sz.vn + 2),
t = alloc_limbs(sz.un + 2),
383 gr = alloc_limbs(sz.vn), g2 = alloc_limbs(sz.vn);
390 TEST_CHECK_MSG(
check_gcdext(g, gn,
s, sn,
t, tn, u, sz.un, v, sz.vn),
"bezout+bounds");
397 TEST_RUN(
"numth/gcdext", gcdext_11);
400 TEST_RUN(
"numth/gcdext", gcdext_lehmer_and_dispatch);
401 TEST_RUN(
"numth/gcdext", gcdext_fibonacci);
402 TEST_RUN(
"numth/gcdext", gcdext_large_cross);
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
const mp_limb_t * mp_srcptr
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]
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
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]
mp_size_t lmmp_gcd_lehmer_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(Lehmer算法)
ulong lmmp_gcdext_11_(ulong u, ulong v, slong *s, slong *t)
扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g
mp_size_t lmmp_fibonacci2_(mp_ptr dst, mp_ptr dst2, mp_size_t rn, ulong n)
计算 Fibonacci 数对:[dst,rn] = F[n],[dst2,rn] = F[n-1]
mp_size_t lmmp_gcd_2_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp)
计算两个无符号整数的最大公约数
mp_size_t lmmp_gcdext_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
扩展欧几里得(通用分发入口):g = gcd(u,v),s*u + t*v = g
mp_size_t lmmp_gcdext_2_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp)
扩展欧几里得(任意长度对双 limb):g = gcd([up,un],[vp,2]),s*u + t*v = g
mp_size_t lmmp_gcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(通用分发入口)
mp_size_t lmmp_fibonacci_size_(ulong n)
计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度
mp_size_t lmmp_gcdext_1_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, ulong v)
扩展欧几里得(任意长度对单 limb):g = gcd([up,un],v),s*u + t*v = g
#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 u64 gcd_u64(u64 a, u64 b)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static bool bezout_identity_l(const mp_limb_t *u, mp_size_t un, const mp_limb_t *v, mp_size_t vn, const mp_limb_t *g, mp_size_t gn, mp_ptr s, mp_ssize_t sn, mp_ptr t, mp_ssize_t tn)
static bool scalar_bezout(u64 u, u64 v, u64 g, slong s, slong t)
static void run_gcdext_pair(u64 *seed, mp_size_t un, mp_size_t vn, int mode)
static bool coeff_bound_l(const mp_limb_t *v, mp_size_t vn, const mp_limb_t *g, mp_size_t gn, mp_ptr s, mp_ssize_t sn)
static bool check_gcdext(mp_ptr g, mp_size_t gn, mp_ptr s, mp_ssize_t sn, mp_ptr t, mp_ssize_t tn, mp_srcptr u, mp_size_t un, mp_srcptr v, mp_size_t vn)
static mp_size_t abs_coeffs(mp_ptr out, mp_ptr s, mp_ssize_t sn)