LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
gcdext_lehmer.c 文件参考
#include "numth/gcd.h"
#include "impl/tmp_alloc.h"
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
gcdext_lehmer.c 的引用(Include)关系图:

浏览该文件的源代码.

结构体

struct  sco_t
 Copyright (C) 2026 HJimmyK (Jericho Knox) 更多...

函数

static void lc1_ (sco_t *dst, slong al, mp_srcptr x, mp_size_t xn, slong be, mp_srcptr y, mp_size_t yn)
 dst = al*x + be*y(x,y 为非负幅度;al,be 为带符号标量,|al|,|be| < 2^63)
mp_size_t lmmp_gcdext_lehmer_ (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)
 扩展欧几里得(Lehmer 算法):g = gcd(u,v),s*u + t*v = g
static int mag_cmp_ (mp_srcptr x, mp_size_t xn, mp_srcptr y, mp_size_t yn)
static void pool_free2_ (int ia, int ib, int *f1, int *f2)

结构体说明

◆ sco_t

struct sco_t

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

在文件 gcdext_lehmer.c 第 82 行定义.

sco_t 的协作图:
成员变量
mp_size_t n
int neg
mp_ptr p

函数说明

◆ lc1_()

void lc1_ ( sco_t * dst,
slong al,
mp_srcptr x,
mp_size_t xn,
slong be,
mp_srcptr y,
mp_size_t yn )
static

dst = al*x + be*y(x,y 为非负幅度;al,be 为带符号标量,|al|,|be| < 2^63)

参数
dst输出槽(容量 >= max(xn,yn)+2;与 x,y 缓冲分离)
注解
两条快路均为两遍扫描(GMP gcdext 的 mul_1+addmul_1 / mul_1+submul_1 结构):
  • 同号(行更新常态,收敛子符号交替定理保证两项幅度无抵消): mul_1 + addmul_1 直加;
  • 异号(数对更新常态,收敛矩阵行异号):长项 mul_1 后 submul_1 减短项, 借位经 sub_1 传播;借位穿底表示真值为负,须换向重算。 逐次运行时核验借位/进位,正确性不依赖符号性质或值序假设

在文件 gcdext_lehmer.c 第 104 行定义.

