LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
gcd.h 文件参考
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
gcd.h 的引用(Include)关系图:
此图展示该文件被哪些文件直接或间接地引用了:

浏览该文件的源代码.

结构体

struct  lmmp_gcd_lehmer_t
struct  lmmp_hgcd_scratch_t

宏定义

#define A   (M->m11)
#define B   (M->m12)
#define C   (M->m21)
#define D   (M->m22)
#define GCD_LEHMER_EXACT_BITS   63
#define GCD_LEHMER_MIN_V   0x100000000ll
#define HGCD_RECURSE_THRESHOLD   64
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

static void lmmp_gcd_lehmer_extract_ (mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn, slong *restrict a, slong *restrict b)
static void lmmp_gcd_lehmer_step_ (slong u, slong v, lmmp_gcd_lehmer_t *M)
static void lmmp_gcd_matrix_init_buf_ (lmmp_hgcd_matrix_t *M, mp_ptr buf, mp_size_t alloc)
static mp_size_t lmmp_gcd_matrix_maxlen_ (const lmmp_hgcd_matrix_t *M)
static void lmmp_gcd_matrix_swap_cols_ (lmmp_hgcd_matrix_t *M)
static void lmmp_gcd_mul_ (mp_ptr dst, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)
static mp_size_t lmmp_gcd_norm_ (mp_srcptr p, mp_size_t n)
mp_size_t lmmp_gcdext_derive_ (mp_ptr dst, int *tneg, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sn, int sneg, mp_srcptr xp, mp_size_t xn, mp_srcptr yp, mp_size_t yn, mp_ptr nb, mp_ptr yt, mp_ptr qt)
 导出另一侧系数:tv = (g - S·X)/Y(S 为 X 侧系数,恒等式保证整除)
void lmmp_gcdext_emit_ (mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sun, int suneg, int sw, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn, mp_ptr nb, mp_ptr yt, mp_ptr qt)
 发射:g 与 S(值序大者系数)按 sw 映射到 (dsts,dstt),另一系数经恒等式导出
static void lmmp_gcdext_smag_ (mp_ptr dst, mp_size_t *n, int *neg, mp_srcptr x, mp_size_t xn, int xneg, mp_srcptr y, mp_size_t yn, int yneg)
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 与归约后的高位对)合入完整数对
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_ptr lmmp_hgcd_salloc_ (lmmp_hgcd_scratch_t *sc, mp_size_t n)
mp_size_t lmmp_hgcd_scratch_size_ (mp_size_t n)
 计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)

结构体说明

◆ lmmp_gcd_lehmer_t

struct lmmp_gcd_lehmer_t

在文件 gcd.h 第 103 行定义.

lmmp_gcd_lehmer_t 的协作图:
成员变量
slong m11
slong m12
slong m21
slong m22

◆ lmmp_hgcd_scratch_t

struct lmmp_hgcd_scratch_t

在文件 gcd.h 第 35 行定义.

lmmp_hgcd_scratch_t 的协作图:
成员变量
mp_ptr base
mp_size_t cap
mp_size_t used

宏定义说明

◆ A

◆ B

◆ C

#define C   (M->m21)

◆ D

#define D   (M->m22)

◆ GCD_LEHMER_EXACT_BITS

#define GCD_LEHMER_EXACT_BITS   63

在文件 gcd.h 第 101 行定义.

被这些函数引用 lmmp_gcd_lehmer_extract_().

◆ GCD_LEHMER_MIN_V

#define GCD_LEHMER_MIN_V   0x100000000ll

在文件 gcd.h 第 100 行定义.

被这些函数引用 lmmp_gcd_lehmer_step_().

◆ HGCD_RECURSE_THRESHOLD

#define HGCD_RECURSE_THRESHOLD   64

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 gcd.h 第 33 行定义.

被这些函数引用 lmmp_gcd_hgcd_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_core_() , 以及 lmmp_hgcd_scratch_size_().

函数说明

◆ lmmp_gcd_lehmer_extract_()

void lmmp_gcd_lehmer_extract_ ( mp_srcptr up,
mp_size_t un,
mp_srcptr vp,
mp_size_t vn,
slong *restrict a,
slong *restrict b )
inlinestatic

在文件 gcd.h 第 142 行定义.

