LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
factorial_extra.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#include "impl/tmp_alloc.h"
31#include "lmmp/lmmpn.h"
32#include "lmmp/numth.h"
33
34
35#define MUL(dst, ap, an, bp, bn) \
36 if (an >= bn) \
37 lmmp_mul_(dst, ap, an, bp, bn); \
38 else \
39 lmmp_mul_(dst, bp, bn, ap, an)
40
41// 无分支,_c_为0时可能导致越界写入高位0
42#define mul_1(dst, rn, v) \
43 do { \
44 mp_limb_t _c_ = lmmp_mul_1_(dst, dst, rn, v); \
45 dst[rn] = _c_; \
46 rn += _c_ > 0; \
47 } while (0)
48
50 mp_size_t rn;
51 uint k;
52 if (n < 30) {
53 rn = 64;
54 k = n / 2;
55 if (n % 2 == 0) {
56 *bits = n - lmmp_limb_popcnt_(k);
57 } else {
58 *bits = 0;
59 }
60 } else {
61 // log2(m!) = lgamma(m+1)/ln2
62 const double ln2 = 0.69314718055994531;
63 k = n / 2;
64 if (n % 2 == 0) {
65 // n=2k
66 // n! = (2k)! = 2^k * (k!)
67 rn = k + (mp_size_t)ceil(lgamma((double)k + 1) / ln2);
68 *bits = n - lmmp_limb_popcnt_(k);
69 } else {
70 // n=2k+1
71 // n! = (2k+1)! = (2k+1)! / (2k)!! = (2k+1)! / (2^k * (k!))
72 rn = (mp_size_t)ceil(lgamma((double)n + 1) / ln2);
73 rn -= k + (mp_size_t)floor(lgamma((double)k + 1) / ln2);
74 *bits = 0;
75 }
76 }
77 rn = (rn + LIMB_BITS - 1) / LIMB_BITS + 2; // more two limbs
78 return rn;
79}
80
81/*
82 N N/2 N
83 +--+ / +--+ \ 2 / +--+ \
84 | | P_i ^ (e_i) = | | | P_i ^ (e_i / 2) | * | | | P_i ^ ( e_i mod 2) |
85 | | \ | | / \ | | /
86 i=0 i=0 i=0
87*/
88
90 lmmp_param_assert(dst != NULL && fac != NULL);
91 lmmp_param_assert(rn > 0 && nfactors > 0);
92 if (nfactors <= FACTORS_MUL_N_THRESHOLD && rn < 20) {
93 // 此处额外校验rn的大小,因为hyper阶乘和super阶乘在阶数较小时,仅有很少的因子,但其指数很大
94 // 为了避免算法退化,此处校验rn,仅对rn较小时进行朴素乘法。
95 dst[0] = 1;
96 rn = 1;
97 mp_limb_t t = 1;
98 for (ushort i = 0; i < nfactors; i++) {
99 ushort f = fac[i].f;
100 uint j = fac[i].j;
101 lmmp_debug_assert(j != 0);
102#define MAX_T 0xffffffffffff
103 for (uint e = 0; e < j; e++) {
104 t *= f;
105 if (t > MAX_T) {
106 mul_1(dst, rn, t);
107 t = 1;
108 }
109 }
110 }
111 if (t != 1) {
112 mul_1(dst, rn, t);
113 }
114#undef MAX_T
115 return rn;
116 } else {
117 TEMP_DECL;
118 ushort new_nfactors = 0;
119 ulongp restrict limbs = TALLOC_TYPE(nfactors / 4 + 1, ulong);
120 ulong t = 1;
121 mp_size_t limbn = 0;
122 for (ushort i = 0; i < nfactors; ++i) {
123 ushort f = fac[i].f;
124 uint j = fac[i].j;
125 if (j > 1) {
126 fac[new_nfactors].f = f;
127 fac[new_nfactors++].j = j >> 1;
128 }
129 if (j & 1) {
130 t *= f;
131#define MAX_T 0xffffffffffff
132 if (t > MAX_T) {
133 limbs[limbn++] = t;
134 t = 1;
135 }
136#undef MAX_T
137 }
138 }
139 if (t != 1) {
140 limbs[limbn++] = t;
141 }
142
143 mp_ptr restrict mp = TALLOC_TYPE(limbn * 2, mp_limb_t);
144 mp_size_t mpn = 0;
145
146 if (new_nfactors > 0) {
147 if (limbn > 0) {
148 mpn = lmmp_elem_mul_ulong_(mp, limbs, limbn, mp + limbn);
149 lmmp_debug_assert(rn >= mpn);
150 mp_size_t tn = ((rn - mpn) >> 1) + 1;
151 // 这里根据mpn的大小估计剩余因子乘积的长度,额外分配两倍的tn,以进行平方。
152 mp_ptr restrict tp = BALLOC_TYPE(3 * tn + 3, mp_limb_t);
153 tn = lmmp_factors_mul_ushort_(tp, tn, fac, new_nfactors);
154
155 mp_ptr restrict tp2 = tp + tn + 1;
156 lmmp_sqr_(tp2, tp, tn);
157 tn <<= 1;
158 tn -= tp2[tn - 1] == 0;
159 MUL(dst, tp2, tn, mp, mpn);
160 rn = tn + mpn;
161 rn -= dst[rn - 1] == 0;
162 } else {
163 mp_size_t tn = (rn >> 1) + 1;
165 tn = lmmp_factors_mul_ushort_(tp, tn, fac, new_nfactors);
166 lmmp_sqr_(dst, tp, tn);
167 rn = tn << 1;
168 rn -= dst[rn - 1] == 0;
169 }
170 } else {
171 lmmp_debug_assert(limbn > 0);
172 // 这里不能直接乘入dst,因为dst的大小可能小于limbn,导致溢出
173 if (rn >= limbn) {
174 rn = lmmp_elem_mul_ulong_(dst, limbs, limbn, mp);
175 } else {
176 rn = lmmp_elem_mul_ulong_(mp, limbs, limbn, mp + limbn);
177 lmmp_copy(dst, mp, rn);
178 }
179 }
180 TEMP_FREE;
181 return rn;
182 }
183}
184
185static inline uint count_2facodd_factors(fac_ptr fac, uint nfactors, uint n, uint k, uint p) {
186 uint e = 0;
187 uint pn = n;
188 ulong inv = MP_ULONG_MAX / p + 1;
189 while (pn > 0) {
190 _udiv32by32_q_preinv(pn, pn, inv);
191 e += pn;
192 }
193 pn = k;
194 while (pn > 0) {
195 _udiv32by32_q_preinv(pn, pn, inv);
196 e -= pn;
197 }
198 if (e > 0) {
199 fac[nfactors].f = p;
200 fac[nfactors++].j = e;
201 }
202 return nfactors;
203}
204
205/**
206 * @brief 计算奇数双阶乘(n!!)
207 * @param dst 输出数组
208 * @param rn 输出数组的长度
209 * @param n 奇数,等于2k+1
210 * @param k 双阶乘的参数
211 * @return 输出数组的长度
212 */
214 TEMP_DECL;
215 ushort primen = lmmp_prime_cnt16_(n);
216 ushort nfactors = primen;
217 fac_ptr restrict fac = TALLOC_TYPE(nfactors, fac_t);
218 nfactors = 0;
219 for (ushort i = 1; i < primen; ++i) {
221 nfactors = count_2facodd_factors(fac, nfactors, n, k, p);
222 }
223
224 rn = lmmp_factors_mul_ushort_(dst, rn, fac, nfactors);
225
226 TEMP_FREE;
227 return rn;
228}
229
230/**
231 * @brief 计算奇数双阶乘(n!!)
232 * @param dst 输出数组
233 * @param rn 输出数组的长度
234 * @param n 奇数,等于2k+1
235 * @param k 双阶乘的参数
236 * @return 输出数组的长度
237 */
241 uint nfactors = lmmp_prime_size_(n);
242 fac_ptr restrict fac = BALLOC_TYPE(nfactors, fac_t);
243 nfactors = 0;
244
245 prime_cache_t cache;
246 lmmp_prime_cache_init_(&cache, n);
247 while (cache.is_end == 0) {
249 for (uint i = 0; i < cache.size; i++) {
250 // 对于阶乘n!,对于所有小于等于n的质数,贡献都至少为1
251 nfactors = count_2facodd_factors(fac, nfactors, n, k, cache.pp[i]);
252 }
253 }
255
256 rn = lmmp_factors_mul_(dst, rn, fac, nfactors);
257
259 return rn;
260}
261
263 static const mp_limb_t odd_2factorial_table[17] = {1, 3, 15, 105, 945, 10395, 135135,
264 2027025, 34459425, 654729075,
265 13749310575, 316234143225,
266 7905853580625, 213458046676875,
267 6190283353629375, 191898783962510625,
268 6332659870762850625};
269
270 lmmp_param_assert(dst != NULL);
271 mp_size_t shw = bits / LIMB_BITS;
272 lmmp_param_assert(rn > shw);
273 bits %= LIMB_BITS;
274 lmmp_zero(dst, shw);
275
276 uint k = n / 2;
277 if (n % 2 == 0) {
278 if (k <= MP_USHORT_MAX)
279 rn = lmmp_odd_nPr_ushort_(dst + shw, rn - shw, k, k);
280 else
281 rn = lmmp_odd_factorial_uint_(dst + shw, rn - shw, k);
282 } else {
283 if (k < 17) {
284 dst[shw] = odd_2factorial_table[k];
285 rn = 1;
286 } else if (n <= MP_USHORT_MAX)
287 rn = lmmp_odd_2factorial_ushort_(dst + shw, rn - shw, n, k);
288 else
289 rn = lmmp_odd_2factorial_uint_(dst + shw, rn - shw, n, k);
290 }
291
292 if (bits > 0) {
293 dst[shw + rn] = lmmp_shl_(dst + shw, dst + shw, rn, bits);
294 rn += shw + 1;
295 rn -= dst[rn - 1] == 0;
296 } else {
297 rn += shw;
298 }
299 return rn;
300}
301
303 uint v = 0;
304 uint npi = n / p;
305 uint pi = p;
306 while (npi > 0) {
307 v += pi * npi * (npi + 1) / 2;
308 npi /= p;
309 pi *= p;
310 }
311 return v;
312}
313
315 uint v = 0;
316 uint pi = p;
317 uint N = (uint)n + 1;
318 uint npi = n / pi;
319 while (npi > 0) {
320 v += npi * N - pi * npi * (npi + 1) / 2;
321 pi *= p;
322 npi /= p;
323 }
324 return v;
325}
326
328 if (n == 0 || n == 1) {
329 *bits = 0;
330 return 1;
331 }
332 // A = 1.2824271291006226369 Glaisher–Kinkelin constant
333 const double logA = 0.24875447703378426;
334 const double log2 = 0.69314718055994531; // log(2)
335 double n_sqr = (uint)n * n;
336 double log_n = log(n);
337 double r = 0.5 * n_sqr * log_n - 0.25 * n_sqr + 0.5 * log_n * (double)n + 1.0 / 12.0 * log_n + logA;
338 mp_size_t rn = (mp_size_t)ceil(r / log2);
339 rn = (rn + LIMB_BITS - 1) / LIMB_BITS + 2; // more two limbs
340 *bits = count_hyperfac_factors(n, 2);
341 return rn;
342}
343
345 if (n == 0 || n == 1) {
346 *bits = 0;
347 return 1;
348 }
349 // zeta函数在-1处的导数
350 // zeta(-1) = 1/12 - log(A) // A 即 Glaisher–Kinkelin constant
351 const double zeta_diff_neg1 = -0.16542114370045093;
352 const double log2 = 0.69314718055994531; // log(2)
353 const double log_2pi = 1.83787706640934548; // log(2*pi)
354 double z = (double)n + 1;
355 double z_sqr = z * z;
356 double log_z = log(z);
357 double r = 0.5 * z_sqr * log_z - 0.75 * z_sqr + 0.5 * z * log_2pi - 1.0 / 12.0 * log_z + zeta_diff_neg1;
358 mp_size_t rn = (mp_size_t)ceil(r / log2);
359 rn = (rn + LIMB_BITS - 1) / LIMB_BITS + 2; // more two limbs
360 *bits = count_superfac_factors(n, 2);
361 return rn;
362}
363
365 lmmp_param_assert(dst != NULL);
366 mp_size_t shw = bits / LIMB_BITS;
367 bits %= LIMB_BITS;
368 if (n == 0) {
369 lmmp_debug_assert(shw == 0);
370 dst[0] = 1;
371 return 1;
372 } else if (n <= 8) {
373 lmmp_debug_assert(shw == 0);
374 static const mp_limb_t odd_hyperfac_table[8] = {1, 1, 27, 27, 84375, 61509375, 50655615215625, 50655615215625};
375 dst[0] = odd_hyperfac_table[n - 1];
376 rn = 1;
377 } else {
378 lmmp_zero(dst, shw);
379 TEMP_DECL;
380 ushort primen = lmmp_prime_cnt16_(n);
381 ushort nfactors = primen;
382 fac_ptr restrict fac = TALLOC_TYPE(nfactors, fac_t);
383 nfactors = 0;
384 for (ushort i = 1; i < primen; ++i) {
387 fac[nfactors].f = p;
388 fac[nfactors++].j = j;
389 }
390
391 lmmp_param_assert(rn > shw);
392 rn = lmmp_factors_mul_ushort_(dst + shw, rn - shw, fac, nfactors);
393 TEMP_FREE;
394 }
395 if (bits > 0) {
396 dst[shw + rn] = lmmp_shl_(dst + shw, dst + shw, rn, bits);
397 rn += shw + 1;
398 rn -= dst[rn - 1] == 0;
399 } else {
400 rn += shw;
401 }
402 return rn;
403}
404
406 lmmp_param_assert(dst != NULL);
407 mp_size_t shw = bits / LIMB_BITS;
408 bits %= LIMB_BITS;
409 if (n == 0) {
410 lmmp_debug_assert(shw == 0);
411 dst[0] = 1;
412 return 1;
413 } else if (n <= 8) {
414 lmmp_debug_assert(shw == 0);
415 static const mp_limb_t odd_superfac_table[8] = {1, 1, 3, 9, 135, 6075, 1913625, 602791875};
416 dst[0] = odd_superfac_table[n - 1];
417 rn = 1;
418 } else {
419 lmmp_zero(dst, shw);
420 TEMP_DECL;
421 ushort primen = lmmp_prime_cnt16_(n);
422 ushort nfactors = primen;
423 fac_ptr restrict fac = TALLOC_TYPE(nfactors, fac_t);
424 nfactors = 0;
425 for (ushort i = 1; i < primen; ++i) {
428 fac[nfactors].f = p;
429 fac[nfactors++].j = j;
430 }
431
432 lmmp_param_assert(rn > shw);
433 rn = lmmp_factors_mul_ushort_(dst + shw, rn - shw, fac, nfactors);
434 TEMP_FREE;
435 }
436 if (bits > 0) {
437 dst[shw + rn] = lmmp_shl_(dst + shw, dst + shw, rn, bits);
438 rn += shw + 1;
439 rn -= dst[rn - 1] == 0;
440 } else {
441 rn += shw;
442 }
443 return rn;
444}
445
447 // Chebyshev's estimate
448 // pn# < exp(1.000028*n)
449 const double log2 = 0.69314718055994531; // log(2)
450 double l = 1.000028 * (double)n;
451 l /= log2;
452 mp_size_t rn = (mp_size_t)ceil(l);
453 rn = (rn + LIMB_BITS - 1) / LIMB_BITS + 2; // more two limbs
454 return rn;
455}
456
458 if (n < 2) {
459 dst[0] = 1;
460 return 1;
461 } else if (n <= MP_USHORT_MAX) {
463 ushort primen = lmmp_prime_cnt16_(n);
464 /* 至少4个质数的乘积才可能填满一个limb */
465 ulongp restrict pp = SALLOC_TYPE(primen / 4 + 1, ulong);
466 ulong t = 1;
467 mp_size_t pn = 0;
468 for (ushort i = 0; i < primen; i++) {
469 t *= prime_short_table[i];
470#define MAX_T 0xffffffffffff
471 if (t > MAX_T) {
472 pp[pn++] = t;
473 t = 1;
474 }
475#undef MAX_T
476 }
477 if (t > 1) {
478 pp[pn++] = t;
479 }
480
481 if (rn >= pn) {
483 pn = lmmp_elem_mul_ulong_(dst, pp, pn, tp);
484 } else {
486 pn = lmmp_elem_mul_ulong_(prod, pp, pn, prod + pn);
487 lmmp_debug_assert(rn >= pn);
488 lmmp_copy(dst, prod, pn);
489 }
491 return pn;
492 } else {
495 uint pn = lmmp_prime_size_(n);
496 /* 至少2个质数的乘积才可能填满一个limb */
497 ulongp restrict pp = BALLOC_TYPE(pn / 2 + 1, ulong);
498 pn = 0;
499 ulong t = 2; // 2 is the smallest prime number
500
501 prime_cache_t cache;
502 lmmp_prime_cache_init_(&cache, n);
503 while (cache.is_end == 0) {
505 for (uint i = 0; i < cache.size; i++) {
506 t *= cache.pp[i];
507 if (t > MP_UINT_MAX) {
508 pp[pn++] = t;
509 t = 1;
510 }
511 }
512 }
514
515 if (t > 1) {
516 pp[pn++] = t;
517 }
518
519 if (rn >= pn) {
521 pn = lmmp_elem_mul_ulong_(dst, pp, pn, tp);
522 } else {
524 pn = lmmp_elem_mul_ulong_(prod, pp, pn, prod + pn);
525 lmmp_debug_assert(rn >= pn);
526 lmmp_copy(dst, prod, pn);
527 }
528
530 return pn;
531 }
532}
#define k
#define prod
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(dst, ap, an, bp, bn)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define MAX_T
#define mul_1(dst, rn, v)
static uint count_superfac_factors(ushort n, ushort p)
static mp_size_t lmmp_odd_2factorial_ushort_(mp_ptr restrict dst, mp_size_t rn, ushort n, ushort k)
计算奇数双阶乘(n!
static mp_size_t lmmp_odd_2factorial_uint_(mp_ptr restrict dst, mp_size_t rn, uint n, uint k)
计算奇数双阶乘(n!
static uint count_hyperfac_factors(ushort n, ushort p)
static uint count_2facodd_factors(fac_ptr fac, uint nfactors, uint n, uint k, uint p)
#define lmmp_sqr_
#define lmmp_limb_popcnt_
#define MP_UINT_MAX
#define MP_USHORT_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 t
#define tp
#define n
#define FACTORS_MUL_N_THRESHOLD
mp_size_t lmmp_odd_factorial_uint_(mp_ptr dst, mp_size_t rn, uint n)
计算 n!
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
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_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_hyperfac_size_(ushort n, mp_bitcnt_t *bits)
计算hyper阶乘的 limb 缓冲区长度
uint16_t ushort
定义 numth.h:36
mp_size_t lmmp_primefac_(mp_ptr dst, mp_size_t rn, uint n)
计算质数阶乘(不超过n的质数累乘)
uint64_t ulong
定义 numth.h:39
mp_size_t lmmp_superfac_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ushort n)
计算super阶乘(k!
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