LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
factorial.c 文件参考
#include <math.h>
#include "numth/ele_mul.h"
#include "impl/inlines.h"
#include "mparam.h"
#include "impl/prime_table.h"
#include "impl/tmp_alloc.h"
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
factorial.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define MAX_T   0xffffffffffff
#define MUL(dst, ap, an, bp, bn)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define mul_1(dst, rn, v)

函数

static void count_factors (fac_ptr fac, uint nfactors, uint n, uint p)
mp_size_t lmmp_factorial_ (mp_ptr restrict dst, mp_bitcnt_t bits, mp_size_t rn, uint n)
mp_size_t lmmp_factorial_size_ (uint n, mp_bitcnt_t *restrict bits)
mp_size_t lmmp_factors_mul_ (mp_ptr restrict dst, mp_size_t rn, fac_ptr restrict fac, uint nfactors)
mp_size_t lmmp_odd_factorial_uint_ (mp_ptr restrict dst, mp_size_t rn, uint n)

宏定义说明

◆ MAX_T

#define MAX_T   0xffffffffffff

◆ MUL

#define MUL ( dst,
ap,
an,
bp,
bn )
值:
if (an >= bn) \
lmmp_mul_(dst, ap, an, bp, bn); \
else \
lmmp_mul_(dst, bp, bn, ap, an)
#define an
#define bn

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 factorial.c 第 34 行定义.

被这些函数引用 lmmp_factors_mul_() , 以及 lmmp_factors_mul_ushort_().

◆ mul_1

#define mul_1 ( dst,
rn,
v )
值:
do { \
mp_limb_t _c_ = lmmp_mul_1_(dst, dst, rn, v); \
dst[rn] = _c_; \
rn += _c_ > 0; \
} while (0)
uint64_t mp_limb_t
定义 lmmp.h:92
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

在文件 factorial.c 第 41 行定义.

被这些函数引用 lmmp_factors_mul_(), lmmp_factors_mul_ushort_(), lmmp_odd_nCr_uint_(), lmmp_odd_nCr_ushort_(), lmmp_odd_nPr_uint_(), lmmp_odd_nPr_ulong_() , 以及 lmmp_odd_nPr_ushort_().

函数说明

◆ count_factors()

void count_factors ( fac_ptr fac,
uint nfactors,
uint n,
uint p )
inlinestatic

在文件 factorial.c 第 163 行定义.

163 {
164 uint pn = n;
165 uint e = 0;
166 while (pn > 0) {
167 pn /= p;
168 e += pn;
169 }
170 fac[nfactors].f = p;
171 fac[nfactors].j = e;
172}
#define n
uint32_t uint
定义 numth.h:38

引用了 count_factors(), fac_t::f, fac_t::j , 以及 n.

被这些函数引用 count_factors(), count_factors(), count_factors(), count_factors(), lmmp_odd_factorial_uint_(), lmmp_odd_multinomial_uint_(), lmmp_odd_multinomial_ushort_(), lmmp_odd_nCr_uint_(), lmmp_odd_nCr_ushort_(), lmmp_odd_nPr_uint_() , 以及 lmmp_odd_nPr_ushort_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_factorial_()

mp_size_t lmmp_factorial_ ( mp_ptr restrict dst,
mp_bitcnt_t bits,
mp_size_t rn,
uint n )

在文件 factorial.c 第 202 行定义.

202 {
203 lmmp_param_assert(dst != NULL);
204 mp_size_t shw = bits / LIMB_BITS;
205 lmmp_param_assert(rn > shw);
206 bits %= LIMB_BITS;
207 lmmp_zero(dst, shw);
208
209 if (n <= NPR_SHORT_LIMIT)
210 rn = lmmp_odd_nPr_ushort_(dst + shw, rn - shw, n, n);
211 else
212 rn = lmmp_odd_factorial_uint_(dst + shw, rn - shw, n);
213
214 if (bits > 0) {
215 dst[shw + rn] = lmmp_shl_(dst + shw, dst + shw, rn, bits);
216 rn += shw + 1;
217 rn -= dst[rn - 1] == 0;
218 } else {
219 rn += shw;
220 }
221 return rn;
222}
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
#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 NPR_SHORT_LIMIT
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 排列数的奇数部分

