LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
hgcd.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/*
24hgcd(half-GCD,半扩展欧几里得)算法
25
26一、问题定义
27
28给定 n limb 的数对 (a; b)(a > b > 0),在 O(M(n) log n) 时间内将其归约至约
29n/2 limb,同时累积 2x2 变换矩阵 M 满足
30
31 / a \ / m00 m01 \ / a' \
32 | | = | | * | |
33 \ b / \ m10 m11 / \ b' /
34
35其中 (a'; b') 为归约后的数对。矩阵元素均非负,det(M) = ±1。由于 M 幺模,
36gcd(a, b) = gcd(a', b') 严格保持。反复调用 hgcd 直至规模降到阈值以下,再用
37Lehmer 算法收尾,即得完整 gcd(见 lmmp_gcd_hgcd_)。lmmp_gcd_hgcd_ 对不平衡
38输入(an >= 2*bn,此时 hgcd 阶段 A 的递归失效)先做取模预归约拉近两数长度,
39详见其实现注。
40
41二、单步步进(lmmp_hgcd_step_)
42
43每一步尝试将数对消去约 62 位,方式有二:
44
451. 近似矩阵步。从 (a, b) 顶端对齐提取 127 位近似窗口 (x; y)(按 a 的最高位
46 对齐,a 与 b 使用同一尺度),在 (x; y) 上运行小规模欧几里得并累积单 limb
47 矩阵 U,约定 (x; y) = U * (u; v)。停机采用 break-before 策略:余数将跌破
48 2^65 时不再前进,保证终态 v >= 2^65,从而
49 - U 的元素 <= x / v < 2^127 / 2^65 < 2^62,可放入单 limb;
50 - 对真值应用的误差(< 2^63 ulp)小于信号(>= 2^65 ulp),U^{-1} 作用
51 于完整 (a; b) 的结果保证非负。
52 商的计算用 u_hi / (v_hi + 1) 下界估计加减法校正,避免 128 位除法。
53 得到 U 后更新 M <- M * U,并将 (V0; V1) = U^{-1} * (a; b) 写回数对。
54 det(U) = ±1 决定 V 的符号方向,数对翻转时以列交换后的 U 复合(U*P)。
55
562. 真除法回退。近似失效(两数顶端 127 位相同,或 y < 2^65 即商过大)时做
57 带下限的除法:全除 a = q*b + r 若余数不低于下限则直接采用;否则做部分
58 除法 Q = (a - B^(fl-1)) div b,令 r' = a - Q*b >= B^(fl-1)。部分商 Q 可
59 为多 limb。
60
61下限 fl = n/2 + 2 是本实现正确性的核心不变量:任何步进结果保证较小分量
62>= B^(fl-1),而矩阵元素 <= B^(n-fl+1) < B^(fl-1),两者严格分离。这保证了
63上层递归做矩阵合并时修补项不会淹没保留的高位(见 adjust 的推导),也使得
64"过冲检测 + 回滚"策略成立。
65
66三、递归结构(lmmp_hgcd_core_)
67
68对规模超过递归阈值(HGCD_RECURSE_THRESHOLD)的数对做两阶段分治:
69
70阶段 A:将 a、b 的高半部分(各 hn = n - n/2 limb)复制到独立缓冲,递归
71调用 hgcd 将其归约至约 hn/2,得到子矩阵 M1;随后用"高位直写 + 低位修补"
72(lmmp_hgcd_adjust_)或模乘合并(lmmp_hgcd_apply_mod_)把 M1 的作用合并到
73完整数对。合并后规模约降至 3n/4。
74
75桥接:用少量单步步进将规模从约 3n/4 降到 3n/4 + 1(通常常数步)。
76
77阶段 B:p2 = 2*fl - n + 1,对新的高半部分(约 n - p2 limb)再次递归并
78合并,规模降至约 fl,即约一半。
79
80appr(近似)模式(appr 参数):仅保证 M 累积至足够规模,阶段 B 退化为
81纯矩阵复合 M <- M*M1(无数对修补),复合完成立即返回。
82由于 lmmp_hgcd_apply_mod_ 以 4 次模乘从完整数对直接重构、不依赖子递归的
83数对输出,凡本层用模乘合并处,子递归即可用 appr 模式;用 adjust(需要子
84数对的精确归约结果)处子递归必须精确。appr 使每个递归节点的 4 乘法合并
85次数从 2 降至 1,大输入下整体约省 15%。
86
87提交与回滚:递归成果先写入 sa/sb 副本,仅当(1)修补无借位(结果非负),
88(2)较小分量长度大于 M1 最大元素长度(下限不变量保持),(3)规模确实
89下降,三个条件都满足时才提交并复合 M <- M * M1;否则放弃递归成果,数对
90保持原状,交由步进循环继续。过冲只会损失性能而不会破坏正确性。
91
92det 符号穿线:矩阵的行列式符号在递归中逐点跟踪(F(q) 型更新变号、列交
93换变号等),adjust 直接使用,免去每次两次 Mn*Mn 乘法的判定开销。
94
95四、矩阵复合(lmmp_hgcd_matrix_mul_)
96
97M <- M * M1 经由库内 lmmp_mat22_mul_ 完成,按元素最大长度自动分派:
98basecase(8 乘)或 Winograd-Strassen(7 乘;FFT 缓存乘法路径曾实现并
99证伪后删除,见 mat22_mul.h 头注)。M 为单位阵时退化为按长度直接拷贝。
100矩阵存储为"逐元素显式长度"布局:各元素真实长度存于 M->n[i][j](归一
101化,0 表示零元素),无零填充不变量;与 lmmp_mat22_t 公共前缀同构(指
102针强转零开销),配合指针交换实现 O(1) 的行列交换。
103
104五、内存管理
105
106全部内部函数经由穿线的递增分配器(lmmp_hgcd_scratch_t)获取临时空间:
107顶层按 lmmp_hgcd_scratch_size_ 给出的上界一次性分配,各函数入口取标记、
108出口恢复,兄弟调用复用同一区域,无逐层堆分配。lmmp_gcd_hgcd_ 的数对工作
109缓冲与矩阵缓冲也在循环外一次分配复用。scratch 上界按"沿递归路径取 max"
110核算(子层临时空间与本层合并相位共享同一区域,仅常驻高位副本跨层叠加,
111见 lmmp_hgcd_scratch_size_ 注),约 15n limb,较早期逐层累加的 48n 缩至
112约 1/3(51000 limb 约 19.6MB -> 6.1MB)。
113
114六、模乘合并变体(lmmp_hgcd_apply_mod_)
115
116以 4 次 mod B^rn-1 的梅森模乘精确重构 M1^{-1}*(a; b)(真值为正且
117< B^nn <= B^(rn-1) 时模结果即真值)。数对折叠至 rn limb,矩阵元素以
118原始长度(M1->n,必小于 rn)直接参与模乘,无需填充。fa/fb 各被两个
119矩阵元素相乘。模乘走梅森分发入口(dc 按操作数实际长度计价,不平衡
120形状亦有收益);达到 HGCD_MODMUL_CACHE_THRESHOLD 后改用 lmmp_mul_mersenne_cache_
121系列缓存 fa/fb 的前向变换,第二次模乘省一次全尺寸前向变换。朴素修补
122与模乘的分界由 HGCD_MODMUL_THRESHOLD 控制,正确性已经与 Lehmer 的
123批量交叉验证,性能由 LmmpMeasure 的 numth/gcd 测量组标定。
124
125七、复杂度
126
127每层递归的乘法工作为 O(M(n)),递归深度 O(log n),总计 O(M(n) log n)。
128
129参考:
130 GMP 的 hgcd/hgcd_appr/hgcd_reduce/hgcd_matrix_adjust 设计思想,
131 https://www.cnblogs.com/whx1003/p/16217087.html
132*/
133
134#include "numth/gcd.h"
135#include "impl/longlong.h"
136#include "mparam.h"
137#include "numth/mat22_mul.h"
138#include "impl/mul_cache.h"
139#include "impl/tmp_alloc.h"
140#include "lmmp/lmmpn.h"
141#include "lmmp/numth.h"
142
144
145
146/* 递归阈值 / scratch 分配器 / 各小助手(norm、矩阵极值与列交换、大数在前乘法)
147 见 impl/gcd.h(与 gcdext.c 共享) */
148
149/**
150 * @brief 计算 hgcd 内部临时空间大小
151 * @param n 输入长度
152 * @warning n>0
153 * @note 峰值沿递归路径取 max 而非逐层求和:递增分配器经 mark 复位使
154 * 子层临时空间与本层合并相位(sa/sb 副本、adjust/apply_mod/矩阵
155 * 复合缓冲,合计约 14n)共享同一区域,二者不同时达峰;真正叠加
156 * 的只有递归期间常驻的高位副本与子矩阵缓冲。子问题规模上界取
157 * 2n/3 + 2(阶段 B 的 p2 分裂在最不利时接近该比例,严于实际的
158 * n - n/2 与 2n_cur - n0 - 5)。本层合并相位预算 15n + 512(含
159 * apply_mod 折叠缓冲的 next_size 取整余量与矩阵复合 9(2mx+4)),
160 * 步进循环 8n + 64。对比旧的逐层累加(约 48n)内存占用降至约 1/3
161 */
163 mp_size_t acc = 0; /* 递归路径常驻前缀(高位副本累计) */
164 mp_size_t best = 8 * n + 64; /* 基础步进循环(含除法回退路径) */
165 while (n > HGCD_RECURSE_THRESHOLD) {
166 mp_size_t hn = 2 * n / 3 + 2; /* 子问题规模上界(见注) */
167 mp_size_t level = acc + 15 * n + 512; /* 本层合并相位峰值 */
168 if (level > best) {
169 best = level;
170 }
171 acc += 6 * hn + 16; /* ha/hb/M1buf:子递归期间常驻不释放 */
172 mp_size_t steps = acc + 8 * n + 64; /* 桥接/收尾步进循环峰值 */
173 if (steps > best) {
174 best = steps;
175 }
176 n = hn;
177 }
178 mp_size_t tail = acc + 8 * n + 64;
179 if (tail > best) {
180 best = tail;
181 }
182 return best;
183}
184
185/**
186 * @brief 在 [ap,n] 与 [bp,n] 的 127 位顶端近似上运行小规模欧几里得,累积单 limb 矩阵 U
187 * @param pu00 输出矩阵元素 m00(仅返回 1 时写入)
188 * @param pu01 输出矩阵元素 m01(仅返回 1 时写入)
189 * @param pu10 输出矩阵元素 m10(仅返回 1 时写入)
190 * @param pu11 输出矩阵元素 m11(仅返回 1 时写入)
191 * @param ap 较大数指针(长度为 n 个limb,ap[n-1]>0)
192 * @param bp 较小数指针(长度为 n 个limb,允许高位为零:窗口按 a 的顶位对齐,
193 * b 的高位零只使 y 偏小,不破坏正确性)
194 * @param n ap,bp 的公共长度
195 * @return 1 表示 U 非单位矩阵(可用近似步进);0 表示需走真除法回退
196 * @warning ap!=NULL, bp!=NULL, n>=3, ap[n-1]>0, [bp,n]>0(值序 a>b)
197 * @note 约定 (x;y) = U*(u;v),元素非负且 < 2^62,det(U) = [1|-1]。
198 * 127 位窗口 + break-before 停机(余数将跌破 2^65 时不再前进),
199 * 终态 v >= 2^65 保证元素界 x/v < 2^62 与对真值应用的非负性
200 * (误差 < 2·2^62 ulp < 2^63 ulp <= v ulp)。每步约消去 62 位。
201 * 商用 u_hi/(v_hi+1) 下界估计 + 减法校正,避免 128 位除法
202 */
204 mp_limb_t* pu00,
205 mp_limb_t* pu01,
206 mp_limb_t* pu10,
207 mp_limb_t* pu11,
208 mp_srcptr ap,
209 mp_srcptr bp,
211) {
212 /* 顶端对齐提取 127 位窗口(按 a 的顶位对齐,a 与 b 使用同一尺度) */
213 mp_limb_t xh, xl, yh, yl;
214 int kz = lmmp_limb_bits_(ap[n - 1]);
215 if (kz >= 64) {
216 xh = ap[n - 1] >> 1;
217 xl = (ap[n - 1] << 63) | (ap[n - 2] >> 1);
218 yh = bp[n - 1] >> 1;
219 yl = (bp[n - 1] << 63) | (bp[n - 2] >> 1);
220 } else if (kz == 63) {
221 xh = ap[n - 1];
222 xl = ap[n - 2];
223 yh = bp[n - 1];
224 yl = bp[n - 2];
225 } else {
226 int sh = 63 - kz; /* [1,62] */
227 xh = (ap[n - 1] << sh) | (ap[n - 2] >> (64 - sh));
228 xl = (ap[n - 2] << sh) | (ap[n - 3] >> (64 - sh));
229 yh = (bp[n - 1] << sh) | (bp[n - 2] >> (64 - sh));
230 yl = (bp[n - 2] << sh) | (bp[n - 3] >> (64 - sh));
231 }
232 if (xh == yh && xl == yl) {
233 return 0; /* 顶 127 位相同:两数过近,商失真 */
234 }
235 if (yh < 2) {
236 return 0; /* y < 2^65:商过大,走真除法回退 */
237 }
238
239 /* 小规模欧几里得:(u;v) 为 u128 对;除法用 (u_hi / (v_hi+1)) 下界估计 + 减法校正 */
240 mp_limb_t u00 = 1, u01 = 0, u10 = 0, u11 = 1;
241 mp_limb_t uh = xh, ul = xl, vh = yh, vl = yl;
242 for (;;) {
243 mp_limb_t q = uh / (vh + 1); /* 下界:q_hat*v <= u,余数非负 */
244 mp_limb_t al, ah, bl, bh, rl, rh;
245 _umul64to128_(q, vl, &bl, &bh);
246 _umul64to128_(q, vh, &al, &ah);
247 /* q*v = (al + bh : bl),ah 必为 0(q*v <= u < 2^127) */
248 rl = ul - bl;
249 rh = uh - al - bh - (ul < bl);
250 lmmp_debug_assert(rh <= uh && (rh < uh || rl <= ul)); /* 估计保证非负 */
251 while (rh > vh || (rh == vh && rl >= vl)) {
252 /* r >= v:q 偏小,减 v 校正(估计算法保证至多两次) */
253 ++q;
254 mp_limb_t t = rl - vl;
255 int borrow = rl < vl;
256 rl = t;
257 rh = rh - vh - borrow;
258 }
259 /* 停机判定:r < 2^65 即 rh < 2 */
260 if (rh < 2) {
261 break; /* break-before:终态保证 v >= 2^65 */
262 }
263 /* (u;v) = F(q)*(v;r);U <- U*F(q):新 col0 = q*col0 + col1,新 col1 = col0 */
264 mp_limb_t a00 = u00, a10 = u10;
265 mp_limb_t b00 = q * a00 + u01;
266 mp_limb_t b10 = q * a10 + u11;
267 u01 = a00;
268 u11 = a10;
269 u00 = b00;
270 u10 = b10;
271 uh = vh;
272 ul = vl;
273 vh = rh;
274 vl = rl;
275 }
276 if (u00 == 1 && u01 == 0 && u10 == 0 && u11 == 1) {
277 return 0;
278 }
279 *pu00 = u00;
280 *pu01 = u01;
281 *pu10 = u10;
282 *pu11 = u11;
283 return 1;
284}
285
286/**
287 * @brief M <- M*U,U 为单 limb 元素的非负矩阵
288 * @param M 变换矩阵:输入读各元素 [0,M->n[i][j]),输出写各元素与
289 * M->n[i][j](新长度至多旧长度+1)
290 * @param sc 临时空间(max(M->n[i][j])+2 个limb)
291 * @param detsign det(M) 的符号,输入输出同源(乘 det(U)=[1|-1] 调整)
292 * @param u00 U 的元素 m00(非负且 < 2^62)
293 * @param u01 U 的元素 m01(非负且 < 2^62)
294 * @param u10 U 的元素 m10(非负且 < 2^62)
295 * @param u11 U 的元素 m11(非负且 < 2^62)
296 * @warning sc!=NULL, M!=NULL, max(M->n[i][j])+2 <= M->alloc
297 * @note 长度显式维护:col' = u_a*col_a + u_b*col_b 的长度为
298 * L+进位(L = max(la,lb),双乘进位之和 < 2^63 无再进位),
299 * mul_1/addmul_1 的进位经 [l,L) 区补零对齐后并入顶端
300 */
304 int* detsign,
305 mp_limb_t u00,
306 mp_limb_t u01,
307 mp_limb_t u10,
308 mp_limb_t u11
309) {
310 /* det(U) = u00*u11 - u01*u10 = ±1,元素 < 2^62,乘积需 u128 比较 */
311 mp_limb_t dlo, dhi, elo, ehi;
312 _umul64to128_(u00, u11, &dlo, &dhi);
313 _umul64to128_(u01, u10, &elo, &ehi);
314 *detsign *= (dhi > ehi || (dhi == ehi && dlo >= elo)) ? 1 : -1;
316 lmmp_debug_assert(mx + 2 <= M->alloc);
317 mp_size_t mark = sc->used;
318 mp_ptr t = lmmp_hgcd_salloc_(sc, mx + 2);
319
320 for (int row = 0; row < 2; ++row) {
321 mp_ptr c0 = M->m[row][0];
322 mp_ptr c1 = M->m[row][1];
323 mp_size_t l0 = M->n[row][0];
324 mp_size_t l1 = M->n[row][1];
325 mp_size_t L = l0 > l1 ? l0 : l1;
326
327 mp_limb_t c, cc;
328 mp_size_t l1n;
329 if (u01 == 0 || l0 == 0) {
330 if (u11 == 0 || l1 == 0) {
331 l1n = 0; /* 两项皆零(det=[1|-1] 保证不会两列同零,防御) */
332 } else {
333 c = lmmp_mul_1_(t, c1, l1, u11);
334 t[l1] = c;
335 l1n = l1 + (c != 0);
336 }
337 } else if (u11 == 0 || l1 == 0) {
338 c = lmmp_mul_1_(t, c0, l0, u01);
339 t[l0] = c;
340 l1n = l0 + (c != 0);
341 } else {
342 c = lmmp_mul_1_(t, c0, l0, u01);
343 t[l0] = c;
344 /* 对齐补零(长度差,矩阵元素通常 0~2);l1 > l0 时 L == l1,
345 多补的 [L] 供顶位判断与 add_1_ 回读(见上) */
346 lmmp_zero(t + l0 + 1, L - l0 + (l1 > l0));
347 cc = lmmp_addmul_1_(t, c1, l1, u11);
348 /* 进位属于 [l1] 位置,经 add_1_ 传播,顶端无出界(和 < 2^63) */
349 if (cc != 0) {
350 lmmp_add_1_(t + l1, t + l1, L + 1 - l1, cc);
351 }
352 l1n = L + (t[L] != 0);
353 if (t[l1n - 1] == 0 && l1n > 1) {
354 --l1n;
355 }
356 if (t[l1n - 1] == 0 && l1n > 1) {
357 --l1n;
358 }
359 }
360 /* 新 col0 = u00*col0 + u10*col1,原地(col1 尚未覆写),同构 */
361 mp_size_t l0n;
362 if (u00 == 0 || l0 == 0) {
363 if (u10 == 0 || l1 == 0) {
364 l0n = 0;
365 } else {
366 c = lmmp_mul_1_(c0, c1, l1, u10);
367 c0[l1] = c;
368 l0n = l1 + (c != 0);
369 }
370 } else if (u10 == 0 || l1 == 0) {
371 c = lmmp_mul_1_(c0, c0, l0, u00);
372 c0[l0] = c;
373 l0n = l0 + (c != 0);
374 } else {
375 c = lmmp_mul_1_(c0, c0, l0, u00);
376 c0[l0] = c;
377 lmmp_zero(c0 + l0 + 1, L - l0 + (l1 > l0)); /* 含顶位预置(见上) */
378 cc = lmmp_addmul_1_(c0, c1, l1, u10);
379 if (cc != 0) {
380 lmmp_add_1_(c0 + l1, c0 + l1, L + 1 - l1, cc);
381 }
382 l0n = L + (c0[L] != 0);
383 if (c0[l0n - 1] == 0 && l0n > 1) {
384 --l0n;
385 }
386 if (c0[l0n - 1] == 0 && l0n > 1) {
387 --l0n;
388 }
389 }
390 lmmp_copy(c1, t, l1n);
391 M->n[row][0] = l0n;
392 M->n[row][1] = l1n;
393 }
394 sc->used = mark;
395}
396
397/**
398 * @brief 真除法步进的矩阵累积
399 * @param M 变换矩阵:输入读各元素 [0,M->n[i][j]),输出写更新列各元素
400 * 与长度(另一列仅按 col 语义搬移/保持)
401 * @param sc 临时空间(qn+max(M->n[i][j])+1 个limb)
402 * @param detsign det(M) 的符号,输入输出同源(col=0 时乘 det(F)=-1 变号)
403 * @param q 商数组(长度为 qn 个limb,q[qn-1]>0)
404 * @param qn 商的 limb 长度,qn>0
405 * @param col 被更新列编号,亦即右乘矩阵的选择。按本模块约定 (a;b) = M*(a';b'),
406 * 数对做一步带商 q 的欧几里得步进 a = q*b + r 后,需右乘 X 使
407 * (a;b) = (M*X)*(新数对),两种步进方向对应:
408 * col=0(无翻转,新数对 (b; r),r 作新的较小分量):
409 * X = F(q) = / q 1 \ ,det = -1;
410 * \ 1 0 /
411 * 列语义:新 col0 = q*col0 + col1,新 col1 = 旧 col0。
412 * 验证:F(q)*(b;r) = (q*b+r; b) = (a; b)
413 * col=1(翻转,新数对 (r; b),r 作新的较大分量;部分除法中
414 * 商被压低使 r' >= b 时发生):
415 * X = E(q) = / 1 q \ ,det = +1;
416 * \ 0 1 /
417 * 列语义:新 col1 = q*col0 + col1,col0 不变。
418 * 验证:E(q)*(r;b) = (r+q*b; b) = (a; b)
419 * (E(q) = F(q)*P,P 为列交换,即数对翻转在矩阵侧的簿记)
420 * @warning M!=NULL, sc!=NULL, q!=NULL, qn>0, sep(q,M)
421 * @note 更新列长度显式维护:t = q*col0 + col1 的长度 = max(lt, l1)+进位,
422 * 其中积长 lt = qn+l0 或 qn+l0-1(积 >= B^(qn+l0-2),顶 limb 单次
423 * 判断);l0==0(零元素)时 t = col1 长度直接已知
424 */
428 int* detsign,
429 mp_srcptr q,
430 mp_size_t qn,
431 int col
432) {
433 if (col == 0) {
434 *detsign = -*detsign; /* F(q) det = -1 */
435 }
437 mp_size_t mark = sc->used;
438 mp_ptr t = lmmp_hgcd_salloc_(sc, qn + mx + 1);
439
440 /*
441 F(q):col0' = q*col0 + col1,col1' = col0_old
442 E(q):col1' = q*col0 + col1,col0' 不变
443 两种情形的更新列均为 q*col0 + col1,区别在另一列的去向
444 */
445 for (int row = 0; row < 2; ++row) {
446 mp_size_t l0 = M->n[row][0];
447 mp_size_t l1 = M->n[row][1];
448 mp_size_t lt;
449 if (l0 == 0) {
450 lmmp_copy(t, M->m[row][1], l1);
451 lt = l1;
452 } else {
453 lmmp_gcd_mul_(t, q, qn, M->m[row][0], l0);
454 if (l1 == 0) {
455 /* 零元素:lmmp_add_ 对 nb==0 不安全(内联宏经 do-while 汇编),
456 且积 >= B^(qn+l0-2),长度顶 limb 单次判断 */
457 lt = qn + l0 - (t[qn + l0 - 1] == 0);
458 } else {
459 /* 乘积缓冲 [0, qn+l0) 有效,若 col1 更长需先清零对齐区,
460 再以两者最大长度相加,满足 lmmp_add_ 的 na>=nb 契约 */
461 mp_size_t m = qn + l0;
462 if (l1 > m) {
463 lmmp_zero(t + m, l1 - m);
464 m = l1;
465 }
466 mp_limb_t carry = lmmp_add_(t, t, m, M->m[row][1], l1);
467 /* lmmp_add_ 等长相加的进位仅经返回值报告,需显式落盘 */
468 if (carry != 0) {
469 t[m] = carry;
470 }
471 lt = m + (carry != 0);
472 /* 归一化:和 >= max(积, col1) >= B^(m-1),至多两个前导零 limb */
473 if (t[lt - 1] == 0 && lt > 1) {
474 --lt;
475 }
476 if (t[lt - 1] == 0 && lt > 1) {
477 --lt;
478 }
479 }
480 }
481 int dst = col == 0 ? 0 : 1;
482 if (col == 0) {
483 /* col1 <- col0_old(指针与长度一并搬移后写回更新列) */
484 lmmp_copy(M->m[row][1], M->m[row][0], l0);
485 M->n[row][1] = l0;
486 }
487 lmmp_copy(M->m[row][dst], t, lt);
488 M->n[row][dst] = lt;
489 }
490 sc->used = mark;
491}
492
493/**
494 * @brief 将连续缓冲初始化为单位矩阵
495 * @param M 变换矩阵(写入 M->m 指针、M->n、M->alloc,并置对角元为 1)
496 * @param buf 连续缓冲
497 * @param alloc 每元素容量(limb)
498 * @warning M!=NULL, buf!=NULL, alloc>0
499 */
501 lmmp_debug_assert(M != NULL && buf != NULL && alloc > 0);
502 M->m[0][0] = buf;
503 M->m[0][1] = buf + alloc;
504 M->m[1][0] = buf + 2 * alloc;
505 M->m[1][1] = buf + 3 * alloc;
506 M->n[0][0] = 1;
507 M->n[0][1] = 0;
508 M->n[1][0] = 0;
509 M->n[1][1] = 1;
510 M->alloc = alloc;
511 M->m[0][0][0] = 1;
512 M->m[1][1][0] = 1;
513}
514
515/**
516 * @brief M <- M*M1(经由库内 lmmp_mat22_mul_,按元素最大长度自动分派
517 * basecase / Winograd-Strassen 路径)
518 * @param M 左矩阵,输入读各元素 [0,M->n[i][j]),输出写各元素与长度字段
519 * (新长度 <= max(M->n[i][k]) + max(M1->n[k][j]) + 1)
520 * @param M1 右矩阵(只读,各元素 [0,M1->n[i][j]) 有效)
521 * @param sc 临时空间(8*(mx(M)+mx(M1))+16 个limb)
522 * @warning M!=NULL, M1!=NULL, sc!=NULL, sep(M,M1),
523 * maxlen(M)+maxlen(M1)+4 <= M->alloc
524 * @note M 为单位阵时退化为按长度直接拷贝 M1。lmmp_hgcd_matrix_t 与
525 * lmmp_mat22_t 公共前缀同构(m[2][2]+n[2][2]),指针强转零开销
526 */
528 if (M->n[0][0] == 1 && M->m[0][0][0] == 1
529 && M->n[1][1] == 1 && M->m[1][1][0] == 1
530 && M->n[0][1] == 0 && M->n[1][0] == 0) {
531 /* M 为单位阵:M*M1 = M1,按各元素真实长度整段拷贝 */
532 for (int i = 0; i < 2; ++i) {
533 for (int j = 0; j < 2; ++j) {
534 lmmp_copy(M->m[i][j], M1->m[i][j], M1->n[i][j]);
535 M->n[i][j] = M1->n[i][j];
536 }
537 }
538 return;
539 }
540
543 lmmp_debug_assert(mx + mx1 + 4 <= M->alloc);
544 mp_size_t mark = sc->used;
545 mp_ptr tp = lmmp_hgcd_salloc_(sc, 8 * (mx + mx1) + 16);
546 lmmp_mat22_mul_((lmmp_mat22_t*)M, (const lmmp_mat22_t*)M, (const lmmp_mat22_t*)M1, tp);
547 sc->used = mark;
548}
549
550/*
551高位直写 + 低位修补(契约详见 impl/gcd.h;对 gcdext.c 暴露,
552供其驱动循环合并每轮 hgcd 的子递归成果)
553*/
556 int detsign,
557 mp_ptr dap,
558 mp_ptr dbp,
559 mp_size_t* blen,
560 mp_srcptr ha,
561 mp_srcptr hb,
562 mp_size_t hn0,
563 mp_srcptr ap,
564 mp_srcptr bp,
565 mp_size_t n,
566 mp_size_t p,
568) {
570 mp_size_t mark = sc->used;
571 mp_size_t N = p + mn + 1;
572 mp_ptr t0 = lmmp_hgcd_salloc_(sc, N);
573 mp_ptr t1 = lmmp_hgcd_salloc_(sc, N);
574 mp_ptr t2 = lmmp_hgcd_salloc_(sc, N);
575 mp_ptr t3 = lmmp_hgcd_salloc_(sc, N);
576 /* 长度前提(由子递归的下限不变量保证,防御性检查) */
577 if (n - p < mn || n < p + mn) {
578 *blen = 0;
579 sc->used = mark;
580 return 0;
581 }
582
583 /*
584 det 由穿线符号跟踪(构造保证 = ±1)。零元素(长度 0)跳过乘法——
585 lmmp_mul_ 契约要求 nb>0,乘积缓冲置零以维持后续加减的定长语义。
586 乘积仅写 [0, p+n_ij),而后续加减按 mn 定长读取 [p, p+mn):
587 元素长度 n_ij < mn 时须补零 [p+n_ij, p+mn),否则读到未写残留
588 */
589 int det = detsign;
590 mp_size_t n11 = M1->n[1][1], n10 = M1->n[1][0], n01 = M1->n[0][1], n00 = M1->n[0][0];
591 if (n11 != 0) {
592 lmmp_gcd_mul_(t0, ap, p, M1->m[1][1], n11); /* m11*a_lo */
593 lmmp_zero(t0 + p + n11, mn - n11);
594 } else {
595 lmmp_zero(t0, N);
596 }
597 if (n10 != 0) {
598 lmmp_gcd_mul_(t1, ap, p, M1->m[1][0], n10); /* m10*a_lo */
599 lmmp_zero(t1 + p + n10, mn - n10);
600 } else {
601 lmmp_zero(t1, N);
602 }
603 if (n01 != 0) {
604 lmmp_gcd_mul_(t2, bp, p, M1->m[0][1], n01); /* m01*b_lo */
605 lmmp_zero(t2 + p + n01, mn - n01);
606 } else {
607 lmmp_zero(t2, N);
608 }
609 if (n00 != 0) {
610 lmmp_gcd_mul_(t3, bp, p, M1->m[0][0], n00); /* m00*b_lo */
611 lmmp_zero(t3 + p + n00, mn - n00);
612 } else {
613 lmmp_zero(t3, N);
614 }
615
616 /*
617 det=+1:new_a = ha + t0 - t2,new_b = hb + t3 - t1
618 det=-1:new_a = ha + t2 - t0,new_b = hb + t1 - t3
619 */
620 mp_ptr adda = det > 0 ? t0 : t2;
621 mp_ptr suba = det > 0 ? t2 : t0;
622 mp_ptr addb = det > 0 ? t3 : t1;
623 mp_ptr subb = det > 0 ? t1 : t3;
624
625 /* new_a:低 p 位直写被加积,高位段为 ha 再加被加积高位,最后整体减被减积 */
626 lmmp_copy(dap + p, ha, hn0);
627 lmmp_zero(dap + p + hn0, n - p - hn0);
628 lmmp_copy(dap, adda, p);
629 mp_limb_t carry = lmmp_add_(dap + p, dap + p, n - p, adda + p, mn);
630 if (carry != 0) {
631 sc->used = mark;
632 return 0;
633 }
634 mp_limb_t borrow = lmmp_sub_(dap, dap, n, suba, p + mn);
635 if (borrow != 0) {
636 sc->used = mark;
637 return 0; /* 过冲:new_a < 0 */
638 }
639
640 /* new_b:同构 */
641 lmmp_copy(dbp + p, hb, hn0);
642 lmmp_zero(dbp + p + hn0, n - p - hn0);
643 lmmp_copy(dbp, addb, p);
644 carry = lmmp_add_(dbp + p, dbp + p, n - p, addb + p, mn);
645 if (carry != 0) {
646 sc->used = mark;
647 return 0;
648 }
649 borrow = lmmp_sub_(dbp, dbp, n, subb, p + mn);
650 if (borrow != 0) {
651 sc->used = mark;
652 return 0; /* 过冲:new_b < 0 */
653 }
654
655 /*
656 结果分量经加减抵消,长度无进位信息可用,须扫描获取(数对输出);
657 返回公共长度 rn = max(la,lb),blen 出参单独给出分量 b 的长度
658 (供上层校验,免去二次扫描)。数对为零填充公共长度表示:输出
659 需将两分量补零至 rn(上层的规范化序比较按公共长度读取)
660 */
661 mp_size_t la = n;
662 while (la > 0 && dap[la - 1] == 0) {
663 --la;
664 }
665 mp_size_t lb = n;
666 while (lb > 0 && dbp[lb - 1] == 0) {
667 --lb;
668 }
669 mp_size_t rn = la > lb ? la : lb;
670 lmmp_zero(dap + la, rn - la);
671 lmmp_zero(dbp + lb, rn - lb);
672 *blen = lb;
673 sc->used = mark;
674 return rn;
675}
676
677/**
678 * @brief 单步步进:用近似矩阵 U 或一次(可能部分的)除法归约数对
679 * @param M 变换矩阵(累积):输入读各元素长度为 M->n 个limb,输出零填充至新公共长度
680 * @param ap 较大分量输入兼输出数组:输入读 [ap,n)(ap[n-1]>0),输出写 [ap,nn)
681 * 并零填充至新公共长度 nn(规范序:归约后较大者写入 ap)
682 * @param bp 较小分量输入兼输出数组:输入读 [bp,n)(允许高位为零,[bp,n]>0),
683 * 输出写 [bp,nn) 并零填充至 nn
684 * @param n ap,bp 的公共长度
685 * @param fl 步进下限:结果较小分量 >= B^(fl-1)。保证矩阵元素 <= B^(n-fl+1) < B^(fl-1),
686 * 使上层递归的矩阵修补非负性成立
687 * @param sc 临时空间(峰值约 6n+6 个limb:除法回退路径的商/余/被除副本
688 * 与矩阵更新的嵌套需求)
689 * @param detsign det(M) 的符号,输入输出同源(本函数依更新矩阵调整其值)
690 * @return 新公共长度 nn(<=n,等于两分量真实长度的最大值,即 ap[nn-1]>0);
691 * 0 表示无法在不破坏下限的前提下继续归约,数对保持 [0,n) 原值
692 * @warning M!=NULL, sc!=NULL, ap!=NULL, bp!=NULL, sep(ap,bp), n>=3, n>fl, a>b>0
693 */
696 mp_ptr ap,
697 mp_ptr bp,
698 mp_size_t n,
699 mp_size_t fl,
701 int* detsign
702) {
703 mp_limb_t u00, u01, u10, u11;
704 if (lmmp_hgcd_lehmer2_(&u00, &u01, &u10, &u11, ap, bp, n)) {
705 /*
706 (V0;V1) = U^{-1}*(a;b):V0 = D*(u11*a - u01*b),V1 = D*(u00*b - u10*a),
707 D = det(U) = ±1。乘减融合(mul_1 + submul_1)于两个暂存中完成并做下限
708 检查,通过后才写回(返回 0 时数对必须保持原值,供上层继续使用)。
709 det 的符号直接决定减法方向(lehmer2 的 break-before 停机保证被减方
710 更大,高位 limb 相等即非负性成立)
711 */
712 mp_size_t mark = sc->used;
713 mp_size_t N = n + 1;
714 mp_ptr t0 = lmmp_hgcd_salloc_(sc, N);
715 mp_ptr t3 = lmmp_hgcd_salloc_(sc, N);
716 mp_limb_t dlo, dhi, elo, ehi;
717 _umul64to128_(u00, u11, &dlo, &dhi);
718 _umul64to128_(u01, u10, &elo, &ehi);
719 int det = (dhi > ehi || (dhi == ehi && dlo >= elo)) ? 1 : -1;
720 mp_limb_t h0, h1;
721 if (det > 0) {
722 /* V0 = u11*a - u01*b;V1 = u00*b - u10*a */
723 h0 = lmmp_mul_1_(t0, ap, n, u11);
724 h1 = lmmp_submul_1_(t0, bp, n, u01);
725 lmmp_debug_assert(h0 == h1);
726 h0 = lmmp_mul_1_(t3, bp, n, u00);
727 h1 = lmmp_submul_1_(t3, ap, n, u10);
728 lmmp_debug_assert(h0 == h1);
729 } else {
730 /* V0 = u01*b - u11*a;V1 = u10*a - u00*b */
731 h0 = lmmp_mul_1_(t0, bp, n, u01);
732 h1 = lmmp_submul_1_(t0, ap, n, u11);
733 lmmp_debug_assert(h0 == h1);
734 h0 = lmmp_mul_1_(t3, ap, n, u10);
735 h1 = lmmp_submul_1_(t3, bp, n, u00);
736 lmmp_debug_assert(h0 == h1);
737 }
738
739 /*
740 an,bn ∈ {n-1, n}:V0 = u11*a - u01*b > a/2^62 >= B^(n-1)/2^62
741 > 2^(64n-127),即长度 >= n-1;又 V0 < B^n(mul/submul 高位 limb
742 相等的断言保证非负且无出界)——单次顶 limb 判断即得真实长度
743 */
744 mp_size_t an = n - (t0[n - 1] == 0);
745 mp_size_t bn = n - (t3[n - 1] == 0);
746 if (an < fl || bn < fl) {
747 sc->used = mark;
748 return 0; /* 继续将破坏下限(差值已达目标规模),数对保持原值 */
749 }
750 mp_size_t nn = an > bn ? an : bn;
751 lmmp_debug_assert(nn <= n);
752 if (lmmp_cmp_(t0, t3, n) >= 0) {
753 lmmp_hgcd_matrix_mul_u_(M, sc, detsign, u00, u01, u10, u11); /* M <- M*U */
754 lmmp_copy(ap, t0, an);
755 lmmp_zero(ap + an, nn - an);
756 lmmp_copy(bp, t3, bn);
757 lmmp_zero(bp + bn, nn - bn);
758 } else {
759 /* M <- M*(U*P):参数即 U*P 的元素,mul_u 内部 det 计算已正确 */
760 lmmp_hgcd_matrix_mul_u_(M, sc, detsign, u01, u00, u11, u10);
761 lmmp_copy(ap, t3, bn);
762 lmmp_zero(ap + bn, nn - bn);
763 lmmp_copy(bp, t0, an);
764 lmmp_zero(bp + an, nn - an);
765 }
766 sc->used = mark;
767 return nn;
768 }
769
770 /*
771 除法回退(带下限):先试全除 a = q*b + r;
772 若 r 将跌破下限,改用部分除法:Q = (a - B^(fl-1)) div b,r' = a - Q*b >= B^(fl-1)
773 */
774 /* 数对为零填充公共长度表示,除数真实长度显式信息不可得,须扫描(首步
775 进时 b 可任意小、不变量未建立,扫描量 O(n),较除法本身可忽略) */
776 mp_size_t nb = lmmp_gcd_norm_(bp, n);
777 mp_size_t mark = sc->used;
778 mp_ptr q = lmmp_hgcd_salloc_(sc, n + 2);
779 mp_ptr r = lmmp_hgcd_salloc_(sc, n + 2);
780 lmmp_div_(q, r, ap, n, bp, nb);
781 /*
782 全商 qn ∈ {n-nb, n-nb+1}:a >= B^(n-1) 且 b < B^nb,故
783 q >= B^(n-nb-1)(nb==n 时 q >= 1,因 a >= b);q < B^(n-nb+1)
784 ——单次顶 limb 判断
785 */
786 mp_size_t qn = n - nb + 1 - (q[n - nb] == 0);
787 /* 余数无下界(可为任意小),长度须扫描;此回退路径罕见 */
788 mp_size_t rr = lmmp_gcd_norm_(r, nb);
789
790 if (rr >= fl) {
791 /* 全商:数对更新为 (b; r),b > r 无翻转 */
792 lmmp_hgcd_matrix_update_q_(M, sc, detsign, q, qn, 0);
793 mp_size_t nn = nb > rr ? nb : rr;
794 lmmp_copy(ap, bp, nb);
795 lmmp_zero(ap + nb, nn - nb);
796 lmmp_copy(bp, r, rr);
797 lmmp_zero(bp + rr, nn - rr);
798 sc->used = mark;
799 return nn;
800 }
801
802 /* 部分除法:t = a - B^(fl-1)(n >= fl+1 保证 a > B^fl > B^(fl-1),减法不借位穿底) */
803 mp_ptr t = lmmp_hgcd_salloc_(sc, n + 1);
804 lmmp_copy(t, ap, n);
805 lmmp_dec(t + (fl - 1));
806 lmmp_div_(q, r, t, n, bp, nb);
807 /* 部分商可为零(t < b 时),下界缺失,长度须扫描;此回退路径罕见 */
808 qn = lmmp_gcd_norm_(q, n - nb + 1);
809 if (qn == 0) {
810 sc->used = mark;
811 return 0; /* t < b:两数之差已在下限内,目标达成 */
812 }
813 /*
814 r' = (t mod b) + B^(fl-1)。由 a = q*b + r(r < B^(fl-1))可推得
815 t mod b = b + r - B^(fl-1),故 r' = b + r <= a < B^n,
816 即 rr <= n:数对写界不超出输入公共长度。r 的长度相对 nb 无下界
817 (首次步进 b 可远短于下限,r' 由 r 主导),长度信息不存在,
818 须扫描;此回退路径罕见
819 */
820 lmmp_zero(r + nb, n + 2 - nb);
821 lmmp_inc(r + (fl - 1));
822 rr = lmmp_gcd_norm_(r, n + 1);
823 lmmp_debug_assert(rr >= fl && rr <= n);
824 mp_size_t nn = nb > rr ? nb : rr;
825 if (lmmp_cmp_(bp, r, nn) > 0) {
826 /* b > r':M <- M*F(Q),数对 (b; r') 无翻转 */
827 lmmp_hgcd_matrix_update_q_(M, sc, detsign, q, qn, 0);
828 lmmp_copy(ap, bp, nb);
829 lmmp_zero(ap + nb, nn - nb);
830 lmmp_copy(bp, r, rr);
831 lmmp_zero(bp + rr, nn - rr);
832 } else {
833 /* r' >= b:M <- M*(F(Q)*P) = M*E(Q)(列1更新),数对 (r'; b) */
834 lmmp_hgcd_matrix_update_q_(M, sc, detsign, q, qn, 1);
835 lmmp_copy(ap, r, rr);
836 lmmp_zero(ap + rr, nn - rr);
837 lmmp_zero(bp + nb, nn - nb); /* bp 保持 b,仅清零至公共长度 */
838 }
839 sc->used = mark;
840 return nn;
841}
842
843/**
844 * @brief 将 [src,sn] 折叠为模 B^rn-1 的表示:写入 [dst,rn)
845 * @param dst 输出数组(长度为 rn 个limb)
846 * @param src 源数组(长度为 sn 个limb,sn 与 rn 任意大小关系)
847 * @param sn src 的长度
848 * @param rn 模长(limb)
849 * @warning dst!=NULL, src!=NULL, sep(dst,src), rn>0, sn>0, dst 容量 rn
850 * @note 分段累加 [k*rn,(k+1)*rn) 并将进位 +1 回绕(B^rn ≡ 1 mod B^rn-1)。
851 * 累加和为全 F 时(≡ 0)不再产生回绕,lmmp_inc 不会越界
852 */
854 lmmp_copy(dst, src, sn <= rn ? sn : rn);
855 lmmp_zero(dst + (sn <= rn ? sn : rn), rn - (sn <= rn ? sn : rn));
856 while (sn > rn) {
857 src += rn;
858 sn -= rn;
859 mp_limb_t cy = lmmp_add_(dst, dst, rn, src, sn <= rn ? sn : rn);
860 if (cy != 0) {
861 lmmp_inc(dst);
862 }
863 }
864}
865
866/**
867 * @brief 模 B^rn-1 梅森乘法版矩阵应用:
868 * new = adj(M1)*(a;b),经 4 次模乘与模减精确重构
869 * @param M1 子递归累积的矩阵(只读,各元素长度为 M1->n 个limb,M1->n<rn)
870 * @param detsign det(M1) 的符号,[1|-1]
871 * @param dap 分量 a 输出数组(写入 rn_out 个limb,rn_out 为返回值;返回 0 时内容无效)
872 * @param dbp 分量 b 输出数组(写入 rn_out 个limb)
873 * @param ap 源完整较大分量(只读,长度为 n 个limb)
874 * @param bp 源完整较小分量(只读,长度为 n 个limb)
875 * @param n ap,bp 的公共长度
876 * @param sc 临时空间(6*rn 个limb;FFT 缓存上下文另行经由库内临时池分配)
877 * @return 合入后的公共长度 rn_out(两分量真实长度最大值);0 表示过冲
878 * @warning M1!=NULL, dap!=NULL, dbp!=NULL, sc!=NULL, sep([dap|dbp],[ap|bp]),
879 * n>0, M1->n>1, ap[n-1]>0
880 * @note 真值满足 0 <= new < B^nn <= B^(rn-1)(nn 为下方推导的界),
881 * 过冲(new < 0)时模结果回绕为接近 rn 长度,据此刻检测并返回 0。
882 * 数对折叠至 rn limb 参与模乘;矩阵元素以原始长度 M1->n 直接参与
883 * (M1->n<rn 保证落在模内)。fa/fb 各被两个矩阵元素乘,经
884 * lmmp_mul_mersenne_cache_ 系列复用其前向 FFT 变换
885 */
888 int detsign,
889 mp_ptr dap,
890 mp_ptr dbp,
891 mp_size_t* blen,
892 mp_srcptr ap,
893 mp_srcptr bp,
894 mp_size_t n,
895 int use_cache,
897) {
898 mp_size_t mark = sc->used;
899 mp_size_t m00 = M1->n[0][0];
900 mp_size_t m01 = M1->n[0][1];
901 mp_size_t m10 = M1->n[1][0];
902 mp_size_t m11 = M1->n[1][1];
903 mp_size_t an = n;
904 /* 数对为零填充公共长度表示,b 真实长度显式信息不可得,须扫描
905 (下限不变量保证 bn >= fl,扫描量有界) */
907
908 /* 结果 limb 上界:new_a < B^min(an-m00, bn-m10)+1 等 */
909 mp_size_t un = (an > m00 ? an - m00 : 1);
910 if (bn - m10 < un) un = bn > m10 ? bn - m10 : 1;
911 mp_size_t vn = (an > m01 ? an - m01 : 1);
912 if (bn > m11 && bn - m11 < vn) vn = bn - m11;
913 mp_size_t nn = un > vn ? un : vn;
914 ++nn;
915
916 mp_size_t rn = use_cache ? lmmp_fft_next_size_(nn + 1) /* 缓存档:仅 fft 尺寸可用 */
917 : lmmp_mersenne_next_size_(nn + 1); /* 分发档:细粒度低 padding */
918 if (rn <= lmmp_gcd_matrix_maxlen_(M1) || rn > n + 1) {
919 *blen = 0;
920 sc->used = mark;
921 return 0; /* 尺寸关系异常(防御) */
922 }
923
924 /* 折叠与填充 */
925 mp_ptr fa = lmmp_hgcd_salloc_(sc, rn);
926 mp_ptr fb = lmmp_hgcd_salloc_(sc, rn);
927 lmmp_hgcd_fold_mod_(fa, ap, an, rn);
928 lmmp_hgcd_fold_mod_(fb, bp, bn, rn);
929
930 mp_ptr t11 = lmmp_hgcd_salloc_(sc, rn);
931 mp_ptr t01 = lmmp_hgcd_salloc_(sc, rn);
932 mp_ptr t00 = lmmp_hgcd_salloc_(sc, rn);
933 mp_ptr t10 = lmmp_hgcd_salloc_(sc, rn);
934 /*
935 逐元素长度可能相差且可为 0(矩阵元素平衡,通常 0~2 limb),显式补零
936 对齐到 ml(行列式非零保证 ml1/ml2 >= 1):缓存版须等长操作数,
937 分发版亦须 nb>=1
938 */
939 mp_size_t ml1 = LMMP_MAX(m00, m01);
940 mp_size_t ml2 = LMMP_MAX(m10, m11);
941 lmmp_zero(M1->m[0][0] + m00, ml1 - m00);
942 lmmp_zero(M1->m[0][1] + m01, ml1 - m01);
943 lmmp_zero(M1->m[1][0] + m10, ml2 - m10);
944 lmmp_zero(M1->m[1][1] + m11, ml2 - m11);
945 if (use_cache) {
946 /* fa/fb 前向变换缓存,第二次模乘省去一次全尺寸前向变换 */
947 fft_gr_cache ca, cb;
948 lmmp_mul_mersenne_cache_init_(t11, rn, M1->m[1][1], ml2, fa, rn, &ca);
949 lmmp_mul_mersenne_cache_(t10, M1->m[1][0], &ca);
950 lmmp_mul_mersenne_cache_init_(t01, rn, M1->m[0][1], ml1, fb, rn, &cb);
951 lmmp_mul_mersenne_cache_(t00, M1->m[0][0], &cb);
954 } else {
955 /* 分发入口不缓存(长操作数 fa/fb 置于 numa 满足 nb<=na 契约) */
956 lmmp_mul_mersenne_(t11, rn, fa, rn, M1->m[1][1], ml2);
957 lmmp_mul_mersenne_(t10, rn, fa, rn, M1->m[1][0], ml2);
958 lmmp_mul_mersenne_(t01, rn, fb, rn, M1->m[0][1], ml1);
959 lmmp_mul_mersenne_(t00, rn, fb, rn, M1->m[0][0], ml1);
960 }
961
962 /* 模减:x - y (mod B^rn-1);借位回绕 +1 */
963 mp_ptr va, vb;
964 mp_limb_t cy;
965 if (detsign > 0) {
966 va = t11; vb = t00;
967 cy = lmmp_sub_n_(va, t11, t01, rn);
968 if (cy) lmmp_inc(va);
969 cy = lmmp_sub_n_(vb, t00, t10, rn);
970 if (cy) lmmp_inc(vb);
971 } else {
972 va = t01; vb = t10;
973 cy = lmmp_sub_n_(va, t01, t11, rn);
974 if (cy) lmmp_inc(va);
975 cy = lmmp_sub_n_(vb, t10, t00, rn);
976 if (cy) lmmp_inc(vb);
977 }
978
979 /* 真值校验:结果必须落在 nn limb 内(负值回绕会产生接近 rn 的长度) */
980 /* 模减回绕结果无进位信息,长度须扫描(数对中间量) */
981 mp_size_t alen = lmmp_gcd_norm_(va, rn);
982 mp_size_t lb = lmmp_gcd_norm_(vb, rn);
983 if (alen > nn || lb > nn) {
984 *blen = 0;
985 sc->used = mark;
986 return 0; /* 过冲 */
987 }
988
989 mp_size_t rn_out = alen > lb ? alen : lb;
990 if (rn_out == 0) {
991 *blen = 0;
992 sc->used = mark;
993 return 0;
994 }
995 *blen = lb;
996 lmmp_copy(dap, va, alen);
997 lmmp_zero(dap + alen, rn_out - alen);
998 lmmp_copy(dbp, vb, lb);
999 lmmp_zero(dbp + lb, rn_out - lb);
1000 sc->used = mark;
1001 return rn_out;
1002}
1003
1004/*
1005hgcd 递归核(契约与原理详见 impl/gcd.h 与本文件头注;
1006对 gcdext.c 暴露,驱动 GMP 式单行共因子跟踪的拓展欧几里得)
1007*/
1010 mp_ptr ap,
1011 mp_ptr bp,
1012 mp_size_t n,
1014 int* detsign,
1015 int appr
1016) {
1017 *detsign = 1; /* 入口为单位矩阵 */
1018 if (n < 3) {
1019 return 0; /* lehmer2 的 127 位窗口需读至 ap[n-3],更小规模无归约意义 */
1020 }
1021 lmmp_debug_assert(M->alloc >= n + 2);
1022
1023 mp_size_t s = n / 2 + 1;
1024 mp_size_t fl = s + 1;
1025 if (fl > n - 1) {
1026 fl = n - 1; /* 极小规模的下限放宽(仅直接调用小 n 时出现,递归子问题不会) */
1027 }
1028 int success = 0;
1029 mp_size_t n0 = n;
1030
1031 if (n0 > HGCD_RECURSE_THRESHOLD) {
1032 /* 本层合并方式:模乘合并不需要子递归的数对输出,子递归可用 appr 模式 */
1033 int use_mod = (n0 >= HGCD_MODMUL_THRESHOLD);
1034
1035 /* 阶段 A:对高半部分递归,规模降至约 3n/4 */
1036 mp_size_t p = n0 / 2;
1037 if (!lmmp_zero_q_(bp + p, n0 - p)) { /* b 高半存在非零才可递归(存在性检查,非求长度) */
1038 mp_size_t mark = sc->used;
1039 mp_size_t hn = n0 - p;
1040 /* 高位副本恰 hn limbs:递归核的数对读写均不超出其公共长度 */
1041 mp_ptr ha = lmmp_hgcd_salloc_(sc, hn);
1042 mp_ptr hb = lmmp_hgcd_salloc_(sc, hn);
1043 lmmp_copy(ha, ap + p, hn);
1044 lmmp_copy(hb, bp + p, hn);
1046 mp_ptr M1buf = lmmp_hgcd_salloc_(sc, 4 * (hn + 2));
1047 lmmp_hgcd_matrix_init_buf_(&M1, M1buf, hn + 2);
1048 int dsub = 1;
1049 mp_size_t nn = lmmp_hgcd_core_(&M1, ha, hb, hn, sc, &dsub, use_mod);
1050 if (nn > 0) {
1051 /*
1052 高位直写 + 低位修补合入完整数对,校验"较小分量长度 > M1 最大元素长度"
1053 后才提交,否则视为过冲,放弃递归成果(保持原数对,交由步进循环处理)
1054 */
1055 mp_size_t mark2 = sc->used;
1056 mp_ptr sa = lmmp_hgcd_salloc_(sc, n0 + 1);
1057 mp_ptr sb = lmmp_hgcd_salloc_(sc, n0 + 1);
1058 mp_size_t rn;
1059 mp_size_t blen;
1060 if (use_mod) {
1061 rn = lmmp_hgcd_apply_mod_(&M1, dsub, sa, sb, &blen, ap, bp, n0,
1062 n0 >= HGCD_MODMUL_CACHE_THRESHOLD, sc);
1063 } else {
1064 rn = lmmp_hgcd_adjust_(&M1, dsub, sa, sb, &blen, ha, hb, nn, ap, bp, n0, p, sc);
1065 }
1067 if (rn > 0 && rn < n0 && blen > maxlen) {
1068 if (lmmp_cmp_(sa, sb, rn) >= 0) {
1069 lmmp_copy(ap, sa, rn);
1070 lmmp_copy(bp, sb, rn);
1071 } else {
1072 /* 规范序翻转:M1 右乘列交换(det 变号),拷贝方向对调 */
1074 dsub = -dsub;
1075 lmmp_copy(ap, sb, rn);
1076 lmmp_copy(bp, sa, rn);
1077 }
1078 /* [rn,n0) 为无效残留:后续所有读写均以新公共长度 rn 为界 */
1079 n = rn;
1080 lmmp_hgcd_matrix_mul_(M, &M1, sc);
1081 *detsign *= dsub;
1082 success = 1;
1083 }
1084 sc->used = mark2;
1085 }
1086 sc->used = mark;
1087 }
1088
1089 /* 桥接:步进至 3n0/4 + 1(通常只需常数步) */
1090 mp_size_t n2 = (3 * n0) / 4 + 1;
1091 while (n > n2) {
1092 mp_size_t nn = lmmp_hgcd_step_(M, ap, bp, n, fl, sc, detsign);
1093 if (nn == 0) {
1094 return success ? n : 0;
1095 }
1096 n = nn;
1097 success = 1;
1098 }
1099
1100 /* 阶段 B:再次对高半递归,规模降至约 fl */
1101 if (n > fl + 2) {
1102 mp_size_t p2 = 2 * fl - n + 1;
1103 if (!lmmp_zero_q_(bp + p2, n - p2)) { /* 同上:存在性检查 */
1104 mp_size_t mark = sc->used;
1105 mp_size_t hn = n - p2;
1106 /* 高位副本恰 hn limbs:递归核的数对读写均不超出其公共长度 */
1107 mp_ptr ha = lmmp_hgcd_salloc_(sc, hn);
1108 mp_ptr hb = lmmp_hgcd_salloc_(sc, hn);
1109 lmmp_copy(ha, ap + p2, hn);
1110 lmmp_copy(hb, bp + p2, hn);
1112 mp_ptr M1buf = lmmp_hgcd_salloc_(sc, 4 * (hn + 2));
1113 lmmp_hgcd_matrix_init_buf_(&M1, M1buf, hn + 2);
1114 int dsub = 1;
1115 /*
1116 appr 模式的阶段 B 为纯矩阵复合:递归成果只入 M,数对不修补,
1117 复合完成即返回(矩阵规模已足够,调用方不依赖数对);
1118 容量守卫不满足时直接放弃本阶段(不落入精确路径,子数对不精确)。
1119 精确模式下子递归模式须与阶段 B 自身的合并方式一致(按当前 n 判断)
1120 */
1121 if (appr) {
1122 mp_size_t nn = lmmp_hgcd_core_(&M1, ha, hb, hn, sc, &dsub, 1);
1123 if (nn > 0 && lmmp_gcd_matrix_maxlen_(M) + lmmp_gcd_matrix_maxlen_(&M1) + 4 <= M->alloc) {
1124 lmmp_hgcd_matrix_mul_(M, &M1, sc);
1125 *detsign *= dsub;
1126 sc->used = mark;
1127 return n; /* 数对停留在约 3n/4,仅供本层步进使用过 */
1128 }
1129 sc->used = mark;
1130 } else {
1131 mp_size_t nn = lmmp_hgcd_core_(&M1, ha, hb, hn, sc, &dsub, n >= HGCD_MODMUL_THRESHOLD);
1132 if (nn > 0) {
1133 mp_size_t mark2 = sc->used;
1134 mp_ptr sa = lmmp_hgcd_salloc_(sc, n + 1);
1135 mp_ptr sb = lmmp_hgcd_salloc_(sc, n + 1);
1136 mp_size_t rn;
1137 mp_size_t blen;
1138 if (n >= HGCD_MODMUL_THRESHOLD) {
1139 rn = lmmp_hgcd_apply_mod_(&M1, dsub, sa, sb, &blen, ap, bp, n,
1141 } else {
1142 rn = lmmp_hgcd_adjust_(&M1, dsub, sa, sb, &blen, ha, hb, nn, ap, bp, n, p2, sc);
1143 }
1145 if (rn > 0 && rn < n && blen > maxlen) {
1146 if (lmmp_cmp_(sa, sb, rn) >= 0) {
1147 lmmp_copy(ap, sa, rn);
1148 lmmp_copy(bp, sb, rn);
1149 } else {
1151 dsub = -dsub;
1152 lmmp_copy(ap, sb, rn);
1153 lmmp_copy(bp, sa, rn);
1154 }
1155 /* [rn,n) 为无效残留:后续所有读写均以新公共长度 rn 为界 */
1156 n = rn;
1157 lmmp_hgcd_matrix_mul_(M, &M1, sc);
1158 *detsign *= dsub;
1159 success = 1;
1160 }
1161 sc->used = mark2;
1162 }
1163 sc->used = mark;
1164 }
1165 }
1166 }
1167 }
1168
1169 /* 基础步进循环:降至下限 */
1170 while (n > fl) {
1171 mp_size_t nn = lmmp_hgcd_step_(M, ap, bp, n, fl, sc, detsign);
1172 if (nn == 0) {
1173 return success ? n : 0;
1174 }
1175 n = nn;
1176 success = 1;
1177 }
1178 return success ? n : 0;
1179}
1180
1182 lmmp_param_assert(M != NULL);
1183 lmmp_param_assert(alloc > 0);
1184 mp_ptr buf = ALLOC_TYPE(4 * alloc, mp_limb_t);
1185 lmmp_hgcd_matrix_init_buf_(M, buf, alloc);
1186}
1187
1189 lmmp_param_assert(M != NULL);
1190 lmmp_free(M->m[0][0]);
1191 M->m[0][0] = NULL;
1192 M->m[0][1] = NULL;
1193 M->m[1][0] = NULL;
1194 M->m[1][1] = NULL;
1195 M->n[0][0] = M->n[0][1] = M->n[1][0] = M->n[1][1] = 0;
1196 M->alloc = 0;
1197}
1198
1200 lmmp_param_assert(M != NULL && ap != NULL && bp != NULL);
1201 lmmp_param_assert(n > 0);
1202 lmmp_debug_assert(M->alloc >= n + 2);
1203 lmmp_param_assert(ap[n - 1] != 0);
1204 if (lmmp_cmp_(ap, bp, n) <= 0) {
1205 return 0; /* a == b:gcd 即自身,无归约意义;a < b 违反契约 */
1206 }
1207 /* 一次性 scratch(与 lmmp_gcd_hgcd_ 相同的裸上界;矩阵元素缓冲由调用方提供) */
1209 mp_ptr scbuf = ALLOC_TYPE(scsz, mp_limb_t);
1210 lmmp_hgcd_scratch_t sc = {scbuf, scsz, 0};
1211 int dtop = 1;
1212 mp_size_t rn = lmmp_hgcd_core_(M, ap, bp, n, &sc, &dtop, 0);
1213 lmmp_free(scbuf);
1214 return rn;
1215}
1216
1218 lmmp_param_assert(dst != NULL && ap != NULL && bp != NULL);
1219 lmmp_param_assert(an >= bn && bn > 0);
1220
1221 /*
1222 不平衡预归约:当 bn <= an/2 时,b 的高半(bp[an/2,an))全零,hgcd 阶段 A
1223 的递归无法触发,数对逐层退化为"全除 + 部分除"两次 O(M(n)) 除法步进;
1224 先做一次取模将规模直接降至 b,再在平衡形状上运行分治。余数 r < b,
1225 若 r 仍显著短于 b(比例 <= 1/2)则继续取模,问题规模每轮几何递减。
1226 */
1227 mp_ptr pre0 = NULL, pre1 = NULL;
1228 if (an >= 2 * bn) {
1229 pre0 = ALLOC_TYPE(bn + 1, mp_limb_t);
1230 pre1 = ALLOC_TYPE(bn + 1, mp_limb_t);
1231 mp_srcptr up = ap, vp = bp;
1232 mp_size_t un = an, vn = bn;
1233 while (un >= 2 * vn) {
1234 mp_ptr rp = (vp == pre0) ? pre1 : pre0; /* 余数写入与除数分离的缓冲 */
1235 lmmp_div_(NULL, rp, up, un, vp, vn);
1236 mp_size_t rn = vn;
1237 while (rn > 0 && rp[rn - 1] == 0) {
1238 --rn;
1239 }
1240 if (rn == 0) { /* vp 整除 up:gcd 即 vp */
1241 lmmp_copy(dst, vp, vn);
1242 lmmp_free(pre0);
1243 lmmp_free(pre1);
1244 return vn;
1245 }
1246 up = vp;
1247 un = vn;
1248 vp = rp;
1249 vn = rn;
1250 }
1251 ap = up; /* vp 可能指向 pre0/pre1 内部,复制进工作副本后方可释放 */
1252 an = un;
1253 bp = vp;
1254 bn = vn;
1255 }
1256
1257 mp_size_t cap = an;
1258 mp_ptr wbuf = ALLOC_TYPE(cap * 2, mp_limb_t);
1259 mp_ptr wa = wbuf;
1260 mp_ptr wb = wbuf + cap;
1261 lmmp_copy(wa, ap, an);
1262 lmmp_copy(wb, bp, bn);
1263 lmmp_zero(wb + bn, cap - bn);
1264 if (pre0 != NULL) {
1265 lmmp_free(pre0);
1266 lmmp_free(pre1);
1267 }
1268
1269 mp_size_t rn;
1270 int cmp = lmmp_cmp_(wa, wb, cap);
1271 if (cmp == 0) {
1272 rn = an; /* wa 为归一化输入 ap 的副本,真实长度即 an */
1273 lmmp_copy(dst, wa, rn);
1274 lmmp_free(wbuf);
1275 return rn;
1276 } else if (cmp < 0) {
1277 LMMP_SWAP(wa, wb, mp_ptr);
1278 }
1279
1280 /* 一次性分配:scratch 与顶层矩阵缓冲,循环内复用(矩阵容量按最大 cur) */
1282 mp_ptr scbuf = ALLOC_TYPE(scsz, mp_limb_t);
1283 lmmp_hgcd_scratch_t sc = {scbuf, scsz, 0};
1284 mp_ptr mbuf = ALLOC_TYPE(4 * (an + 2), mp_limb_t);
1285
1286 mp_size_t cur = an;
1287 for (;;) {
1288 if (cur <= HGCD_RECURSE_THRESHOLD) {
1289 break;
1290 }
1292 lmmp_hgcd_matrix_init_buf_(&M, mbuf, cur + 2);
1293 int dtop = 1;
1294 mp_size_t nn = lmmp_hgcd_core_(&M, wa, wb, cur, &sc, &dtop, 0);
1295 if (nn == 0 || nn >= cur) {
1296 break; /* 无归约(防御性) */
1297 }
1298 /* [nn,cur) 为无效残留:循环内所有读写均以返回长度为界 */
1299 cur = nn;
1300 if (lmmp_zero_q_(wb, cur)) {
1301 break; /* b 归约为 0:gcd = a(存在性检查) */
1302 }
1303 if (lmmp_cmp_(wa, wb, cur) < 0) {
1304 LMMP_SWAP(wa, wb, mp_ptr); /* 指针交换 */
1305 }
1306 }
1307
1308 lmmp_free(scbuf);
1309 lmmp_free(mbuf);
1310
1311 mp_size_t ra = lmmp_gcd_norm_(wa, cur);
1312 mp_size_t rb = lmmp_gcd_norm_(wb, cur);
1313 if (rb == 0) {
1314 rn = ra;
1315 lmmp_copy(dst, wa, ra);
1316 } else {
1317 rn = lmmp_gcd_lehmer_(dst, wa, ra, wb, rb);
1318 }
1319 lmmp_free(wbuf);
1320 return rn;
1321}
#define rp
mp_size_t lmmp_hgcd_scratch_size_(mp_size_t n)
计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)
定义 hgcd.c:162
mp_size_t lmmp_hgcd_core_(lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n, lmmp_hgcd_scratch_t *sc, int *detsign, int appr)
hgcd 递归核:将数对归约至约 n/2 规模并累积变换矩阵(详见 hgcd.c 实现注)
static mp_size_t lmmp_gcd_norm_(mp_srcptr p, mp_size_t n)
定义 gcd.h:49
mp_size_t lmmp_hgcd_adjust_(lmmp_hgcd_matrix_t *M1, int detsign, mp_ptr dap, mp_ptr dbp, mp_size_t *blen, mp_srcptr ha, mp_srcptr hb, mp_size_t hn0, mp_srcptr ap, mp_srcptr bp, mp_size_t n, mp_size_t p, lmmp_hgcd_scratch_t *sc)
高位直写 + 低位修补:将子递归成果(矩阵 M1 与归约后的高位对)合入完整数对
定义 hgcd.c:554
#define HGCD_RECURSE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 gcd.h:33
static mp_ptr lmmp_hgcd_salloc_(lmmp_hgcd_scratch_t *sc, mp_size_t n)
定义 gcd.h:42
static mp_size_t lmmp_gcd_matrix_maxlen_(const lmmp_hgcd_matrix_t *M)
定义 gcd.h:56
static void lmmp_gcd_mul_(mp_ptr dst, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)
定义 gcd.h:92
static void lmmp_gcd_matrix_swap_cols_(lmmp_hgcd_matrix_t *M)
定义 gcd.h:70
#define an
#define bn
static int lmmp_hgcd_lehmer2_(mp_limb_t *pu00, mp_limb_t *pu01, mp_limb_t *pu10, mp_limb_t *pu11, mp_srcptr ap, mp_srcptr bp, mp_size_t n)
在 [ap,n] 与 [bp,n] 的 127 位顶端近似上运行小规模欧几里得,累积单 limb 矩阵 U
定义 hgcd.c:203
static void lmmp_hgcd_matrix_init_buf_(lmmp_hgcd_matrix_t *M, mp_ptr buf, mp_size_t alloc)
将连续缓冲初始化为单位矩阵
定义 hgcd.c:500
static void lmmp_hgcd_fold_mod_(mp_ptr dst, mp_srcptr src, mp_size_t sn, mp_size_t rn)
将 [src,sn] 折叠为模 B^rn-1 的表示:写入 [dst,rn)
定义 hgcd.c:853
static void lmmp_hgcd_matrix_mul_u_(lmmp_hgcd_matrix_t *M, lmmp_hgcd_scratch_t *sc, int *detsign, mp_limb_t u00, mp_limb_t u01, mp_limb_t u10, mp_limb_t u11)
M <- M*U,U 为单 limb 元素的非负矩阵
定义 hgcd.c:301
static mp_size_t lmmp_hgcd_apply_mod_(lmmp_hgcd_matrix_t *M1, int detsign, mp_ptr dap, mp_ptr dbp, mp_size_t *blen, mp_srcptr ap, mp_srcptr bp, mp_size_t n, int use_cache, lmmp_hgcd_scratch_t *sc)
模 B^rn-1 梅森乘法版矩阵应用: new = adj(M1)*(a;b),经 4 次模乘与模减精确重构
定义 hgcd.c:886
static mp_size_t lmmp_hgcd_step_(lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n, mp_size_t fl, lmmp_hgcd_scratch_t *sc, int *detsign)
单步步进:用近似矩阵 U 或一次(可能部分的)除法归约数对
定义 hgcd.c:694
static void lmmp_hgcd_matrix_mul_(lmmp_hgcd_matrix_t *M, const lmmp_hgcd_matrix_t *M1, lmmp_hgcd_scratch_t *sc)
M <- M*M1(经由库内 lmmp_mat22_mul_,按元素最大长度自动分派 basecase / Winograd-Strassen 路径)
定义 hgcd.c:527
static void lmmp_hgcd_matrix_update_q_(lmmp_hgcd_matrix_t *M, lmmp_hgcd_scratch_t *sc, int *detsign, mp_srcptr q, mp_size_t qn, int col)
真除法步进的矩阵累积
定义 hgcd.c:425
#define lmmp_limb_bits_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义 lmmp.h:458
#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
#define lmmp_debug_assert(x)
定义 lmmp.h:498
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define LMMP_MAX(h, i)
返回两个数中的较大值
定义 lmmp.h:454
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_VECT_CONSERVATIVE
定义 lmmp.h:201
#define lmmp_param_assert(x)
定义 lmmp.h:509
void lmmp_mul_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
#define lmmp_dec(p)
减1宏(预期无借位)
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
#define lmmp_inc(p)
加1宏(预期无进位)
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
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_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
定义 mul_1.c:76
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
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
void lmmp_mat22_mul_(lmmp_mat22_t *dst, const lmmp_mat22_t *a, const lmmp_mat22_t *b, mp_ptr tp)
计算 D <- A*B(2x2 非负矩阵乘法)
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_mul_mersenne_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
static void lmmp_fft_gr_cache_free_(fft_gr_cache *ctx)
释放费马或梅森数模乘法缓存上下文
void lmmp_mul_mersenne_cache_init_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1 第二个操作数将被缓存
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define t
#define tp
#define s
#define n
#define vh
#define c1
#define c0
#define HGCD_MODMUL_CACHE_THRESHOLD
#define HGCD_MODMUL_THRESHOLD
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_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 变换矩阵的元素缓冲
void lmmp_hgcd_matrix_init_(lmmp_hgcd_matrix_t *M, mp_size_t alloc)
初始化 hgcd 变换矩阵为单位矩阵(堆分配元素缓冲)
hgcd 变换矩阵
#define M1
#define ALLOC_TYPE(n, type)