LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
gcdext_lehmer.c
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23/*
24扩展欧几里得(Lehmer 算法,单行共因子跟踪)。
25
26一、骨架(与本库 gcd_lehmer.c 同构,窗口提取与步进矩阵经 impl/gcd.h 共享)
27
28窗口提取(顶端 63 位对齐)、步进矩阵(小规模欧几里得,break-before 停机于
292^32)、幅度数对更新与除法回退均取自 gcd_lehmer.c 的流程;bn==1 时经
30lmmp_gcdext_1_ 尾合并——归约路径与库内 gcd 完全一致。
31
32二、单行共因子跟踪(GMP mpn_gcdext 的行向量思想)
33
34值序归一化 U >= V 后全程维护精确恒等式
35
36 V = u0*a + u1*b
37
38其中 (a;b) 为当前数对(幅度语义——本库 Lehmer 步进矩阵为带符号收敛矩阵,
39新值组合可能为负,幅度对 gcd 无害但共因子须携带符号),行元素 (u0,u1) 为
40符号-幅度数。记累积变换 (U;V) = M*(a;b),行即 M 的第 1 行,
41detsign = det(M) = [1|-1]:
42
43 - 除法步(a = q*b + r,数对变 (b;r)):(a;b) = E*(b;r),E = /q 1; 1 0/
44 (det = -1)。行 <- 行*E:(u0,u1) <- (q*u0 + u1, u0),detsign 变号。
45 商为单 limb 时经 lc1_ 标量线性组合(同号项熔合,见 lc1_ 注);
46 - 矩阵步((new_a;new_b) = N*(a;b),N 按 lehmer 消费序为 /C D; A B/,即
47 new_a = C*a + D*b、new_b = A*a + B*b):行 <- 行*N_applied^{-1}。幅度
48 语义下实际生效矩阵为 N_applied = diag(sa,sb)*N(sa/sb 为新值组合的
49 符号,即 lc1_ 结果的 neg 位),
50 N_applied^{-1} = det_lin*adj(N_applied)*diag(sa,sb) 展开的四元素为带
51 符号标量(|A..D| < 2^31,停机界保证),行更新经 lc1_ 两次标量线性组合
52 完成(行自身的符号折入标量);detsign <- detsign*sa*sb*det_lin。
53 数对值序翻转即数对左乘列交换 P(det = -1):行分量对调、detsign 变号。
54
55三、终态贝祖系数(s 为值序较大者的系数,单模变换保持极小性)
56
57 - 数对第二分量归零((g;0)):V = u0*g,解间隔 V/g = u0,候选
58 {detsign*u1 + k*u0},取距 0 近者:2*u1 < u0 取 detsign*u1;2*u1 > u0
59 取 detsign*(u1-u0)(幅度 u0-u1 < u0/2,符号与 detsign 相反);
60 2*u1 == u0 平局恒取 +u1——该侧配对系数满足 |t| <= U/(2g),另一侧
61 |g + u1*U| > u1*U 必然越界(GMP 同此选择);
62 - bn == 1 尾合并:g = sigma*a + tau*b(lmmp_gcdext_1_ 给极小系数),
63 s = detsign*(sigma*u1 - tau*u0)(一次全乘 + 一次标量乘)。
64
65t 不跟踪,输出相位按 t = (g - s*A)/B(A/B 为值序大/小原对)经
66lmmp_divexact_(B 偶时剥 2^k)导出,dstt==NULL 时跳过;发射映射(sw 换序
67与导出次序)经 impl/gcd.h 的 lmmp_gcdext_emit_ 与 hgcd 驱动共享。
68
69四、界与内存
70
71|u0|,|u1| <= V/g(收敛子界),行槽 un+2 覆盖乘进位。单块 TEMP:数对池
724 槽(矩阵步取两空闲槽轮换)、行槽 4(u0/u1/k0/k1 指针轮换)、lc1_ 临时
732、除法回退商/余/行积、尾合并与发射缓冲。
74*/
75
76#include "numth/gcd.h"
77#include "impl/tmp_alloc.h"
78#include "lmmp/lmmpn.h"
79#include "lmmp/numth.h"
80
81/* 符号-幅度系数(n 归一化;n==0 即零,neg 恒 0) */
82typedef struct {
85 int neg;
86} sco_t;
87
89 if (xn != yn)
90 return xn < yn ? -1 : 1;
91 return xn == 0 ? 0 : lmmp_cmp_(x, y, xn);
92}
93
94/**
95 * @brief dst = al*x + be*y(x,y 为非负幅度;al,be 为带符号标量,|al|,|be| < 2^63)
96 * @param dst 输出槽(容量 >= max(xn,yn)+2;与 x,y 缓冲分离)
97 * @note 两条快路均为两遍扫描(GMP gcdext 的 mul_1+addmul_1 / mul_1+submul_1 结构):
98 * - 同号(行更新常态,收敛子符号交替定理保证两项幅度无抵消):
99 * mul_1 + addmul_1 直加;
100 * - 异号(数对更新常态,收敛矩阵行异号):长项 mul_1 后 submul_1 减短项,
101 * 借位经 sub_1 传播;借位穿底表示真值为负,须换向重算。
102 * 逐次运行时核验借位/进位,正确性不依赖符号性质或值序假设
103 */
104static void lc1_(sco_t* dst, slong al, mp_srcptr x, mp_size_t xn, slong be, mp_srcptr y,
105 mp_size_t yn) {
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}
192
193/* 数对池 4 槽中排除 ia/ib 的两个空闲槽 */
194static void pool_free2_(int ia, int ib, int* f1, int* f2) {
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}
208
210 mp_ssize_t* tn, mp_srcptr up, mp_size_t un, mp_srcptr vp,
211 mp_size_t vn) {
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}
#define xn
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)
mp_size_t n
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_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
int64_t mp_ssize_t
定义 lmmp.h:95
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
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
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]
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
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
int64_t slong
定义 numth.h:41
uint64_t ulong
定义 numth.h:39
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
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
#define TEMP_B_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_B_FREE