引用了 LIMB_BITS, lmmp_factorial_(), lmmp_odd_factorial_uint_(), lmmp_odd_nPr_ushort_(), lmmp_param_assert, lmmp_shl_(), lmmp_zero, n, NPR_SHORT_LIMIT , 以及 restrict.

函数调用图:

◆ lmmp_factorial_size_()

mp_size_t lmmp_factorial_size_ ( uint n,
mp_bitcnt_t *restrict bits )

在文件 factorial.c 第 48 行定义.

48 {
49 mp_size_t rn;
50 if (n < 20) {
51 rn = 64;
52 } else {
53 // n!的位数为ceil(log2(n!)),log2(n!) = lgamma(n+1)/ln2
54 const double ln2 = 0.69314718055994531;
55 rn = (mp_size_t)ceil(lgamma((double)n + 1) / ln2);
56 }
57 rn = (rn + LIMB_BITS - 1) / LIMB_BITS + 2; // more two limbs
58 *bits = n - lmmp_limb_popcnt_(n);
59 return rn;
60}
#define lmmp_limb_popcnt_

引用了 LIMB_BITS, lmmp_factorial_size_(), lmmp_limb_popcnt_, n , 以及 restrict.

函数调用图:

◆ lmmp_factors_mul_()

mp_size_t lmmp_factors_mul_ ( mp_ptr restrict dst,
mp_size_t rn,
fac_ptr restrict fac,
uint nfactors )

在文件 factorial.c 第 70 行定义.

70 {
71 lmmp_param_assert(dst != NULL && fac != NULL);
72 lmmp_param_assert(rn > 0 && nfactors > 0);
73 if (nfactors <= FACTORS_MUL_N_THRESHOLD) {
74 // 绝大多数情况下,大的质因数的指数都很小,所以这里只需要考虑小的质因数。
75 dst[0] = 1;
76 rn = 1;
77 mp_limb_t t = 1;
78 for (uint i = 0; i < nfactors; i++) {
79 uint f = fac[i].f;
80 uint j = fac[i].j;
81 lmmp_debug_assert(j != 0 && f <= MP_USHORT_MAX);
82#define MAX_T 0xffffffffffff
83 for (uint e = 0; e < j; e++) {
84 t *= f;
85 if (t > MAX_T) {
86 mul_1(dst, rn, t);
87 t = 1;
88 }
89 }
90 }
91 if (t != 1) {
92 mul_1(dst, rn, t);
93 }
94#undef MAX_T
95 return rn;
96 } else {
98 uint new_nfactors = 0;
99 ulongp restrict limbs = TALLOC_TYPE(nfactors / 2 + 1, ulong);
100 ulong t = 1;
101 mp_size_t limbn = 0;
102 for (uint i = 0; i < nfactors; ++i) {
103 uint f = fac[i].f;
104 uint j = fac[i].j;
105 if (j > 1) {
106 fac[new_nfactors].f = f;
107 fac[new_nfactors++].j = j >> 1;
108 }
109 if (j & 1) {
110 t *= f;
111 if (t > MP_UINT_MAX) {
112 limbs[limbn++] = t;
113 t = 1;
114 }
115 }
116 }
117 if (t != 1) {
118 limbs[limbn++] = t;
119 }
120
121 mp_ptr restrict mp = TALLOC_TYPE(limbn * 2, mp_limb_t);
122 mp_size_t mpn = 0;
123
124 if (new_nfactors > 0) {
125 if (limbn > 0) {
126 mpn = lmmp_elem_mul_ulong_(mp, limbs, limbn, mp + limbn);
127 lmmp_debug_assert(rn >= mpn);
128 mp_size_t tn = ((rn - mpn) >> 1) + 1;
129 // 这里根据mpn的大小估计剩余因子乘积的长度,额外分配两倍的tn,以进行平方。
130 mp_ptr restrict tp = BALLOC_TYPE(3 * tn + 3, mp_limb_t);
131 tn = lmmp_factors_mul_(tp, tn, fac, new_nfactors);
132
133 mp_ptr restrict tp2 = tp + tn + 1;
134 lmmp_sqr_(tp2, tp, tn);
135 tn <<= 1;
136 tn -= tp2[tn - 1] == 0;
137 MUL(dst, tp2, tn, mp, mpn);
138 rn = tn + mpn;
139 rn -= dst[rn - 1] == 0;
140 } else {
141 mp_size_t tn = (rn >> 1) + 1;
143 tn = lmmp_factors_mul_(tp, tn, fac, new_nfactors);
144 lmmp_sqr_(dst, tp, tn);
145 rn = tn << 1;
146 rn -= dst[rn - 1] == 0;
147 }
148 } else {
149 lmmp_debug_assert(limbn > 0);
150 // 这里不能直接乘入dst,因为dst的大小可能小于limbn,导致溢出
151 if (rn >= limbn) {
152 rn = lmmp_elem_mul_ulong_(dst, limbs, limbn, mp);
153 } else {
154 rn = lmmp_elem_mul_ulong_(mp, limbs, limbn, mp + limbn);
155 lmmp_copy(dst, mp, rn);
156 }
157 }
158 TEMP_FREE;
159 return rn;
160 }
161}
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_(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)
#define lmmp_sqr_
#define MP_UINT_MAX
#define MP_USHORT_MAX
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define t
#define tp
#define FACTORS_MUL_N_THRESHOLD
uint64_t * ulongp
定义 numth.h:48
uint64_t ulong
定义 numth.h:39
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)
#define BALLOC_TYPE(n, type)

引用了 BALLOC_TYPE, FACTORS_MUL_N_THRESHOLD, lmmp_copy, lmmp_debug_assert, lmmp_elem_mul_ulong_(), lmmp_factors_mul_(), lmmp_param_assert, lmmp_sqr_, MAX_T, MP_UINT_MAX, MP_USHORT_MAX, MUL, mul_1, restrict, t, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

函数调用图:

◆ lmmp_odd_factorial_uint_()

mp_size_t lmmp_odd_factorial_uint_ ( mp_ptr restrict dst,
mp_size_t rn,
uint n )

在文件 factorial.c 第 174 行定义.

174 {
175 lmmp_param_assert(dst != NULL);
176 lmmp_param_assert(rn > 0);
178
181 uint nfactors = lmmp_prime_size_(n);
182 fac_ptr restrict fac = BALLOC_TYPE(nfactors, fac_t);
183 nfactors = 0;
184
185 prime_cache_t cache;
186 lmmp_prime_cache_init_(&cache, n);
187 while (cache.is_end == 0) {
189 for (uint i = 0; i < cache.size; i++) {
190 // 对于阶乘n!,对于所有小于等于n的质数,贡献都至少为1
191 count_factors(fac, nfactors++, n, cache.pp[i]);
192 }
193 }
195
196 rn = lmmp_factors_mul_(dst, rn, fac, nfactors);
197
199 return rn;
200}
fac_t * fac_ptr
static void count_factors(fac_ptr fac, uint nfactors, uint n, uint p)
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 范围内的素数数量
void lmmp_prime_int_table_init_(uint n)
初始化全局素数表
void lmmp_prime_cache_init_(prime_cache_t *cache, uint n)
初始化素数表缓存
#define TEMP_B_DECL
#define TEMP_B_FREE

引用了 BALLOC_TYPE, count_factors(), prime_cache_t::is_end, lmmp_factors_mul_(), lmmp_odd_factorial_uint_(), lmmp_param_assert, lmmp_prime_cache_free_(), lmmp_prime_cache_init_(), lmmp_prime_cache_next_(), lmmp_prime_int_table_init_(), lmmp_prime_size_(), MP_USHORT_MAX, n, prime_cache_t::pp, restrict, prime_cache_t::size, TEMP_B_DECL , 以及 TEMP_B_FREE.

函数调用图: