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

浏览该文件的源代码.

函数

ulong lmmp_gcdext_11_ (ulong u, ulong v, slong *s, slong *t)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
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

函数说明

◆ lmmp_gcdext_11_()

ulong lmmp_gcdext_11_ ( ulong u,
ulong v,
slong * s,
slong * t )

Copyright (C) 2026 HJimmyK (Jericho Knox)

扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g

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

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
u第一个无符号整数
v第二个无符号整数
s输出 u 的贝祖系数(带符号)
t输出 v 的贝祖系数(带符号,可为 NULL 表示不需要)
警告
u!=0, v!=0, s!=NULL
返回
最大公约数 g
注解
取极小系数:|s| <= v/(2g)、|t| <= u/(2g)(由此唯一)。v|u 时 s=0、t=1

在文件 gcdext_1.c 第 48 行定义.

48 {
49 lmmp_param_assert(u > 0 && v > 0);
50 lmmp_param_assert(s != NULL);
51
52 int sw = 0;
53 if (u < v) {
54 LMMP_SWAP(u, v, ulong);
55 sw = 1;
56 }
57 // u >= v
58
59 ulong r1 = u % v;
60 if (r1 == 0) {
61 // v | u:g = v,系数在较小者
62 *s = sw ? 1 : 0;
63 if (t != NULL)
64 *t = sw ? 0 : 1;
65 return v;
66 }
67
68 ulong r0 = v;
69 ulong su0 = 0, su1 = 1; // u 系数幅度(符号交替,su1 当前为正)
70 ulong tv0 = 1, tv1 = u / v; // v 系数幅度(与 su 相位相反)
71 int phase = 1; // su1 的符号 [+1|-1]
72 for (;;) {
73 ulong q = r0 / r1;
74 ulong r2 = r0 % r1;
75 if (r2 == 0)
76 break; // g = r1,系数即 (su1, tv1) 当前行
77 ulong su2 = q * su1 + su0;
78 ulong tv2 = q * tv1 + tv0;
79 r0 = r1;
80 r1 = r2;
81 su0 = su1;
82 su1 = su2;
83 tv0 = tv1;
84 tv1 = tv2;
85 phase = -phase;
86 }
87 slong gu = phase > 0 ? (slong)su1 : -(slong)su1;
88 slong gv = phase > 0 ? -(slong)tv1 : (slong)tv1;
89 *s = sw ? gv : gu;
90 if (t != NULL)
91 *t = sw ? gu : gv;
92 return r1;
93}
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义 lmmp.h:458
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define r2
#define r1
#define r0
#define t
#define s
int64_t slong
定义 numth.h:41
uint64_t ulong
定义 numth.h:39

引用了 lmmp_gcdext_11_(), lmmp_param_assert, LMMP_SWAP, r0, r1, r2, s , 以及 t.

被这些函数引用 lmmp_gcdext_11_(), lmmp_gcdext_1_(), lmmp_modinv_ulong_() , 以及 TEST_CASE().

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

◆ lmmp_gcdext_1_()

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

参数
dstg结果指针(长度为 1 个limb)
dstsu 的贝祖系数幅度(长度为 1 个limb,s==0 时写 0)
sn输出 s 的带符号 limb 长度([1|-1|0])
dsttv 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL 表示不需要)
tn输出 t 的带符号 limb 长度(dstt==NULL 时忽略,可为 NULL)
up第一个无符号整数指针
un第一个无符号整数的 limb 长度
v第二个无符号整数(单 limb)
警告
up!=NULL, un>0, v!=0, dstg!=NULL, dsts!=NULL, sn!=NULL, sep([dsts|dstt],dstg)
返回
g 的 limb 长度(恒 1)
注解
取极小系数 |s| <= v/(2g)(单 limb)、|t| <= u/(2g)。v|[up,un] 时 s=0、t=1。 dstg 允许与 up 别名(eqsep);dsts/dstt 在 up 的所有读取完成后才写入

在文件 gcdext_1.c 第 95 行定义.

