LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
gcd.c 文件参考
#include "mparam.h"
#include "lmmp/numth.h"
gcd.c 的引用(Include)关系图:

浏览该文件的源代码.

函数

mp_size_t lmmp_gcd_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数说明

◆ lmmp_gcd_()

mp_size_t lmmp_gcd_ ( mp_ptr dst,
mp_srcptr up,
mp_size_t un,
mp_srcptr vp,
mp_size_t vn )

Copyright (C) 2026 HJimmyK (Jericho Knox)

计算两个无符号整数的最大公约数(通用分发入口)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst结果指针(长度至少为 min(un,vn))
up第一个无符号整数指针
un第一个无符号整数的 limb 长度
vp第二个无符号整数指针
vn第二个无符号整数的 limb 长度
警告
up!=NULL, un>0, vp!=NULL, vn>0, eqsep(dst,[up|vp]), dst!=NULL, up[un-1]!=0, vp[vn-1]!=0
返回
dst 的实际 limb 长度

在文件 gcd.c 第 27 行定义.

27 {
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}
#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_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

引用了 GCD_HGCD_THRESHOLD, lmmp_gcd_(), lmmp_gcd_11_(), lmmp_gcd_1_(), lmmp_gcd_22_(), lmmp_gcd_2_(), lmmp_gcd_hgcd_(), lmmp_gcd_lehmer_(), lmmp_param_assert , 以及 LMMP_SWAP.

被这些函数引用 lmmp_gcd_(), small_factor_q(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图: