LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_gcd_lehmer.c
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23#include "lmmp/lmmpn.h"
24#include "lmmp/numth.h"
25#include "cases.h"
27
28#include <string.h>
29
30/*
31 Lehmer / hgcd / 分发入口验证(铁律:无自建算法 oracle,库除法欧几里得
32 参考已删)。验证网:
33 1. 精确锚点:gcd(fib(m), fib(n)) == fib(gcd(m,n))(fib 库构造)、
34 b=1 / a=b+1 / 相邻 fib → gcd=1、a=k*b → gcd=b、u=v*B^d → gcd=v
35 2. 恒等式:乘法消去律 gcd(k*u, k*v) == k*gcd(u,v)、整除性 g|u、g|v
36 3. 库内交叉:lehmer(矩阵路径)× hgcd(分治归约)× 分发器三路径
37 同输入一致——三条路径的归约序列互不相同,错一则失一致
38 4. hgcd 结构:矩阵行关系 (a;b)==M*(a';b')、det==±1、规范序
39*/
40
41static u64 gcd_u64(u64 a, u64 b) {
42 while (b) {
43 u64 t = a % b;
44 a = b;
45 b = t;
46 }
47 return a;
48}
49
50// 读取 hgcd 矩阵元素(去零填充)的有效长度
51static mp_size_t hgcd_len(const lmmp_hgcd_matrix_t* M, int i, int j) { return M->n[i][j]; }
52
53TEST_CASE("numth/gcd", gcd_lehmer_identities) {
54 u64 seed = 0x5ac635d8aa3a93e7ull;
55
56 // 小尺寸随机:lehmer × hgcd 双路径交叉 + 整除性
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) {
59 mp_size_t n = n_values[n_index];
60 for (int iter = 0; iter < 8; ++iter) {
61 mp_size_t un = n + (iter % 5);
62 mp_size_t vn = n > 1 ? n : 1;
63 if (vn > un) vn = un;
64 mp_ptr u = alloc_limbs(un), v = alloc_limbs(vn), d2 = alloc_limbs(un),
65 d3 = alloc_limbs(un);
66 random_limbs(u, un, &seed);
67 random_limbs(v, vn, &seed);
68 mp_size_t g2 = lmmp_gcd_lehmer_(d2, u, un, v, vn);
69 mp_size_t g3 = lmmp_gcd_hgcd_(d3, u, un, v, vn);
70 TEST_CHECK(mpn_eq(d2, g2, d3, g3));
71 TEST_CHECK_MSG(divides_all(d2, g2, u, un), "lehmer divides u");
72 TEST_CHECK_MSG(divides_all(d2, g2, v, vn), "lehmer divides v");
73 lmmp_free(u); lmmp_free(v); lmmp_free(d2); lmmp_free(d3);
74 }
75 }
76
77 // 斐波那契恒等式:gcd(fib(m), fib(n)) == fib(gcd(m,n))(大尺寸精确锚点)。
78 // 长度一律取 fibonacci_ 返回的实际长度(size_ 含 2-4 limb 冗余,缓冲
79 // 上方是未初始化内存,不得作为输入长度);dst 容量取 min(rm,rn)。
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];
86 if (m == n) continue;
89 mp_ptr fm = alloc_limbs(rm), fn = alloc_limbs(rn_),
90 g = alloc_limbs(rn_ < rm ? rn_ : rm), fg = alloc_limbs(rg);
91 mp_size_t lm = lmmp_fibonacci_(fm, rm, m);
92 mp_size_t ln = lmmp_fibonacci_(fn, rn_, n);
93 mp_size_t lg = lmmp_fibonacci_(fg, rg, gcd_u64(m, n));
94 mp_size_t gn = lmmp_gcd_lehmer_(g, fm, lm, fn, ln);
95 TEST_CHECK(mpn_eq(g, gn, fg, lg));
96 lmmp_free(fm); lmmp_free(fn); lmmp_free(g); lmmp_free(fg);
97 }
98 }
99
100 // 乘法消去律:gcd(k*u, k*v) == k*gcd(u,v)
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) {
103 mp_size_t n = 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);
108 mp_size_t gn = lmmp_gcd_lehmer_(g, u, n, v, n);
109 u64 k = xorshift64(&seed) | 1;
110 u64 h1 = lmmp_mul_1_(ku, u, n, k);
111 u64 h2 = lmmp_mul_1_(kv, v, n, k);
112 u64 h3 = lmmp_mul_1_(kg, g, gn, k);
113 mp_size_t kun = h1 ? n + 1 : n, kvn = h2 ? n + 1 : n;
114 if (h1) ku[n] = h1;
115 if (h2) kv[n] = h2;
116 mp_size_t kgn = h3 ? gn + 1 : gn;
117 if (h3) kg[gn] = h3;
118 mp_size_t g2 = lmmp_gcd_lehmer_(t, ku, kun, kv, kvn);
119 TEST_CHECK(mpn_eq(t, g2, kg, kgn));
120 lmmp_free(u); lmmp_free(v); lmmp_free(g); lmmp_free(ku); lmmp_free(kv);
121 lmmp_free(kg); lmmp_free(t);
122 }
123}
124
125TEST_CASE("numth/gcd", gcd_lehmer_large) {
126 // 回归:A==0 分支曾用 b 而非 q*b 作减数,且 bn 被乘积进位污染,
127 // 未初始化 limb 可能混入结果。大尺寸与悬殊比例都会经过 Lehmer 矩阵路径。
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) {
133 mp_ptr u = alloc_limbs(s.un);
134 mp_ptr v = alloc_limbs(s.vn);
135 mp_ptr d = alloc_limbs(s.vn);
136 random_limbs(u, s.un, &seed);
137 random_limbs(v, s.vn, &seed);
138 mp_size_t gn = lmmp_gcd_lehmer_(d, u, s.un, v, s.vn);
139 TEST_CHECK_MSG(gn > 0, "gcd positive length");
140 TEST_CHECK_MSG(divides_all(d, gn, u, s.un), "gcd divides u");
141 TEST_CHECK_MSG(divides_all(d, gn, v, s.vn), "gcd divides v");
142 // 与 hgcd 入口交叉一致
143 mp_ptr d2 = alloc_limbs(s.vn);
144 mp_size_t g2 = lmmp_gcd_hgcd_(d2, u, s.un, v, s.vn);
145 TEST_CHECK(mpn_eq(d, gn, d2, g2));
146 lmmp_free(u); lmmp_free(v); lmmp_free(d); lmmp_free(d2);
147 }
148 }
149}
150
151TEST_CASE("numth/gcd", hgcd_matrix_reduction) {
152 // hgcd 结构正确性:矩阵关系 (a;b) == M*(a';b')、行列式 [1|-1]、规模折半、规范序。
153 // gcd 不变性由矩阵关系(幺模变换)数学保证。关系重建全用库乘加。
154 // 零长矩阵元素(单位阵提前返回形态)跳过乘法,零垫乘积段。
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) {
158 mp_size_t n = 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) {
162 mp_size_t N = n; // 本迭代工作长度(fib 分支取 F(k+1) 实际长度)
163 mp_ptr a = alloc_limbs(n + 8);
164 mp_ptr b = alloc_limbs(n + 8);
165 if (bmode == 3) {
166 // 相邻 Fibonacci 对(商全 1 的最坏情形),fib_pair 库构造;
167 // 按实际长度 N 拷贝保证 a 顶 limb 非零(hgcd 归一化契约)
168 mp_ptr fx = alloc_limbs(n + 8), fy = alloc_limbs(n + 8);
169 N = fib_pair(fx, fy, n + 8, n);
170 lmmp_zero(a, n + 8);
171 lmmp_zero(b, n + 8);
172 memcpy(a, fy, (size_t)N * 8); // a = F(k+1)(大者)
173 memcpy(b, fx, (size_t)N * 8); // b = F(k)(高位已零垫)
174 lmmp_free(fx);
175 lmmp_free(fy);
176 } else {
177 random_limbs(a, n, &seed);
178 if (bmode == 0) {
179 random_limbs(b, n, &seed);
180 b[n - 1] >>= 1;
181 if (b[n - 1] == 0) b[n - 1] = 1;
182 } else if (bmode == 1) {
183 mp_size_t bn = n / 2 + 1;
184 random_limbs(b, bn, &seed);
185 for (mp_size_t i = bn; i < n; ++i) b[i] = 0;
186 } else {
187 b[0] = 0x9e3779b97f4a7c15ull | 1;
188 for (mp_size_t i = 1; i < n; ++i) b[i] = 0;
189 }
190 }
191 if (mpn_cmp(a, N, b, N) < 0) {
192 mp_ptr t = a; a = b; b = t;
193 }
194 if (mpn_eq(a, N, b, N)) {
195 lmmp_free(a); lmmp_free(b);
196 continue; // hgcd 契约要求 a > b
197 }
198 mp_ptr wa = alloc_limbs(N), wb = alloc_limbs(N);
199 lmmp_copy(wa, a, N);
200 lmmp_copy(wb, b, N);
202 lmmp_hgcd_matrix_init_(&M, N + 2);
203 mp_size_t nn = lmmp_hgcd_(&M, wa, wb, N);
204 if (nn > 0) {
205 // 行关系:m00*a' + m01*b' == a;m10*a' + m11*b' == b
206 for (int row = 0; row < 2; ++row) {
207 mp_size_t lm0 = hgcd_len(&M, row, 0), lm1 = hgcd_len(&M, row, 1);
208 mp_size_t mx = lm0 + nn + lm1 + nn + 4;
209 mp_ptr p1 = alloc_limbs(mx), p2 = alloc_limbs(mx), sum = alloc_limbs(mx);
210 lmmp_zero(p1, lm0 + nn); // 零长元素形态下乘积段保持零
211 if (lm0 > 0) {
212 if (lm0 >= nn) lmmp_mul_(p1, M.m[row][0], lm0, wa, nn);
213 else lmmp_mul_(p1, wa, nn, M.m[row][0], lm0);
214 }
215 lmmp_zero(p2, lm1 + nn);
216 if (lm1 > 0) {
217 if (lm1 >= nn) lmmp_mul_(p2, M.m[row][1], lm1, wb, nn);
218 else lmmp_mul_(p2, wb, nn, M.m[row][1], lm1);
219 }
220 mp_size_t l1 = lm0 + nn, l2 = lm1 + nn;
221 pad_add(p1, l1, p2, l2, mx, sum);
222 const mp_limb_t* expectv = row == 0 ? a : b;
223 TEST_CHECK_MSG(mpn_eq(sum, mx, expectv, N), "hgcd row relation");
224 lmmp_free(p1); lmmp_free(p2); lmmp_free(sum);
225 }
226 // det = m00*m11 - m01*m10 == ±1(等长零垫后相减)
227 {
228 mp_size_t l00 = hgcd_len(&M, 0, 0), l11 = hgcd_len(&M, 1, 1);
229 mp_size_t l01 = hgcd_len(&M, 0, 1), l10 = hgcd_len(&M, 1, 0);
230 mp_size_t l0 = l00 + l11, l1 = l01 + l10;
231 mp_size_t mx = (l0 > l1 ? l0 : l1) + 1;
232 mp_ptr p0 = alloc_limbs(mx), p1 = alloc_limbs(mx), q0 = alloc_limbs(mx),
233 q1 = alloc_limbs(mx), diff = alloc_limbs(mx);
234 lmmp_zero(q0, l0); // 任一因子零长时乘积段保持零
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);
238 }
239 lmmp_zero(q1, l1);
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);
243 }
244 lmmp_zero(p0, mx); memcpy(p0, q0, (size_t)l0 * 8);
245 lmmp_zero(p1, mx); memcpy(p1, q1, (size_t)l1 * 8);
246 lmmp_sub_(diff, p0, mx, p1, mx);
247 mp_size_t dl = norm_len(diff, mx);
248 bool det_ok = (dl == 1 && diff[0] == 1); // 差恰为 +1(dl==0 为奇异阵,拒)
249 if (!det_ok) {
250 lmmp_sub_(diff, p1, mx, p0, mx); // 反向:差为 +1 ⟺ 原差为 -1
251 dl = norm_len(diff, mx);
252 det_ok = (dl == 1 && diff[0] == 1);
253 }
254 TEST_CHECK_MSG(det_ok, "hgcd det == +-1");
255 lmmp_free(p0); lmmp_free(p1); lmmp_free(q0); lmmp_free(q1); lmmp_free(diff);
256 }
257 TEST_CHECK_MSG(mpn_cmp(wa, nn, wb, nn) >= 0, "hgcd canonical order");
258 } else {
259 // 无归约合法(如下限阻止),此时数对应未被破坏
260 TEST_CHECK_MSG(mpn_eq(wa, N, a, N) && mpn_eq(wb, N, b, N),
261 "hgcd no-reduction keeps pair");
262 }
264 lmmp_free(a); lmmp_free(b); lmmp_free(wa); lmmp_free(wb);
265 }
266 }
267 }
268}
269
270TEST_CASE("numth/gcd", gcd_hgcd_correctness) {
271 // gcd_hgcd:构造形态(b=1、a=b+1、a=k*b、相邻 fib)给出精确已知 gcd;
272 // 随机形态与 lehmer(独立归约序列)交叉;全部形态附整除性。
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) {
276 mp_size_t n = 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) {
280 mp_ptr a = alloc_limbs(n + 2);
281 mp_ptr b = alloc_limbs(n + 2);
282 lmmp_zero(a, n + 2); // 清掉容量冗余段:norm_len(a,n+2) 不得吃到垃圾
283 lmmp_zero(b, n + 2);
284 mp_ptr exp = alloc_limbs(n + 2); // 已知期望值缓冲
285 mp_size_t bn = n;
286 mp_size_t expect_len = 0; // 0 = 无已知期望
287 if (mode == 0) { // 随机同长
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) { // b = 1 → gcd = 1
293 random_limbs(a, n, &seed);
294 b[0] = 1;
295 for (mp_size_t i = 1; i < n; ++i) b[i] = 0;
296 bn = 1;
297 exp[0] = 1;
298 expect_len = 1;
299 } else if (mode == 2) { // a = b+1 → gcd = 1
300 random_limbs(b, n, &seed);
301 lmmp_copy(a, b, n);
302 mp_limb_t carry = 1;
303 for (mp_size_t i = 0; i < n && carry; ++i) {
304 mp_limb_t t = a[i] + carry;
305 carry = t < carry;
306 a[i] = t;
307 }
308 if (carry) a[n] = 1; // b 全 F 形态:a = B^n,gcd 仍为 1
309 exp[0] = 1;
310 expect_len = 1;
311 } else if (mode == 3) { // a = k*b(gcd 恰为 b,库 mul_1 构造)
312 random_limbs(b, n, &seed);
313 b[0] |= 1;
314 u64 k = 3 + (xorshift64(&seed) & 0xff);
315 lmmp_zero(a, n + 2);
316 u64 hi = lmmp_mul_1_(a, b, n, k);
317 if (hi) a[n] = hi;
318 memcpy(exp, b, (size_t)n * 8);
319 expect_len = n;
320 } else { // 相邻 Fibonacci(gcd = 1,数学已知)
321 // 容量含 size_ 冗余(2-4 limb):fib_pair 内部需以 need 调
322 // fibonacci2_,缓冲不足会跳过唯一可行档位
323 mp_ptr fx = alloc_limbs(n + 8), fy = alloc_limbs(n + 8);
324 mp_size_t rn = fib_pair(fx, fy, n + 8, n);
325 lmmp_zero(a, n + 2);
326 lmmp_zero(b, n + 2);
327 memcpy(a, fy, (size_t)rn * 8);
328 memcpy(b, fx, (size_t)rn * 8);
329 exp[0] = 1;
330 expect_len = 1;
331 lmmp_free(fx);
332 lmmp_free(fy);
333 }
334
335 mp_size_t an = norm_len(a, n + 2);
336 if (mpn_cmp(a, an, b, bn) < 0) {
337 mp_ptr t = a; a = b; b = t;
338 mp_size_t tn = an; an = bn; bn = tn;
339 }
340 if (mpn_eq(a, an, b, bn)) {
341 lmmp_free(a); lmmp_free(b);
342 lmmp_free(exp);
343 continue;
344 }
345
346 mp_ptr g = alloc_limbs(an);
347 mp_size_t gn = lmmp_gcd_hgcd_(g, a, an, b, bn);
348 if (expect_len) {
349 TEST_CHECK_MSG(mpn_eq(g, gn, exp, expect_len), "gcd_hgcd known result");
350 } else {
351 // 随机形态:与 lehmer 交叉(两条归约路径必同值)
352 mp_ptr d2 = alloc_limbs(an);
353 mp_size_t g2 = lmmp_gcd_lehmer_(d2, a, an, b, bn);
354 TEST_CHECK_MSG(mpn_eq(g, gn, d2, g2), "gcd_hgcd vs lehmer");
355 lmmp_free(d2);
356 }
357 TEST_CHECK_MSG(divides_all(g, gn, a, an), "gcd divides a");
358 TEST_CHECK_MSG(divides_all(g, gn, b, bn), "gcd divides b");
359 lmmp_free(g);
360 lmmp_free(a);
361 lmmp_free(b);
362 lmmp_free(exp);
363 }
364 }
365 }
366}
367
368TEST_CASE("numth/gcd", gcd_dispatch) {
369 // 通用分发入口:随机输入与 Lehmer 交叉 + 整除性(<GCD_HGCD_THRESHOLD 分发
370 // 到 lehmer/gcd_1/gcd_2,交叉覆盖各档一致性;>=86 走 hgcd 与 lehmer 独立)
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) {
374 mp_size_t n = n_values[n_index];
375 for (int iter = 0; iter < 5; ++iter) {
376 mp_size_t un = n;
377 mp_size_t vn = 1 + (mp_size_t)(xorshift64(&seed) % (u64)n);
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);
382 mp_size_t gn = lmmp_gcd_(d, u, un, v, vn);
383 mp_size_t ln = lmmp_gcd_lehmer_(gr, u, un, v, vn);
384 TEST_CHECK(mpn_eq(d, gn, gr, ln));
385 TEST_CHECK_MSG(divides_all(d, gn, u, un), "gcd_ divides u");
386 lmmp_free(u); lmmp_free(v); lmmp_free(d); lmmp_free(gr);
387 }
388 }
389
390 // 大尺寸(Lehmer 与 hgcd 两条路径)交叉一致 + 整除性
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) {
393 mp_size_t n = n_values2[n_index];
394 mp_ptr u = alloc_limbs(n);
395 mp_ptr v = alloc_limbs(n);
396 random_limbs(u, n, &seed);
397 random_limbs(v, n, &seed);
398 v[n - 1] >>= 1;
399 if (v[n - 1] == 0) v[n - 1] = 1;
400 mp_ptr d1 = alloc_limbs(n);
401 mp_ptr d2 = alloc_limbs(n);
402 mp_size_t g1 = lmmp_gcd_lehmer_(d1, u, n, v, n);
403 mp_size_t g2 = lmmp_gcd_(d2, u, n, v, n);
404 TEST_CHECK_MSG(mpn_eq(d1, g1, d2, g2), "gcd_ matches lehmer");
405 TEST_CHECK_MSG(divides_all(d2, g2, u, n), "gcd_ divides u");
406 lmmp_free(u); lmmp_free(v); lmmp_free(d1); lmmp_free(d2);
407 }
408}
409
410TEST_CASE("numth/gcd", gcd_unbalanced) {
411 // 不平衡输入系统覆盖:预归约路径(un >= 2*vn 触发)、2:1 边界两侧、
412 // 整除早退(r == 0)、链式取模(余数仍显著短于除数)、单/双 limb 除数。
413 // 与 Lehmer(原生处理不平衡)交叉对照 + 整除性验证
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},
420 };
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) {
424 mp_size_t d = s.un - s.vn;
425 if (mode == 2 && d <= 3) continue; // 链式取模形态需要余数空间
426 for (int iter = 0; iter < 3; ++iter) {
427 mp_ptr v = alloc_limbs(s.vn);
428 random_limbs(v, s.vn, &seed);
429 mp_ptr u = alloc_limbs(s.un);
430 if (mode == 0) {
431 // 随机(余数均匀分布,通常 1~2 次预归约后平衡)
432 random_limbs(u, s.un, &seed);
433 } else if (mode == 1) {
434 // u = v * B^d:整除,gcd = v(预归约 r == 0 早退)
435 lmmp_zero(u, d);
436 lmmp_copy(u + d, v, s.vn);
437 } else {
438 // u = v * B^d + tiny:余数仅 3 limb,触发链式取模
439 lmmp_zero(u, d);
440 lmmp_copy(u + d, v, s.vn);
441 u[0] = 0x9e3779b97f4a7c15ull | 1;
442 u[1] = 0x51ce1b7ea4df7c21ull | 1;
443 u[2] = 0x2b44ae9d4d6c8f13ull | 1;
444 }
445
446 mp_ptr d1 = alloc_limbs(s.un);
447 mp_ptr d2 = alloc_limbs(s.un);
448 mp_size_t g1 = lmmp_gcd_(d1, u, s.un, v, s.vn);
449 mp_size_t g2 = lmmp_gcd_lehmer_(d2, u, s.un, v, s.vn);
450 TEST_CHECK_MSG(mpn_eq(d1, g1, d2, g2), "unbalanced gcd_ matches lehmer");
451 TEST_CHECK_MSG(g1 > 0, "unbalanced gcd positive length");
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");
454 if (mode == 1) {
455 TEST_CHECK_MSG(mpn_eq(d1, g1, v, s.vn), "unbalanced exact-multiple gcd is v");
456 }
457 // 大输入直接走 hgcd 分治入口(含预归约)复核
458 if (s.un >= 100) {
459 mp_ptr d3 = alloc_limbs(s.un);
460 mp_size_t g3 = lmmp_gcd_hgcd_(d3, u, s.un, v, s.vn);
461 TEST_CHECK_MSG(mpn_eq(d3, g3, d1, g1), "unbalanced gcd_hgcd matches");
462 lmmp_free(d3);
463 }
464 lmmp_free(u); lmmp_free(v); lmmp_free(d1); lmmp_free(d2);
465 }
466 }
467 }
468}
469
470void test_gcd_lehmer(void) {
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);
477}
#define k
#define an
#define bn
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
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
定义 mul_1.c:27
#define t
#define s
#define n
void test_gcd_lehmer(void)
mp_size_t n[2][2]
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)
计算两个无符号整数的最大公约数(通用分发入口)
定义 gcd.c:27
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 变换矩阵的元素缓冲
uint64_t ulong
定义 numth.h:39
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 变换矩阵为单位矩阵(堆分配元素缓冲)
hgcd 变换矩阵
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_RUN(category, name)
定义 test.h:36
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)