LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
nCr.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 "lmmp/numth.h"
nCr.c 的引用(Include)关系图:

浏览该文件的源代码.

结构体

struct  bino_choose_t

宏定义

#define div_1(dst, rn, v)
#define mul_1(dst, rn, v)

函数

static uint count_factors (fac_ptr fac, uint nfactors, uint n, uint r, uint nr, uint p)
static uint factor_size_int (mp_size_t rn, uint n)
static ushort factor_size_short (mp_size_t rn)
mp_size_t lmmp_nCr_ (mp_ptr restrict dst, mp_bitcnt_t bits, mp_size_t rn, uint n, uint r)
mp_size_t lmmp_nCr_size_ (uint n, uint r, mp_bitcnt_t *restrict bits)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
static mp_size_t lmmp_odd_factorial_ (mp_ptr restrict dst, mp_size_t rn, uint n)
static mp_size_t lmmp_odd_nCr_div_ (mp_ptr restrict dst, mp_size_t rn, bino_choose_t *restrict ctx)
mp_size_t lmmp_odd_nCr_uint_ (mp_ptr restrict dst, mp_size_t rn, uint n, uint r)
mp_size_t lmmp_odd_nCr_ushort_ (mp_ptr restrict dst, mp_size_t rn, uint n, uint r)
static mp_size_t lmmp_odd_nPr_product_ (mp_ptr restrict dst, mp_size_t rn, uint n, uint r)
 使用累乘函数计算nPr(奇数部分)

结构体说明

◆ bino_choose_t

struct bino_choose_t

在文件 nCr.c 第 175 行定义.

bino_choose_t 的协作图:
成员变量
mp_bitcnt_t fac_bits
mp_size_t fac_n
uint n
mp_bitcnt_t nPr_bits
mp_size_t nPr_n
uint r

宏定义说明

◆ div_1

#define div_1 ( dst,
rn,
v )
值:
do { \
lmmp_divexact_1_(dst, dst, rn, v, _dinv_); \
rn -= dst[rn - 1] == 0; \
} while (0)
uint64_t mp_limb_t
定义 lmmp.h:92
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元

在文件 nCr.c 第 74 行定义.

被这些函数引用 lmmp_odd_nCr_uint_() , 以及 lmmp_odd_nCr_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)
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

在文件 nCr.c 第 67 行定义.

函数说明

◆ count_factors()

uint count_factors ( fac_ptr fac,
uint nfactors,
uint n,
uint r,
uint nr,
uint p )
inlinestatic

在文件 nCr.c 第 108 行定义.

108 {
109 uint pn = n;
110 uint e = 0;
111 ulong inv = MP_ULONG_MAX / p + 1;
112 while (pn > 0) {
113 _udiv32by32_q_preinv(pn, pn, inv);
114 e += pn;
115 }
116 pn = r;
117 while (pn > 0) {
118 _udiv32by32_q_preinv(pn, pn, inv);
119 e -= pn;
120 }
121 pn = nr;
122 while (pn > 0) {
123 _udiv32by32_q_preinv(pn, pn, inv);
124 e -= pn;
125 }
126 if (e > 0) {
127 fac[nfactors].f = p;
128 fac[nfactors++].j = e;
129 }
130 return nfactors;
131}
#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_factors(), fac_t::f, fac_t::j, MP_ULONG_MAX , 以及 n.

函数调用图:

◆ factor_size_int()

uint factor_size_int ( mp_size_t rn,
uint n )
inlinestatic

在文件 nCr.c 第 81 行定义.

