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

浏览该文件的源代码.

宏定义

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

函数

static uint count_2facodd_factors (fac_ptr fac, uint nfactors, uint n, uint k, uint p)
static uint count_hyperfac_factors (ushort n, ushort p)
static uint count_superfac_factors (ushort n, ushort p)
mp_size_t lmmp_2factorial_ (mp_ptr restrict dst, mp_bitcnt_t bits, mp_size_t rn, uint n)
mp_size_t lmmp_2factorial_size_ (uint n, mp_bitcnt_t *restrict bits)
mp_size_t lmmp_factors_mul_ushort_ (mp_ptr restrict dst, mp_size_t rn, fac_ptr restrict fac, ushort nfactors)
mp_size_t lmmp_hyperfac_ (mp_ptr restrict dst, mp_bitcnt_t bits, mp_size_t rn, ushort n)
mp_size_t lmmp_hyperfac_size_ (ushort n, mp_bitcnt_t *restrict bits)
static mp_size_t lmmp_odd_2factorial_uint_ (mp_ptr restrict dst, mp_size_t rn, uint n, uint k)
 计算奇数双阶乘(n!
static mp_size_t lmmp_odd_2factorial_ushort_ (mp_ptr restrict dst, mp_size_t rn, ushort n, ushort k)
 计算奇数双阶乘(n!
mp_size_t lmmp_primefac_ (mp_ptr restrict dst, mp_size_t rn, uint n)
mp_size_t lmmp_primefac_size_ (uint n)
 计算质数阶乘的 limb 缓冲区长度
mp_size_t lmmp_superfac_ (mp_ptr restrict dst, mp_bitcnt_t bits, mp_size_t rn, ushort n)
mp_size_t lmmp_superfac_size_ (ushort n, mp_bitcnt_t *restrict bits)

宏定义说明

◆ MAX_T [1/3]

#define MAX_T   0xffffffffffff

◆ MAX_T [2/3]

#define MAX_T   0xffffffffffff

◆ MAX_T [3/3]

#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_extra.c 第 35 行定义.

◆ 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_extra.c 第 42 行定义.

函数说明

◆ count_2facodd_factors()

uint count_2facodd_factors ( fac_ptr fac,
uint nfactors,
uint n,
uint k,
uint p )
inlinestatic

在文件 factorial_extra.c 第 185 行定义.

185 {
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}
#define k
#define MP_ULONG_MAX
#define _udiv32by32_q_preinv(q, n0, dinv)
#define n
uint32_t uint
定义 numth.h:38
uint64_t ulong
定义 numth.h:39

引用了 _udiv32by32_q_preinv, count_2facodd_factors(), fac_t::f, fac_t::j, k, MP_ULONG_MAX , 以及 n.

被这些函数引用 count_2facodd_factors(), lmmp_odd_2factorial_uint_() , 以及 lmmp_odd_2factorial_ushort_().

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

◆ count_hyperfac_factors()

uint count_hyperfac_factors ( ushort n,
ushort p )
inlinestatic

在文件 factorial_extra.c 第 302 行定义.

302 {
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}

引用了 count_hyperfac_factors() , 以及 n.

被这些函数引用 count_hyperfac_factors(), lmmp_hyperfac_() , 以及 lmmp_hyperfac_size_().

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

◆ count_superfac_factors()

uint count_superfac_factors ( ushort n,
ushort p )
inlinestatic

在文件 factorial_extra.c 第 314 行定义.

314 {
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}

引用了 count_superfac_factors() , 以及 n.

被这些函数引用 count_superfac_factors(), lmmp_superfac_() , 以及 lmmp_superfac_size_().

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

◆ lmmp_2factorial_()

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

在文件 factorial_extra.c 第 262 行定义.

262 {
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}
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!
#define MP_USHORT_MAX
#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
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 排列数的奇数部分

引用了 k, LIMB_BITS, lmmp_2factorial_(), lmmp_odd_2factorial_uint_(), lmmp_odd_2factorial_ushort_(), lmmp_odd_factorial_uint_(), lmmp_odd_nPr_ushort_(), lmmp_param_assert, lmmp_shl_(), lmmp_zero, MP_USHORT_MAX, n , 以及 restrict.

函数调用图:

◆ lmmp_2factorial_size_()

mp_size_t lmmp_2factorial_size_ ( uint n,
mp_bitcnt_t *restrict bits )

在文件 factorial_extra.c 第 49 行定义.

49 {
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}
#define lmmp_limb_popcnt_

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

函数调用图:

◆ lmmp_factors_mul_ushort_()

mp_size_t lmmp_factors_mul_ushort_ ( mp_ptr restrict dst,
mp_size_t rn,
fac_ptr restrict fac,
ushort nfactors )

在文件 factorial_extra.c 第 89 行定义.

89 {
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}
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中
#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_
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
uint16_t ushort
定义 numth.h:36
#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_ushort_(), lmmp_param_assert, lmmp_sqr_, MAX_T, MUL, mul_1, restrict, t, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

函数调用图:

◆ lmmp_hyperfac_()

mp_size_t lmmp_hyperfac_ ( mp_ptr restrict dst,
mp_bitcnt_t bits,
mp_size_t rn,
ushort n )

在文件 factorial_extra.c 第 364 行定义.

364 {
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}
fac_t * fac_ptr
static uint count_hyperfac_factors(ushort n, ushort p)
const ushort prime_short_table[6542]
Copyright (C) 2026 HJimmyK (Jericho Knox)
ushort lmmp_prime_cnt16_(ushort n)
计算小于等于 n 的素数数量

引用了 count_hyperfac_factors(), LIMB_BITS, lmmp_debug_assert, lmmp_factors_mul_ushort_(), lmmp_hyperfac_(), lmmp_param_assert, lmmp_prime_cnt16_(), lmmp_shl_(), lmmp_zero, n, prime_short_table, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

函数调用图:

◆ lmmp_hyperfac_size_()

mp_size_t lmmp_hyperfac_size_ ( ushort n,
mp_bitcnt_t *restrict bits )

在文件 factorial_extra.c 第 327 行定义.

327 {
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}

引用了 count_hyperfac_factors(), LIMB_BITS, lmmp_hyperfac_size_(), n , 以及 restrict.

函数调用图:

◆ lmmp_odd_2factorial_uint_()

mp_size_t lmmp_odd_2factorial_uint_ ( mp_ptr restrict dst,
mp_size_t rn,
uint n,
uint k )
static

计算奇数双阶乘(n!

!)

参数
dst输出数组
rn输出数组的长度
n奇数,等于2k+1
k双阶乘的参数
返回
输出数组的长度

在文件 factorial_extra.c 第 238 行定义.

238 {
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}
mp_size_t lmmp_factors_mul_(mp_ptr dst, mp_size_t rn, fac_ptr fac, uint nfactors)
计算因子的累乘,并将结果放入dst中
static uint count_2facodd_factors(fac_ptr fac, uint nfactors, uint n, uint k, 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_2facodd_factors(), prime_cache_t::is_end, k, lmmp_factors_mul_(), lmmp_odd_2factorial_uint_(), lmmp_prime_cache_free_(), lmmp_prime_cache_init_(), lmmp_prime_cache_next_(), lmmp_prime_int_table_init_(), lmmp_prime_size_(), n, prime_cache_t::pp, restrict, prime_cache_t::size, TEMP_B_DECL , 以及 TEMP_B_FREE.

被这些函数引用 lmmp_2factorial_() , 以及 lmmp_odd_2factorial_uint_().

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

◆ lmmp_odd_2factorial_ushort_()

mp_size_t lmmp_odd_2factorial_ushort_ ( mp_ptr restrict dst,
mp_size_t rn,
ushort n,
ushort k )
static

计算奇数双阶乘(n!

!)

参数
dst输出数组
rn输出数组的长度
n奇数,等于2k+1
k双阶乘的参数
返回
输出数组的长度

在文件 factorial_extra.c 第 213 行定义.

213 {
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}

引用了 count_2facodd_factors(), k, lmmp_factors_mul_ushort_(), lmmp_odd_2factorial_ushort_(), lmmp_prime_cnt16_(), n, prime_short_table, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 lmmp_2factorial_() , 以及 lmmp_odd_2factorial_ushort_().

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

◆ lmmp_primefac_()

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

在文件 factorial_extra.c 第 457 行定义.

457 {
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 prod
#define MP_UINT_MAX
#define SALLOC_TYPE(n, type)
#define TEMP_S_DECL
#define TEMP_S_FREE

引用了 BALLOC_TYPE, prime_cache_t::is_end, lmmp_copy, lmmp_debug_assert, lmmp_elem_mul_ulong_(), lmmp_prime_cache_free_(), lmmp_prime_cache_init_(), lmmp_prime_cache_next_(), lmmp_prime_cnt16_(), lmmp_prime_int_table_init_(), lmmp_prime_size_(), lmmp_primefac_(), MAX_T, MP_UINT_MAX, MP_USHORT_MAX, n, prime_cache_t::pp, prime_short_table, prod, restrict, SALLOC_TYPE, prime_cache_t::size, t, TEMP_B_DECL, TEMP_B_FREE, TEMP_S_DECL, TEMP_S_FREE , 以及 tp.

函数调用图:

◆ lmmp_primefac_size_()

mp_size_t lmmp_primefac_size_ ( uint n)

计算质数阶乘的 limb 缓冲区长度

参数
n质数阶乘的阶数
返回
质数阶乘的 limb 缓冲区长度

在文件 factorial_extra.c 第 446 行定义.

446 {
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}

引用了 LIMB_BITS, lmmp_primefac_size_() , 以及 n.

被这些函数引用 lmmp_primefac_size_(), lmmp_superfac_(), small_factor_q() , 以及 TEST_CASE().

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

◆ lmmp_superfac_()

mp_size_t lmmp_superfac_ ( mp_ptr restrict dst,
mp_bitcnt_t bits,
mp_size_t rn,
ushort n )

在文件 factorial_extra.c 第 405 行定义.

405 {
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}
static uint count_superfac_factors(ushort n, ushort p)

引用了 count_superfac_factors(), LIMB_BITS, lmmp_debug_assert, lmmp_factors_mul_ushort_(), lmmp_param_assert, lmmp_prime_cnt16_(), lmmp_shl_(), lmmp_superfac_(), lmmp_zero, n, prime_short_table, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

函数调用图:

◆ lmmp_superfac_size_()

mp_size_t lmmp_superfac_size_ ( ushort n,
mp_bitcnt_t *restrict bits )

在文件 factorial_extra.c 第 344 行定义.

344 {
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}

引用了 count_superfac_factors(), LIMB_BITS, lmmp_superfac_size_(), n , 以及 restrict.

函数调用图: