LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
nPr.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#include <math.h>
24
25#include "numth/ele_mul.h"
26#include "impl/inlines.h"
27#include "impl/longlong.h"
28#include "mparam.h"
29#include "impl/prime_table.h"
30
31
32// 无分支,_c_为0时可能导致越界写入高位0
33#define mul_1(dst, rn, v) \
34 do { \
35 mp_limb_t _c_ = lmmp_mul_1_(dst, dst, rn, v); \
36 dst[rn] = _c_; \
37 rn += _c_ > 0; \
38 } while (0)
39
40
41static const ulong odd_factorial[25] = {1, 1, 3, 3, 15, 45, 315, 315,
42 2835, 14175, 155925,
43 467775, 6081075, 42567525,
44 638512875, 638512875, 10854718875, 97692469875,
45 1856156927625, 9280784638125, 194896477400625,
46 2143861251406875, 49308808782358125,
47 147926426347074375ull, 3698160658676859375ull};
48
50 lmmp_param_assert(n >= r);
51 lmmp_param_assert(bits != NULL);
53 shl -= (n - r) - lmmp_limb_popcnt_(n - r);
54 *bits = shl;
55 if (n < ODD_FACTORIAL_SIZE || r <= 2) {
56 return 3;
57 } else if (n <= MP_UINT_MAX) {
58 // nPr = n!/(n-r)!,分子ceil、分母floor保证不低估
59 // log2(m!) = lgamma(m+1)/ln2
60 const double ln2 = 0.69314718055994531;
61 mp_size_t l1, l2;
62 l1 = (mp_size_t)ceil(lgamma((double)n + 1) / ln2);
63 if (n - r < ODD_FACTORIAL_SIZE)
64 l2 = 0;
65 else
66 l2 = (mp_size_t)floor(lgamma((double)(n - r) + 1) / ln2);
67 mp_size_t rn = l1 - l2;
68 return (rn + LIMB_BITS - 1) / LIMB_BITS + 2; // more 2 limb
69 } else {
70 // nPr < (n - r/2 + 1)^r
71 ulong mean = n - r / 2 + 1;
72 return lmmp_pow_1_size_(mean, r);
73 }
74}
75
76static inline uint count_factors(fac_ptr fac, uint nfactors, uint n, uint r, uint p) {
77 uint pn = n;
78 uint e = 0;
79 ulong inv = MP_ULONG_MAX / p + 1;
80 while (pn > 0) {
81 _udiv32by32_q_preinv(pn, pn, inv);
82 e += pn;
83 }
84 pn = r;
85 while (pn > 0) {
86 _udiv32by32_q_preinv(pn, pn, inv);
87 e -= pn;
88 }
89 if (e > 0) {
90 fac[nfactors].f = p;
91 fac[nfactors++].j = e;
92 }
93 return nfactors;
94}
95
96/**
97 * @brief 使用累乘函数计算nPr(奇数部分)
98 */
100 TEMP_DECL;
101 ulongp restrict limbs = TALLOC_TYPE(r / 2 + 1, ulong);
102 mp_size_t limbn = 0;
103 ulong t = 1;
104 uint v;
105 mp_bitcnt_t cnt = 0;
106 // 需注意 n==UINT_MAX 的情况
107 uint ibase = n - r + 1;
108 for (uint k = 0; k < r; ++k) {
109 ctz_shr_u32(v, ibase + k, cnt);
110 t *= v;
111 if (t > MP_UINT_MAX) {
112 limbs[limbn++] = t;
113 t = 1;
114 }
115 }
116 if (t != 1)
117 limbs[limbn++] = t;
118
119 if (rn >= limbn) {
121 rn = lmmp_elem_mul_ulong_(dst, limbs, limbn, tp);
122 } else {
123 mp_ptr restrict tp = TALLOC_TYPE(limbn * 2, mp_limb_t);
124 rn = lmmp_elem_mul_ulong_(tp, limbs, limbn, tp + limbn);
125 lmmp_copy(dst, tp, rn);
126 }
127 TEMP_FREE;
128 return rn;
129}
130
131
133 lmmp_param_assert(n >= r);
135 if (n < ODD_FACTORIAL_SIZE) {
136 if (n == 0) {
137 dst[0] = 1;
138 } else if (n == r) {
139 dst[0] = odd_factorial[n - 1];
140 } else {
141 dst[0] = odd_factorial[n - 1] / odd_factorial[n - r - 1];
142 }
143 return 1;
144 } else if (r <= 10) {
145 dst[0] = 1;
146 rn = 1;
147 ulong t = 1, v;
148 ulong i = n - r + 1;
149 mp_bitcnt_t cnt = 0;
150 lmmp_debug_assert(n >= 3);
151 for (; i <= n - 3; i += 3) {
152 t = i * (i + 1) * (i + 2);
153 ctz_shr_u64(v, t, cnt);
154 mul_1(dst, rn, v);
155 }
156 t = 1;
157 for (; i <= n; ++i) {
158 t *= i;
159 }
160 ctz_shr_u64(v, t, cnt);
161 if (v != 1) {
162 mul_1(dst, rn, v);
163 }
164 return rn;
165 } else if (n <= MP_UCHAR_MAX) {
166 lmmp_debug_assert(n >= 7);
167 lmmp_debug_assert(r >= 2);
168 dst[0] = 1;
169 rn = 1;
170 ulong t = 0, v;
171 ulong i = n - r + 1;
172 mp_bitcnt_t cnt;
173 for (; i <= n - 7; i += 7) {
174 t = i * (i + 1) * (i + 2) * (i + 3) * (i + 4) * (i + 5) * (i + 6);
175 ctz_shr_u64(v, t, cnt);
176 mul_1(dst, rn, v);
177 }
178 t = 1;
179 for (; i <= n; ++i) {
180 t *= i;
181 }
182 ctz_shr_u64(v, t, cnt);
183 if (v != 1) {
184 mul_1(dst, rn, v);
185 }
186 return rn;
187 } else if (n <= 0xfff) {
189 ulongp restrict limbs = SALLOC_TYPE(r / 5 + 1, ulong);
190 mp_size_t limbn = 0;
191 ulong t, v;
192 ulong i = n - r + 1;
193 mp_bitcnt_t cnt;
194 lmmp_debug_assert(n >= 5);
195 for (; i <= (ulong)n - 5; i += 5) {
196 t = i * (i + 1) * (i + 2) * (i + 3) * (i + 4);
197 ctz_shr_u64(v, t, cnt);
198 limbs[limbn++] = v;
199 }
200 t = 1;
201 for (; i <= n; ++i) {
202 t *= i;
203 }
204 ctz_shr_u64(v, t, cnt);
205 if (v != 1)
206 limbs[limbn++] = v;
207 mp_ptr restrict tp = SALLOC_TYPE(limbn * 2, mp_limb_t);
208 // 这里不能直接乘入dst,因为dst的大小可能小于limbn,导致溢出
209 rn = lmmp_elem_mul_ulong_(tp, limbs, limbn, tp + limbn);
210 lmmp_copy(dst, tp, rn);
212 return rn;
214 /* 测量发现,累乘法和因子分解法的算法耗时流形交线大致为直线 */
215 return lmmp_odd_nPr_product_(dst, rn, n, r);
216 } else {
217 TEMP_DECL;
218 ushort primen = lmmp_prime_cnt16_(n);
219 ushort nfactors = primen;
220 fac_ptr restrict fac = TALLOC_TYPE(nfactors, fac_t);
221 r = n - r;
222 nfactors = 0;
223 for (ushort i = 1; i < primen; ++i) {
225 nfactors = count_factors(fac, nfactors, n, r, p);
226 }
227
228 rn = lmmp_factors_mul_ushort_(dst, rn, fac, nfactors);
229
230 TEMP_FREE;
231 return rn;
232 }
233}
234
236 lmmp_param_assert(n >= r);
238 if (r <= 10) {
239 dst[0] = 1;
240 rn = 1;
241 ulong v;
242 mp_bitcnt_t cnt;
243 for (ulong i = n - r + 1; i <= n; ++i) {
244 ctz_shr_u64(v, i, cnt);
245 mul_1(dst, rn, v);
246 }
247 return rn;
249 /* 这个调优值是在近似忽略了质数表的初始化开销,主要瓶颈集中在质数表的遍历的情况下测得的 */
250 /* 因此,当质数表未初始化时,这个调优值将无法代表真实性能边界 */
251 return lmmp_odd_nPr_product_(dst, rn, n, r);
252 } else{
254
256 uint nfactors = lmmp_prime_size_(n);
257 fac_ptr restrict fac = BALLOC_TYPE(nfactors, fac_t);
258 r = n - r;
259 nfactors = 0;
260
261 prime_cache_t cache;
262 lmmp_prime_cache_init_(&cache, n);
263 while (cache.is_end == 0) {
265 for (uint i = 0; i < cache.size; ++i) {
266 nfactors = count_factors(fac, nfactors, n, r, cache.pp[i]);
267 }
268 }
270
271 rn = lmmp_factors_mul_(dst, rn, fac, nfactors);
272
274 return rn;
275 }
276}
277
279 lmmp_param_assert(n >= r);
280 if (r < 10) {
281 dst[0] = 1;
282 rn = 1;
283 ulong v;
284 mp_bitcnt_t cnt;
285 // 需注意 n==UINT_MAX 的情况
286 ulong ibase = n - r + 1;
287 for (ulong k = 0; k < r; ++k) {
288 ctz_shr_u64(v, ibase + k, cnt);
289 if (v != 1) {
290 mul_1(dst, rn, v);
291 }
292 }
293 return rn;
294 }
295 TEMP_DECL;
296 ulongp restrict limbs = TALLOC_TYPE(r, ulong);
297 mp_size_t limbn = 0;
298 ulong v;
299 mp_bitcnt_t cnt;
300 ulong ibase = n - r + 1;
301 for (ulong k = 0; k < r; ++k) {
302 ctz_shr_u64(v, ibase + k, cnt);
303 if (v != 1)
304 limbs[limbn++] = v;
305 }
306
307 if (rn >= limbn) {
309 rn = lmmp_elem_mul_ulong_(dst, limbs, limbn, tp);
310 } else {
311 mp_ptr restrict tp = TALLOC_TYPE(limbn * 2, mp_limb_t);
312 rn = lmmp_elem_mul_ulong_(tp, limbs, limbn, tp + limbn);
313 lmmp_copy(dst, tp, rn);
314 }
315 TEMP_FREE;
316 return rn;
317}
318
320 lmmp_debug_assert(n >= r);
321 lmmp_param_assert(dst != NULL);
322 mp_size_t shw = bits / LIMB_BITS;
323 lmmp_param_assert(rn > shw);
324
325 bits %= LIMB_BITS;
326 lmmp_zero(dst, shw);
327
328 if (n <= NPR_SHORT_LIMIT)
329 rn = lmmp_odd_nPr_ushort_(dst + shw, rn - shw, n, r);
330 else if (n <= NPR_INT_LIMIT)
331 rn = lmmp_odd_nPr_uint_(dst + shw, rn - shw, n, r);
332 else
333 rn = lmmp_odd_nPr_ulong_(dst + shw, rn - shw, n, r);
334
335 if (bits > 0) {
336 dst[shw + rn] = lmmp_shl_(dst + shw, dst + shw, rn, bits);
337 rn += shw + 1;
338 rn -= dst[rn - 1] == 0;
339 } else {
340 rn += shw;
341 }
342 return rn;
343}
#define k
mp_size_t lmmp_elem_mul_ulong_(mp_ptr restrict dst, const ulongp restrict limbs, mp_size_t n, mp_ptr restrict tp)
mp_size_t lmmp_factors_mul_ushort_(mp_ptr dst, mp_size_t rn, fac_ptr fac, ushort nfactors)
计算因子的累乘,并将结果放入dst中
fac_t * fac_ptr
mp_size_t lmmp_factors_mul_(mp_ptr dst, mp_size_t rn, fac_ptr fac, uint nfactors)
计算因子的累乘,并将结果放入dst中
#define mul_1(dst, rn, v)
static void count_factors(fac_ptr fac, uint nfactors, uint n, uint p)
#define lmmp_limb_popcnt_
#define MP_UINT_MAX
#define MP_UCHAR_MAX
#define MP_ULONG_MAX
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
#define _udiv32by32_q_preinv(q, n0, dinv)
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define ctz_shr_u32(r, x, cnt)
#define t
#define tp
#define n
static mp_size_t lmmp_odd_nPr_product_(mp_ptr restrict dst, mp_size_t rn, uint n, uint r)
使用累乘函数计算nPr(奇数部分)
定义 nCr.c:136
static const ulong odd_factorial[25]
定义 nPr.c:41
#define NPR_SHORT_LIMIT
#define NPR_INT_LIMIT
#define PERMUTATION_USHORT_B_THRESHOLD
#define PERMUTATION_UINT_B_THRESHOLD
#define PERMUTATION_UINT_K_THRESHOLD
#define PERMUTATION_USHORT_K_THRESHOLD
#define ODD_FACTORIAL_SIZE
mp_size_t lmmp_pow_1_size_(mp_limb_t base, ulong exp)
计算幂次方需要的limb缓冲区长度 base ^ exp
定义 pow.c:65
mp_size_t lmmp_odd_nPr_ushort_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
uint64_t * ulongp
定义 numth.h:48
uint32_t uint
定义 numth.h:38
uint16_t ushort
定义 numth.h:36
mp_size_t lmmp_nPr_size_(ulong n, ulong r, mp_bitcnt_t *bits)
计算 nPr 排列数的 limb 缓冲区长度
uint64_t ulong
定义 numth.h:39
mp_size_t lmmp_odd_nPr_ulong_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
mp_size_t lmmp_nPr_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数 ( nPr = n!
mp_size_t lmmp_odd_nPr_uint_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
void lmmp_prime_cache_free_(prime_cache_t *cache)
释放素数表缓存
void lmmp_prime_cache_next_(prime_cache_t *cache)
素数表缓存更新(从小到大遍历全局质数表)
uintp restrict pp
static ulong lmmp_prime_size_(ulong n)
估计 n 范围内的素数数量
const ushort prime_short_table[6542]
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_prime_int_table_init_(uint n)
初始化全局素数表
ushort lmmp_prime_cnt16_(ushort n)
计算小于等于 n 的素数数量
void lmmp_prime_cache_init_(prime_cache_t *cache, uint n)
初始化素数表缓存
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define SALLOC_TYPE(n, type)
#define TEMP_S_DECL
#define TALLOC_TYPE(n, type)
#define TEMP_B_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_S_FREE
#define TEMP_B_FREE