LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
gcd_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#include "lmmp/lmmpn.h"
24#include "lmmp/numth.h"
25#include "numth/gcd.h"
26#include "impl/tmp_alloc.h"
27
28/* 步进矩阵与窗口提取见 impl/gcd.h(与 gcdext_lehmer.c 共享) */
29
38
39/**
40 * @brief dst = |x - y|(大数减法取绝对值),返回归一化长度
41 * @warning eqsep(dst,[x|y])
42 */
44 mp_size_t rn;
45 if (xn > yn) {
46 lmmp_sub_(dst, x, xn, y, yn);
47 rn = xn;
48 } else if (xn < yn) {
49 lmmp_sub_(dst, y, yn, x, xn);
50 rn = yn;
51 } else {
52 int cmp = lmmp_cmp_(x, y, xn);
53 if (cmp >= 0) {
54 lmmp_sub_(dst, x, xn, y, yn);
55 } else {
56 lmmp_sub_(dst, y, yn, x, xn);
57 }
58 rn = xn;
59 }
60 while (rn > 0 && dst[rn - 1] == 0) {
61 --rn;
62 }
63 return rn;
64}
65
66/**
67 * @brief / a \ = / A B \ * / a \
68 * \ b / \ C D / \ b /
69 * @warning [a,an] > [b,bn]
70 * @note 不保证返回结果 [a,an] > [b,bn]
71 * @return a和b是否有一个为0;返回 true 时保证 [a,an] 非零(若 a 先归零
72 * 则将 b 移入 a,gcd 即 a)
73 */
75#define A (M->m11)
76#define B (M->m12)
77#define C (M->m21)
78#define D (M->m22)
79#define an (*an)
80#define bn (*bn)
81 if (A == 0) {
82 /* / 0 1 \ / a \ = / b \
83 \ 1 -q / \ b / \ a - q*b (new a) / */
84 lmmp_debug_assert(B == 1 && C == 1 && D < 0);
85 mp_limb_t c = lmmp_mul_1_(ms->tp, b, bn, -D);
86 mp_size_t tn = bn;
87 if (c != 0) {
88 ++tn;
89 (ms->tp)[tn - 1] = c;
90 }
91 // a = |a - q*b|, b = b
92 an = lmmp_lehmer_sub_mag_(a, a, an, ms->tp, tn);
93 if (an == 0) {
94 // a - q*b == 0:b | a,gcd = b,移入 a
95 lmmp_copy(a, b, bn);
96 an = bn;
97 b[0] = 0;
98 bn = 0;
99 }
100 return bn == 0;
101 } else {
102 if (A < 0) {
103 A = -A;
104 D = -D;
105 } else {
106 B = -B;
107 C = -C;
108 }
109 // ms->np = |A * a - (-B) * b|(B 取负后系数均为正,差的绝对值即线性组合)
110 mp_limb_t ca = lmmp_mul_1_(ms->tp, a, an, A);
111 ms->tn = an;
112 if (ca != 0)
113 (ms->tp)[ms->tn++] = ca;
114 ca = lmmp_mul_1_(ms->mp, b, bn, B);
115 ms->mn = bn;
116 if (ca != 0)
117 (ms->mp)[ms->mn++] = ca;
118 ms->nn = lmmp_lehmer_sub_mag_(ms->np, ms->tp, ms->tn, ms->mp, ms->mn);
119
120 // a = |C * a - (-D) * b|
121 ca = lmmp_mul_1_(ms->tp, a, an, C);
122 ms->tn = an;
123 if (ca != 0)
124 (ms->tp)[ms->tn++] = ca;
125 ca = lmmp_mul_1_(ms->mp, b, bn, D);
126 ms->mn = bn;
127 if (ca != 0)
128 (ms->mp)[ms->mn++] = ca;
129 an = lmmp_lehmer_sub_mag_(a, ms->tp, ms->tn, ms->mp, ms->mn);
130
131 // now a = C * a + D * b
132 // ms->np = A * a + B * b
133 if (an == 0) {
134 // a 归零:gcd = ms->np,移入 a
135 lmmp_copy(a, ms->np, ms->nn);
136 an = ms->nn;
137 b[0] = 0;
138 bn = 0;
139 return true;
140 }
141 if (ms->nn > 0) {
142 lmmp_copy(b, ms->np, ms->nn);
143 bn = ms->nn;
144 return false;
145 } else {
146 b[0] = 0;
147 bn = 0;
148 return true;
149 }
150 }
151#undef A
152#undef B
153#undef C
154#undef D
155#undef an
156#undef bn
157}
158
160 lmmp_param_assert(un > 0 && vn > 0);
161 lmmp_param_assert(up != NULL && vp != NULL);
162 lmmp_param_assert(dst != NULL);
163
164 lmmp_param_assert(up[un - 1] != 0);
165 lmmp_param_assert(vp[vn - 1] != 0);
166
167 if (un < vn) {
168 LMMP_SWAP(up, vp, mp_srcptr);
169 LMMP_SWAP(un, vn, mp_size_t);
170 } else if (un == vn) {
171 int cmp = lmmp_cmp_(up, vp, un);
172 if (cmp == 0) {
173 lmmp_copy(dst, up, un);
174 return un;
175 } else if (cmp < 0) {
176 LMMP_SWAP(up, vp, mp_srcptr);
177 }
178 }
179 // u > v
180
182 slong x = 0, y = 0;
183
184#define an un
185#define bn vn
187 // [a,an+1] [b,bn+1]
188 // A * a_old may overlow
189 mp_ptr a = BALLOC_TYPE(an + 1, mp_limb_t);
190 mp_ptr b = BALLOC_TYPE(bn + 1, mp_limb_t);
192 mp_ptr temp = BALLOC_TYPE((an + 1) * 3, mp_limb_t);
193 ms.tp = temp;
194 ms.mp = temp + (an + 1);
195 ms.np = temp + (an + 1) * 2;
196
197 lmmp_copy(a, up, an);
198 lmmp_copy(b, vp, bn);
199
200 bool bzero = false;
201 while (bzero == false) {
202 if (an > 1 && bn == 1) {
203 dst[0] = lmmp_gcd_1_(a, an, b[0]);
205 return 1;
206 } else if (an == 1 && bn == 1) {
207 dst[0] = lmmp_gcd_11_(a[0], b[0]);
209 return 1;
210 }
211 // a > b
212 lmmp_gcd_lehmer_extract_(a, an, b, bn, &x, &y);
213 lmmp_gcd_lehmer_step_(x, y, &M);
214
215 if (M.m21 == 0) {
216 lmmp_div_(NULL, dst, a, an, b, bn);
217 lmmp_copy(a, b, bn);
218 an = bn;
219 while (bn > 0 && dst[bn - 1] == 0) {
220 --bn;
221 }
222 if (bn == 0)
223 bzero = true;
224 else
225 lmmp_copy(b, dst, bn);
226 } else {
227 bzero = lmmp_lehmer_mul_(a, &an, b, &bn, &M, &ms);
228 if ((an < bn) || (an == bn && lmmp_cmp_(a, b, an) < 0)) {
229 LMMP_SWAP(a, b, mp_ptr);
231 }
232 }
233 }
234 lmmp_copy(dst, a, an);
236 return an;
237#undef an
238#undef bn
239}
#define xn
#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
#define A
#define C
#define D
static mp_size_t lmmp_lehmer_sub_mag_(mp_ptr dst, mp_srcptr x, mp_size_t xn, mp_srcptr y, mp_size_t yn)
dst = |x - y|(大数减法取绝对值),返回归一化长度
#define an
static bool lmmp_lehmer_mul_(mp_ptr a, mp_size_t *an, mp_ptr b, mp_size_t *bn, lmmp_gcd_lehmer_t *M, lehmer_stack_t *ms)
/ a \ = / A B \ * / a \ \ b / \ C D / \ b /
#define bn
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
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
#define lmmp_param_assert(x)
定义 lmmp.h:509
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_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_size_t lmmp_gcd_lehmer_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(Lehmer算法)
int64_t slong
定义 numth.h:41
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:28
mp_limb_t lmmp_gcd_1_(mp_srcptr up, mp_size_t un, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:46
#define TEMP_B_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_B_FREE