143 {
144 int kz = lmmp_limb_bits_(up[un - 1]);
145 if (kz >= GCD_LEHMER_EXACT_BITS) {
146 *a = up[un - 1] >> (kz - GCD_LEHMER_EXACT_BITS);
147 if (vn == un)
148 *b = vp[vn - 1] >> (kz - GCD_LEHMER_EXACT_BITS);
149 else
150 *b = 0;
151 } else {
152 *a = up[un - 1] << (GCD_LEHMER_EXACT_BITS - kz);
153 *a |= up[un - 2] >> (LIMB_BITS - (GCD_LEHMER_EXACT_BITS - kz));
154 if (un > vn + 1) {
155 *b = 0;
156 } else if (un == vn + 1) {
157 *b = vp[vn - 1] >> (LIMB_BITS - (GCD_LEHMER_EXACT_BITS - kz));
158 } else {
159 *b = vp[vn - 1] << (GCD_LEHMER_EXACT_BITS - kz);
160 *b |= vp[vn - 2] >> (LIMB_BITS - (GCD_LEHMER_EXACT_BITS - kz));
161 }
162 }
163}
#define GCD_LEHMER_EXACT_BITS
定义 gcd.h:101
#define lmmp_limb_bits_
#define LIMB_BITS
定义 lmmp.h:102

引用了 GCD_LEHMER_EXACT_BITS, LIMB_BITS, lmmp_gcd_lehmer_extract_(), lmmp_limb_bits_ , 以及 restrict.

被这些函数引用 lmmp_gcd_lehmer_(), lmmp_gcd_lehmer_extract_() , 以及 lmmp_gcdext_lehmer_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_gcd_lehmer_step_()

void lmmp_gcd_lehmer_step_ ( slong u,
slong v,
lmmp_gcd_lehmer_t * M )
inlinestatic

在文件 gcd.h 第 113 行定义.

113 {
114#define A (M->m11)
115#define B (M->m12)
116#define C (M->m21)
117#define D (M->m22)
118 A = 1;
119 B = 0;
120 C = 0;
121 D = 1;
122 while (v != 0) {
123 slong q = u / v;
124 slong t = u % v;
125 u = v;
126 v = t;
127 t = A - q * C;
128 A = C;
129 C = t;
130 t = B - q * D;
131 B = D;
132 D = t;
133 if (v < (slong)GCD_LEHMER_MIN_V)
134 break;
135 }
136#undef A
137#undef B
138#undef C
139#undef D
140}
#define B
#define GCD_LEHMER_MIN_V
定义 gcd.h:100
#define A
#define C
#define D
#define t
int64_t slong
定义 numth.h:41

引用了 A, B, C, D, GCD_LEHMER_MIN_V, lmmp_gcd_lehmer_step_() , 以及 t.

被这些函数引用 lmmp_gcd_lehmer_(), lmmp_gcd_lehmer_step_() , 以及 lmmp_gcdext_lehmer_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_gcd_matrix_init_buf_()

void lmmp_gcd_matrix_init_buf_ ( lmmp_hgcd_matrix_t * M,
mp_ptr buf,
mp_size_t alloc )
inlinestatic

在文件 gcd.h 第 77 行定义.

77 {
78 lmmp_debug_assert(M != NULL && buf != NULL && alloc > 0);
79 M->m[0][0] = buf;
80 M->m[0][1] = buf + alloc;
81 M->m[1][0] = buf + 2 * alloc;
82 M->m[1][1] = buf + 3 * alloc;
83 M->n[0][0] = 1;
84 M->n[0][1] = 0;
85 M->n[1][0] = 0;
86 M->n[1][1] = 1;
87 M->alloc = alloc;
88 M->m[0][0][0] = 1;
89 M->m[1][1][0] = 1;
90}
#define lmmp_debug_assert(x)
定义 lmmp.h:498
mp_size_t n[2][2]

引用了 lmmp_hgcd_matrix_t::alloc, lmmp_debug_assert, lmmp_gcd_matrix_init_buf_(), lmmp_hgcd_matrix_t::m , 以及 lmmp_hgcd_matrix_t::n.

被这些函数引用 lmmp_gcd_matrix_init_buf_() , 以及 lmmp_gcdext_hgcd_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_gcd_matrix_maxlen_()