81 {
82 /*
83 我们可以知道,nCr的大小一定不会超过B^rn,因此,B^rn的可以含有的质因数数量即为nCr可以含有的质因数数量的上限。
84 同时,我们这里只计算的是奇数部分,比如我们可以用B^rn可以含有的3的质因数个数来估计nCr的质因数种类数,
85 这是一个绝对上界,同时在不平衡时比pi(n)这个平方上界要紧得多。当然即使是这个上界,实际的质因数个数也可能远远
86 小于这个上界。一个改进想法是,我们使用更大一点的质数,对于n>0xffff,我们选取这个质数为251,
87 而log(B)/log(251)约等于8.02855802854906,我们近似视为8,这也是这里的常数的由来,当然,此估计可能存在低估,
88 但是经过大量的校验,我们未发现任何低估的反例。
89 为了同时处理不平衡与不平衡的情况,我们这里对两个估计进行比较,取较小的一个作为最终结果。不平衡时,approx1要更紧一些。
90 */
91 // 此处假定了LIMB_BITS为64
92 ulong approx1 = rn * 8;
94 ulong approx2 = lmmp_prime_size_(n);
95 return approx1 < approx2 ? approx1 : approx2;
96}
#define MP_UINT_MAX
#define lmmp_debug_assert(x)
定义 lmmp.h:498
static ulong lmmp_prime_size_(ulong n)
估计 n 范围内的素数数量

引用了 factor_size_int(), lmmp_debug_assert, lmmp_prime_size_(), MP_UINT_MAX , 以及 n.

函数调用图:

◆ factor_size_short()

ushort factor_size_short ( mp_size_t rn)
inlinestatic

在文件 nCr.c 第 98 行定义.

98 {
99 /*
100 经过大量的校验,*8即使是在ushort输入下,也未见低估,但是为了留有冗余,我们还是选择*10,大致相当于质数83。
101 */
102 // 此处假定了LIMB_BITS为64
103 uint approx1 = rn * 10;
105 return (ushort)approx1;
106}
#define MP_USHORT_MAX
uint16_t ushort
定义 numth.h:36

引用了 factor_size_short(), lmmp_debug_assert , 以及 MP_USHORT_MAX.

函数调用图:

◆ lmmp_nCr_()

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

在文件 nCr.c 第 348 行定义.

348 {
349 lmmp_param_assert(r <= (n / 2));
350 lmmp_param_assert(dst != NULL);
351 mp_size_t shw = bits / LIMB_BITS;
352 lmmp_param_assert(rn > shw);
353
354 bits %= LIMB_BITS;
355 lmmp_zero(dst, shw);
356
357 if (n <= NCR_SHORT_LIMIT)
358 rn = lmmp_odd_nCr_ushort_(dst + shw, rn - shw, n, r);
359 else
360 rn = lmmp_odd_nCr_uint_(dst + shw, rn - shw, n, r);
361
362 if (bits > 0) {
363 dst[shw + rn] = lmmp_shl_(dst + shw, dst + shw, rn, bits);
364 rn += shw + 1;
365 rn -= dst[rn - 1] == 0;
366 } else {
367 rn += shw;
368 }
369 return rn;
370}
#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 NCR_SHORT_LIMIT
mp_size_t lmmp_odd_nCr_uint_(mp_ptr dst, mp_size_t rn, uint n, uint r)
计算 nCr 组合数的奇数部分
mp_size_t lmmp_odd_nCr_ushort_(mp_ptr dst, mp_size_t rn, uint n, uint r)
计算 nCr 组合数的奇数部分

引用了 LIMB_BITS, lmmp_nCr_(), lmmp_odd_nCr_uint_(), lmmp_odd_nCr_ushort_(), lmmp_param_assert, lmmp_shl_(), lmmp_zero, n, NCR_SHORT_LIMIT , 以及 restrict.

函数调用图:

◆ lmmp_nCr_size_()

mp_size_t lmmp_nCr_size_ ( uint n,
uint r,
mp_bitcnt_t *restrict bits )

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

在文件 nCr.c 第 33 行定义.

33 {
34 lmmp_param_assert(r <= n / 2);
35 lmmp_param_assert(bits != NULL);
36 // nCr = n!/(r!*(n-r)!),分子ceil、分母floor保证不低估
37 // log2(m!) = lgamma(m+1)/ln2
38 const double ln2 = 0.69314718055994531;
39 mp_size_t rn;
40 if (r < 4 || n < ODD_FACTORIAL_SIZE) {
41 rn = 3;
42 } else if (n == MP_UINT_MAX) {
43 uint mean = n - r / 2 + 1;
44 mp_size_t l1, l2;
45 l1 = lmmp_pow_1_size_(mean, r);
46 l2 = (mp_size_t)floor(lgamma((double)r + 1) / ln2);
47 l2 /= LIMB_BITS;
48 rn = l1 - l2;
49 } else {
50 mp_size_t l1, l2, l3;
51 l1 = (mp_size_t)ceil(lgamma((double)n + 1) / ln2);
52 l2 = (mp_size_t)floor(lgamma((double)r + 1) / ln2);
53 if (n - r < ODD_FACTORIAL_SIZE)
54 l3 = 0;
55 else
56 l3 = (mp_size_t)floor(lgamma((double)(n - r) + 1) / ln2);
57 rn = l1 - l2 - l3;
58 rn = (rn + LIMB_BITS - 1) / LIMB_BITS;
59 }
60 (*bits) = n - lmmp_limb_popcnt_(n);
61 (*bits) -= r - lmmp_limb_popcnt_(r);
62 (*bits) -= n - r - lmmp_limb_popcnt_(n - r);
63 return rn + 2; // more 2 limb
64}
#define lmmp_limb_popcnt_
#define ODD_FACTORIAL_SIZE
mp_size_t lmmp_pow_1_size_(mp_limb_t base, ulong exp)
计算幂次方需要的limb缓冲区长度 base ^ exp
定义 pow.c:65

引用了 LIMB_BITS, lmmp_limb_popcnt_, lmmp_nCr_size_(), lmmp_param_assert, lmmp_pow_1_size_(), MP_UINT_MAX, n, ODD_FACTORIAL_SIZE , 以及 restrict.

函数调用图:

◆ lmmp_odd_factorial_()

mp_size_t lmmp_odd_factorial_ ( mp_ptr restrict dst,
mp_size_t rn,
uint n )
inlinestatic

在文件 nCr.c 第 168 行定义.

168 {
169 if (n <= NPR_SHORT_LIMIT)
170 return lmmp_odd_nPr_ushort_(dst, rn, n, n);
171 else
172 return lmmp_odd_factorial_uint_(dst, rn, n);
173}
#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 排列数的奇数部分

引用了 lmmp_odd_factorial_(), lmmp_odd_factorial_uint_(), lmmp_odd_nPr_ushort_(), n, NPR_SHORT_LIMIT , 以及 restrict.

被这些函数引用 lmmp_odd_factorial_() , 以及 lmmp_odd_nCr_div_().

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

◆ lmmp_odd_nCr_div_()

mp_size_t lmmp_odd_nCr_div_ ( mp_ptr restrict dst,
mp_size_t rn,
bino_choose_t *restrict ctx )
static

在文件 nCr.c 第 184 行定义.

184 {
185 lmmp_param_assert(rn > 0 && dst != NULL);
186 TEMP_DECL;
187
189 mp_size_t shw1 = ctx->nPr_bits / LIMB_BITS;
190 mp_size_t nPr_n = lmmp_odd_nPr_product_(nPr, ctx->nPr_n - shw1, ctx->n, ctx->r);
191
192 mp_size_t shw2 = ctx->fac_bits / LIMB_BITS;
194 mp_size_t fac_n = lmmp_odd_factorial_(fac, ctx->fac_n - shw2, ctx->r);
195
196 lmmp_debug_assert(rn >= nPr_n - fac_n + 1);
197 lmmp_divexact_(dst, nPr, nPr_n, fac, fac_n);
198 rn = nPr_n - fac_n + 1;
199 rn -= dst[rn - 1] == 0;
200 TEMP_FREE;
201 return rn;
202}
mp_limb_t * mp_ptr
定义 lmmp.h:96
mp_bitcnt_t nPr_bits
定义 nCr.c:178
static mp_size_t lmmp_odd_nPr_product_(mp_ptr restrict dst, mp_size_t rn, uint n, uint r)
使用累乘函数计算nPr(奇数部分)
定义 nCr.c:136
mp_size_t fac_n
定义 nCr.c:177
mp_size_t nPr_n
定义 nCr.c:176
static mp_size_t lmmp_odd_factorial_(mp_ptr restrict dst, mp_size_t rn, uint n)
定义 nCr.c:168
mp_bitcnt_t fac_bits
定义 nCr.c:179
void lmmp_divexact_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 LIMB_BITS, lmmp_debug_assert, lmmp_divexact_(), lmmp_odd_factorial_(), lmmp_odd_nCr_div_(), lmmp_odd_nPr_product_(), lmmp_param_assert, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 lmmp_odd_nCr_div_() , 以及 lmmp_odd_nCr_uint_().

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

