LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
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_limb_t * mp_ptr
定义 lmmp.h:96
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义 lmmp.h:458
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define GCD_HGCD_THRESHOLD
mp_size_t lmmp_gcd_lehmer_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(Lehmer算法)
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_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(通用分发入口)
定义 gcd.c:27
mp_size_t lmmp_gcd_hgcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
mp_limb_t lmmp_gcd_1_(mp_srcptr up, mp_size_t un, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:46
mp_size_t lmmp_gcd_22_(mp_ptr dst, mp_srcptr up, mp_srcptr vp)
计算两个无符号整数的最大公约数
定义 gcd_2.c:60