LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
gcd_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/inlines.h"
24#include "lmmp/lmmpn.h"
25#include "lmmp/numth.h"
26
27
28/**
29 * @brief 128 位尾零数
30 * @return if (lo != 0) return ctz(lo); else return 64 + ctz(hi);
31 */
32static inline int ctz_u128(mp_limb_t lo, mp_limb_t hi) {
33 return lo ? lmmp_tailing_zeros_(lo) : (64 + lmmp_tailing_zeros_(hi));
34}
35
36static inline void lshr_u128(mp_limb_t* lo, mp_limb_t* hi, int k) {
37 if (k == 0)
38 return;
39 if (k < 64) {
40 *lo = (*lo >> k) | (*hi << (64 - k));
41 *hi >>= k;
42 } else {
43 *lo = *hi >> (k - 64);
44 *hi = 0;
45 }
46}
47
48static inline void lshl_u128(mp_limb_t* lo, mp_limb_t* hi, int k) {
49 if (k == 0)
50 return;
51 if (k < 64) {
52 *hi = (*lo >> (64 - k)) | (*hi << k);
53 *lo <<= k;
54 } else {
55 *hi = *lo << (k - 64);
56 *lo = 0;
57 }
58}
59
61 lmmp_param_assert(dst != NULL);
62 lmmp_param_assert(up != NULL);
63 lmmp_param_assert(vp != NULL);
64 lmmp_param_assert(!(up[1] == 0 && up[0] == 0));
65 lmmp_param_assert(!(vp[1] == 0 && vp[0] == 0));
66 mp_limb_t u0 = up[0], u1 = up[1];
67 mp_limb_t v0 = vp[0], v1 = vp[1];
68
69 if ((u1 | v1) == 0) {
70 dst[0] = lmmp_gcd_11_(u0, v0);
71 dst[1] = 0;
72 return 1;
73 }
74
75 // cnt = min(tz(u), tz(v)) 为 gcd 中的 2 因子幂
76 int ku = ctz_u128(u0, u1);
77 int kv = ctz_u128(v0, v1);
78 int cnt = ku < kv ? ku : kv;
79 lshr_u128(&u0, &u1, ku);
80 lshr_u128(&v0, &v1, kv);
81 // u, v 均为奇数;去冗余最低位(隐式最低位表示),腾出符号位
82 u0 = (u0 >> 1) | (u1 << 63);
83 u1 >>= 1;
84 v0 = (v0 >> 1) | (v1 << 63);
85 v1 >>= 1;
86
87 while (u1 | v1) { // 至少一方仍为双 limb
88 mp_limb_t t0 = u0 - v0;
89 mp_limb_t t1 = u1 - v1 - (u0 < v0);
90 mp_limb_t m = -(mp_limb_t)(t1 >> 63); // u<v -> 1
91 if (t0 == 0) {
92 if (t1 == 0)
93 break;
94
95 v1 += m & t1; // v1 = min(u1, v1)(v0 == u0,无需更新)
96 u0 = (t1 ^ m) - m; // |u1 - v1|
97 u0 >>= lmmp_tailing_zeros_(t1) + 1;
98 u1 = 0;
99 } else {
100 int c = lmmp_tailing_zeros_(t0) + 1;
101 // v = min(u, v)(128 位加法 v += m & t)
102 mp_limb_t w0 = m & t0;
103 mp_limb_t w1 = m & t1;
104 v0 += w0;
105 v1 += w1 + (v0 < w0);
106
107 u0 = (t0 ^ m) - m;
108 u1 = t1 ^ m;
109 if (c == 64) {
110 u0 = u1;
111 u1 = 0;
112 } else {
113 u0 = (u0 >> c) | (u1 << (64 - c));
114 u1 >>= c;
115 }
116 }
117 }
118
119 mp_limb_t g0, g1; // 奇数 gcd
120 if (u1 | v1) {
121 g0 = (u0 << 1) | 1;
122 g1 = (u1 << 1) | (u0 >> 63);
123 } else {
124 while ((u0 | v0) >> 63) { // 任一 >= 2^63 则真值 >= 2^64,至多两次迭代
125 mp_limb_t t = u0 - v0;
126 if (t == 0)
127 break; // u == v
128 mp_limb_t m = -(mp_limb_t)(u0 < v0); // 符号掩码
129 v0 += m & t; // v = min(u0, v0)
130 u0 = (t ^ m) - m; // |u0 - v0|
131 u0 = (u0 >> 1) >> lmmp_tailing_zeros_(t);
132 }
133 if (u0 == v0) {
134 g0 = (u0 << 1) | 1;
135 g1 = u0 >> 63;
136 } else {
137 g0 = lmmp_gcd_11_((u0 << 1) + 1, (v0 << 1) + 1);
138 g1 = 0;
139 }
140 }
141
142 dst[0] = g0;
143 dst[1] = g1;
144 if (cnt > 0)
145 lshl_u128(&dst[0], &dst[1], cnt);
146 return dst[1] == 0 ? 1 : 2;
147}
148
150 lmmp_param_assert(dst != NULL);
151 lmmp_param_assert(up != NULL);
152 lmmp_param_assert(vp != NULL);
153 lmmp_param_assert(un > 2);
154 lmmp_param_assert(vp[1] != 0);
155 mp_limb_t u[2] = {vp[0], vp[1]};
156 lmmp_mod_2_(up, un, u);
157 if (u[1] == 0 && u[0] == 0) {
158 dst[0] = vp[0];
159 dst[1] = vp[1];
160 return 2;
161 } else {
162 return lmmp_gcd_22_(dst, vp, u);
163 }
164}
#define k
static int ctz_u128(mp_limb_t lo, mp_limb_t hi)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 gcd_2.c:32
static void lshr_u128(mp_limb_t *lo, mp_limb_t *hi, int k)
定义 gcd_2.c:36
static void lshl_u128(mp_limb_t *lo, mp_limb_t *hi, int k)
定义 gcd_2.c:48
#define lmmp_tailing_zeros_
mp_limb_t * mp_ptr
定义 lmmp.h:96
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
void lmmp_mod_2_(mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数取余 (除数为2个limb)
定义 div.c:215
#define v0
#define v1
#define t
#define w0
#define lo
mp_size_t lmmp_gcd_2_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp)
计算两个无符号整数的最大公约数
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:28
mp_size_t lmmp_gcd_22_(mp_ptr dst, mp_srcptr up, mp_srcptr vp)
计算两个无符号整数的最大公约数
定义 gcd_2.c:60