◆ lmmp_odd_nCr_uint_()

mp_size_t lmmp_odd_nCr_uint_ ( mp_ptr restrict dst,
mp_size_t rn,
uint n,
uint r )

在文件 nCr.c 第 274 行定义.

274 {
275 lmmp_param_assert(r <= (n / 2));
276 lmmp_param_assert(rn > 0 && dst != NULL);
277 if (r <= 3 || (n > 0xfffffff && rn < BINOMIAL_RN_BASECASE_THRESHOLD)) {
278 dst[0] = 1;
279 rn = 1;
280 ulong t, v;
281 mp_bitcnt_t cnt;
282 for (ulong i = 1; i <= r; ++i) {
283 t = n - i + 1;
284 ctz_shr_u64(v, t, cnt);
285 mul_1(dst, rn, v);
286 ctz_shr_u64(v, i, cnt);
287 div_1(dst, rn, v);
288 }
289 return rn;
290 } else if (rn < BINOMIAL_RN_BASECASE_THRESHOLD) {
291 dst[0] = 1;
292 rn = 1;
293 ulong i = 1;
294 ulong t = 1, d = 1, v;
295 mp_bitcnt_t cnt;
296 for (; i <= (ulong)r - 2; i += 2) {
297 d = i * (i + 1);
298 t = (n - i + 1) * (n - i);
299 ctz_shr_u64(v, t, cnt);
300 mul_1(dst, rn, v);
301 ctz_shr_u64(v, d, cnt);
302 div_1(dst, rn, v);
303 }
304 for (; i <= r; ++i) {
305 t = n - i + 1;
306 ctz_shr_u64(v, t, cnt);
307 mul_1(dst, rn, v);
308 ctz_shr_u64(v, i, cnt);
309 div_1(dst, rn, v);
310 }
311 return rn;
312 } else {
313 bino_choose_t ctx;
314 ctx.nPr_n = lmmp_nPr_size_(n, r, &ctx.nPr_bits);
315 ctx.fac_n = lmmp_factorial_size_(r, &ctx.fac_bits);
317 /* 这个调优值是在近似忽略了质数表的初始化开销,主要瓶颈集中在质数表的遍历的情况下测得的 */
318 /* 因此,当质数表未初始化时,这个调优值将无法代表真实性能边界 */
319 ctx.n = n;
320 ctx.r = r;
321 return lmmp_odd_nCr_div_(dst, rn, &ctx);
322 } else {
325 uint nfactors = factor_size_int(rn, n);
326 fac_ptr restrict fac = BALLOC_TYPE(nfactors, fac_t);
327 uint nr = n - r;
328
329 nfactors = 0;
330 prime_cache_t cache;
331 lmmp_prime_cache_init_(&cache, n);
332 while (cache.is_end == 0) {
334 for (uint i = 0; i < cache.size; ++i) {
335 nfactors = count_factors(fac, nfactors, n, r, nr, cache.pp[i]);
336 }
337 }
339
340 rn = lmmp_factors_mul_(dst, rn, fac, nfactors);
341
343 return rn;
344 }
345 }
346}
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)
size_t mp_bitcnt_t
定义 lmmp.h:98
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define t
static uint factor_size_int(mp_size_t rn, uint n)
static mp_size_t lmmp_odd_nCr_div_(mp_ptr restrict dst, mp_size_t rn, bino_choose_t *restrict ctx)
定义 nCr.c:184
#define div_1(dst, rn, v)
定义 nCr.c:74
#define BINOMIAL_DIV_B_THRESHOLD
#define BINOMIAL_RN_BASECASE_THRESHOLD
#define BINOMIAL_DIV_K_THRESHOLD
mp_size_t lmmp_factorial_size_(uint n, mp_bitcnt_t *bits)
计算 n!
mp_size_t lmmp_nPr_size_(ulong n, ulong r, mp_bitcnt_t *bits)
计算 nPr 排列数的 limb 缓冲区长度
void lmmp_prime_cache_free_(prime_cache_t *cache)
释放素数表缓存
void lmmp_prime_cache_next_(prime_cache_t *cache)
素数表缓存更新(从小到大遍历全局质数表)
uintp restrict pp
void lmmp_prime_int_table_init_(uint n)
初始化全局素数表
void lmmp_prime_cache_init_(prime_cache_t *cache, uint n)
初始化素数表缓存
#define TEMP_B_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_B_FREE

