41 u64 r = 1 % p, a = base % p;
43 if (exp & 1) r = r * a % p;
56 mp_ptr d1 = alloc_limbs(cap), d2 = alloc_limbs(cap);
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]);
72 mp_ptr pe = alloc_limbs(need + 2), pm = alloc_limbs(need + 2);
77 if (hi) pm[rm++] = hi;
78 TEST_CHECK_MSG(mpn_eq(pe, re, pm, rm),
"pow law b^e == b^(e-1)*b");
93 struct power_case {
ulong base, exp;
u64 w[3];
int n; } anchors[] = {
94 {2, 64, {0, 1, 0}, 2},
95 {2, 127, {0, 0x8000000000000000ull, 0}, 2},
96 {2, 128, {0, 0, 1}, 3},
97 {(
ulong)1 << 32, 2, {0, 1, 0}, 2},
98 {10, 19, {0x8ac7230489e80000ull, 0, 0}, 1},
99 {1, 1000, {1, 0, 0}, 1},
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);
105 bool ok = rn == (
mp_size_t)a.n && memcmp(d, a.w, (
size_t)a.n * 8) == 0;
111 mp_ptr d = alloc_limbs(3),
prod = alloc_limbs(2);
115 u64 t19 = 0x8ac7230489e80000ull;
124 static const ulong exps[] = {
125 25, 26, 31, 32, 33, 47, 48, 63, 64, 100, 127, 128, 255, 256, 341, 511, 1024, 2000
128 const ulong bases[] = {1, 2, 3, 6, 10, 15,
129 255, 256, 2760, 2761, 7386, 2642246,
130 50854530, 0x2bad99ul, 0xfffffffful, 0x100000000ul, 0xdeadbeefcafebul,
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];
141 if (base >= 2 && base <= 0xfffffffful)
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];
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) {
166 for (
int iter = 0; iter < 3; ++iter) {
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];
173 mp_ptr dst = alloc_limbs(need + 2), dst2 = alloc_limbs(need + 2),
174 dst3 = alloc_limbs(need + 2);
178 "pow_ vs pow_win2_");
184 "pow length bounds");
187 for (
int i = 0; i < MOD_P_CNT && ok; ++i) {
189 ok = mod32(dst, rn, p) ==
modpow32(mod32(base,
n, p), exp, p);
195 mp_ptr c1 = alloc_limbs(need + 2), c2 = alloc_limbs(need + 2);
208 if (exp % 2 == 1 && exp >= 3 && exp <= 17) {
211 "pow_ vs pow_basecase_");
223 TEST_RUN(
"numth/pow", pow_1_variants_and_anchors);
224 TEST_RUN(
"numth/pow", pow_multi_variants);
#define lmmp_copy(dst, src, n)
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
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
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
mp_size_t lmmp_pow_size_(mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEST_CHECK_MSG(cond, msg)
#define TEST_CASE(category, name)
#define TEST_RUN(category, name)
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)