mp_size_t lmmp_gcd_matrix_maxlen_ ( const lmmp_hgcd_matrix_t * M)
inlinestatic

在文件 gcd.h 第 56 行定义.

56 {
57 mp_size_t mx = 0;
58 if (M->n[0][0] > mx)
59 mx = M->n[0][0];
60 if (M->n[0][1] > mx)
61 mx = M->n[0][1];
62 if (M->n[1][0] > mx)
63 mx = M->n[1][0];
64 if (M->n[1][1] > mx)
65 mx = M->n[1][1];
66 return mx;
67}
uint64_t mp_size_t
定义 lmmp.h:93

引用了 lmmp_gcd_matrix_maxlen_() , 以及 lmmp_hgcd_matrix_t::n.

被这些函数引用 gcdext_row_mul_(), lmmp_gcd_matrix_maxlen_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_adjust_(), lmmp_hgcd_apply_mod_(), lmmp_hgcd_core_(), lmmp_hgcd_matrix_mul_(), lmmp_hgcd_matrix_mul_u_() , 以及 lmmp_hgcd_matrix_update_q_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_gcd_matrix_swap_cols_()

void lmmp_gcd_matrix_swap_cols_ ( lmmp_hgcd_matrix_t * M)
inlinestatic

在文件 gcd.h 第 70 行定义.

70 {
71 LMMP_SWAP(M->m[0][0], M->m[0][1], mp_ptr);
72 LMMP_SWAP(M->m[1][0], M->m[1][1], mp_ptr);
73 LMMP_SWAP(M->n[0][0], M->n[0][1], mp_size_t);
74 LMMP_SWAP(M->n[1][0], M->n[1][1], mp_size_t);
75}
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义 lmmp.h:458

引用了 lmmp_gcd_matrix_swap_cols_(), LMMP_SWAP, lmmp_hgcd_matrix_t::m , 以及 lmmp_hgcd_matrix_t::n.

被这些函数引用 lmmp_gcd_matrix_swap_cols_(), lmmp_gcdext_hgcd_() , 以及 lmmp_hgcd_core_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_gcd_mul_()

void lmmp_gcd_mul_ ( mp_ptr dst,
mp_srcptr a,
mp_size_t an,
mp_srcptr b,
mp_size_t bn )
inlinestatic

在文件 gcd.h 第 92 行定义.

92 {
93 if (an >= bn) {
94 lmmp_mul_(dst, a, an, b, bn);
95 } else {
96 lmmp_mul_(dst, b, bn, a, an);
97 }
98}
#define an
#define bn
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]

引用了 an, bn, lmmp_gcd_mul_() , 以及 lmmp_mul_().

被这些函数引用 gcdext_row_mul_(), lmmp_gcd_mul_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_adjust_() , 以及 lmmp_hgcd_matrix_update_q_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_gcd_norm_()

mp_size_t lmmp_gcd_norm_ ( mp_srcptr p,
mp_size_t n )
inlinestatic

在文件 gcd.h 第 49 行定义.

49 {
50 while (n > 0 && p[n - 1] == 0) {
51 --n;
52 }
53 return n;
54}
#define n

引用了 lmmp_gcd_norm_() , 以及 n.

被这些函数引用 lmmp_gcd_hgcd_(), lmmp_gcd_norm_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_apply_mod_() , 以及 lmmp_hgcd_step_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_gcdext_derive_()

mp_size_t lmmp_gcdext_derive_ ( mp_ptr dst,
int * tneg,
mp_srcptr gp,
mp_size_t gn,
mp_srcptr sp,
mp_size_t sn,
int sneg,
mp_srcptr xp,
mp_size_t xn,
mp_srcptr yp,
mp_size_t yn,
mp_ptr nb,
mp_ptr yt,
mp_ptr qt )

导出另一侧系数:tv = (g - S·X)/Y(S 为 X 侧系数,恒等式保证整除)