引用了 BALLOC_TYPE, BINOMIAL_DIV_B_THRESHOLD, BINOMIAL_DIV_K_THRESHOLD, BINOMIAL_RN_BASECASE_THRESHOLD, count_factors(), ctz_shr_u64, div_1, bino_choose_t::fac_bits, bino_choose_t::fac_n, factor_size_int(), prime_cache_t::is_end, lmmp_factorial_size_(), lmmp_factors_mul_(), lmmp_nPr_size_(), lmmp_odd_nCr_div_(), lmmp_odd_nCr_uint_(), lmmp_param_assert, lmmp_prime_cache_free_(), lmmp_prime_cache_init_(), lmmp_prime_cache_next_(), lmmp_prime_int_table_init_(), mul_1, bino_choose_t::n, n, bino_choose_t::nPr_bits, bino_choose_t::nPr_n, prime_cache_t::pp, bino_choose_t::r, restrict, prime_cache_t::size, t, TEMP_B_DECL , 以及 TEMP_B_FREE.

函数调用图:

◆ lmmp_odd_nCr_ushort_()

mp_size_t lmmp_odd_nCr_ushort_ ( mp_ptr restrict dst,
mp_size_t rn,
uint n,
uint r )

在文件 nCr.c 第 204 行定义.

204 {
206 lmmp_param_assert(rn > 0 && dst != NULL);
207 lmmp_param_assert(r <= n / 2);
208 if (r < ODD_FACTORIAL_SIZE) {
209 rn = lmmp_odd_nPr_ushort_(dst, rn, n, r);
210 mp_limb_t t = 0;
211 lmmp_odd_nPr_ushort_(&t, 1, r, r);
212 div_1(dst, rn, t);
213 return rn;
214 } else if (rn < BINOMIAL_RN_BASECASE_THRESHOLD) {
215 if (r <= 4 || n > 0xfff) {
216 dst[0] = 1;
217 rn = 1;
218 ulong t, v;
219 mp_bitcnt_t cnt;
220 for (ulong i = 1; i <= r; ++i) {
221 t = n - i + 1;
222 ctz_shr_u64(v, t, cnt);
223 mul_1(dst, rn, v);
224 ctz_shr_u64(v, i, cnt);
225 div_1(dst, rn, v);
226 }
227 return rn;
228 } else {
229 dst[0] = 1;
230 rn = 1;
231 ulong i = 1;
232 ulong t = 1, d = 1, v;
233 mp_bitcnt_t cnt;
234 for (; i <= (ulong)r - 4; i += 4) {
235 // 相邻四个数必含有3这个公共因子
236 d = i * (i + 1) * (i + 2) * (i + 3);
237 d /= 3;
238 t = (n - i + 1) * (n - i) * (n - i - 1) * (n - i - 2);
239 t /= 3;
240 ctz_shr_u64(v, t, cnt);
241 mul_1(dst, rn, v);
242 ctz_shr_u64(v, d, cnt);
243 div_1(dst, rn, v);
244 }
245 for (; i <= r; ++i) {
246 t = n - i + 1;
247 ctz_shr_u64(v, t, cnt);
248 mul_1(dst, rn, v);
249 ctz_shr_u64(v, i, cnt);
250 div_1(dst, rn, v);
251 }
252 return rn;
253 }
254 } else {
255 TEMP_DECL;
256 ushort primen = lmmp_prime_cnt16_(n);
257 ushort nfactors = factor_size_short(rn);
258 nfactors = primen < nfactors ? primen : nfactors;
259 fac_ptr restrict fac = TALLOC_TYPE(nfactors, fac_t);
260 ushort nr = n - r;
261 nfactors = 0;
262 for (ushort i = 1; i < primen; ++i) {
264 nfactors = count_factors(fac, nfactors, n, r, nr, p);
265 }
266
267 rn = lmmp_factors_mul_ushort_(dst, rn, fac, nfactors);
268
269 TEMP_FREE;
270 return rn;
271 }
272}
mp_size_t lmmp_factors_mul_ushort_(mp_ptr dst, mp_size_t rn, fac_ptr fac, ushort nfactors)
计算因子的累乘,并将结果放入dst中
static ushort factor_size_short(mp_size_t rn)
const ushort prime_short_table[6542]
Copyright (C) 2026 HJimmyK (Jericho Knox)
ushort lmmp_prime_cnt16_(ushort n)
计算小于等于 n 的素数数量

引用了 BINOMIAL_RN_BASECASE_THRESHOLD, count_factors(), ctz_shr_u64, div_1, factor_size_short(), lmmp_factors_mul_ushort_(), lmmp_odd_nCr_ushort_(), lmmp_odd_nPr_ushort_(), lmmp_param_assert, lmmp_prime_cnt16_(), MP_USHORT_MAX, mul_1, n, ODD_FACTORIAL_SIZE, prime_short_table, restrict, t, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

函数调用图:

◆ lmmp_odd_nPr_product_()

mp_size_t lmmp_odd_nPr_product_ ( mp_ptr restrict dst,
mp_size_t rn,
uint n,
uint r )
static

使用累乘函数计算nPr(奇数部分)

在文件 nCr.c 第 136 行定义.

136 {
137 TEMP_DECL;
138 ulongp restrict limbs = TALLOC_TYPE(r / 2 + 1, ulong);
139 mp_size_t limbn = 0;
140 ulong t = 1;
141 uint v;
142 mp_bitcnt_t cnt = 0;
143 // 需注意 n==UINT_MAX 的情况
144 uint ibase = n - r + 1;
145 for (uint k = 0; k < r; ++k) {
146 ctz_shr_u32(v, ibase + k, cnt);
147 t *= v;
148 if (t > MP_UINT_MAX) {
149 limbs[limbn++] = t;
150 t = 1;
151 }
152 }
153 if (t != 1)
154 limbs[limbn++] = t;
155
156 if (rn >= limbn) {
158 rn = lmmp_elem_mul_ulong_(dst, limbs, limbn, tp);
159 } else {
160 mp_ptr restrict tp = TALLOC_TYPE(limbn * 2, mp_limb_t);
161 rn = lmmp_elem_mul_ulong_(tp, limbs, limbn, tp + limbn);
162 lmmp_copy(dst, tp, rn);
163 }
164 TEMP_FREE;
165 return rn;
166}
#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)
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define ctz_shr_u32(r, x, cnt)
#define tp
uint64_t * ulongp
定义 numth.h:48

引用了 ctz_shr_u32, k, lmmp_copy, lmmp_elem_mul_ulong_(), lmmp_odd_nPr_product_(), MP_UINT_MAX, n, restrict, t, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

被这些函数引用 lmmp_odd_nCr_div_(), lmmp_odd_nPr_product_(), lmmp_odd_nPr_product_(), lmmp_odd_nPr_uint_() , 以及 lmmp_odd_nPr_ushort_().

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