LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
gcd.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 "mparam.h"
24
#include "
lmmp/numth.h
"
25
26
27
mp_size_t
lmmp_gcd_
(
mp_ptr
dst,
mp_srcptr
up,
mp_size_t
un,
mp_srcptr
vp,
mp_size_t
vn) {
28
lmmp_param_assert
(un > 0 && vn > 0);
29
lmmp_param_assert
(up != NULL && vp != NULL && dst != NULL);
30
lmmp_param_assert
(up[un - 1] != 0);
31
lmmp_param_assert
(vp[vn - 1] != 0);
32
33
if
(un < vn) {
34
LMMP_SWAP
(up, vp,
mp_srcptr
);
35
LMMP_SWAP
(un, vn,
mp_size_t
);
36
}
37
// u >= v
38
39
if
(vn == 1) {
40
dst[0] = (un == 1) ?
lmmp_gcd_11_
(up[0], vp[0]) :
lmmp_gcd_1_
(up, un, vp[0]);
41
return
1;
42
}
43
if
(vn == 2) {
44
return
(un == 2) ?
lmmp_gcd_22_
(dst, up, vp) :
lmmp_gcd_2_
(dst, up, un, vp);
45
}
46
if
(un >=
GCD_HGCD_THRESHOLD
) {
47
return
lmmp_gcd_hgcd_
(dst, up, un, vp, vn);
48
}
49
return
lmmp_gcd_lehmer_
(dst, up, un, vp, vn);
50
}
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
LMMP_SWAP
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义
lmmp.h:458
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
GCD_HGCD_THRESHOLD
#define GCD_HGCD_THRESHOLD
定义
mparam.h:73
numth.h
lmmp_gcd_lehmer_
mp_size_t lmmp_gcd_lehmer_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(Lehmer算法)
定义
gcd_lehmer.c:159
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_
mp_size_t lmmp_gcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(通用分发入口)
定义
gcd.c:27
lmmp_gcd_hgcd_
mp_size_t lmmp_gcd_hgcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
定义
hgcd.c:1217
lmmp_gcd_1_
mp_limb_t lmmp_gcd_1_(mp_srcptr up, mp_size_t un, mp_limb_t v)
计算两个无符号整数的最大公约数
定义
gcd_1.c:46
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.c
生成于
, 为 LMMP使用
1.18.0