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

浏览该文件的源代码.

函数

static bool check_pow1_agree (ulong base, ulong exp, mp_size_t(*fn)(mp_ptr, mp_size_t, ulong, ulong))
static void check_pow1_laws (ulong base, ulong exp)
static u64 modpow32 (u64 base, u64 exp, u32 p)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
 TEST_CASE ("numth/pow", pow_1_variants_and_anchors)
 TEST_CASE ("numth/pow", pow_multi_variants)
void test_pow (void)
static int top_bits (u64 x)

函数说明

◆ check_pow1_agree()

bool check_pow1_agree ( ulong base,
ulong exp,
mp_size_t(* fn )(mp_ptr, mp_size_t, ulong, ulong) )
static

在文件 test_pow.c 第 54 行定义.

54 {
55 mp_size_t cap = lmmp_pow_1_size_(base, exp) + 2;
56 mp_ptr d1 = alloc_limbs(cap), d2 = alloc_limbs(cap);
57 mp_size_t r1 = fn(d1, cap, base, exp);
58 mp_size_t r2 = lmmp_pow_1_(d2, cap, base, exp);
59 bool ok = r1 == r2 && r1 <= lmmp_pow_1_size_(base, exp);
60 ok = ok && (r1 == 0 || d1[r1 - 1] != 0);
61 ok = ok && memcmp(d1, d2, (size_t)r1 * 8) == 0;
62 for (int i = 0; i < MOD_P_CNT && ok; ++i)
63 ok = mod32(d1, r1, MOD_P[i]) == modpow32(base, exp, MOD_P[i]);
64 lmmp_free(d1);
65 lmmp_free(d2);
66 return ok;
67}
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define r2
#define r1
mp_size_t lmmp_pow_1_size_(mp_limb_t base, ulong exp)
计算幂次方需要的limb缓冲区长度 base ^ exp
定义 pow.c:65
mp_size_t lmmp_pow_1_(mp_ptr dst, mp_size_t rn, mp_limb_t base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
static u64 modpow32(u64 base, u64 exp, u32 p)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 check_pow1_agree(), lmmp_free(), lmmp_pow_1_(), lmmp_pow_1_size_(), modpow32(), r1 , 以及 r2.

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

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

◆ check_pow1_laws()

void check_pow1_laws ( ulong base,
ulong exp )
static

在文件 test_pow.c 第 70 行定义.

70 {
71 mp_size_t need = lmmp_pow_1_size_(base, exp);
72 mp_ptr pe = alloc_limbs(need + 2), pm = alloc_limbs(need + 2);
73 mp_size_t re = lmmp_pow_1_(pe, need, base, exp);
74 if (exp >= 2) {
75 mp_size_t rm = lmmp_pow_1_(pm, need, base, exp - 1);
76 u64 hi = lmmp_mul_1_(pm, pm, rm, base);
77 if (hi) pm[rm++] = hi;
78 TEST_CHECK_MSG(mpn_eq(pe, re, pm, rm), "pow law b^e == b^(e-1)*b");
79 }
80 if (exp % 2 == 0) {
81 mp_size_t rk = lmmp_pow_1_(pm, need, base, exp / 2);
82 mp_ptr sq = alloc_limbs(2 * rk + 2);
83 lmmp_sqr_(sq, pm, rk);
84 TEST_CHECK_MSG(mpn_eq(pe, re, sq, 2 * rk), "pow law b^2k == sqr(b^k)");
85 lmmp_free(sq);
86 }
87 lmmp_free(pe);
88 lmmp_free(pm);
89}
#define rk
#define lmmp_sqr_
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
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
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38

引用了 check_pow1_laws(), lmmp_free(), lmmp_mul_1_(), lmmp_pow_1_(), lmmp_pow_1_size_(), lmmp_sqr_, rk , 以及 TEST_CHECK_MSG.

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

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

◆ modpow32()

u64 modpow32 ( u64 base,
u64 exp,
u32 p )
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_pow.c 第 40 行定义.

40 {
41 u64 r = 1 % p, a = base % p;
42 while (exp) {
43 if (exp & 1) r = r * a % p;
44 a = a * a % p;
45 exp >>= 1;
46 }
47 return r;
48}

引用了 modpow32().

函数调用图:

◆ TEST_CASE() [1/2]

TEST_CASE ( "numth/pow" ,
pow_1_variants_and_anchors  )

在文件 test_pow.c 第 91 行定义.

91 {
92 // 写死锚点(精确 limb 比对)
93 struct power_case { ulong base, exp; u64 w[3]; int n; } anchors[] = {
94 {2, 64, {0, 1, 0}, 2}, // 2^64
95 {2, 127, {0, 0x8000000000000000ull, 0}, 2}, // 2^127
96 {2, 128, {0, 0, 1}, 3}, // 2^128
97 {(ulong)1 << 32, 2, {0, 1, 0}, 2}, // (2^32)^2 = 2^64
98 {10, 19, {0x8ac7230489e80000ull, 0, 0}, 1}, // 10^19 < 2^64
99 {1, 1000, {1, 0, 0}, 1},
100 };
101 for (size_t a_index = 0; a_index < ARRAY_SIZE(anchors); ++a_index) {
102 const struct power_case a = anchors[a_index];
103 mp_ptr d = alloc_limbs(4);
104 mp_size_t rn = lmmp_pow_1_(d, 4, a.base, a.exp);
105 bool ok = rn == (mp_size_t)a.n && memcmp(d, a.w, (size_t)a.n * 8) == 0;
106 lmmp_free(d);
107 TEST_CHECK_MSG(ok, "pow_1 anchor");
108 }
109 // (2^64-1)^2 与 10^38:经 mullh 独立重建(全积原语)
110 {
111 mp_ptr d = alloc_limbs(3), prod = alloc_limbs(2);
112 mp_size_t rn = lmmp_pow_1_(d, 3, UINT64_MAX, 2);
113 lmmp_mullh_(UINT64_MAX, UINT64_MAX, prod);
114 TEST_CHECK_MSG(mpn_eq(d, rn, prod, 2), "(2^64-1)^2 == mullh");
115 u64 t19 = 0x8ac7230489e80000ull;
116 rn = lmmp_pow_1_(d, 3, 10, 38);
117 lmmp_mullh_(t19, t19, prod);
118 TEST_CHECK_MSG(mpn_eq(d, rn, prod, 2), "10^38 == mullh(10^19)");
119 lmmp_free(d);
121 }
122
123 // 域边界扫描(各族 2^k 边界 ±1、窗口进位形态、历史 bug 底数)
124 static const ulong exps[] = {
125 25, 26, 31, 32, 33, 47, 48, 63, 64, 100, 127, 128, 255, 256, 341, 511, 1024, 2000
126 };
127 int checked = 0;
128 const ulong bases[] = {1, 2, 3, 6, 10, 15,
129 255, 256, 2760, 2761, 7386, 2642246,
130 50854530, 0x2bad99ul, 0xfffffffful, 0x100000000ul, 0xdeadbeefcafebul,
131 UINT64_MAX};
132 for (size_t exp_index = 0; exp_index < ARRAY_SIZE(exps); ++exp_index) {
133 ulong exp = exps[exp_index];
134 for (size_t base_index = 0; base_index < ARRAY_SIZE(bases); ++base_index) {
135 ulong base = bases[base_index];
136 bool ok = check_pow1_agree(base, exp, lmmp_pow_1_);
137 if (base <= 15) ok = ok && check_pow1_agree(base, exp, lmmp_u4_pow_1_);
138 // u8/u16/u32 八进制梯子契约 base>=2(base=1 由 u4 档覆盖)
139 if (base >= 2 && base <= 255) ok = ok && check_pow1_agree(base, exp, lmmp_u8_pow_1_);
140 if (base >= 2 && base <= 0xffff) ok = ok && check_pow1_agree(base, exp, lmmp_u16_pow_1_);
141 if (base >= 2 && base <= 0xfffffffful)
142 ok = ok && check_pow1_agree(base, exp, lmmp_u32_pow_1_);
143 if (base > 0xfffffffful) ok = ok && check_pow1_agree(base, exp, lmmp_u64_pow_1_);
144 TEST_CHECK_MSG(ok, "pow_1 family agree");
145 ++checked;
146 }
147 }
148 TEST_CHECK_MSG(checked > 200, "sweep coverage");
149 // 指数律抽样
150 const ulong law_bases[] = {3, 10, 0x2bad99, 0xffffffff, UINT64_MAX - 1};
151 for (size_t base_index = 0; base_index < ARRAY_SIZE(law_bases); ++base_index) {
152 ulong base = law_bases[base_index];
153 const ulong exp_values[] = {2ul, 3ul, 17ul, 64ul, 255ul};
154 for (size_t exp_index = 0; exp_index < ARRAY_SIZE(exp_values); ++exp_index) {
155 ulong exp = exp_values[exp_index];
156 check_pow1_laws(base, exp);
157 }
158 }
159}
#define prod
#define lmmp_mullh_
#define n
mp_size_t lmmp_u4_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_u32_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_u64_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_u8_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_u16_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
uint64_t ulong
定义 numth.h:39
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
static void check_pow1_laws(ulong base, ulong exp)
static bool check_pow1_agree(ulong base, ulong exp, mp_size_t(*fn)(mp_ptr, mp_size_t, ulong, ulong))

引用了 ARRAY_SIZE, check_pow1_agree(), check_pow1_laws(), lmmp_free(), lmmp_mullh_, lmmp_pow_1_(), lmmp_u16_pow_1_(), lmmp_u32_pow_1_(), lmmp_u4_pow_1_(), lmmp_u64_pow_1_(), lmmp_u8_pow_1_(), n, prod, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [2/2]

TEST_CASE ( "numth/pow" ,
pow_multi_variants  )

在文件 test_pow.c 第 161 行定义.

161 {
162 u64 seed = 0xf0f0f0f0c3c3c3c3ull;
163 const mp_size_t n_values[] = {1, 2, 5, 10, 30, 100};
164 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
165 mp_size_t n = n_values[n_index];
166 for (int iter = 0; iter < 3; ++iter) {
167 mp_ptr base = alloc_limbs(n);
168 random_limbs(base, n, &seed);
169 ulong exps[] = {1, 2, 3, 5, 7, 17, 31, 63};
170 for (size_t exp_index = 0; exp_index < ARRAY_SIZE(exps); ++exp_index) {
171 ulong exp = exps[exp_index];
172 mp_size_t need = lmmp_pow_size_(base, n, exp);
173 mp_ptr dst = alloc_limbs(need + 2), dst2 = alloc_limbs(need + 2),
174 dst3 = alloc_limbs(need + 2);
175 mp_size_t rn = lmmp_pow_(dst, need, base, n, exp);
176 mp_size_t r2 = lmmp_pow_win2_(dst2, need, base, n, exp);
177 TEST_CHECK_MSG(rn == r2 && memcmp(dst, dst2, (size_t)rn * 8) == 0,
178 "pow_ vs pow_win2_");
179 // 位长区间:2^(bits-1) <= b < 2^bits ⟹ b^e ∈ [2^(e(bits-1)), 2^(e*bits))
180 u64 bits = (u64)(n - 1) * 64 + (u64)top_bits(base[n - 1]);
181 mp_size_t lo = (mp_size_t)(((bits - 1) * exp - 1) / 64) + 1;
182 mp_size_t hi = (mp_size_t)((bits * exp - 1) / 64) + 1;
183 TEST_CHECK_MSG(rn >= lo && rn <= hi && (rn == 0 || dst[rn - 1] != 0),
184 "pow length bounds");
185 // 模检查(dst 为全值 b^e,模 p 比对合法)
186 bool ok = true;
187 for (int i = 0; i < MOD_P_CNT && ok; ++i) {
188 u32 p = MOD_P[i];
189 ok = mod32(dst, rn, p) == modpow32(mod32(base, n, p), exp, p);
190 }
191 TEST_CHECK_MSG(ok, "pow modpow check");
192 // 小指数乘法链重建(b^1/b^2/b^3 经库乘精确比对;乒乓双缓冲
193 // 保持 sep(dst,a,b))
194 if (exp <= 3) {
195 mp_ptr c1 = alloc_limbs(need + 2), c2 = alloc_limbs(need + 2);
196 lmmp_copy(c1, base, n);
197 mp_size_t cn = n;
198 for (ulong k = 1; k < exp; ++k) {
199 lmmp_mul_(c2, c1, cn, base, n); // cn >= n 恒成立
200 mp_ptr tswap = c1; c1 = c2; c2 = tswap;
201 cn += n;
202 }
203 TEST_CHECK_MSG(mpn_eq(dst, rn, c1, cn), "pow chain rebuild");
204 lmmp_free(c1);
205 lmmp_free(c2);
206 }
207 // pow_basecase_(奇 exp 3..17,旧界内)
208 if (exp % 2 == 1 && exp >= 3 && exp <= 17) {
209 mp_size_t r3 = lmmp_pow_basecase_(dst3, need, base, n, exp);
210 TEST_CHECK_MSG(r3 == rn && memcmp(dst, dst3, (size_t)rn * 8) == 0,
211 "pow_ vs pow_basecase_");
212 }
213 lmmp_free(dst);
214 lmmp_free(dst2);
215 lmmp_free(dst3);
216 }
217 lmmp_free(base);
218 }
219 }
220}
#define k
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
#define r3
#define lo
#define c1
mp_size_t lmmp_pow_win2_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方2比特窗口快速幂算法 [dst,rn] = [base,n] ^ exp
mp_size_t lmmp_pow_basecase_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算奇数次幂算法 [dst,rn] = [base,n] ^ exp
mp_size_t lmmp_pow_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算大整数幂 [dst,rn] = [base,n] ^ exp
mp_size_t lmmp_pow_size_(mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
定义 pow.c:103
static int top_bits(u64 x)

引用了 ARRAY_SIZE, c1, k, lmmp_copy, lmmp_free(), lmmp_mul_(), lmmp_pow_(), lmmp_pow_basecase_(), lmmp_pow_size_(), lmmp_pow_win2_(), lo, modpow32(), n, r2, r3, TEST_CASE, TEST_CHECK_MSG , 以及 top_bits().

函数调用图:

◆ test_pow()

void test_pow ( void )

在文件 test_pow.c 第 222 行定义.

222 {
223 TEST_RUN("numth/pow", pow_1_variants_and_anchors);
224 TEST_RUN("numth/pow", pow_multi_variants);
225}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_pow() , 以及 TEST_RUN.

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

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

◆ top_bits()

int top_bits ( u64 x)
static

在文件 test_pow.c 第 51 行定义.

51{ return 64 - __builtin_clzll(x); }

引用了 top_bits().

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

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