LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_pow.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/* 整数幂家族验证(无 BigInt oracle;模幂见 test_numth_powmod.cpp):
24 1. 标量幂:pow_1 家族五入口互比(精确 limb)+ 32 位素数模幂参考
25 (base^exp mod p,u64 乘积无溢出)+ 指数律 b^(e-1)*b、平方律
26 b^(2k)==sqr(b^k)(库乘重建)+ 写死锚点(2^64、2^127、(2^64-1)^2、
27 10^19 等)
28 2. 多 limb 幂:pow_/pow_win2_/pow_basecase_ 三实现互比 + 模检查 +
29 小指数乘法链重建(b^3==b*b*b)+ 位长区间
30*/
31
32#include "lmmp/lmmpn.h"
33#include "lmmp/numth.h"
34#include "cases.h"
36
37#include <string.h>
38
39// 32 位素数模幂参考(p < 2^32,u64 中间乘积不溢出)
40static u64 modpow32(u64 base, u64 exp, u32 p) {
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}
49
50// 顶部 limb 有效位数
51static int top_bits(u64 x) { return 64 - __builtin_clzll(x); }
52
53// 标量幂全检:五入口与顶层 pow_1_ 精确一致 + 归一化长度 + 模幂参考
54static bool check_pow1_agree(ulong base, ulong exp, mp_size_t (*fn)(mp_ptr, mp_size_t, ulong, ulong)) {
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}
68
69// 指数律重建:pow(b,e) == pow(b,e-1)*b 与 pow(b,2k) == sqr(pow(b,k))(库乘)
70static void check_pow1_laws(ulong base, ulong exp) {
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}
90
91TEST_CASE("numth/pow", pow_1_variants_and_anchors) {
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}
160
161TEST_CASE("numth/pow", pow_multi_variants) {
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}
221
222void test_pow(void) {
223 TEST_RUN("numth/pow", pow_1_variants_and_anchors);
224 TEST_RUN("numth/pow", pow_multi_variants);
225}
#define k
#define prod
#define rk
#define lmmp_mullh_
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
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]
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 r2
#define r1
#define r3
#define n
#define lo
#define c1
void test_pow(void)
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_pow_1_size_(mp_limb_t base, ulong exp)
计算幂次方需要的limb缓冲区长度 base ^ exp
定义 pow.c:65
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_u32_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_pow_1_(mp_ptr dst, mp_size_t rn, mp_limb_t base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ 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_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
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
uint64_t ulong
定义 numth.h:39
mp_size_t lmmp_pow_size_(mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
定义 pow.c:103
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_RUN(category, name)
定义 test.h:36
static int top_bits(u64 x)
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))
static u64 modpow32(u64 base, u64 exp, u32 p)
Copyright (C) 2026 HJimmyK (Jericho Knox)