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

浏览该文件的源代码.

函数

static int ctz_u128 (mp_limb_t lo, mp_limb_t hi)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_size_t lmmp_gcd_22_ (mp_ptr dst, mp_srcptr up, mp_srcptr vp)
 计算两个无符号整数的最大公约数
mp_size_t lmmp_gcd_2_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp)
 计算两个无符号整数的最大公约数
static void lshl_u128 (mp_limb_t *lo, mp_limb_t *hi, int k)
static void lshr_u128 (mp_limb_t *lo, mp_limb_t *hi, int k)

函数说明

◆ ctz_u128()

int ctz_u128 ( mp_limb_t lo,
mp_limb_t hi )
inlinestatic

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

128 位尾零数

返回
if (lo != 0) return ctz(lo); else return 64 + ctz(hi);

在文件 gcd_2.c 第 32 行定义.

32 {
33 return lo ? lmmp_tailing_zeros_(lo) : (64 + lmmp_tailing_zeros_(hi));
34}
#define lmmp_tailing_zeros_
#define lo

引用了 ctz_u128(), lmmp_tailing_zeros_ , 以及 lo.

被这些函数引用 ctz_u128() , 以及 lmmp_gcd_22_().

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

◆ lmmp_gcd_22_()

mp_size_t lmmp_gcd_22_ ( mp_ptr dst,
mp_srcptr up,
mp_srcptr vp )

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

参数
up第一个无符号整数指针,长度为 2
vp第二个无符号整数指针,长度为 2
dst结果指针(长度为 2,两个 limb 都会进行写入,即使最高位可能为0)
警告
up!=NULL, vp!=NULL, [up,2]!=0, [vp,2]!=0, dst!=NULL, eqsep(dst,[up|vp])
注解
up 和 vp 的高位允许为 0,但要求任一个数的高低位不能全为 0
返回
dst 的实际 limb 长度

在文件 gcd_2.c 第 60 行定义.

60 {
61 lmmp_param_assert(dst != NULL);
62 lmmp_param_assert(up != NULL);
63 lmmp_param_assert(vp != NULL);
64 lmmp_param_assert(!(up[1] == 0 && up[0] == 0));
65 lmmp_param_assert(!(vp[1] == 0 && vp[0] == 0));
66 mp_limb_t u0 = up[0], u1 = up[1];
67 mp_limb_t v0 = vp[0], v1 = vp[1];
68
69 if ((u1 | v1) == 0) {
70 dst[0] = lmmp_gcd_11_(u0, v0);
71 dst[1] = 0;
72 return 1;
73 }
74
75 // cnt = min(tz(u), tz(v)) 为 gcd 中的 2 因子幂
76 int ku = ctz_u128(u0, u1);
77 int kv = ctz_u128(v0, v1);
78 int cnt = ku < kv ? ku : kv;
79 lshr_u128(&u0, &u1, ku);
80 lshr_u128(&v0, &v1, kv);
81 // u, v 均为奇数;去冗余最低位(隐式最低位表示),腾出符号位
82 u0 = (u0 >> 1) | (u1 << 63);
83 u1 >>= 1;
84 v0 = (v0 >> 1) | (v1 << 63);
85 v1 >>= 1;
86
87 while (u1 | v1) { // 至少一方仍为双 limb
88 mp_limb_t t0 = u0 - v0;
89 mp_limb_t t1 = u1 - v1 - (u0 < v0);
90 mp_limb_t m = -(mp_limb_t)(t1 >> 63); // u<v -> 1
91 if (t0 == 0) {
92 if (t1 == 0)
93 break;
94
95 v1 += m & t1; // v1 = min(u1, v1)(v0 == u0,无需更新)
96 u0 = (t1 ^ m) - m; // |u1 - v1|
97 u0 >>= lmmp_tailing_zeros_(t1) + 1;
98 u1 = 0;
99 } else {
100 int c = lmmp_tailing_zeros_(t0) + 1;
101 // v = min(u, v)(128 位加法 v += m & t)
102 mp_limb_t w0 = m & t0;
103 mp_limb_t w1 = m & t1;
104 v0 += w0;
105 v1 += w1 + (v0 < w0);
106
107 u0 = (t0 ^ m) - m;
108 u1 = t1 ^ m;
109 if (c == 64) {
110 u0 = u1;
111 u1 = 0;
112 } else {
113 u0 = (u0 >> c) | (u1 << (64 - c));
114 u1 >>= c;
115 }
116 }
117 }
118
119 mp_limb_t g0, g1; // 奇数 gcd
120 if (u1 | v1) {
121 g0 = (u0 << 1) | 1;
122 g1 = (u1 << 1) | (u0 >> 63);
123 } else {
124 while ((u0 | v0) >> 63) { // 任一 >= 2^63 则真值 >= 2^64,至多两次迭代
125 mp_limb_t t = u0 - v0;
126 if (t == 0)
127 break; // u == v
128 mp_limb_t m = -(mp_limb_t)(u0 < v0); // 符号掩码
129 v0 += m & t; // v = min(u0, v0)
130 u0 = (t ^ m) - m; // |u0 - v0|
131 u0 = (u0 >> 1) >> lmmp_tailing_zeros_(t);
132 }
133 if (u0 == v0) {
134 g0 = (u0 << 1) | 1;
135 g1 = u0 >> 63;
136 } else {
137 g0 = lmmp_gcd_11_((u0 << 1) + 1, (v0 << 1) + 1);
138 g1 = 0;
139 }
140 }
141
142 dst[0] = g0;
143 dst[1] = g1;
144 if (cnt > 0)
145 lshl_u128(&dst[0], &dst[1], cnt);
146 return dst[1] == 0 ? 1 : 2;
147}
static int ctz_u128(mp_limb_t lo, mp_limb_t hi)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 gcd_2.c:32
static void lshr_u128(mp_limb_t *lo, mp_limb_t *hi, int k)
定义 gcd_2.c:36
static void lshl_u128(mp_limb_t *lo, mp_limb_t *hi, int k)
定义 gcd_2.c:48
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define v0
#define v1
#define t
#define w0
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:28

引用了 ctz_u128(), lmmp_gcd_11_(), lmmp_gcd_22_(), lmmp_param_assert, lmmp_tailing_zeros_, lshl_u128(), lshr_u128(), t, v0, v1 , 以及 w0.

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

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

◆ lmmp_gcd_2_()

mp_size_t lmmp_gcd_2_ ( mp_ptr dst,
mp_srcptr up,
mp_size_t un,
mp_srcptr vp )

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

参数
up第一个无符号整数指针
un第一个无符号整数的 limb 长度
vp第二个无符号整数指针,长度为 2
dst结果指针(长度至少为 2,两个 limb 都会进行写入,即使最高位可能为0)
警告
up!=NULL, un>2, vp!=NULL, vp[1]!=0, dst!=NULL, eqsep(dst,[up|vp])
返回
dst 的实际 limb 长度

在文件 gcd_2.c 第 149 行定义.

149 {
150 lmmp_param_assert(dst != NULL);
151 lmmp_param_assert(up != NULL);
152 lmmp_param_assert(vp != NULL);
153 lmmp_param_assert(un > 2);
154 lmmp_param_assert(vp[1] != 0);
155 mp_limb_t u[2] = {vp[0], vp[1]};
156 lmmp_mod_2_(up, un, u);
157 if (u[1] == 0 && u[0] == 0) {
158 dst[0] = vp[0];
159 dst[1] = vp[1];
160 return 2;
161 } else {
162 return lmmp_gcd_22_(dst, vp, u);
163 }
164}
void lmmp_mod_2_(mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数取余 (除数为2个limb)
定义 div.c:215
mp_size_t lmmp_gcd_22_(mp_ptr dst, mp_srcptr up, mp_srcptr vp)
计算两个无符号整数的最大公约数
定义 gcd_2.c:60

引用了 lmmp_gcd_22_(), lmmp_gcd_2_(), lmmp_mod_2_() , 以及 lmmp_param_assert.

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

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

◆ lshl_u128()

void lshl_u128 ( mp_limb_t * lo,
mp_limb_t * hi,
int k )
inlinestatic

在文件 gcd_2.c 第 48 行定义.

48 {
49 if (k == 0)
50 return;
51 if (k < 64) {
52 *hi = (*lo >> (64 - k)) | (*hi << k);
53 *lo <<= k;
54 } else {
55 *hi = *lo << (k - 64);
56 *lo = 0;
57 }
58}
#define k

引用了 k, lo , 以及 lshl_u128().

被这些函数引用 lmmp_gcd_22_() , 以及 lshl_u128().

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

◆ lshr_u128()

void lshr_u128 ( mp_limb_t * lo,
mp_limb_t * hi,
int k )
inlinestatic

在文件 gcd_2.c 第 36 行定义.

36 {
37 if (k == 0)
38 return;
39 if (k < 64) {
40 *lo = (*lo >> k) | (*hi << (64 - k));
41 *hi >>= k;
42 } else {
43 *lo = *hi >> (k - 64);
44 *hi = 0;
45 }
46}

引用了 k, lo , 以及 lshr_u128().

被这些函数引用 lmmp_gcd_22_() , 以及 lshr_u128().

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