LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
multinomial.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
33 if (n < 20) {
34 return 0;
35 } else {
36 // log2(n!) = lgamma(n+1)/ln2,下界取floor
37 const double ln2 = 0.69314718055994531;
38 return (mp_size_t)floor(lgamma((double)n + 1) / ln2);
39 }
40}
41
43 if (n < 20) {
44 return 64;
45 } else {
46 // log2(n!) = lgamma(n+1)/ln2,上界取ceil
47 const double ln2 = 0.69314718055994531;
48 return (mp_size_t)ceil(lgamma((double)n + 1) / ln2);
49 }
50}
51
53 ulong n_ret = 0;
54 uint i = 0;
55 for (; i < m; ++i) n_ret += r[i];
56
58 lmmp_param_assert(n_ret > 0);
59 *n = n_ret;
60 mp_size_t rn = fac_size_bigger(n_ret);
61
62 for (i = 0; i < m; ++i) {
63 rn -= fac_size_lower(r[i]);
64 }
65 rn = (rn + LIMB_BITS - 1) / LIMB_BITS;
66 return rn + 2;
67}
68
69static inline uint count_factors(fac_ptr fac, uint nfactors, uint n, const uintp r, uint m, uint p) {
70 uint pn = n;
71 uint e = 0;
72 ulong inv = MP_ULONG_MAX / p + 1;
73 while (pn > 0) {
74 _udiv32by32_q_preinv(pn, pn, inv);
75 e += pn;
76 }
77 for (uint i = 0; i < m; ++i) {
78 pn = r[i];
79 while (pn > 0) {
80 _udiv32by32_q_preinv(pn, pn, inv);
81 e -= pn;
82 }
83 }
84 if (e > 0) {
85 fac[nfactors].f = p;
86 fac[nfactors++].j = e;
87 }
88 return nfactors;
89}
90
91static inline uint factor_size_int(mp_size_t rn, uint n) {
92 /*
93 使用类似组合数的思路来估计缓冲区大小。
94 */
95 ulong approx1 = rn * 8;
97 ulong approx2 = lmmp_prime_size_(n);
98 return approx1 < approx2 ? approx1 : approx2;
99}
100
102 ushort approx1 = rn * 8;
104 return approx1;
105}
106
108 mp_ptr restrict dst,
109 mp_size_t rn,
110 uint n,
111 const uintp restrict r,
112 uint m
113) {
114 if (n < ODD_FACTORIAL_SIZE) {
115 lmmp_odd_nPr_ushort_(dst, rn, n, n);
116 mp_limb_t t = 0;
117 for (uint i = 0; i < m; ++i) {
118 lmmp_odd_nPr_ushort_(&t, 1, r[i], r[i]);
119 dst[0] /= t;
120 }
121 return 1;
122 } else {
123 TEMP_DECL;
124 ushort primen = lmmp_prime_cnt16_(n);
125 ushort nfactors = factor_size_short(rn);
126 nfactors = primen < nfactors ? primen : nfactors;
127 fac_ptr restrict fac = TALLOC_TYPE(nfactors, fac_t);
128 nfactors = 0;
129 for (ushort i = 1; i < primen; ++i) {
131 nfactors = count_factors(fac, nfactors, n, r, m, p);
132 }
133
134 rn = lmmp_factors_mul_ushort_(dst, rn, fac, nfactors);
135
136 TEMP_FREE;
137 return rn;
138 }
139}
140
144 uint nfactors = factor_size_int(rn, n);
145 fac_ptr restrict fac = BALLOC_TYPE(nfactors, fac_t);
146
147 nfactors = 0;
148 prime_cache_t cache;
149 lmmp_prime_cache_init_(&cache, n);
150 while (cache.is_end == 0) {
152 for (uint i = 0; i < cache.size; ++i) {
153 nfactors = count_factors(fac, nfactors, n, r, m, cache.pp[i]);
154 }
155 }
157
158 rn = lmmp_factors_mul_(dst, rn, fac, nfactors);
159
161 return rn;
162}
163
164#define MULTINOMIAL_SHORT_LIMIT (0xffff)
165#define MULTINOMIAL_INT_LIMIT (0xffffffff)
166
169 for (uint j = 0; j < m; ++j) {
170 shl += lmmp_limb_popcnt_(r[j]);
171 shl -= r[j];
172 }
173 mp_size_t shw = shl / LIMB_BITS;
174 shl %= LIMB_BITS;
175 lmmp_zero(dst, shw);
176 if (n <= MULTINOMIAL_SHORT_LIMIT) {
177 rn = lmmp_odd_multinomial_ushort_(dst + shw, rn - shw, n, r, m);
178 } else {
179 rn = lmmp_odd_multinomial_uint_(dst + shw, rn - shw, n, r, m);
180 }
181
182 if (shl > 0) {
183 dst[shw + rn] = lmmp_shl_(dst + shw, dst + shw, rn, shl);
184 rn += shw + 1;
185 rn -= dst[rn - 1] == 0 ? 1 : 0;
186 } else {
187 rn += shw;
188 }
189 return rn;
190}
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中
static void count_factors(fac_ptr fac, uint nfactors, uint n, uint p)
#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_zero(dst, n)
定义 lmmp.h:476
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 n
static mp_size_t lmmp_odd_multinomial_ushort_(mp_ptr restrict dst, mp_size_t rn, uint n, const uintp restrict r, uint m)
static uint factor_size_int(mp_size_t rn, uint n)
static mp_size_t fac_size_lower(uint n)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static ushort factor_size_short(mp_size_t rn)
#define MULTINOMIAL_SHORT_LIMIT
static mp_size_t lmmp_odd_multinomial_uint_(mp_ptr restrict dst, mp_size_t rn, uint n, const uintp restrict r, uint m)
static mp_size_t fac_size_bigger(uint n)
#define ODD_FACTORIAL_SIZE
mp_size_t lmmp_multinomial_size_(const uintp r, uint m, ulong *n)
计算多项式系数的 limb 缓冲区长度
mp_size_t lmmp_odd_nPr_ushort_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
uint32_t uint
定义 numth.h:38
uint32_t * uintp
定义 numth.h:46
uint16_t ushort
定义 numth.h:36
mp_size_t lmmp_multinomial_(mp_ptr dst, mp_size_t rn, uint n, const uintp r, uint m)
计算多项式系数
uint64_t ulong
定义 numth.h:39
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 TALLOC_TYPE(n, type)
#define TEMP_B_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_B_FREE