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

浏览该文件的源代码.

结构体

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

宏定义

#define A   (M->m11)
#define an   un
#define an   (*an)
#define B   (M->m12)
#define bn   vn
#define bn   (*bn)
#define C   (M->m21)
#define D   (M->m22)

函数

mp_size_t lmmp_gcd_lehmer_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
 计算两个无符号整数的最大公约数(Lehmer算法)
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 /
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|(大数减法取绝对值),返回归一化长度

结构体说明

◆ lehmer_stack_t

struct lehmer_stack_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

在文件 gcd_lehmer.c 第 30 行定义.

lehmer_stack_t 的协作图:
成员变量
mp_size_t mn
mp_ptr mp
mp_size_t nn
mp_ptr np
mp_size_t tn
mp_ptr tp

宏定义说明

◆ A

#define A   (M->m11)

◆ an [1/2]

#define an   un

◆ an [2/2]

◆ B

#define B   (M->m12)

◆ bn [1/2]

#define bn   vn

◆ bn [2/2]

◆ C

#define C   (M->m21)

◆ D

#define D   (M->m22)

函数说明

◆ lmmp_gcd_lehmer_()

mp_size_t lmmp_gcd_lehmer_ ( mp_ptr dst,
mp_srcptr up,
mp_size_t un,
mp_srcptr vp,
mp_size_t vn )

计算两个无符号整数的最大公约数(Lehmer算法)

参数
dst结果指针(长度至少为 min(un,vn))
up第一个无符号整数指针
un第一个无符号整数的 limb 长度
vp第二个无符号整数指针
vn第二个无符号整数的 limb 长度
警告
up!=NULL, un>0, vp!=NULL, vn>0, eqsep(dst,[up|vp]), dst!=NULL, up[un-1]!=0, vp[vn-1]!=0
返回
dst 的实际 limb 长度

在文件 gcd_lehmer.c 第 159 行定义.

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

引用了 an, BALLOC_TYPE, bn, lmmp_cmp_(), lmmp_copy, lmmp_div_(), lmmp_gcd_11_(), lmmp_gcd_1_(), lmmp_gcd_lehmer_(), lmmp_gcd_lehmer_extract_(), lmmp_gcd_lehmer_step_(), lmmp_lehmer_mul_(), lmmp_param_assert, LMMP_SWAP, lmmp_gcd_lehmer_t::m21, lehmer_stack_t::mp, lehmer_stack_t::np, TEMP_B_DECL, TEMP_B_FREE , 以及 lehmer_stack_t::tp.

被这些函数引用 bench_gcd_lehmer(), lmmp_divexact_(), lmmp_gcd_(), lmmp_gcd_hgcd_(), lmmp_gcd_lehmer_(), run_gcdext_pair(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

◆ lmmp_lehmer_mul_()

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 )
static

/ a \ = / A B \ * / a \ \ b / \ C D / \ b /

警告
[a,an] > [b,bn]
注解
不保证返回结果 [a,an] > [b,bn]
返回
a和b是否有一个为0;返回 true 时保证 [a,an] 非零(若 a 先归零 则将 b 移入 a,gcd 即 a)

在文件 gcd_lehmer.c 第 74 行定义.

74 {
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}
#define B
#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 lmmp_debug_assert(x)
定义 lmmp.h:498
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

引用了 A, an, B, bn, C, D, lmmp_copy, lmmp_debug_assert, lmmp_lehmer_mul_(), lmmp_lehmer_sub_mag_(), lmmp_mul_1_(), lehmer_stack_t::mn, lehmer_stack_t::mp, lehmer_stack_t::nn, lehmer_stack_t::np, lehmer_stack_t::tn , 以及 lehmer_stack_t::tp.

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

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

◆ lmmp_lehmer_sub_mag_()

mp_size_t lmmp_lehmer_sub_mag_ ( mp_ptr dst,
mp_srcptr x,
mp_size_t xn,
mp_srcptr y,
mp_size_t yn )
static

dst = |x - y|(大数减法取绝对值),返回归一化长度

警告
eqsep(dst,[x|y])

在文件 gcd_lehmer.c 第 43 行定义.

43 {
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}
#define xn
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]

引用了 lmmp_cmp_(), lmmp_lehmer_sub_mag_(), lmmp_sub_() , 以及 xn.

被这些函数引用 lmmp_lehmer_mul_() , 以及 lmmp_lehmer_sub_mag_().

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