54 u64 seed = 0x5ac635d8aa3a93e7ull;
57 const mp_size_t n_values[] = {1, 2, 5, 10, 20, 40};
58 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
60 for (
int iter = 0; iter < 8; ++iter) {
64 mp_ptr u = alloc_limbs(un), v = alloc_limbs(vn), d2 = alloc_limbs(un),
66 random_limbs(u, un, &seed);
67 random_limbs(v, vn, &seed);
80 const ulong m_values[] = {240ul, 601ul, 1500ul};
81 for (
size_t m_index = 0; m_index <
ARRAY_SIZE(m_values); ++m_index) {
82 ulong m = m_values[m_index];
83 const ulong n_values2[] = {90ul, 240ul, 977ul};
84 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values2); ++n_index) {
85 ulong n = n_values2[n_index];
89 mp_ptr fm = alloc_limbs(rm), fn = alloc_limbs(rn_),
90 g = alloc_limbs(rn_ < rm ? rn_ : rm), fg = alloc_limbs(rg);
101 const mp_size_t n_values3[] = {7, 33, 120};
102 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values3); ++n_index) {
104 mp_ptr u = alloc_limbs(
n), v = alloc_limbs(
n), g = alloc_limbs(
n), ku = alloc_limbs(
n + 1),
105 kv = alloc_limbs(
n + 1), kg = alloc_limbs(
n + 1),
t = alloc_limbs(
n + 2);
106 random_limbs(u,
n, &seed);
107 random_limbs(v,
n, &seed);
109 u64 k = xorshift64(&seed) | 1;
128 u64 seed = 0x2545f4914f6cdd1dull;
129 struct operand_sizes {
mp_size_t un, vn; } sizes[] = {{60, 3}, {120, 7}, {200, 50}, {300, 299}, {400, 2}};
130 for (
size_t s_index = 0; s_index <
ARRAY_SIZE(sizes); ++s_index) {
131 const struct operand_sizes
s = sizes[s_index];
132 for (
int iter = 0; iter < 3; ++iter) {
136 random_limbs(u,
s.un, &seed);
137 random_limbs(v,
s.vn, &seed);
155 u64 seed = 0x51ce1b7ea4df7c21ull;
156 const mp_size_t n_values[] = {3, 5, 8, 16, 33, 50, 64, 100, 217, 511};
157 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
159 int iters =
n >= 217 ? 2 : 3;
160 for (
int bmode = 0; bmode < 4; ++bmode) {
161 for (
int iter = 0; iter < iters; ++iter) {
168 mp_ptr fx = alloc_limbs(
n + 8), fy = alloc_limbs(
n + 8);
169 N = fib_pair(fx, fy,
n + 8,
n);
172 memcpy(a, fy, (
size_t)N * 8);
173 memcpy(b, fx, (
size_t)N * 8);
177 random_limbs(a,
n, &seed);
179 random_limbs(b,
n, &seed);
181 if (b[
n - 1] == 0) b[
n - 1] = 1;
182 }
else if (bmode == 1) {
184 random_limbs(b,
bn, &seed);
187 b[0] = 0x9e3779b97f4a7c15ull | 1;
191 if (mpn_cmp(a, N, b, N) < 0) {
194 if (mpn_eq(a, N, b, N)) {
198 mp_ptr wa = alloc_limbs(N), wb = alloc_limbs(N);
206 for (
int row = 0; row < 2; ++row) {
209 mp_ptr p1 = alloc_limbs(mx), p2 = alloc_limbs(mx), sum = alloc_limbs(mx);
212 if (lm0 >= nn)
lmmp_mul_(p1, M.
m[row][0], lm0, wa, nn);
217 if (lm1 >= nn)
lmmp_mul_(p2, M.
m[row][1], lm1, wb, nn);
221 pad_add(p1, l1, p2, l2, mx, sum);
222 const mp_limb_t* expectv = row == 0 ? a : b;
230 mp_size_t l0 = l00 + l11, l1 = l01 + l10;
232 mp_ptr p0 = alloc_limbs(mx), p1 = alloc_limbs(mx), q0 = alloc_limbs(mx),
233 q1 = alloc_limbs(mx), diff = alloc_limbs(mx);
235 if (l00 > 0 && l11 > 0) {
236 if (l00 >= l11)
lmmp_mul_(q0, M.
m[0][0], l00, M.
m[1][1], l11);
237 else lmmp_mul_(q0, M.
m[1][1], l11, M.
m[0][0], l00);
240 if (l01 > 0 && l10 > 0) {
241 if (l01 >= l10)
lmmp_mul_(q1, M.
m[0][1], l01, M.
m[1][0], l10);
242 else lmmp_mul_(q1, M.
m[1][0], l10, M.
m[0][1], l01);
244 lmmp_zero(p0, mx); memcpy(p0, q0, (
size_t)l0 * 8);
245 lmmp_zero(p1, mx); memcpy(p1, q1, (
size_t)l1 * 8);
248 bool det_ok = (dl == 1 && diff[0] == 1);
251 dl = norm_len(diff, mx);
252 det_ok = (dl == 1 && diff[0] == 1);
257 TEST_CHECK_MSG(mpn_cmp(wa, nn, wb, nn) >= 0,
"hgcd canonical order");
261 "hgcd no-reduction keeps pair");
273 u64 seed = 0x2b44ae9d4d6c8f13ull;
274 const mp_size_t n_values[] = {1, 3, 5, 8, 16, 33, 64, 120, 200, 321};
275 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
277 int iters =
n >= 200 ? 2 : 3;
278 for (
int mode = 0; mode < 5; ++mode) {
279 for (
int iter = 0; iter < iters; ++iter) {
284 mp_ptr exp = alloc_limbs(
n + 2);
288 random_limbs(a,
n, &seed);
289 random_limbs(b,
n, &seed);
290 if (
n > 1) b[
n - 1] >>= 1;
291 if (b[
n - 1] == 0) b[
n - 1] = 1;
292 }
else if (mode == 1) {
293 random_limbs(a,
n, &seed);
299 }
else if (mode == 2) {
300 random_limbs(b,
n, &seed);
311 }
else if (mode == 3) {
312 random_limbs(b,
n, &seed);
314 u64 k = 3 + (xorshift64(&seed) & 0xff);
318 memcpy(exp, b, (
size_t)
n * 8);
323 mp_ptr fx = alloc_limbs(
n + 8), fy = alloc_limbs(
n + 8);
327 memcpy(a, fy, (
size_t)rn * 8);
328 memcpy(b, fx, (
size_t)rn * 8);
336 if (mpn_cmp(a,
an, b,
bn) < 0) {
340 if (mpn_eq(a,
an, b,
bn)) {
349 TEST_CHECK_MSG(mpn_eq(g, gn, exp, expect_len),
"gcd_hgcd known result");
371 u64 seed = 0x853c49e6748fea9bull;
372 const mp_size_t n_values[] = {1, 2, 3, 5, 9, 17, 33, 60};
373 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
375 for (
int iter = 0; iter < 5; ++iter) {
378 mp_ptr u = alloc_limbs(un), v = alloc_limbs(vn), d = alloc_limbs(un),
379 gr = alloc_limbs(un);
380 random_limbs(u, un, &seed);
381 random_limbs(v, vn, &seed);
391 const mp_size_t n_values2[] = {700, 900, 1300};
392 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values2); ++n_index) {
396 random_limbs(u,
n, &seed);
397 random_limbs(v,
n, &seed);
399 if (v[
n - 1] == 0) v[
n - 1] = 1;
414 u64 seed = 0x853c49e6748fea9bull;
415 struct operand_sizes {
mp_size_t un, vn; } sizes[] = {
416 {90, 45}, {90, 44}, {100, 50}, {100, 51}, {130, 64},
417 {130, 65}, {200, 99}, {200, 100}, {200, 50}, {200, 25},
418 {200, 10}, {200, 4}, {333, 166}, {333, 167}, {333, 83},
419 {333, 40}, {333, 5}, {333, 2}, {333, 1},
421 for (
size_t s_index = 0; s_index <
ARRAY_SIZE(sizes); ++s_index) {
422 const struct operand_sizes
s = sizes[s_index];
423 for (
int mode = 0; mode < 3; ++mode) {
425 if (mode == 2 && d <= 3)
continue;
426 for (
int iter = 0; iter < 3; ++iter) {
428 random_limbs(v,
s.vn, &seed);
432 random_limbs(u,
s.un, &seed);
433 }
else if (mode == 1) {
441 u[0] = 0x9e3779b97f4a7c15ull | 1;
442 u[1] = 0x51ce1b7ea4df7c21ull | 1;
443 u[2] = 0x2b44ae9d4d6c8f13ull | 1;
450 TEST_CHECK_MSG(mpn_eq(d1, g1, d2, g2),
"unbalanced gcd_ matches lehmer");
452 TEST_CHECK_MSG(divides_all(d1, g1, u,
s.un),
"unbalanced gcd divides u");
453 TEST_CHECK_MSG(divides_all(d1, g1, v,
s.vn),
"unbalanced gcd divides v");
455 TEST_CHECK_MSG(mpn_eq(d1, g1, v,
s.vn),
"unbalanced exact-multiple gcd is v");
461 TEST_CHECK_MSG(mpn_eq(d3, g3, d1, g1),
"unbalanced gcd_hgcd matches");
471 TEST_RUN(
"numth/gcd", gcd_lehmer_identities);
472 TEST_RUN(
"numth/gcd", gcd_lehmer_large);
473 TEST_RUN(
"numth/gcd", hgcd_matrix_reduction);
474 TEST_RUN(
"numth/gcd", gcd_hgcd_correctness);
475 TEST_RUN(
"numth/gcd", gcd_dispatch);
476 TEST_RUN(
"numth/gcd", gcd_unbalanced);
#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)
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]
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[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 test_gcd_lehmer(void)
mp_size_t lmmp_gcd_lehmer_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(Lehmer算法)
mp_size_t lmmp_hgcd_(lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n)
半扩展欧几里得:将数对原地归约至约一半规模,并累积变换矩阵
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_gcd_hgcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
void lmmp_hgcd_matrix_free_(lmmp_hgcd_matrix_t *M)
释放 hgcd 变换矩阵的元素缓冲
mp_size_t lmmp_fibonacci_size_(ulong n)
计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度
mp_size_t lmmp_fibonacci_(mp_ptr dst, mp_size_t rn, ulong n)
计算 Fibonacci 数 [dst,rn] = F[n]
void lmmp_hgcd_matrix_init_(lmmp_hgcd_matrix_t *M, mp_size_t alloc)
初始化 hgcd 变换矩阵为单位矩阵(堆分配元素缓冲)
#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)
static mp_size_t hgcd_len(const lmmp_hgcd_matrix_t *M, int i, int j)