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

浏览该文件的源代码.

函数

mp_size_t lmmp_gcdext_2_ (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)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数说明

◆ lmmp_gcdext_2_()

mp_size_t lmmp_gcdext_2_ ( 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 )

Copyright (C) 2026 HJimmyK (Jericho Knox)

扩展欧几里得(任意长度对双 limb):g = gcd([up,un],[vp,2]),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)

参数
dstg结果指针(长度至少为 2 个limb)
dstsu 的贝祖系数幅度(长度至少为 2 个limb,s==0 时写 0)
sn输出 s 的带符号 limb 长度
dsttv 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL)
tn输出 t 的带符号 limb 长度(dstt==NULL 时忽略)
up第一个无符号整数指针
un第一个无符号整数的 limb 长度
vp第二个无符号整数指针(长度为 2)
警告
up!=NULL, un>2, vp!=NULL, vp[1]!=0, dstg!=NULL, dsts!=NULL, sn!=NULL, sep([dsts|dstt],dstg)
返回
g 的实际 limb 长度
注解
取极小系数(同 lmmp_gcdext_11_ 注)。经 lmmp_mod_2_ 预归约后转 lmmp_gcdext_lehmer_(无独立 2x2 核)。dstg 允许与 [up|vp] 别名

在文件 gcdext_2.c 第 40 行定义.

41 {
42 lmmp_param_assert(un > 2);
43 lmmp_param_assert(up != NULL && vp != NULL && dstg != NULL && dsts != NULL && sn != NULL);
44 lmmp_param_assert(vp[1] != 0);
45
46 mp_limb_t r[2] = {vp[0], vp[1]};
47 lmmp_mod_2_(up, un, r);
48 if (r[0] == 0 && r[1] == 0) {
49 // v | u:g = v,s = 0、t = 1
50 lmmp_copy(dstg, vp, 2);
51 dsts[0] = 0;
52 *sn = 0;
53 if (dstt != NULL) {
54 dstt[0] = 1;
55 *tn = 1;
56 }
57 return 2;
58 }
59 mp_size_t rn = (r[1] != 0) ? 2 : 1;
60
61 if (dstt == NULL)
62 return lmmp_gcdext_lehmer_(dstg, dsts, sn, NULL, NULL, r, rn, vp, 2);
63
67 mp_ptr x = BALLOC_TYPE(un + 2, mp_limb_t);
68 mp_ptr nb = BALLOC_TYPE(un + 2, mp_limb_t);
69 mp_ptr tq = BALLOC_TYPE(un + 2, mp_limb_t);
70 mp_ssize_t snn;
71 mp_size_t gn = lmmp_gcdext_lehmer_(gb, sb, &snn, NULL, NULL, r, rn, vp, 2);
72 mp_size_t snabs = snn < 0 ? -snn : snn;
73 lmmp_debug_assert(snabs > 0 && snabs <= 2); // r>0 且 v∤r → s≠0,|s| <= v/(2g) <= 2 limb
74
75 /* t = (g - s*u)/v:X = |s|*u;s>0 时 N = -(X-g)(X >= u > g),s<0 时 N = X+g */
76 if (snabs >= un)
77 lmmp_mul_(x, sb, snabs, up, un);
78 else
79 lmmp_mul_(x, up, un, sb, snabs);
80 mp_size_t xn = snabs + un;
81 while (xn > 0 && x[xn - 1] == 0)
82 --xn;
83 mp_size_t nn;
84 int tneg = 0;
85 if (snn > 0) {
86 lmmp_sub_(nb, x, xn, gb, gn);
87 nn = xn;
88 while (nn > 0 && nb[nn - 1] == 0)
89 --nn;
90 tneg = nn != 0;
91 } else {
92 mp_limb_t cy = lmmp_add_(nb, x, xn, gb, gn);
93 nn = xn;
94 if (cy != 0)
95 nb[nn++] = cy;
96 }
97 mp_size_t tqn = 0;
98 if (nn != 0) {
99 lmmp_div_(tq, NULL, nb, nn, vp, 2);
100 /* 商至多 nn-2+1 个limb(div 契约),高位未写区域不可读 */
101 tqn = nn - 1;
102 while (tqn > 0 && tq[tqn - 1] == 0)
103 --tqn;
104 }
105
106 lmmp_copy(dstg, gb, gn);
107 lmmp_copy(dsts, sb, snabs);
108 *sn = snn;
109 lmmp_copy(dstt, tq, tqn);
110 if (tqn == 0)
111 dstt[0] = 0;
112 *tn = tneg ? -(mp_ssize_t)tqn : (mp_ssize_t)tqn;
114 return gn;
115}
#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
#define lmmp_param_assert(x)
定义 lmmp.h:509
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_mod_2_(mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数取余 (除数为2个limb)
定义 div.c:215
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]
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]
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_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

引用了 BALLOC_TYPE, lmmp_add_(), lmmp_copy, lmmp_debug_assert, lmmp_div_(), lmmp_gcdext_2_(), lmmp_gcdext_lehmer_(), lmmp_mod_2_(), lmmp_mul_(), lmmp_param_assert, lmmp_sub_(), TEMP_B_DECL, TEMP_B_FREE , 以及 xn.

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

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