105 {
106 ulong am = al < 0 ? (ulong)-al : (ulong)al;
107 ulong bm = be < 0 ? (ulong)-be : (ulong)be;
108 if (am == 0 || xn == 0) {
109 /* 项1 为零:dst = be*y */
110 mp_size_t tn = 0;
111 if (bm != 0 && yn != 0) {
112 mp_limb_t c = lmmp_mul_1_(dst->p, y, yn, bm);
113 tn = yn;
114 if (c != 0)
115 dst->p[tn++] = c;
116 }
117 dst->n = tn;
118 dst->neg = tn != 0 && be < 0;
119 return;
120 }
121 if (bm == 0 || yn == 0) {
122 /* 项2 为零:dst = al*x */
123 mp_limb_t c = lmmp_mul_1_(dst->p, x, xn, am);
124 mp_size_t tn = xn;
125 if (c != 0)
126 dst->p[tn++] = c;
127 dst->n = tn;
128 dst->neg = al < 0;
129 return;
130 }
131 if ((al < 0) == (be < 0)) {
132 /* 同号熔合:长项 mul_1 直写(含进位槽),短项 addmul_1 叠加,
133 其进位经 add_1 向顶传播(值界保证不越 xn+1,防御写 xn+2) */
134 if (xn < yn) {
135 LMMP_SWAP(x, y, mp_srcptr);
136 LMMP_SWAP(xn, yn, mp_size_t);
137 LMMP_SWAP(am, bm, ulong);
138 LMMP_SWAP(al, be, slong);
139 }
140 mp_limb_t h1 = lmmp_mul_1_(dst->p, x, xn, am);
141 dst->p[xn] = h1;
142 mp_size_t tn = xn + 1;
143 mp_limb_t h2 = lmmp_addmul_1_(dst->p, y, yn, bm);
144 if (h2 != 0) {
145 mp_limb_t c = lmmp_add_1_(dst->p + yn, dst->p + yn, xn + 1 - yn, h2);
146 if (c != 0) {
147 dst->p[tn] = c;
148 ++tn;
149 }
150 }
151 while (tn > 0 && dst->p[tn - 1] == 0)
152 --tn;
153 dst->n = tn;
154 dst->neg = (al < 0) && tn != 0;
155 return;
156 }
157 /*
158 异号:先按长项为被减数试减。长项 mul_1 直写(含进位槽),短项 submul_1
159 减去,借位经 sub_1 向顶传播;借位穿底即真值为负——换向重算(|be|·y 为
160 被减数,此时必有 |be|*y > |al|*x,借位必清)
161 */
162 if (xn < yn) {
163 LMMP_SWAP(x, y, mp_srcptr);
164 LMMP_SWAP(xn, yn, mp_size_t);
165 LMMP_SWAP(am, bm, ulong);
166 LMMP_SWAP(al, be, slong);
167 }
168 for (int dir = 0;; ++dir) {
169 mp_limb_t h1 = lmmp_mul_1_(dst->p, x, xn, am);
170 dst->p[xn] = h1;
171 if (yn > xn + 1)
172 lmmp_zero(dst->p + xn + 1, yn - xn - 1); /* 换向后短被减数的顶部缺口 */
173 mp_limb_t bw = lmmp_submul_1_(dst->p, y, yn, bm);
174 if (bw != 0)
175 bw = lmmp_sub_1_(dst->p + yn, dst->p + yn, xn + 1 - yn, bw);
176 if (bw == 0) {
177 mp_size_t tn = xn + 1;
178 while (tn > 0 && dst->p[tn - 1] == 0)
179 --tn;
180 dst->n = tn;
181 dst->neg = (al < 0) && tn != 0;
182 return;
183 }
184 /* 真值为负:换向(一次即出,第二轮被减数必大) */
185 LMMP_SWAP(x, y, mp_srcptr);
186 LMMP_SWAP(xn, yn, mp_size_t);
187 LMMP_SWAP(am, bm, ulong);
188 LMMP_SWAP(al, be, slong);
189 lmmp_debug_assert(dir == 0);
190 }
191}
#define xn
mp_size_t n
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义 lmmp.h:458
#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
uint64_t mp_limb_t
定义 lmmp.h:92
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
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
static mp_limb_t lmmp_sub_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
减单精度数静态内联函数 [dst,na]=[numa,na]-x
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
int64_t slong
定义 numth.h:41
uint64_t ulong
定义 numth.h:39

引用了 lc1_(), lmmp_add_1_(), lmmp_addmul_1_(), lmmp_debug_assert, lmmp_mul_1_(), lmmp_sub_1_(), lmmp_submul_1_(), LMMP_SWAP, lmmp_zero, sco_t::n, sco_t::neg, sco_t::p , 以及 xn.

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

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

◆ lmmp_gcdext_lehmer_()

mp_size_t lmmp_gcdext_lehmer_ ( 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 )

扩展欧几里得(Lehmer 算法):g = gcd(u,v),s*u + t*v = g

参数
dstg结果指针(长度至少为 min(un,vn))
dstsu 的贝祖系数幅度(长度至少为 vn 个limb,s==0 时写 0)
sn输出 s 的带符号 limb 长度([1|-1|0])
dsttv 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL 表示不需要)
tn输出 t 的带符号 limb 长度(dstt==NULL 时忽略,可为 NULL)
up第一个无符号整数指针
un第一个无符号整数的 limb 长度
vp第二个无符号整数指针
vn第二个无符号整数的 limb 长度
警告
up!=NULL, un>0, vp!=NULL, vn>0, dstg!=NULL, dsts!=NULL, sn!=NULL, up[un-1]!=0, vp[vn-1]!=0, sep([dsts|dstt],dstg)
返回
g 的实际 limb 长度
注解
取极小系数(同 lmmp_gcdext_11_ 注)。un/vn 任意大小关系(内部值序 归一化,系数按原参数序输出)。归约骨架与 gcd_lehmer.c 同构,共因子 走单行跟踪(GMP 行向量思想):全程保持 V = u0*a + u1*b(行元素非负, a;b 为当前数对),t 在输出相位经恒等式导出(dstt==NULL 时跳过)。 dstg 允许与 [up|vp] 别名(eqsep);dsts/dstt 在 up/vp 的所有读取 完成后才写入

在文件 gcdext_lehmer.c 第 209 行定义.

211 {
212 lmmp_param_assert(un > 0 && vn > 0);
213 lmmp_param_assert(up != NULL && vp != NULL && dstg != NULL && dsts != NULL && sn != NULL);
214 lmmp_param_assert(up[un - 1] != 0 && vp[vn - 1] != 0);
215
216 /* 值序归一化(sw 记录交换;s 恒为值序大者的系数,输出时按 sw 映射回原参数序) */
217 int sw = 0;
218 if (un < vn) {
219 LMMP_SWAP(up, vp, mp_srcptr);
220 LMMP_SWAP(un, vn, mp_size_t);
221 sw = 1;
222 } else if (un == vn) {
223 int c = lmmp_cmp_(up, vp, un);
224 if (c == 0) {
225 lmmp_copy(dstg, up, un);
226 dsts[0] = 0;
227 *sn = 0;
228 if (dstt != NULL) {
229 dstt[0] = 1;
230 *tn = 1;
231 }
232 return un;
233 }
234 if (c < 0) {
235 LMMP_SWAP(up, vp, mp_srcptr);
236 sw = 1;
237 }
238 }
239 // U > V > 0(un >= vn,up/vp 为值序大/小者)
240
241 mp_size_t RSZ = un + 2;
243 mp_ptr buf = BALLOC_TYPE(10 * RSZ + (2 * un + 8) + 3 * (un + 2) + 2, mp_limb_t);
244 mp_ptr pool = buf; /* 数对池 4 槽,各 RSZ */
245 mp_ptr rowp = pool + 4 * RSZ; /* 行槽 4(u0/u1/k0/k1),各 RSZ */
246 mp_ptr t1 = rowp + 4 * RSZ; /* 终态 2*u1 与尾合并组合临时 */
247 mp_ptr t2 = t1 + RSZ;
248 mp_ptr t2f = t2 + RSZ; /* 全乘积缓冲(除法步行积/尾合并 τ·u0/发射 nb) */
249 mp_ptr qt = t2f + (2 * un + 8);
250 mp_ptr rt = qt + (un + 2);
251 mp_ptr tg = rt + (un + 2); /* 尾合并 g(1)+ σ(1)+ τ/S 暂存(un+2) */
252 mp_ptr ts = tg + 1;
253 mp_ptr tt = ts + 1;
254
255 sco_t u0 = {rowp, 0, 0}, u1 = {rowp + RSZ, 0, 0};
256 sco_t k0 = {rowp + 2 * RSZ, 0, 0}, k1 = {rowp + 3 * RSZ, 0, 0};
257 u1.n = 1;
258 u1.p[0] = 1; /* V = 0*a + 1*b */
259 int det = 1;
260
261 int ia = 0, ib = 1;
262 mp_ptr a = pool;
263 mp_ptr b = pool + RSZ;
264 mp_size_t an = un, bn = vn;
265 lmmp_copy(a, up, un);
266 lmmp_copy(b, vp, vn);
267
268 mp_size_t sun = 0; /* S(值序大者系数)幅度长 */
269 int suneg = 0;
270 mp_ptr sp = tt; /* S 幅度暂存(<= vn+1 <= un+2) */
271 mp_ptr gp = NULL; /* g 暂存 */
272 mp_size_t gn = 0;
274 slong x = 0, y = 0;
275 for (;;) {
276 if (bn == 0) {
277 /*
278 (g;0) 终态:V = u0*g(强制 u0 > 0),解间隔 u0 = V/g,候选
279 det*u1 + k*u0 取距 0 近者(平局恒取正候选 +|u1|,见文件注三)
280 */
281 gp = a;
282 gn = an;
283 lmmp_debug_assert(u0.neg == 0); /* V = u0*g 与 V>0 强制 */
284 if (u1.n == 0) {
285 sun = 0;
286 suneg = 0;
287 } else {
288 mp_limb_t c2 = lmmp_mul_1_(t1, u1.p, u1.n, 2);
289 mp_size_t twon = u1.n + (c2 != 0);
290 int cmp2 = mag_cmp_(t1, twon, u0.p, u0.n);
291 int sn1 = (u1.neg != 0) ^ (det < 0); /* S0 = det*u1 的符号 */
292 if (cmp2 < 0) {
293 lmmp_copy(sp, u1.p, u1.n);
294 sun = u1.n;
295 suneg = sn1;
296 } else if (cmp2 > 0) {
297 /* S = S0 - sign(S0)*u0:幅度 u0-|u1| (< u0/2),符号翻转 */
298 lmmp_sub_(sp, u0.p, u0.n, u1.p, u1.n);
299 sun = u0.n;
300 while (sun > 0 && sp[sun - 1] == 0)
301 --sun;
302 suneg = sun != 0 && !sn1;
303 } else {
304 lmmp_copy(sp, u1.p, u1.n); /* 平局恒取正候选 */
305 sun = u1.n;
306 suneg = 0;
307 }
308 }
309 break;
310 }
311 if (bn == 1) {
312 /* 尾合并:g = sigma*a + tau*b(lmmp_gcdext_1_ 极小系数),
313 s = det*(sigma*u1 - tau*u0):一次标量乘 + 一次全乘 + 符号-幅度组合 */
314 mp_ssize_t sgn, tgn;
315 lmmp_gcdext_1_(tg, ts, &sgn, tt, &tgn, a, an, b[0]);
316 lmmp_debug_assert(tg[0] != 0);
317 gp = tg;
318 gn = 1;
319 slong sigma = sgn < 0 ? -(slong)ts[0] : (slong)ts[0];
320 mp_size_t tqn = tgn < 0 ? -tgn : tgn;
321 mp_size_t p1n = 0, p2n = 0;
322 int p1neg = 0, p2neg = 0;
323 if (sigma != 0 && u1.n != 0) {
324 mp_limb_t c = lmmp_mul_1_(k0.p, u1.p, u1.n,
325 sigma < 0 ? (ulong)-sigma : (ulong)sigma);
326 p1n = u1.n;
327 if (c != 0)
328 k0.p[p1n++] = c;
329 p1neg = (sigma < 0) ^ (u1.neg != 0);
330 }
331 if (tqn != 0 && u0.n != 0) {
332 if (tqn >= u0.n)
333 lmmp_mul_(t2f, tt, tqn, u0.p, u0.n);
334 else
335 lmmp_mul_(t2f, u0.p, u0.n, tt, tqn);
336 p2n = tqn + u0.n;
337 while (p2n > 0 && t2f[p2n - 1] == 0)
338 --p2n;
339 p2neg = (tgn < 0) ^ (u0.neg != 0);
340 }
341 /* s = sigma*u1 - tau*u0 = p1 + (-p2)(第二项符号翻转) */
342 lmmp_gcdext_smag_(t1, &sun, &suneg, k0.p, p1n, p1neg, t2f, p2n, !p2neg);
343 lmmp_copy(sp, t1, sun);
344 if (det < 0 && sun != 0)
345 suneg = !suneg;
346 break;
347 }
348
349 lmmp_gcd_lehmer_extract_(a, an, b, bn, &x, &y);
350 lmmp_gcd_lehmer_step_(x, y, &M);
351 if (M.m21 == 0) {
352 /*
353 除法回退:a = q*b + r,数对 (b;r)。行 <- 行*E:(q*u0+u1, u0),
354 det 变号。余数直写旧 a 槽(eqsep 契约),数对槽位交换即可
355 */
356 lmmp_div_(qt, a, a, an, b, bn);
357 mp_size_t qn = an - bn + 1 - (qt[an - bn] == 0);
358 mp_size_t rn = bn;
359 while (rn > 0 && a[rn - 1] == 0)
360 --rn;
361 if (qn == 1 && qt[0] < (1ull << 63)) {
362 /* 商为标量:行更新走 lc1_(两遍扫描快路) */
363 int d0 = u0.neg ? -1 : 1, d1 = u1.neg ? -1 : 1;
364 lc1_(&k0, (slong)qt[0] * d0, u0.p, u0.n, d1, u1.p, u1.n);
365 } else {
366 mp_size_t pn = 0;
367 if (qn != 0 && u0.n != 0) {
368 if (qn >= u0.n)
369 lmmp_mul_(t2f, qt, qn, u0.p, u0.n);
370 else
371 lmmp_mul_(t2f, u0.p, u0.n, qt, qn);
372 pn = qn + u0.n;
373 while (pn > 0 && t2f[pn - 1] == 0)
374 --pn;
375 }
376 lmmp_gcdext_smag_(k0.p, &k0.n, &k0.neg, t2f, pn, u0.neg != 0, u1.p, u1.n,
377 u1.neg != 0);
378 }
379 {
380 sco_t t_ = u1;
381 u1 = u0;
382 u0 = k0;
383 k0 = t_;
384 }
385 mp_ptr ta = a;
386 a = b;
387 b = ta; /* b 槽现持有 r */
388 an = bn;
389 bn = rn;
390 int ti = ia;
391 ia = ib;
392 ib = ti;
393 det = -det;
394 continue;
395 }
396 /*
397 矩阵步:值 (new_a;new_b) = (C*a+D*b; A*a+B*b) 落入两空闲槽;
398 行 <- 行*N_applied^{-1},四组合系数 X(见文件注二)为带符号标量
399 */
400 int f1, f2;
401 pool_free2_(ia, ib, &f1, &f2);
402 sco_t sa = {pool + f1 * RSZ, 0, 0}, sb = {pool + f2 * RSZ, 0, 0};
403 lc1_(&sa, M.m21, a, an, M.m22, b, bn);
404 lc1_(&sb, M.m11, a, an, M.m12, b, bn);
405 lmmp_debug_assert(sa.n != 0 || sb.n != 0);
406 int da = sa.neg ? -1 : 1, db = sb.neg ? -1 : 1;
407 slong dlin = M.m21 * M.m12 - M.m22 * M.m11; /* det_lin = C*B - D*A = ±1 */
408 slong sda = (slong)da * dlin, sdb = (slong)db * dlin;
409 /* 行元素带符号:符号折入组合标量(sda、d0 均为 ±1,|标量| = |矩阵元素| < 2^31) */
410 int d0 = u0.neg ? -1 : 1, d1 = u1.neg ? -1 : 1;
411 lc1_(&k0, sda * M.m12 * d0, u0.p, u0.n, -sda * M.m11 * d1, u1.p, u1.n);
412 lc1_(&k1, -sdb * M.m22 * d0, u0.p, u0.n, sdb * M.m21 * d1, u1.p, u1.n);
413 det = (int)(det * da * db * dlin);
414 {
415 sco_t t_ = u0;
416 u0 = k0;
417 k0 = t_;
418 }
419 {
420 sco_t t_ = u1;
421 u1 = k1;
422 k1 = t_;
423 }
424 /* 数对新槽与值序(值序翻转 = 行分量对调 + det 变号) */
425 if (sa.n == 0) {
426 sco_t t_ = u0;
427 u0 = u1;
428 u1 = t_;
429 det = -det;
430 a = pool + f2 * RSZ;
431 an = sb.n;
432 b = pool + f1 * RSZ;
433 bn = 0;
434 ia = f2;
435 ib = f1;
436 } else if (sb.n == 0) {
437 a = pool + f1 * RSZ;
438 an = sa.n;
439 b = pool + f2 * RSZ;
440 bn = 0;
441 ia = f1;
442 ib = f2;
443 } else if (mag_cmp_(sa.p, sa.n, sb.p, sb.n) < 0) {
444 sco_t t_ = u0;
445 u0 = u1;
446 u1 = t_;
447 det = -det;
448 a = pool + f2 * RSZ;
449 an = sb.n;
450 b = pool + f1 * RSZ;
451 bn = sa.n;
452 ia = f2;
453 ib = f1;
454 } else {
455 a = pool + f1 * RSZ;
456 an = sa.n;
457 b = pool + f2 * RSZ;
458 bn = sb.n;
459 ia = f1;
460 ib = f2;
461 }
462 }
463
464 /* 发射:g 与 S 按 sw 映射 + 恒等式导出(与 hgcd 驱动共享,见 impl/gcd.h) */
465 /* qt 复用 k1 行槽(容量 RSZ=un+2,循环已结束槽位死亡) */
466 lmmp_gcdext_emit_(dstg, dsts, sn, dstt, tn, gp, gn, sp, sun, suneg, sw, up, un, vp, vn, t2f, rt,
467 k1.p);
469 return gn;
470}
static void lmmp_gcd_lehmer_step_(slong u, slong v, lmmp_gcd_lehmer_t *M)
定义 gcd.h:113
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)
定义 gcd.h:142
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)
定义 gcd.h:169
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),另一系数经恒等式导出
#define an
#define bn
static void pool_free2_(int ia, int ib, int *f1, int *f2)
static int mag_cmp_(mp_srcptr x, mp_size_t xn, mp_srcptr y, mp_size_t yn)
static void lc1_(sco_t *dst, slong al, mp_srcptr x, mp_size_t xn, slong be, mp_srcptr y, mp_size_t yn)
dst = al*x + be*y(x,y 为非负幅度;al,be 为带符号标量,|al|,|be| < 2^63)
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
int64_t mp_ssize_t
定义 lmmp.h:95
#define lmmp_param_assert(x)
定义 lmmp.h:509
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]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.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]
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_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 TEMP_B_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_B_FREE

引用了 an, BALLOC_TYPE, bn, lc1_(), lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_div_(), lmmp_gcd_lehmer_extract_(), lmmp_gcd_lehmer_step_(), lmmp_gcdext_1_(), lmmp_gcdext_emit_(), lmmp_gcdext_lehmer_(), lmmp_gcdext_smag_(), lmmp_mul_(), lmmp_mul_1_(), lmmp_param_assert, lmmp_sub_(), LMMP_SWAP, lmmp_gcd_lehmer_t::m11, lmmp_gcd_lehmer_t::m12, lmmp_gcd_lehmer_t::m21, lmmp_gcd_lehmer_t::m22, mag_cmp_(), sco_t::n, sco_t::neg, sco_t::p, pool_free2_(), TEMP_B_DECL , 以及 TEMP_B_FREE.

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

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

◆ mag_cmp_()

int mag_cmp_ ( mp_srcptr x,
mp_size_t xn,
mp_srcptr y,
mp_size_t yn )
static

在文件 gcdext_lehmer.c 第 88 行定义.

88 {
89 if (xn != yn)
90 return xn < yn ? -1 : 1;
91 return xn == 0 ? 0 : lmmp_cmp_(x, y, xn);
92}

引用了 lmmp_cmp_(), mag_cmp_() , 以及 xn.

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

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

◆ pool_free2_()

void pool_free2_ ( int ia,
int ib,
int * f1,
int * f2 )
static

在文件 gcdext_lehmer.c 第 194 行定义.

194 {
195 *f1 = -1;
196 *f2 = -1;
197 for (int i = 0; i < 4; ++i) {
198 if (i != ia && i != ib) {
199 if (*f1 < 0) {
200 *f1 = i;
201 } else {
202 *f2 = i;
203 return;
204 }
205 }
206 }
207}

引用了 pool_free2_().

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

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