参数
dst输出(容量 >= xn+2)
tneg出参,tv 的符号
gpg(归一化)
gng 的长度
spS 的幅度(归一化)
snS 的幅度长
snegS 的符号
xp值序大者原对(归一化)
xn其长度
yp值序小者原对(归一化)
yn其长度
nb全乘积暂存(容量 >= xn+yn+2)
ytY 奇化暂存(容量 >= yn+1)
qt整商暂存(容量 >= xn+2;lmmp_divexact_ 写入长 nn-yn2+1 可超 出 dst 公开容量,先落此处再按归一化长度拷出)
返回
tv 写入长度(tv==0 理论不可达时返回 0)
警告
sep([dst|nb|yt|qt],[gp|sp|xp|yp]),gn>0,sn<=xn
注解
S==0 时 Y|X 且 g==Y,tv=1。Y 偶时剥公因子 2^k 后走 lmmp_divexact_ (要求奇除数;N = tv*Y 保证 N 的低 k 位为零)。S 与 tv 反号(极小 系数性质,|S|*X >= X >= g 使 g 落在 0 与 |S|*X 之间)

在文件 gcdext.c 第 225 行定义.

227 {
228 if (sn == 0) {
229 dst[0] = 1; /* g == Y */
230 *tneg = 0;
231 return 1;
232 }
233 /* P = |S|*X(P >= X >= g,写长 sn+xn) */
234 if (sn >= xn)
235 lmmp_mul_(nb, sp, sn, xp, xn);
236 else
237 lmmp_mul_(nb, xp, xn, sp, sn);
238 mp_size_t pn = sn + xn;
239 while (pn > 0 && nb[pn - 1] == 0)
240 --pn;
241 lmmp_debug_assert(pn > 0);
242 /* N = |g - S*X| */
243 if (sneg) {
244 mp_limb_t c = lmmp_add_(nb, nb, pn, gp, gn);
245 if (c != 0)
246 nb[pn++] = c;
247 *tneg = 0;
248 } else {
249 mp_limb_t bw = lmmp_sub_(nb, nb, pn, gp, gn);
250 lmmp_debug_assert(bw == 0);
251 while (pn > 0 && nb[pn - 1] == 0)
252 --pn;
253 *tneg = pn != 0;
254 }
255 if (pn == 0) {
256 /* 理论不可达:N==0 ⟺ |S|*X == g,仅 X==g 且 |S|==1,即入口 U==V(已早退) */
257 dst[0] = 0;
258 *tneg = 0;
259 return 0;
260 }
261 /* 剥 Y 的 2^k(Y 归一化故 j 扫描必终止) */
262 mp_size_t j = 0;
263 while (yp[j] == 0)
264 ++j;
265 ulong y0; /* 仅需 cnt,奇化值不使用 */
266 int sb;
267 ctz_shr_u64(y0, yp[j], sb);
268 (void)y0;
269 /* N >>= k(整 limb 段 j + 位段 sb,低位必为零) */
270 mp_ptr np = nb + j;
271 mp_size_t nn = pn - j;
272 if (sb != 0) {
273 mp_limb_t out = lmmp_shr_(np, np, nn, sb);
274 lmmp_debug_assert(out == 0);
275 while (nn > 0 && np[nn - 1] == 0)
276 --nn;
277 }
278 /* Y >>= k 奇化到 yt(归一化) */
279 mp_size_t yn2 = yn - j;
280 if (sb != 0) {
281 lmmp_shr_(yt, yp + j, yn2, sb);
282 while (yn2 > 0 && yt[yn2 - 1] == 0)
283 --yn2;
284 } else {
285 lmmp_copy(yt, yp + j, yn2);
286 }
287 lmmp_debug_assert(yn2 > 0 && (yt[0] & 1) == 1);
288 lmmp_debug_assert(nn >= yn2);
289 /*
290 tv = N/Y(|tv| >= 1 故 nn >= yn2)。lmmp_divexact_ 的写入长为 nn-yn2+1
291 (顶 limb 可为零),可能超出 dst 的公开容量契约(值 |tv| <= X/(2g) <=
292 xn limb,但写长至 xn+1)——先整商落内部暂存 qt,再按归一化 rn 拷出
293 */
294 lmmp_divexact_(qt, np, nn, yt, yn2);
295 mp_size_t rn = nn - yn2 + 1;
296 while (rn > 0 && qt[rn - 1] == 0)
297 --rn;
298 lmmp_debug_assert(rn > 0);
299 lmmp_copy(dst, qt, rn);
300 return rn;
301}
#define xn
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
uint64_t mp_limb_t
定义 lmmp.h:92
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]
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.c:26
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]
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define xp
void lmmp_divexact_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
uint64_t ulong
定义 numth.h:39

引用了 ctz_shr_u64, lmmp_add_(), lmmp_copy, lmmp_debug_assert, lmmp_divexact_(), lmmp_gcdext_derive_(), lmmp_mul_(), lmmp_shr_(), lmmp_sub_(), xn , 以及 xp.

被这些函数引用 lmmp_gcdext_derive_() , 以及 lmmp_gcdext_emit_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_gcdext_emit_()

void lmmp_gcdext_emit_ ( mp_ptr dstg,
mp_ptr dsts,
mp_ssize_t * sn,
mp_ptr dstt,
mp_ssize_t * tn,
mp_srcptr gp,
mp_size_t gn,
mp_srcptr sp,
mp_size_t sun,
int suneg,
int sw,
mp_srcptr up,
mp_size_t un,
mp_srcptr vp,
mp_size_t vn,
mp_ptr nb,
mp_ptr yt,
mp_ptr qt )

发射:g 与 S(值序大者系数)按 sw 映射到 (dsts,dstt),另一系数经恒等式导出

参数
dstg结果 g 输出(容量 >= gn)
dstsu 侧系数输出(容量 >= max(un,vn)+1)
sn输出 s 的带符号长度
dsttv 侧系数输出(容量 >= max(un,vn)+1,可为 NULL 表示不需要)
tn输出 t 的带符号长度(dstt==NULL 时忽略,可为 NULL)
gpg(归一化)
gng 的长度
spS 的幅度(归一化)
sunS 的幅度长
sunegS 的符号
sw值序归一化的交换标志(1 表示 up/vp 已交换,S 为 vp 侧系数)
up值序大者原对
un其长度
vp值序小者原对
vn其长度
nb导出全乘积暂存(容量 >= 2*max(un,vn)+4)
yt导出奇化暂存(容量 >= max(un,vn)+2)
qt导出整商暂存(容量 >= max(un,vn)+2)
警告
sep([dsts|dstt],dstg),对 up/vp 的全部读取(导出)先于输出写入

在文件 gcdext.c 第 303 行定义.

306 {
307 if (!sw) {
308 /* s = S(up 为大者),t = (g - S*up)/vp */
309 if (dstt != NULL) {
310 int tneg;
311 mp_size_t rn = lmmp_gcdext_derive_(dstt, &tneg, gp, gn, sp, sun, suneg, up, un, vp, vn,
312 nb, yt, qt);
313 if (rn == 0)
314 dstt[0] = 0;
315 *tn = (rn != 0 && tneg) ? -(mp_ssize_t)rn : (mp_ssize_t)rn;
316 }
317 lmmp_copy(dstg, gp, gn);
318 lmmp_copy(dsts, sp, sun);
319 if (sun == 0)
320 dsts[0] = 0;
321 *sn = (sun != 0 && suneg) ? -(mp_ssize_t)sun : (mp_ssize_t)sun;
322 } else {
323 /* t = S(vp 为大者),s = (g - S*vp)/up(导出 X 用值序大者 up) */
324 int tneg;
325 mp_size_t rn = lmmp_gcdext_derive_(dsts, &tneg, gp, gn, sp, sun, suneg, up, un, vp, vn, nb,
326 yt, qt);
327 lmmp_copy(dstg, gp, gn);
328 if (dstt != NULL) {
329 lmmp_copy(dstt, sp, sun);
330 if (sun == 0)
331 dstt[0] = 0;
332 *tn = (sun != 0 && suneg) ? -(mp_ssize_t)sun : (mp_ssize_t)sun;
333 }
334 if (rn == 0)
335 dsts[0] = 0;
336 *sn = (rn != 0 && tneg) ? -(mp_ssize_t)rn : (mp_ssize_t)rn;
337 }
338}
mp_size_t lmmp_gcdext_derive_(mp_ptr dst, int *tneg, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sn, int sneg, mp_srcptr xp, mp_size_t xn, mp_srcptr yp, mp_size_t yn, mp_ptr nb, mp_ptr yt, mp_ptr qt)
导出另一侧系数:tv = (g - S·X)/Y(S 为 X 侧系数,恒等式保证整除)
int64_t mp_ssize_t
定义 lmmp.h:95

引用了 lmmp_copy, lmmp_gcdext_derive_() , 以及 lmmp_gcdext_emit_().

