LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_gcdext.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 gcdext 验证(铁律:无自建算法 oracle,库除法欧几里得参考已删):
32 1. 贝祖恒等式 |s|*u ± |t|*v == g(32 位素数模同余)与极小系数界
33 2*|s|*g <= v(库乘重建)
34 2. g 值与 gcd_lehmer_ / gcd_2 独立路径交叉(归约序列不同)
35 3. 写死构造:v|u → s=0、g=v;相邻 Fibonacci → g=1;u-1 → g=1
36 4. 标量入口(gcdext_11):64 位 % 欧几里得标量参考 + 穷举小值
37*/
38
39static u64 gcd_u64(u64 a, u64 b) {
40 while (b) {
41 u64 t = a % b;
42 a = b;
43 b = t;
44 }
45 return a;
46}
47
48// 有符号系数的绝对值写入 [out](sn 为 mp_ssize_t,负表示负系数)
50 mp_size_t l = sn < 0 ? (mp_size_t)-sn : (mp_size_t)sn;
51 memcpy(out, s, (size_t)l * 8);
52 return l;
53}
54
55// 贝祖恒等式(模同余):|s|*u ± |t|*v ≡ g (mod p)(符号按 sn/tn;同负取负)
56static bool bezout_identity_l(const mp_limb_t* u, mp_size_t un, const mp_limb_t* v, mp_size_t vn,
57 const mp_limb_t* g, mp_size_t gn, mp_ptr s, mp_ssize_t sn, mp_ptr t,
58 mp_ssize_t tn) {
59 mp_size_t cap = un + vn + 8;
60 mp_ptr sa = alloc_limbs(cap), ta = alloc_limbs(cap);
61 mp_size_t ls = abs_coeffs(sa, s, sn), lt = abs_coeffs(ta, t, tn);
62 bool ok = true;
63 for (int i = 0; i < MOD_P_CNT && ok; ++i) {
64 u64 p = MOD_P[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);
71 }
72 lmmp_free(sa);
73 lmmp_free(ta);
74 return ok;
75}
76
77// 极小系数界:2*|s|*g <= v(库乘重建)
78static 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,
79 mp_ssize_t sn) {
80 mp_size_t cap = vn + gn + 4;
81 mp_ptr sa = alloc_limbs(cap), x = alloc_limbs(cap);
82 mp_size_t ls = abs_coeffs(sa, s, sn);
83 if (ls == 0) {
84 lmmp_free(sa);
85 lmmp_free(x);
86 return true;
87 }
88 if (ls >= gn) lmmp_mul_(x, sa, ls, g, gn);
89 else lmmp_mul_(x, g, gn, sa, ls);
90 mp_size_t lx = ls + gn;
91 lmmp_zero(x + lx, cap - lx);
92 lmmp_add_n_(x, x, x, cap); // x *= 2
93 bool ok = mpn_cmp(x, cap, v, vn) <= 0;
94 lmmp_free(sa);
95 lmmp_free(x);
96 return ok;
97}
98
99// 标量贝祖:模同余检查(s*u + t*v ≡ g (mod p),32 位素数集)
100static bool scalar_bezout(u64 u, u64 v, u64 g, slong s, slong t) {
101 u64 sa = s < 0 ? (u64)-s : (u64)s;
102 u64 ta = t < 0 ? (u64)-t : (u64)t;
103 for (int i = 0; i < MOD_P_CNT; ++i) {
104 u64 p = MOD_P[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);
109 // 同负号时 s*u+t*v = -(ps+pt),须 ≡ g
110 if ((s < 0) && (t < 0)) lhs = (p - lhs) % p;
111 if (lhs != g % p) return false;
112 }
113 return true;
114}
115
116// 汇总检查:恒等式 + 界(g 值由调用方另行验证)
118 mp_srcptr u, mp_size_t un, mp_srcptr v, mp_size_t vn) {
119 if (!bezout_identity_l(u, un, v, vn, g, gn, s, sn, t, tn)) return false;
120 if (!coeff_bound_l(v, vn, g, gn, s, sn)) return false;
121 if (!(mpn_eq(u, un, v, vn)) && !coeff_bound_l(u, un, g, gn, t, tn))
122 return false; // u==v 时 t=1 越界(定理前提 u!=v)
123 return true;
124}
125
126TEST_CASE("numth/gcdext", gcdext_11) {
127 // 穷举小值:恒等式 + 界 + 标量参考
128 for (u64 u = 1; u <= 300; ++u) {
129 for (u64 v = 1; v <= 300; ++v) {
130 slong s, t;
131 ulong g = lmmp_gcdext_11_(u, v, &s, &t);
132 if (g != gcd_u64(u, v)) TEST_CHECK_MSG(false, "gcd mismatch");
133 TEST_CHECK_MSG(scalar_bezout(u, v, g, s, t), "bezout identity");
134 u64 sa = s < 0 ? (u64)-s : (u64)s;
135 u64 ta = t < 0 ? (u64)-t : (u64)t;
136 TEST_CHECK_MSG(2 * sa * g <= v, "s bound");
137 if (u != v) TEST_CHECK_MSG(2 * ta * g <= u, "t bound");
138 }
139 }
140 // 随机 64 位
141 u64 seed = 0x6d2b79f5ull;
142 for (int i = 0; i < 20000; ++i) {
143 u64 u = xorshift64(&seed), v = xorshift64(&seed);
144 if (u == 0) u = 1;
145 if (v == 0) v = 1;
146 slong s, t;
147 ulong g = lmmp_gcdext_11_(u, v, &s, &t);
148 TEST_CHECK_MSG(scalar_bezout(u, v, g, s, t), "bezout identity random");
149 TEST_CHECK_MSG(g == gcd_u64(u, v), "gcd random");
150 u64 sa = s < 0 ? (u64)-s : (u64)s;
151 TEST_CHECK_MSG(sa <= v / g / 2, "s bound random"); // 2*sa*g<=v 的无溢出形式
152 }
153 // 确定性边界:相等、整除、极值、t=NULL
154 slong s, t;
155 TEST_CHECK_EQ(lmmp_gcdext_11_(7, 7, &s, &t), 7u);
156 TEST_CHECK(s == 0 && t == 1);
157 TEST_CHECK_EQ(lmmp_gcdext_11_(UINT64_MAX, UINT64_MAX, &s, &t), UINT64_MAX);
158 TEST_CHECK(s == 0 && t == 1);
159 TEST_CHECK_EQ(lmmp_gcdext_11_(UINT64_MAX, 3, &s, &t), 3u); // 3 | 2^64-1
160 TEST_CHECK(scalar_bezout(UINT64_MAX, 3, 3, s, t));
161 TEST_CHECK_EQ(lmmp_gcdext_11_(1, UINT64_MAX, &s, &t), 1u);
162 TEST_CHECK(scalar_bezout(1, UINT64_MAX, 1, s, t));
163 lmmp_gcdext_11_(12345, 6789, &s, NULL); // t=NULL 路径
164}
165
166TEST_CASE("numth/gcdext", gcdext_1) {
167 u64 seed = 0x3c6ef372fe94f82bull;
168 for (mp_size_t un = 1; un <= 24; ++un) {
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);
174 mp_ssize_t sn, tn;
175 mp_size_t gn = lmmp_gcdext_1_(g, s, &sn, t, &tn, u, un, v);
176 TEST_CHECK_MSG(gn == 1, "g length");
177 // g 值标量参考:gcd(u, v) == gcd(u mod v, v)
178 TEST_CHECK_MSG(g[0] == gcd_u64(lmmp_mod_1_(u, un, v), v), "g value");
179 TEST_CHECK_MSG(check_gcdext(g, gn, s, sn, t, tn, u, un, &v, 1), "identity");
180 // dstt=NULL
181 mp_ssize_t sn2;
182 mp_size_t gn2 = lmmp_gcdext_1_(g, s, &sn2, NULL, NULL, u, un, v);
183 TEST_CHECK_MSG(gn2 == 1 && sn2 == sn, "null t keeps s");
185 }
186 }
187 // dstg 与 up 别名(eqsep 契约)
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);
190 mp_limb_t vp[1] = {12345};
191 mp_ssize_t sn, tn;
192 lmmp_gcdext_1_(g, s, &sn, t, &tn, u, 5, 12345);
193 TEST_CHECK_MSG(check_gcdext(g, 1, s, sn, t, tn, u, 5, vp, 1), "gcdext_1 baseline identity");
194 TEST_CHECK_MSG(g[0] == gcd_u64(lmmp_mod_1_(u, 5, 12345), 12345), "baseline");
195 lmmp_copy(g, u, 5);
196 lmmp_gcdext_1_(g, s, &sn, NULL, NULL, g, 5, 12345);
197 TEST_CHECK_MSG(g[0] == gcd_u64(lmmp_mod_1_(u, 5, 12345), 12345), "alias dstg=up");
199}
200
201TEST_CASE("numth/gcdext", gcdext_2) {
202 u64 seed = 0x9e3779b97f4a7c15ull;
203 for (mp_size_t un = 3; un <= 30; ++un) {
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);
209 mp_ssize_t sn, tn;
210 mp_size_t gn = lmmp_gcdext_2_(g, s, &sn, t, &tn, u, un, v);
211 // g 与库 gcd_2 一致(交叉)+ 恒等式 + 界
212 mp_ptr g2 = alloc_limbs(2);
213 mp_size_t gn2 = lmmp_gcd_2_(g2, u, un, v);
214 TEST_CHECK_MSG(mpn_eq(g, gn, g2, gn2), "g matches gcd_2");
215 TEST_CHECK_MSG(check_gcdext(g, gn, s, sn, t, tn, u, un, v, 2), "identity");
217 }
218 }
219 // v | u:s=0、t=1(u = k*v 经库 mul_1 构造)
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);
225 u64 hi = lmmp_mul_1_(u, v, 2, k);
226 mp_size_t un = hi ? 3 : 2;
227 if (hi) u[2] = hi;
228 mp_ptr g = alloc_limbs(2), s = alloc_limbs(2);
229 mp_ssize_t sn;
230 mp_size_t gn = lmmp_gcdext_2_(g, s, &sn, NULL, NULL, u, un, v);
231 TEST_CHECK_MSG(mpn_eq(g, gn, v, 2) && sn == 0, "exact multiple");
233 }
234}
235
236// 对一对 limb 数组跑 lmmp_gcdext_ 并全检查(允许 un/vn 任意次序)。
237// v 的容量取 max(un,vn):mode 2/4 会把 un limb 的 u 拷入 v(近邻构造)。
238static void run_gcdext_pair(u64 *seed, mp_size_t un, mp_size_t vn, int mode) {
239 mp_ptr u = alloc_limbs(un + 2), v = alloc_limbs((un > vn ? un : vn) + 2);
240 if (mode == 0) { // 随机
241 random_limbs(u, un, seed);
242 random_limbs(v, vn, seed);
243 } else if (mode == 1) { // u = v * k(整除:s=0、g=v;库 mul_1 构造)
244 random_limbs(v, vn, seed);
245 lmmp_zero(u, un + 2);
246 u64 k = 3 + (xorshift64(seed) & 0xFF);
247 u64 hi = lmmp_mul_1_(u, v, vn, k);
248 un = hi ? vn + 1 : vn;
249 if (hi) u[vn] = hi;
250 } else if (mode == 2) { // 近邻(v = u - small)
251 random_limbs(u, un, seed);
252 lmmp_copy(v, u, un);
253 vn = un;
254 sub_small_inplace(v, vn, 1 + (xorshift64(seed) & 0xFF));
255 vn = norm_len(v, vn);
256 } else if (mode == 4) { // 近邻极值 v = u - 1:gcd 恒 1
257 random_limbs(u, un, seed);
258 if (u[0] == 0) u[0] = 2; // 保证借位减 u-1 仍在 un limb 内
259 lmmp_copy(v, u, un);
260 vn = un;
261 sub_small_inplace(v, vn, 1);
262 vn = norm_len(v, vn);
263 } else { // gcd > 1:u = 2x、v = 2y(库 add_n 翻倍)
264 random_limbs(u, un, seed);
265 random_limbs(v, vn, seed);
266 lmmp_zero(u + un, 1);
267 lmmp_zero(v + vn, 1);
268 lmmp_add_n_(u, u, u, un + 1);
269 lmmp_add_n_(v, v, v, vn + 1);
270 un = norm_len(u, un + 1);
271 vn = norm_len(v, vn + 1);
272 }
273 mp_ptr g = alloc_limbs(un + vn);
274 /* s 容量按两个方向的最大 vn 取(swapped 调用时 s/t 角色互换) */
275 mp_size_t mx = (vn > un ? vn : un) + 1;
276 mp_ptr s = alloc_limbs(mx), t = alloc_limbs(mx);
277 mp_ssize_t sn, tn;
278 mp_size_t gn = lmmp_gcdext_(g, s, &sn, t, &tn, u, un, v, vn);
279 mp_ptr gsave = alloc_limbs(un + vn); // 首次调用的 g(已验证),别名检查参照
280 mp_size_t gns = gn;
281 memcpy(gsave, g, (size_t)gn * 8);
282 if (mode == 1) {
283 TEST_CHECK_MSG(mpn_eq(g, gn, v, vn) && sn == 0, "exact multiple gcd/s");
284 } else if (mode == 4) {
285 TEST_CHECK_MSG(gn == 1 && g[0] == 1, "neighbor-1 gcd");
286 TEST_CHECK_MSG(check_gcdext(g, gn, s, sn, t, tn, u, un, v, vn), "neighbor-1 identity");
287 } else {
288 // g 与 gcd_lehmer_ 独立路径交叉(gcdext_lehmer/gcdext_hgcd 的 g 计算
289 // 与 gcd_lehmer 分属不同实现文件,归约序列不同)
290 mp_ptr gr = alloc_limbs(un + vn);
291 mp_size_t en = lmmp_gcd_lehmer_(gr, u, un, v, vn);
292 TEST_CHECK_MSG(mpn_eq(g, gn, gr, en), "g vs gcd_lehmer_");
293 lmmp_free(gr);
294 TEST_CHECK_MSG(check_gcdext(g, gn, s, sn, t, tn, u, un, v, vn), "identity");
295 }
296 // 参数交换(s/t 角色互换)
297 mp_ssize_t sn2, tn2;
298 mp_size_t gn2 = lmmp_gcdext_(g, s, &sn2, t, &tn2, v, vn, u, un);
299 if (mode == 4) {
300 TEST_CHECK_MSG(gn2 == 1 && g[0] == 1, "neighbor-1 swapped gcd");
301 } else if (mode == 1) {
302 // u = k*v:交换后 gcd(v, u) 仍为 v;极小系数下 s=1、t=0(对称于
303 // 首调的 sn==0,|t|<=v/(2g)=1/2 强制 t=0、s*v=v 强制 s=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");
308 } else {
309 TEST_CHECK_MSG(check_gcdext(g, gn2, s, sn2, t, tn2, v, vn, u, un), "swapped");
310 }
311 // dstt=NULL
312 mp_ssize_t sn3;
313 lmmp_gcdext_(g, s, &sn3, NULL, NULL, u, un, v, vn);
314 TEST_CHECK_MSG(sn3 == sn, "null t keeps s");
315 // dstg 与 up 别名(参照首次调用已验证的 g 值)
316 mp_ptr u2 = alloc_limbs(un + vn);
317 lmmp_copy(u2, u, un);
318 mp_size_t gna = lmmp_gcdext_(u2, s, &sn, NULL, NULL, u2, un, v, vn);
319 TEST_CHECK_MSG(gna == gns, "alias dstg=up length");
320 TEST_CHECK_MSG(mpn_eq(u2, gn, gsave, gns), "alias dstg=up");
322 lmmp_free(u2);
323 lmmp_free(gsave);
324}
325
326TEST_CASE("numth/gcdext", gcdext_lehmer_and_dispatch) {
327 u64 seed = 0x5ac635d8aa3a93e7ull;
328 // 尺寸矩阵:跨 1/2/多 limb、GCD_HGCD_THRESHOLD=86 两侧、平衡与悬殊
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},
333 }; // 大尺寸 gcdext 由 gcd 三路径交叉 + 贝祖恒等式覆盖
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) {
339 run_gcdext_pair(&seed, sz.un, sz.vn, mode);
340 }
341 }
342 }
343}
344
345TEST_CASE("numth/gcdext", gcdext_fibonacci) {
346 // 相邻斐波那契(商全 1、系数最大形态);fibonacci2_ 库构造相邻对
347 // F(k), F(k-1),gcd=1 为数学已知
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) {
350 mp_size_t n = n_values[n_index];
351 ulong k = 3;
352 for (;; ++k) {
353 if (lmmp_fibonacci_size_(k) >= n) break;
354 }
356 mp_ptr u = alloc_limbs(rn + 1), v = alloc_limbs(rn + 1);
357 lmmp_zero(u, rn + 1);
358 lmmp_zero(v, rn + 1);
359 lmmp_fibonacci2_(u, v, rn, k); // 契约:u=F(k), v=F(k-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);
362 mp_ssize_t sn, tn;
363 mp_size_t gn = lmmp_gcdext_(g, s, &sn, t, &tn, u, un, v, vn);
364 TEST_CHECK_MSG(gn == 1 && g[0] == 1, "fibonacci gcd 1");
365 TEST_CHECK_MSG(check_gcdext(g, gn, s, sn, t, tn, u, un, v, vn), "fibonacci identity");
367 }
368}
369
370TEST_CASE("numth/gcdext", gcdext_large_cross) {
371 // 大尺寸(gcdext 分发走 hgcd 分治):贝祖恒等式 + 系数界 + g 与
372 // gcd_lehmer_/gcd_ 双路径交叉(归约序列互异)
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);
380 v[sz.vn - 1] >>= 1;
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);
384 mp_ssize_t sn, tn;
385 mp_size_t gn = lmmp_gcdext_(g, s, &sn, t, &tn, u, sz.un, v, sz.vn);
386 mp_size_t en = lmmp_gcd_lehmer_(gr, u, sz.un, v, sz.vn);
387 mp_size_t hn = lmmp_gcd_(g2, u, sz.un, v, sz.vn);
388 TEST_CHECK_MSG(mpn_eq(g, gn, gr, en), "gcdext g vs lehmer");
389 TEST_CHECK_MSG(mpn_eq(g, gn, g2, hn), "gcdext g vs gcd_");
390 TEST_CHECK_MSG(check_gcdext(g, gn, s, sn, t, tn, u, sz.un, v, sz.vn), "bezout+bounds");
392 lmmp_free(gr); lmmp_free(g2);
393 }
394}
395
396void test_gcdext(void) {
397 TEST_RUN("numth/gcdext", gcdext_11);
398 TEST_RUN("numth/gcdext", gcdext_1);
399 TEST_RUN("numth/gcdext", gcdext_2);
400 TEST_RUN("numth/gcdext", gcdext_lehmer_and_dispatch);
401 TEST_RUN("numth/gcdext", gcdext_fibonacci);
402 TEST_RUN("numth/gcdext", gcdext_large_cross);
403}
#define k
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
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
int64_t mp_ssize_t
定义 lmmp.h:95
uint64_t mp_limb_t
定义 lmmp.h:92
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)
单精度数取余
定义 div.c:38
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
定义 mul_1.c:27
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]
定义 add_n.c:76
#define t
#define s
#define n
void test_gcdext(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算法)
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)
计算两个无符号整数的最大公约数
int64_t slong
定义 numth.h:41
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)
计算两个无符号整数的最大公约数(通用分发入口)
定义 gcd.c:27
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_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)
定义 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_CHECK_EQ(a, b)
定义 test.h:39
#define TEST_RUN(category, name)
定义 test.h:36
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)