LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
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
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}
#define k
#define lmmp_tailing_zeros_
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
#define t
int64_t slong
定义 numth.h:41
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:28
mp_limb_t lmmp_gcd_1_(mp_srcptr up, mp_size_t un, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:46