LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
gcd.h
浏览该文件的文档.
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#ifndef __LMMP_IMPL_GCD_H__
24#define __LMMP_IMPL_GCD_H__
25
26#include "lmmp/lmmpn.h"
27#include "lmmp/numth.h"
28
29/*
30hgcd 递归阈值:公共长度超过该值时启用分治路径(hgcd.c 的核与 gcdext.c
31的驱动循环共用;待接入 tune 体系)
32*/
33#define HGCD_RECURSE_THRESHOLD 64
34
35typedef struct {
37 mp_size_t cap; /* 总容量 */
38 mp_size_t used; /* 当前游标 */
40
41/* 从递增分配器取 n limbs(出口用 sc->used = mark 复位) */
44 mp_ptr p = sc->base + sc->used;
45 sc->used += n;
46 return p;
47}
48
50 while (n > 0 && p[n - 1] == 0) {
51 --n;
52 }
53 return n;
54}
55
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}
68
69/* 矩阵列交换(指针交换):对应右乘 P(M <- M*P),数对翻转簿记用 */
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}
76
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}
91
93 if (an >= bn) {
94 lmmp_mul_(dst, a, an, b, bn);
95 } else {
96 lmmp_mul_(dst, b, bn, a, an);
97 }
98}
99
100#define GCD_LEHMER_MIN_V 0x100000000ll /* 停机界:窗口余数将跌破 2^32 时停止 */
101#define GCD_LEHMER_EXACT_BITS 63 /* 顶端对齐窗口位宽 */
102
103typedef struct {
107
108/*
109步进矩阵:在窗口 (u,v) 上运行小规模欧几里得。
110消费序 new_a = C*a + D*b、new_b = A*a + B*b(C=m21、D=m22、A=m11、B=m12),
111元素带符号,|A..D| < 2^31(v >= 2^32 停机界:元素 <= x/2^32 < 2^63/2^32)
112*/
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}
141
143 slong* restrict a, slong* restrict b) {
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}
164
165/*
166dst = (x,xneg) ± (y,yneg):按符号分派和/差;dst 与 x,y 缓冲分离。
167零向量约定 n==0(neg 无意义)
168*/
169static inline void lmmp_gcdext_smag_(mp_ptr dst, mp_size_t* n, int* neg, mp_srcptr x, mp_size_t xn,
170 int xneg, mp_srcptr y, mp_size_t yn, int yneg) {
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}
217
218/**
219 * @brief hgcd 递归核:将数对归约至约 n/2 规模并累积变换矩阵(详见 hgcd.c 实现注)
220 * @param M 变换矩阵:入口应为单位矩阵,出口累积全部归约变换
221 * @param ap 较大分量输入兼输出数组(输入读 [ap,n),ap[n-1]>0;输出写 [ap,rn) 并零填充至 rn)
222 * @param bp 较小分量输入兼输出数组(允许高位为零,输出零填充至 rn)
223 * @param n ap,bp 的公共输入长度
224 * @param sc 临时空间(容量由 lmmp_hgcd_scratch_size_ 给出)
225 * @param detsign 出参,返回 det(M) 的符号
226 * @param appr 1 表示近似模式(仅矩阵累积,数对停留在约 3n/4;见 hgcd.c 实现注)
227 * @return 归约后公共长度 rn;0 表示未做任何归约(M 保持单位矩阵)
228 * @warning M!=NULL, sc!=NULL, ap!=NULL, bp!=NULL, sep(ap,bp), a>b>0, n>=3, M->alloc>=n+2
229 */
231 mp_ptr ap,
232 mp_ptr bp,
233 mp_size_t n,
235 int* detsign,
236 int appr);
237
238/**
239 * @brief 高位直写 + 低位修补:将子递归成果(矩阵 M1 与归约后的高位对)合入完整数对
240 * @param M1 子递归累积的矩阵(各元素输入长度为 M1->n 个limb)
241 * @param detsign det(M1) 的符号,[1|-1]
242 * @param dap 分量 a 输出数组(写入 n 个limb,返回 0 时内容无效)
243 * @param dbp 分量 b 输出数组(写入 n 个limb,返回 0 时内容无效)
244 * @param blen 出参,分量 b 合入后的真实长度(供上层校验)
245 * @param ha 子递归归约后的高位 a(长度为 hn0 个limb,可为 ap+p 原地)
246 * @param hb 子递归归约后的高位 b(长度为 hn0 个limb)
247 * @param hn0 子递归返回的公共长度,hn0<=n-p
248 * @param ap 源完整较大分量(长度为 n 个limb,低 p 位参与修补)
249 * @param bp 源完整较小分量(长度为 n 个limb)
250 * @param n ap,bp 的公共长度
251 * @param p 高低位分裂点
252 * @param sc 临时空间(4*(p+M1->n+1) 个limb)
253 * @return 合入后的公共长度;0 表示子归约过冲(借位穿底)
254 * @warning M1!=NULL, dap!=NULL, dbp!=NULL, sc!=NULL, sep([dap|dbp],[ap|bp|ha|hb]),
255 * n>p>0, ap[n-1]>0
256 */
258 int detsign,
259 mp_ptr dap,
260 mp_ptr dbp,
261 mp_size_t* blen,
262 mp_srcptr ha,
263 mp_srcptr hb,
264 mp_size_t hn0,
265 mp_srcptr ap,
266 mp_srcptr bp,
267 mp_size_t n,
268 mp_size_t p,
270
271/**
272 * @brief 计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)
273 * @param n 输入长度
274 * @warning n>0
275 */
277
278/**
279 * @brief 导出另一侧系数:tv = (g - S·X)/Y(S 为 X 侧系数,恒等式保证整除)
280 * @param dst 输出(容量 >= xn+2)
281 * @param tneg 出参,tv 的符号
282 * @param gp g(归一化)
283 * @param gn g 的长度
284 * @param sp S 的幅度(归一化)
285 * @param sn S 的幅度长
286 * @param sneg S 的符号
287 * @param xp 值序大者原对(归一化)
288 * @param xn 其长度
289 * @param yp 值序小者原对(归一化)
290 * @param yn 其长度
291 * @param nb 全乘积暂存(容量 >= xn+yn+2)
292 * @param yt Y 奇化暂存(容量 >= yn+1)
293 * @param qt 整商暂存(容量 >= xn+2;lmmp_divexact_ 写入长 nn-yn2+1 可超
294 * 出 dst 公开容量,先落此处再按归一化长度拷出)
295 * @return tv 写入长度(tv==0 理论不可达时返回 0)
296 * @warning sep([dst|nb|yt|qt],[gp|sp|xp|yp]),gn>0,sn<=xn
297 * @note S==0 时 Y|X 且 g==Y,tv=1。Y 偶时剥公因子 2^k 后走 lmmp_divexact_
298 * (要求奇除数;N = tv*Y 保证 N 的低 k 位为零)。S 与 tv 反号(极小
299 * 系数性质,|S|*X >= X >= g 使 g 落在 0 与 |S|*X 之间)
300 */
302 mp_size_t sn, int sneg, mp_srcptr xp, mp_size_t xn, mp_srcptr yp,
303 mp_size_t yn, mp_ptr nb, mp_ptr yt, mp_ptr qt);
304
305/**
306 * @brief 发射:g 与 S(值序大者系数)按 sw 映射到 (dsts,dstt),另一系数经恒等式导出
307 * @param dstg 结果 g 输出(容量 >= gn)
308 * @param dsts u 侧系数输出(容量 >= max(un,vn)+1)
309 * @param sn 输出 s 的带符号长度
310 * @param dstt v 侧系数输出(容量 >= max(un,vn)+1,可为 NULL 表示不需要)
311 * @param tn 输出 t 的带符号长度(dstt==NULL 时忽略,可为 NULL)
312 * @param gp g(归一化)
313 * @param gn g 的长度
314 * @param sp S 的幅度(归一化)
315 * @param sun S 的幅度长
316 * @param suneg S 的符号
317 * @param sw 值序归一化的交换标志(1 表示 up/vp 已交换,S 为 vp 侧系数)
318 * @param up 值序大者原对
319 * @param un 其长度
320 * @param vp 值序小者原对
321 * @param vn 其长度
322 * @param nb 导出全乘积暂存(容量 >= 2*max(un,vn)+4)
323 * @param yt 导出奇化暂存(容量 >= max(un,vn)+2)
324 * @param qt 导出整商暂存(容量 >= max(un,vn)+2)
325 * @warning sep([dsts|dstt],dstg),对 up/vp 的全部读取(导出)先于输出写入
326 */
327void lmmp_gcdext_emit_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t* sn, mp_ptr dstt, mp_ssize_t* tn,
328 mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sun, int suneg, int sw,
329 mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn, mp_ptr nb, mp_ptr yt,
330 mp_ptr qt);
331
332#endif /* __LMMP_IMPL_GCD_H__ */
#define xn
mp_size_t lmmp_hgcd_scratch_size_(mp_size_t n)
计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)
定义 hgcd.c:162
#define B
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
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 实现注)
#define GCD_LEHMER_EXACT_BITS
定义 gcd.h:101
#define GCD_LEHMER_MIN_V
定义 gcd.h:100
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 A
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 侧系数,恒等式保证整除)
#define C
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
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_gcd_matrix_init_buf_(lmmp_hgcd_matrix_t *M, mp_ptr buf, mp_size_t alloc)
定义 gcd.h:77
static void lmmp_gcd_matrix_swap_cols_(lmmp_hgcd_matrix_t *M)
定义 gcd.h:70
#define D
#define an
#define bn
#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
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 LIMB_BITS
定义 lmmp.h:102
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]
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]
#define xp
#define t
#define n
mp_size_t n[2][2]
int64_t slong
定义 numth.h:41
hgcd 变换矩阵
#define M1
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)