LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
gcd_1.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/numth.h
"
25
#include "
lmmp/lmmpn.h
"
26
27
28
mp_limb_t
lmmp_gcd_11_
(
mp_limb_t
u,
mp_limb_t
v) {
29
lmmp_param_assert
(u > 0 && v > 0);
30
int
k
=
lmmp_tailing_zeros_
(u | v);
// k = min(tz(u), tz(v))
31
u >>=
lmmp_tailing_zeros_
(u);
32
v >>=
lmmp_tailing_zeros_
(v);
33
// u, v 均为奇数;去冗余最低位(隐式最低位表示)
34
u >>= 1;
35
v >>= 1;
36
while
(u != v) {
37
mp_limb_t
t
= u - v;
38
mp_limb_t
m = (
mp_limb_t
)((
slong
)
t
>> 63);
// u<v -> 1
39
v += m &
t
;
// v = min(u, v)
40
u = (
t
^ m) - m;
// u = |u - v|
41
u = (u >> 1) >>
lmmp_tailing_zeros_
(
t
);
42
}
43
return
((u << 1) + 1) <<
k
;
44
}
45
46
mp_limb_t
lmmp_gcd_1_
(
mp_srcptr
up,
mp_size_t
un,
mp_limb_t
v) {
47
lmmp_param_assert
(un > 0);
48
lmmp_param_assert
(v > 0);
49
mp_limb_t
ulimb;
50
if
(un == 1) {
51
ulimb = up[0];
52
}
else
{
53
ulimb =
lmmp_mod_1_
(up, un, v);
54
}
55
if
(ulimb == 0)
56
return
v;
57
else
58
return
lmmp_gcd_11_
(ulimb, v);
59
}
k
#define k
inlines.h
lmmp_tailing_zeros_
#define lmmp_tailing_zeros_
定义
inlines.h:163
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_1_
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义
div.c:38
t
#define t
numth.h
slong
int64_t slong
定义
numth.h:41
lmmp_gcd_11_
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
定义
gcd_1.c:28
lmmp_gcd_1_
mp_limb_t lmmp_gcd_1_(mp_srcptr up, mp_size_t un, mp_limb_t v)
计算两个无符号整数的最大公约数
定义
gcd_1.c:46
src
lmmp
numth
gcd_1.c
生成于
, 为 LMMP使用
1.18.0