LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
gcdext_2.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 "impl/tmp_alloc.h"
24#include "lmmp/lmmpn.h"
25#include "lmmp/numth.h"
26
27/*
28扩展欧几里得(n limb x 2 limb 层)。
29
30经 lmmp_mod_2_ 归约至 r = u mod v 后转 lmmp_gcdext_lehmer_ 求 g 与 s。
31s 对 (u, v) 直接有效(s*u = s*r (mod v),极小界 |s| <= v/(2g) 不变),但
32归约对的 t' 不适用于原对(差 s*(u-r)/v)——t 须按恒等式导出:
33
34 t = (g - s*u) / v
35
36经一次乘法(|s| x un)、一次符号-幅度加减与一次 2 limb 除法精确得到
37(整除性由恒等式保证;|t| <= u/(2g) <= un 个limb)。
38*/
39
41 mp_srcptr up, mp_size_t un, mp_srcptr vp) {
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
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 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_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)
扩展欧几里得(任意长度对双 limb):g = gcd([up,un],[vp,2]),s*u + t*v = g
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