LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_combin.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;nPr/nCr 见 test_numth_binom.cpp):
24 1. 递推链:n! == n*(n-1)!、n!! == n*(n-2)!!、H(n) == H(n-1)*n^n、
25 S(n) == S(n-1)*n!(乘法全走库 mul_1/mul/factorial_)
26 2. 模检查:结果 mod 32 位素数 == 逐项模乘(u64 简单循环)
27 3. 写死锚点:10!=3628800、20!=2432902008176640000、9!!=945、
28 10!!=3840
29 4. remove 剥除恰 k 个因子(库构造)
30*/
31
32#include "lmmp/lmmpn.h"
33#include "lmmp/numth.h"
34#include "cases.h"
36
37TEST_CASE("numth/fac", factorial) {
38 const size_t CAP = 4000;
39 mp_ptr expect = alloc_limbs(CAP);
40 mp_size_t elen = 0;
41
42 // 写死锚点
43 {
44 mp_bitcnt_t bits = 0;
45 mp_size_t need = lmmp_factorial_size_(10, &bits);
46 mp_ptr dst = alloc_limbs(need + 2);
47 lmmp_zero(dst, need + 2);
48 lmmp_factorial_(dst, bits, need, 10);
49 TEST_CHECK_EQ(dst[0], 3628800ull);
50 TEST_CHECK_EQ(norm_len(dst + 1, need + 1), (mp_size_t)0);
51 lmmp_free(dst);
52 }
53 {
54 mp_bitcnt_t bits = 0;
55 mp_size_t need = lmmp_factorial_size_(20, &bits);
56 mp_ptr dst = alloc_limbs(need + 2);
57 lmmp_zero(dst, need + 2);
58 lmmp_factorial_(dst, bits, need, 20);
59 TEST_CHECK_EQ(dst[0], 2432902008176640000ull);
60 TEST_CHECK_EQ(norm_len(dst + 1, need + 1), (mp_size_t)0);
61 lmmp_free(dst);
62 }
63
64 // 递推链 + 模检查:n! == n * (n-1)!(链跨全部中间档位)
65 u32 built = 0; // expect == built!
66 expect[0] = 1;
67 elen = 1;
68 const u32 n_values[] = {0, 1, 2, 5, 10, 20, 50, 100, 200, 1000, 10000};
69 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
70 u32 n = n_values[n_index];
71 mp_bitcnt_t bits = 0;
72 mp_size_t need = lmmp_factorial_size_(n, &bits);
73 mp_ptr dst = alloc_limbs(need + 2);
74 lmmp_zero(dst, need + 2);
75 lmmp_factorial_(dst, bits, need, n);
76 mp_size_t rn = norm_len(dst, need + 2);
77 if (n == 0) {
78 TEST_CHECK_EQ(dst[0], 1ull);
79 lmmp_free(dst);
80 continue;
81 }
82 for (u32 i = built + 1; i <= n; ++i) elen = chain_mul_small(expect, elen, i, CAP);
83 built = n;
84 TEST_CHECK(mpn_eq(dst, rn, expect, elen));
85
86 // 模检查:n! mod p == 逐项模乘(独立 64 位计算)
87 for (int pi = 0; pi < MOD_P_CNT; ++pi) {
88 u64 p = MOD_P[pi];
89 u64 m = 1;
90 for (u32 i = 2; i <= n; ++i) m = mulmod32(m, i % p, p);
91 TEST_CHECK_EQ(mod32(dst, rn, (u32)p), m);
92 }
93 lmmp_free(dst);
94 }
95
96 // 筛表路径(n > 65535 触发 lmmp_prime_int_table_init_ 的 mod-30 位图):
97 // 递推链过长,改用三素数独立模锚点(素数集错误必致模值不等)
98 {
99 u32 n = 100003;
100 mp_bitcnt_t bits = 0;
101 mp_size_t need = lmmp_factorial_size_(n, &bits);
102 mp_ptr dst = alloc_limbs(need + 2);
103 lmmp_zero(dst, need + 2);
104 lmmp_factorial_(dst, bits, need, n);
105 mp_size_t rn = norm_len(dst, need + 2);
106 for (int pi = 0; pi < MOD_P_CNT; ++pi) {
107 u64 p = MOD_P[pi];
108 u64 m = 1;
109 for (u32 i = 2; i <= n; ++i) m = mulmod32(m, i % p, p);
110 TEST_CHECK_EQ(mod32(dst, rn, (u32)p), m);
111 }
112 lmmp_free(dst);
113 }
114 lmmp_free(expect);
115}
116
117TEST_CASE("numth/fac_extern", double_hyper_super_primefac) {
118 // 双阶乘:n!! == n*(n-2)!! 链 + 写死锚点 9!!=945、10!!=3840
119 {
120 struct known_result { u32 n; u64 v; } known[] = {{0, 1ull}, {1, 1ull}, {9, 945ull}, {10, 3840ull}};
121 for (size_t k_index = 0; k_index < ARRAY_SIZE(known); ++k_index) {
122 const struct known_result k = known[k_index];
123 mp_bitcnt_t bits = 0;
124 mp_size_t need = lmmp_2factorial_size_(k.n, &bits);
125 mp_ptr dst = alloc_limbs(need + 2);
126 lmmp_zero(dst, need + 2);
127 lmmp_2factorial_(dst, bits, need, k.n);
128 TEST_CHECK_EQ(dst[0], k.v);
129 TEST_CHECK_EQ(norm_len(dst + 1, need + 1), (mp_size_t)0);
130 lmmp_free(dst);
131 }
132 }
133 const size_t CAP = 512;
134 mp_ptr e = alloc_limbs(CAP);
135 const u32 n_values[] = {2, 3, 10, 21, 50, 107, 301};
136 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
137 u32 n = n_values[n_index];
138 // 链参考:从 1 起按 n 的奇偶逐项乘
139 e[0] = 1;
140 mp_size_t elen = 1;
141 for (u32 i = (n % 2 == 0 ? 2 : 1); i <= n; i += 2)
142 elen = chain_mul_small(e, elen, i, CAP);
143 mp_bitcnt_t bits = 0;
144 mp_size_t need = lmmp_2factorial_size_(n, &bits);
145 mp_ptr dst = alloc_limbs(need + 2);
146 lmmp_zero(dst, need + 2);
147 lmmp_2factorial_(dst, bits, need, n);
148 TEST_CHECK(mpn_eq(dst, need + 2, e, elen));
149 lmmp_free(dst);
150 }
151 lmmp_free(e);
152
153 // hyper factorial: H(n) == H(n-1) * n^n(n^n 由库 mul 链构造)
154 const size_t CAP2 = 4096;
155 mp_ptr h = alloc_limbs(CAP2), t = alloc_limbs(CAP2);
156 h[0] = 1;
157 mp_size_t hlen = 1;
158 int checked_h = 0;
159 for (u32 k = 1; k <= 20; ++k) {
160 // k^k:k 次乘 k
161 t[0] = 1;
162 mp_size_t tn = 1;
163 for (u32 i = 0; i < k; ++i) tn = chain_mul_small(t, tn, k, CAP2);
164 mp_ptr prod = alloc_limbs(CAP2);
165 mul_sorted(prod, h, hlen, t, tn);
166 hlen = norm_len(prod, hlen + tn);
167 memcpy(h, prod, (size_t)hlen * 8);
169 if (k == 1 || k == 3 || k == 5 || k == 8 || k == 20) {
170 mp_bitcnt_t bits = 0;
171 mp_size_t need = lmmp_hyperfac_size_(k, &bits);
172 mp_ptr dst = alloc_limbs(need + 2);
173 lmmp_zero(dst, need + 2);
174 lmmp_hyperfac_(dst, bits, need, k);
175 TEST_CHECK(mpn_eq(dst, need + 2, h, hlen));
176 lmmp_free(dst);
177 ++checked_h;
178 }
179 }
180 TEST_CHECK_EQ(checked_h, 5);
181 lmmp_free(h);
182 lmmp_free(t);
183
184 // super factorial: S(n) == S(n-1) * n!(n! 用库 factorial_,交叉)
185 const size_t CAP3 = 4096;
186 mp_ptr s = alloc_limbs(CAP3);
187 s[0] = 1;
188 mp_size_t slen = 1;
189 for (u32 k = 1; k <= 30; ++k) {
190 mp_bitcnt_t bits = 0;
191 mp_size_t need = lmmp_factorial_size_(k, &bits);
192 mp_ptr fac = alloc_limbs(need + 2);
193 lmmp_zero(fac, need + 2);
194 lmmp_factorial_(fac, bits, need, k);
195 mp_size_t flen = norm_len(fac, need + 2);
196
197 mp_ptr prod = alloc_limbs(CAP3);
198 mul_sorted(prod, s, slen, fac, flen);
199 slen = norm_len(prod, slen + flen);
200 memcpy(s, prod, (size_t)slen * 8);
201
202 if (k == 1 || k == 3 || k == 5 || k == 8 || k == 30) {
203 need = lmmp_superfac_size_(k, &bits);
204 mp_ptr dst = alloc_limbs(need + 2);
205 lmmp_zero(dst, need + 2);
206 lmmp_superfac_(dst, bits, need, k);
207 TEST_CHECK(mpn_eq(dst, need + 2, s, slen));
208 lmmp_free(dst);
209 }
211 lmmp_free(fac);
212 }
213 lmmp_free(s);
214
215 // prime factorial: 素数判定用 64 位内简单试除,乘积走库链
216 const size_t CAP4 = 4096;
217 mp_ptr pf = alloc_limbs(CAP4);
218 const u32 n_values2[] = {2, 3, 10, 20, 50, 700};
219 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values2); ++n_index) {
220 u32 n = n_values2[n_index];
221 pf[0] = 1;
222 mp_size_t plen = 1;
223 for (u32 p = 2; p <= n; ++p)
224 if (is_prime_small(p)) plen = chain_mul_small(pf, plen, p, CAP4);
226 mp_ptr dst = alloc_limbs(need + 2);
227 lmmp_zero(dst, need + 2);
228 lmmp_primefac_(dst, need, n);
229 TEST_CHECK(mpn_eq(dst, need + 2, pf, plen));
230 lmmp_free(dst);
231 }
232 lmmp_free(pf);
233}
234
235TEST_CASE("numth/remove", remove_factors) {
236 // remove:np = dp^k * 11(库 mul_1 链构造),须剥除恰 k 个因子剩 11
237 const u64 dp_values[] = {2, 3, 5, 7};
238 for (size_t dp_index = 0; dp_index < ARRAY_SIZE(dp_values); ++dp_index) {
239 u64 dp = dp_values[dp_index];
240 mp_ptr np = alloc_limbs(3), d = alloc_limbs(1);
241 d[0] = dp;
242 for (int k = 0; k < 4; ++k) {
243 np[0] = 1;
244 np[1] = 0;
245 np[2] = 0;
246 mp_size_t nn = 1;
247 for (int i = 0; i < k; ++i) nn = chain_mul_small(np, nn, dp, 3);
248 nn = chain_mul_small(np, nn, 11, 3);
249
250 mp_size_t cnt = lmmp_remove_(np, &nn, d, 1);
252 TEST_CHECK_EQ(nn, (mp_size_t)1);
253 TEST_CHECK_EQ(np[0], 11ull);
254 }
255 lmmp_free(np);
256 lmmp_free(d);
257 }
258}
259
260void test_combin(void) {
261 TEST_RUN("numth/fac", factorial);
262 TEST_RUN("numth/fac_extern", double_hyper_super_primefac);
263 TEST_RUN("numth/remove", remove_factors);
264}
#define k
#define prod
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
size_t mp_bitcnt_t
定义 lmmp.h:98
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)
#define t
#define s
#define n
void test_combin(void)
mp_size_t lmmp_remove_(mp_ptr np, mp_size_t *nn, mp_srcptr dp, mp_size_t dn)
除去 [np,nn] 中的 [dp,dn] 的因子
mp_size_t lmmp_superfac_size_(ushort n, mp_bitcnt_t *bits)
计算super阶乘的 limb 缓冲区长度
mp_size_t lmmp_2factorial_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n)
计算 n!
mp_size_t lmmp_factorial_size_(uint n, mp_bitcnt_t *bits)
计算 n!
mp_size_t lmmp_primefac_size_(uint n)
计算质数阶乘的 limb 缓冲区长度
mp_size_t lmmp_hyperfac_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ushort n)
计算hyper阶乘(k^k累乘至n)
mp_size_t lmmp_2factorial_size_(uint n, mp_bitcnt_t *bits)
计算 n!
mp_size_t lmmp_factorial_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n)
计算 n!
mp_size_t lmmp_hyperfac_size_(ushort n, mp_bitcnt_t *bits)
计算hyper阶乘的 limb 缓冲区长度
mp_size_t lmmp_primefac_(mp_ptr dst, mp_size_t rn, uint n)
计算质数阶乘(不超过n的质数累乘)
mp_size_t lmmp_superfac_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ushort n)
计算super阶乘(k!
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_CHECK_EQ(a, b)
定义 test.h:39
#define TEST_RUN(category, name)
定义 test.h:36