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

浏览该文件的源代码.

函数

static u64 gcd_u64 (u64 a, u64 b)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
static void shifted_pair (u64 x, int s, mp_ptr out)
 TEST_CASE ("numth/gcd", gcd_1)
 TEST_CASE ("numth/gcd", gcd_11)
 TEST_CASE ("numth/gcd", gcd_22_and_gcd_2)
 TEST_CASE ("numth/gcd", gcd_22_shapes)
 TEST_CASE ("numth/gcd", gcd_2_multiple_and_gcd_1_zero)
 TEST_CASE ("numth/gcd", gcd_empty)
void test_gcd (void)

函数说明

◆ gcd_u64()

u64 gcd_u64 ( u64 a,
u64 b )
static

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

在文件 test_gcd.c 第 39 行定义.

39 {
40 while (b) {
41 u64 t = a % b;
42 a = b;
43 b = t;
44 }
45 return a;
46}
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define t

引用了 gcd_u64() , 以及 t.

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

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

◆ shifted_pair()

void shifted_pair ( u64 x,
int s,
mp_ptr out )
static

在文件 test_gcd.c 第 49 行定义.

49 {
50 if (s < 64) {
51 out[0] = x << s;
52 out[1] = (s == 0) ? 0 : (x >> (64 - s));
53 } else {
54 out[0] = 0;
55 out[1] = x << (s - 64);
56 }
57}
#define s

引用了 s , 以及 shifted_pair().

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

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

◆ TEST_CASE() [1/6]

TEST_CASE ( "numth/gcd" ,
gcd_1  )

在文件 test_gcd.c 第 73 行定义.

73 {
74 u64 seed = 0x3c6ef372fe94f82bull;
75 for (size_t un = 1; un <= 40; ++un) {
76 for (int iter = 0; iter < 20; ++iter) {
77 mp_ptr u = alloc_limbs(un);
78 random_limbs(u, un, &seed);
79 u64 v = xorshift64(&seed) | 1;
80 // 恒等式一步:gcd(u, v) == gcd(u mod v, v)(mod_1 求余后标量参考)
81 u64 r = lmmp_mod_1_(u, un, v);
82 TEST_CHECK_EQ(lmmp_gcd_1_(u, un, v), gcd_u64(r, v));
83 // 整除性
84 TEST_CHECK_EQ(lmmp_mod_1_(u, un, lmmp_gcd_1_(u, un, v)), 0ull);
85 lmmp_free(u);
86 }
87 }
88}
mp_limb_t * mp_ptr
定义 lmmp.h:96
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
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_1_(mp_srcptr up, mp_size_t un, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:46
#define TEST_CHECK_EQ(a, b)
定义 test.h:39
static u64 gcd_u64(u64 a, u64 b)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 gcd_u64(), lmmp_free(), lmmp_gcd_1_(), lmmp_mod_1_(), TEST_CASE , 以及 TEST_CHECK_EQ.

函数调用图:

◆ TEST_CASE() [2/6]

TEST_CASE ( "numth/gcd" ,
gcd_11  )

在文件 test_gcd.c 第 59 行定义.

59 {
60 u64 seed = 0x6d2b79f5ull;
61 for (int i = 0; i < 500; ++i) {
62 u64 a = xorshift64(&seed) | 1;
63 u64 b = xorshift64(&seed) | 1;
65 }
66 TEST_CHECK_EQ(lmmp_gcd_11_(1, 1), 1u);
67 TEST_CHECK_EQ(lmmp_gcd_11_(UINT64_MAX, UINT64_MAX), UINT64_MAX);
68 // 写死锚点:gcd(2^63, 2^62)=2^62;gcd(2^64-1, 2^63)=1(费马数互素)
69 TEST_CHECK_EQ(lmmp_gcd_11_((u64)1 << 63, (u64)1 << 62), (u64)1 << 62);
70 TEST_CHECK_EQ(lmmp_gcd_11_(UINT64_MAX, (u64)1 << 63), 1u);
71}
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:28

引用了 gcd_u64(), lmmp_gcd_11_(), TEST_CASE , 以及 TEST_CHECK_EQ.

函数调用图:

◆ TEST_CASE() [3/6]

TEST_CASE ( "numth/gcd" ,
gcd_22_and_gcd_2  )

在文件 test_gcd.c 第 90 行定义.

90 {
91 u64 seed = 0x9e3779b97f4a7c15ull;
92 mp_ptr u = alloc_limbs(2), v = alloc_limbs(2), dst = alloc_limbs(2), gr = alloc_limbs(2);
93 // gcd_22:与 gcd_lehmer_(通用 Lehmer 路径)交叉 + 整除性
94 for (int iter = 0; iter < 200; ++iter) {
95 random_limbs(u, 2, &seed);
96 random_limbs(v, 2, &seed);
97 mp_size_t gn = lmmp_gcd_22_(dst, u, v);
98 mp_size_t ln = lmmp_gcd_lehmer_(gr, u, 2, v, 2);
99 TEST_CHECK(mpn_eq(dst, gn, gr, ln));
100 TEST_CHECK_MSG(divides_all(dst, gn, u, 2), "gcd_22 divides u");
101 TEST_CHECK_MSG(divides_all(dst, gn, v, 2), "gcd_22 divides v");
102 }
103 // gcd_2:多 limb u 对 2 limb v —— 与 gcd_lehmer_ 交叉(Lehmer 原生处理不平衡)
104 for (int iter = 0; iter < 100; ++iter) {
105 mp_size_t un = 3 + (iter % 40);
106 mp_ptr ub = alloc_limbs(un);
107 random_limbs(ub, un, &seed);
108 random_limbs(v, 2, &seed);
109 mp_size_t gn = lmmp_gcd_2_(dst, ub, un, v);
110 mp_size_t ln = lmmp_gcd_lehmer_(gr, ub, un, v, 2);
111 TEST_CHECK(mpn_eq(dst, gn, gr, ln));
112 TEST_CHECK_MSG(divides_all(dst, gn, ub, un), "gcd_2 divides u");
113 lmmp_free(ub);
114 }
115 lmmp_free(u); lmmp_free(v); lmmp_free(dst); lmmp_free(gr);
116}
uint64_t mp_size_t
定义 lmmp.h:93
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_size_t lmmp_gcd_22_(mp_ptr dst, mp_srcptr up, mp_srcptr vp)
计算两个无符号整数的最大公约数
定义 gcd_2.c:60
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38

引用了 lmmp_free(), lmmp_gcd_22_(), lmmp_gcd_2_(), lmmp_gcd_lehmer_(), TEST_CASE, TEST_CHECK , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [4/6]

TEST_CASE ( "numth/gcd" ,
gcd_22_shapes  )

在文件 test_gcd.c 第 118 行定义.

118 {
119 // 覆盖单/双 limb 与低位为 0 的形态组合。强制高位的随机测试几乎不可能
120 // 命中这些分支(单个 limb 为 0 的概率约 2^-64),gcd_22 曾因此在
121 // u0==v0==0 的路径上漏检(漏乘 B),此用例系统性遍历移位组合。
122 // 期望 = gcd(x,y)*2^min(a,b)(x,y 奇)。构造约束:x,y < 2^63 且
123 // s <= 64,保证 x*2^s < 2^127 不溢出 128 位(溢出截断会使期望式失效)
124 u64 seed = 0x51ce1b7ea4df7c21ull;
125 mp_ptr u = alloc_limbs(2), v = alloc_limbs(2), d = alloc_limbs(2), e = alloc_limbs(2);
126 for (int a = 0; a <= 64; ++a) {
127 for (int b = 0; b <= 64; b += 4) {
128 u64 x = (xorshift64(&seed) & (((u64)1 << 63) - 1)) | 1; // 奇且 < 2^63
129 u64 y = (xorshift64(&seed) & (((u64)1 << 63) - 1)) | 1;
130 shifted_pair(x, a, u);
131 shifted_pair(y, b, v);
132 mp_size_t gn = lmmp_gcd_22_(d, u, v);
133 // 期望 = gcd(x,y)*2^min(a,b)(标量 gcd + 移位装配,精确已知)
134 int m = a < b ? a : b;
135 u64 g = gcd_u64(x, y);
136 shifted_pair(g, m, e);
137 mp_size_t en = norm_len(e, 2);
138 TEST_CHECK(mpn_eq(d, gn, e, en));
139 }
140 }
141 // 确定性用例:写死精确期望(B 的倍数 / 单 limb / 相等 / 混合形态)
142 struct gcd_case { u64 u0, u1, v0, v1; mp_size_t n; u64 w0, w1; } fixed[] = {
143 {0, 1, 0, 3, 2, 0, 1}, // gcd(B, 3B) = B
144 {0, 9, 0, 6, 2, 0, 3}, // gcd(9B, 6B) = 3B
145 {0, 2, 0, 6, 2, 0, 2}, // gcd(2B, 6B) = 2B
146 {0, 1, 0, 1ull << 63, 2, 0, 1}, // gcd(B, 2^63*B) = B
147 {1, 0, 3, 0, 1, 1, 0}, // 双方单 limb:gcd(1,3)=1
148 {12, 0, 18, 0, 1, 6, 0}, // gcd(12,18)=6
149 {0, 1, 5, 0, 1, 1, 0}, // gcd(B,5)=1
150 {7, 9, 7, 9, 2, 7, 9}, // 相等
151 {10, 2, 0, 1, 1, 2, 0}, // gcd(2B+10, B) = gcd(10, B) = 2
152 {0, 1, 0, 1, 2, 0, 1}, // 双方相等且均为 B
153 };
154 for (size_t t_index = 0; t_index < ARRAY_SIZE(fixed); ++t_index) {
155 const struct gcd_case t = fixed[t_index];
156 u64 pu[2] = {t.u0, t.u1}, pv[2] = {t.v0, t.v1};
157 mp_size_t gn = lmmp_gcd_22_(d, pu, pv);
158 TEST_CHECK_MSG(gn == t.n && d[0] == t.w0 && d[1] == t.w1, "gcd_22 fixed shape");
159 }
160 lmmp_free(u); lmmp_free(v); lmmp_free(d); lmmp_free(e);
161}
#define v0
#define v1
#define n
#define w0
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
static void shifted_pair(u64 x, int s, mp_ptr out)

引用了 ARRAY_SIZE, gcd_u64(), lmmp_free(), lmmp_gcd_22_(), n, shifted_pair(), t, TEST_CASE, TEST_CHECK, TEST_CHECK_MSG, v0, v1 , 以及 w0.

函数调用图:

◆ TEST_CASE() [5/6]

TEST_CASE ( "numth/gcd" ,
gcd_2_multiple_and_gcd_1_zero  )

在文件 test_gcd.c 第 163 行定义.

163 {
164 // gcd_2:u 为 v 的整数倍 → 余数为 0 → 直接返回 v(u = k*v 经库 mul_1 构造)
165 u64 seed = 0x2b44ae9d4d6c8f13ull;
166 for (int iter = 0; iter < 20; ++iter) {
167 mp_ptr v = alloc_limbs(2);
168 random_limbs(v, 2, &seed);
169 u64 k = 3 + (xorshift64(&seed) & 0xf);
170 mp_ptr up = alloc_limbs(4);
171 u64 hi = lmmp_mul_1_(up, v, 2, k); // u = k*v
172 mp_size_t un = hi ? 3 : 2;
173 if (hi) up[2] = hi;
174 mp_ptr d = alloc_limbs(2);
175 mp_size_t gn = lmmp_gcd_2_(d, up, un, v);
176 TEST_CHECK(mpn_eq(d, gn, v, 2));
177 lmmp_free(v); lmmp_free(up); lmmp_free(d);
178 }
179
180 // gcd_1:[up,un] == 0 → gcd(0,v) = v(契约允许 u 为 0)
181 mp_ptr z = alloc_limbs(5);
182 lmmp_zero(z, 5);
183 TEST_CHECK_EQ(lmmp_gcd_1_(z, 5, 7), 7u);
184 TEST_CHECK_EQ(lmmp_gcd_1_(z, 1, 7), 7u);
185 TEST_CHECK_EQ(lmmp_gcd_1_(z + 1, 4, 12), 12u);
186 lmmp_free(z);
187}
#define k
#define lmmp_zero(dst, n)
定义 lmmp.h:476
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义 mul_1.c:27

引用了 k, lmmp_free(), lmmp_gcd_1_(), lmmp_gcd_2_(), lmmp_mul_1_(), lmmp_zero, TEST_CASE, TEST_CHECK , 以及 TEST_CHECK_EQ.

函数调用图:

◆ TEST_CASE() [6/6]

TEST_CASE ( "numth/gcd" ,
gcd_empty  )

在文件 test_gcd.c 第 189 行定义.

189 {
190 // gcd(B^k, B^k) = B^k:lehmer/hgcd 两条路径的顶 limb 传播
191 const mp_size_t n_values[] = {2, 3, 5, 8, 16, 53, 64, 120, 200, 321};
192 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
193 mp_size_t n = n_values[n_index];
194 mp_ptr a = alloc_limbs(n);
195 mp_ptr b = alloc_limbs(n);
196 mp_ptr c = alloc_limbs(n);
197 mp_ptr d = alloc_limbs(n);
198
199 lmmp_zero(a, n - 1);
200 lmmp_zero(b, n - 1);
201 a[n - 1] = 1;
202 b[n - 1] = 1;
203 mp_size_t cn = lmmp_gcd_lehmer_(c, a, n, b, n);
204 TEST_CHECK_MSG(cn == n && c[n - 1] == 1, "lehmer gcd high limb is one");
205 for (mp_size_t i = 0; i < cn - 1; i++) {
206 TEST_CHECK_MSG(c[i] == 0, "lehmer gcd low limbs is zero");
207 }
208
209 mp_size_t dn = lmmp_gcd_hgcd_(d, a, n, b, n);
210 TEST_CHECK_MSG(dn == n && d[n - 1] == 1, "hgcd gcd is equal to B^n");
211 for (mp_size_t i = 0; i < dn - 1; i++) {
212 TEST_CHECK_MSG(d[i] == 0, "hgcd gcd low limbs is zero");
213 }
214 lmmp_free(a); lmmp_free(b); lmmp_free(c); lmmp_free(d);
215 }
216}
mp_size_t lmmp_gcd_hgcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)

引用了 ARRAY_SIZE, lmmp_free(), lmmp_gcd_hgcd_(), lmmp_gcd_lehmer_(), lmmp_zero, n, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ test_gcd()

void test_gcd ( void )

在文件 test_gcd.c 第 218 行定义.

218 {
219 TEST_RUN("numth/gcd", gcd_11);
220 TEST_RUN("numth/gcd", gcd_1);
221 TEST_RUN("numth/gcd", gcd_22_and_gcd_2);
222 TEST_RUN("numth/gcd", gcd_22_shapes);
223 TEST_RUN("numth/gcd", gcd_2_multiple_and_gcd_1_zero);
224 TEST_RUN("numth/gcd", gcd_empty);
225}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_gcd() , 以及 TEST_RUN.

被这些函数引用 main() , 以及 test_gcd().

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