被这些函数引用 lmmp_gcdext_emit_(), lmmp_gcdext_hgcd_() , 以及 lmmp_gcdext_lehmer_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_gcdext_smag_()

void lmmp_gcdext_smag_ ( mp_ptr dst,
mp_size_t * n,
int * neg,
mp_srcptr x,
mp_size_t xn,
int xneg,
mp_srcptr y,
mp_size_t yn,
int yneg )
inlinestatic

在文件 gcd.h 第 169 行定义.

170 {
171 if (xn == 0) {
172 lmmp_copy(dst, y, yn);
173 *n = yn;
174 *neg = yneg;
175 return;
176 }
177 if (yn == 0) {
178 lmmp_copy(dst, x, xn);
179 *n = xn;
180 *neg = xneg;
181 return;
182 }
183 if (xneg == yneg) {
184 mp_limb_t c;
185 if (xn >= yn) {
186 c = lmmp_add_(dst, x, xn, y, yn);
187 *n = xn;
188 } else {
189 c = lmmp_add_(dst, y, yn, x, xn);
190 *n = yn;
191 }
192 if (c != 0)
193 dst[(*n)++] = c;
194 *neg = xneg;
195 return;
196 }
197 int c = (xn != yn) ? (xn < yn ? -1 : 1) : lmmp_cmp_(x, y, xn);
198 if (c == 0) {
199 *n = 0;
200 *neg = 0;
201 return;
202 }
203 if (c > 0) {
204 lmmp_sub_(dst, x, xn, y, yn);
205 *n = xn;
206 *neg = xneg;
207 } else {
208 lmmp_sub_(dst, y, yn, x, xn);
209 *n = yn;
210 *neg = yneg;
211 }
212 while (*n > 0 && dst[*n - 1] == 0)
213 --*n;
214 if (*n == 0)
215 *neg = 0;
216}
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26

引用了 lmmp_add_(), lmmp_cmp_(), lmmp_copy, lmmp_gcdext_smag_(), lmmp_sub_(), n , 以及 xn.

被这些函数引用 lmmp_gcdext_hgcd_(), lmmp_gcdext_lehmer_() , 以及 lmmp_gcdext_smag_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_hgcd_adjust_()

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 与归约后的高位对)合入完整数对

参数
M1子递归累积的矩阵(各元素输入长度为 M1->n 个limb)
detsigndet(M1) 的符号,[1|-1]
dap分量 a 输出数组(写入 n 个limb,返回 0 时内容无效)
dbp分量 b 输出数组(写入 n 个limb,返回 0 时内容无效)
blen出参,分量 b 合入后的真实长度(供上层校验)
ha子递归归约后的高位 a(长度为 hn0 个limb,可为 ap+p 原地)
hb子递归归约后的高位 b(长度为 hn0 个limb)
hn0子递归返回的公共长度,hn0<=n-p
ap源完整较大分量(长度为 n 个limb,低 p 位参与修补)
bp源完整较小分量(长度为 n 个limb)
nap,bp 的公共长度
p高低位分裂点
sc临时空间(4*(p+M1->n+1) 个limb)
返回
合入后的公共长度;0 表示子归约过冲(借位穿底)
警告
M1!=NULL, dap!=NULL, dbp!=NULL, sc!=NULL, sep([dap|dbp],[ap|bp|ha|hb]), n>p>0, ap[n-1]>0

在文件 hgcd.c 第 554 行定义.

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}
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
#define lmmp_zero(dst, n)
定义 lmmp.h:476
#define M1

引用了 lmmp_add_(), lmmp_copy, lmmp_gcd_matrix_maxlen_(), lmmp_gcd_mul_(), lmmp_hgcd_adjust_(), lmmp_hgcd_salloc_(), lmmp_sub_(), lmmp_zero, M1, n , 以及 lmmp_hgcd_scratch_t::used.

被这些函数引用 lmmp_gcdext_hgcd_(), lmmp_hgcd_adjust_() , 以及 lmmp_hgcd_core_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_hgcd_core_()

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 实现注)

参数
M变换矩阵:入口应为单位矩阵,出口累积全部归约变换
ap较大分量输入兼输出数组(输入读 [ap,n),ap[n-1]>0;输出写 [ap,rn) 并零填充至 rn)
bp较小分量输入兼输出数组(允许高位为零,输出零填充至 rn)
nap,bp 的公共输入长度
sc临时空间(容量由 lmmp_hgcd_scratch_size_ 给出)
detsign出参,返回 det(M) 的符号
appr1 表示近似模式(仅矩阵累积,数对停留在约 3n/4;见 hgcd.c 实现注)
返回
归约后公共长度 rn;0 表示未做任何归约(M 保持单位矩阵)
警告
M!=NULL, sc!=NULL, ap!=NULL, bp!=NULL, sep(ap,bp), a>b>0, n>=3, M->alloc>=n+2

在文件 hgcd.c 第 1008 行定义.

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}
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 实现注)
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 void lmmp_gcd_matrix_swap_cols_(lmmp_hgcd_matrix_t *M)
定义 gcd.h:70
static void lmmp_hgcd_matrix_init_buf_(lmmp_hgcd_matrix_t *M, mp_ptr buf, mp_size_t alloc)
将连续缓冲初始化为单位矩阵
定义 hgcd.c:500
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
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
#define s
#define HGCD_MODMUL_CACHE_THRESHOLD
#define HGCD_MODMUL_THRESHOLD
hgcd 变换矩阵

引用了 lmmp_hgcd_matrix_t::alloc, HGCD_MODMUL_CACHE_THRESHOLD, HGCD_MODMUL_THRESHOLD, HGCD_RECURSE_THRESHOLD, lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_gcd_matrix_maxlen_(), lmmp_gcd_matrix_swap_cols_(), lmmp_hgcd_adjust_(), lmmp_hgcd_apply_mod_(), lmmp_hgcd_core_(), lmmp_hgcd_matrix_init_buf_(), lmmp_hgcd_matrix_mul_(), lmmp_hgcd_salloc_(), lmmp_hgcd_step_(), lmmp_zero_q_(), M1, n, s , 以及 lmmp_hgcd_scratch_t::used.

被这些函数引用 lmmp_gcd_hgcd_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_() , 以及 lmmp_hgcd_core_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_hgcd_salloc_()

mp_ptr lmmp_hgcd_salloc_ ( lmmp_hgcd_scratch_t * sc,
mp_size_t n )
inlinestatic

在文件 gcd.h 第 42 行定义.

42 {
44 mp_ptr p = sc->base + sc->used;
45 sc->used += n;
46 return p;
47}

引用了 lmmp_hgcd_scratch_t::base, lmmp_debug_assert, lmmp_hgcd_salloc_(), n , 以及 lmmp_hgcd_scratch_t::used.

被这些函数引用 gcdext_row_mul_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_adjust_(), lmmp_hgcd_apply_mod_(), lmmp_hgcd_core_(), lmmp_hgcd_matrix_mul_(), lmmp_hgcd_matrix_mul_u_(), lmmp_hgcd_matrix_update_q_(), lmmp_hgcd_salloc_() , 以及 lmmp_hgcd_step_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_hgcd_scratch_size_()

mp_size_t lmmp_hgcd_scratch_size_ ( mp_size_t n)

计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
n输入长度
警告
n>0

计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

计算 hgcd 内部临时空间大小

参数
n输入长度
警告
n>0
注解
峰值沿递归路径取 max 而非逐层求和:递增分配器经 mark 复位使 子层临时空间与本层合并相位(sa/sb 副本、adjust/apply_mod/矩阵 复合缓冲,合计约 14n)共享同一区域,二者不同时达峰;真正叠加 的只有递归期间常驻的高位副本与子矩阵缓冲。子问题规模上界取 2n/3 + 2(阶段 B 的 p2 分裂在最不利时接近该比例,严于实际的 n - n/2 与 2n_cur - n0 - 5)。本层合并相位预算 15n + 512(含 apply_mod 折叠缓冲的 next_size 取整余量与矩阵复合 9(2mx+4)), 步进循环 8n + 64。对比旧的逐层累加(约 48n)内存占用降至约 1/3

在文件 hgcd.c 第 162 行定义.

162 {
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}

引用了 HGCD_RECURSE_THRESHOLD, lmmp_hgcd_scratch_size_() , 以及 n.

被这些函数引用 lmmp_gcd_hgcd_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_() , 以及 lmmp_hgcd_scratch_size_().

函数调用图:
这是这个函数的调用关系图: