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

浏览该文件的源代码.

函数

mp_limb_t lmmp_gcd_11_ (mp_limb_t u, mp_limb_t v)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_gcd_1_ (mp_srcptr up, mp_size_t un, mp_limb_t v)
 计算两个无符号整数的最大公约数

函数说明

◆ lmmp_gcd_11_()

mp_limb_t lmmp_gcd_11_ ( mp_limb_t u,
mp_limb_t v )

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)

参数
u第一个无符号整数
v第二个无符号整数
返回
最大公约数
警告
u!=0, v!=0

在文件 gcd_1.c 第 28 行定义.

28 {
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}
#define k
#define lmmp_tailing_zeros_
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define t
int64_t slong
定义 numth.h:41

引用了 k, lmmp_gcd_11_(), lmmp_param_assert, lmmp_tailing_zeros_ , 以及 t.

被这些函数引用 lmmp_divexact_(), lmmp_gcd_(), lmmp_gcd_11_(), lmmp_gcd_1_(), lmmp_gcd_22_(), lmmp_gcd_lehmer_() , 以及 TEST_CASE().

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

◆ lmmp_gcd_1_()

mp_limb_t lmmp_gcd_1_ ( mp_srcptr up,
mp_size_t un,
mp_limb_t v )

计算两个无符号整数的最大公约数

参数
up第一个无符号整数指针
un第一个无符号整数的 limb 长度
v第二个无符号整数
警告
v!=0, up!=NULL, un>0
返回
最大公约数

在文件 gcd_1.c 第 46 行定义.

46 {
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}
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:28

引用了 lmmp_gcd_11_(), lmmp_gcd_1_(), lmmp_mod_1_() , 以及 lmmp_param_assert.

被这些函数引用 lmmp_divexact_(), lmmp_gcd_(), lmmp_gcd_1_(), lmmp_gcd_lehmer_(), TEST_CASE() , 以及 TEST_CASE().

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