LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
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
*/
32
static
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
36
static
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
48
static
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
60
mp_size_t
lmmp_gcd_22_
(
mp_ptr
dst,
mp_srcptr
up,
mp_srcptr
vp) {
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
149
mp_size_t
lmmp_gcd_2_
(
mp_ptr
dst,
mp_srcptr
up,
mp_size_t
un,
mp_srcptr
vp) {
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
}
k
#define k
ctz_u128
static int ctz_u128(mp_limb_t lo, mp_limb_t hi)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
gcd_2.c:32
lshr_u128
static void lshr_u128(mp_limb_t *lo, mp_limb_t *hi, int k)
定义
gcd_2.c:36
lshl_u128
static void lshl_u128(mp_limb_t *lo, mp_limb_t *hi, int k)
定义
gcd_2.c:48
inlines.h
lmmp_tailing_zeros_
#define lmmp_tailing_zeros_
定义
inlines.h:163
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
lmmpn.h
lmmp_mod_2_
void lmmp_mod_2_(mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数取余 (除数为2个limb)
定义
div.c:215
v0
#define v0
v1
#define v1
t
#define t
w0
#define w0
lo
#define lo
numth.h
lmmp_gcd_2_
mp_size_t lmmp_gcd_2_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp)
计算两个无符号整数的最大公约数
定义
gcd_2.c:149
lmmp_gcd_11_
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
定义
gcd_1.c:28
lmmp_gcd_22_
mp_size_t lmmp_gcd_22_(mp_ptr dst, mp_srcptr up, mp_srcptr vp)
计算两个无符号整数的最大公约数
定义
gcd_2.c:60
src
lmmp
numth
gcd_2.c
生成于
, 为 LMMP使用
1.18.0