96 {
97 lmmp_param_assert(un > 0 && v > 0);
98 lmmp_param_assert(up != NULL && dstg != NULL && dsts != NULL && sn != NULL);
99
100 ulong r = lmmp_mod_1_(up, un, v);
101 if (r == 0) {
102 dstg[0] = v;
103 dsts[0] = 0;
104 *sn = 0;
105 if (dstt != NULL) {
106 dstt[0] = 1;
107 *tn = 1;
108 }
109 return 1;
110 }
111
112 slong sg;
113 ulong g = lmmp_gcdext_11_(r, v, &sg, NULL);
114 lmmp_debug_assert(sg != 0); // r>0 且 v∤r → g<v → σ≠0
115
116 if (dstt == NULL) {
117 dstg[0] = g;
118 dsts[0] = sg < 0 ? (ulong)-sg : (ulong)sg;
119 *sn = sg < 0 ? -1 : 1; /* 带符号长度(sg!=0 已断言) */
120 return 1;
121 }
122
123 /* t = (g - sg*u)/v:X = |sg|*u;N = g - sg*u(符号-幅度,X >= u >= g
124 保证 sg>0 时差非负方向确定);|t| = N/v。对 up 的读取(X)先于全部
125 输出写入(允许 dstg/dsts/dstt 与 up 别名的契约次序) */
127 mp_ptr x = BALLOC_TYPE(un + 2, mp_limb_t);
128 mp_ptr nb = BALLOC_TYPE(un + 2, mp_limb_t);
129 mp_ptr tq = BALLOC_TYPE(un + 2, mp_limb_t);
130 ulong sm = sg < 0 ? (ulong)-sg : (ulong)sg;
131 mp_limb_t c = lmmp_mul_1_(x, up, un, sm);
132 mp_size_t xn = un;
133 if (c != 0)
134 x[xn++] = c;
135 mp_size_t nn;
136 int tneg = 0;
137 if (sg > 0) {
138 // N = g - X = -(X - g),X >= g(|sg|>=1 且 g|u)
139 lmmp_sub_(nb, x, xn, &g, 1);
140 nn = xn;
141 while (nn > 0 && nb[nn - 1] == 0)
142 --nn;
143 tneg = nn != 0;
144 } else {
145 // N = g + X > 0
146 mp_limb_t cy = lmmp_add_(nb, x, xn, &g, 1);
147 nn = xn;
148 if (cy != 0)
149 nb[nn++] = cy;
150 }
151 // |t| = N/v(恒等式保证整除;N==0 即 t==0 时跳过除法)
152 mp_size_t tqn = 0;
153 if (nn != 0) {
154 mp_limb_t vv[1] = {v};
155 lmmp_div_(tq, NULL, nb, nn, vv, 1);
156 tqn = nn;
157 while (tqn > 0 && tq[tqn - 1] == 0)
158 --tqn;
159 }
160
161 dstg[0] = g;
162 dsts[0] = sm;
163 *sn = sg < 0 ? -1 : 1;
164 lmmp_copy(dstt, tq, tqn);
165 if (tqn == 0)
166 dstt[0] = 0;
167 *tn = tneg ? -(mp_ssize_t)tqn : (mp_ssize_t)tqn;
169 return 1;
170}
#define xn
mp_limb_t * mp_ptr
定义 lmmp.h:96
#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
int64_t mp_ssize_t
定义 lmmp.h:95
uint64_t mp_limb_t
定义 lmmp.h:92
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]
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
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
ulong lmmp_gcdext_11_(ulong u, ulong v, slong *s, slong *t)
扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g
#define TEMP_B_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_B_FREE

引用了 BALLOC_TYPE, lmmp_add_(), lmmp_copy, lmmp_debug_assert, lmmp_div_(), lmmp_gcdext_11_(), lmmp_gcdext_1_(), lmmp_mod_1_(), lmmp_mul_1_(), lmmp_param_assert, lmmp_sub_(), TEMP_B_DECL, TEMP_B_FREE , 以及 xn.

被这些函数引用 lmmp_gcdext_(), lmmp_gcdext_1_(), lmmp_gcdext_lehmer_() , 以及 TEST_CASE().

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