LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
arith_seqprod.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 "mparam.h"
27#include "impl/tmp_alloc.h"
28#include "impl/longlong.h"
29#include "lmmp/lmmpn.h"
30#include "lmmp/numth.h"
31
32
34 lmmp_param_assert(x > 0);
36 lmmp_param_assert(m > 1);
37 /*
38 P = x(x+m)...(x+nm) = m^(n+1) * gamma(x/m+n+1)/gamma(x/m)
39 log2(P) = [(n+1)ln(m) + lgamma(x/m+n+1) - lgamma(x/m)] / ln2
40 由 x+n*m <= 2^32-1 的约束,lgamma参数不超过2^31,估计误差远小于1bit。
41 位数 = floor(log2(P))+1,故取floor+1。
42 */
43 const double ln2 = 0.69314718055994531;
44 double a = (double)x / (double)m;
45 double lp = ((double)(n + 1) * log((double)m) + lgamma(a + (double)(n + 1)) - lgamma(a)) / ln2;
46 mp_size_t rn1 = (((uint64_t)floor(lp) + 1) + LIMB_BITS - 1) / LIMB_BITS + 2;
47 // 共有n+1个数,每个数的位数最多为uint,一个limb最多可以容纳两个uint乘积
48 // 奇部积至多 ceil((n+1)/2) limb,shl 进位无条件写 dst[shw+bn] 需再留 1 limb
49 mp_size_t rn2 = (n + 1) / 2 + 2;
50 return LMMP_MIN(rn1, rn2);
51}
52
53static inline mp_size_t _odd_pow_(mp_ptr restrict dst, mp_size_t rn, uint base, ulong exp) {
54 if (base <= 0xf)
55 return lmmp_u4_pow_1_(dst, rn, base, exp);
56 else if (base <= MP_UCHAR_MAX)
57 return lmmp_u8_pow_1_(dst, rn, base, exp);
58 else if (base <= MP_USHORT_MAX)
59 return lmmp_u16_pow_1_(dst, rn, base, exp);
60 else
61 return lmmp_u32_pow_1_(dst, rn, base, exp);
62}
63
65 if (n <= NPR_SHORT_LIMIT) {
66 return lmmp_odd_nPr_ushort_(dst, rn, n, r);
67 } else {
68 return lmmp_odd_nPr_uint_(dst, rn, n, r);
69 }
70}
71
72/*
73当x=p*m时,
74x(x+m)...(x+n*m) = p*m * (p+1)*m * ... * (p+n)*m
75 = m^(n+1) * p(p+1)...(p+n)
76分别计算幂和组合数,然后相乘
77*/
78static inline mp_size_t pow_nPr_(mp_ptr restrict dst, mp_size_t rn, uint x, uint n, uint m) {
80 uint p = x / m;
81
82 mp_bitcnt_t bits;
83 mp_size_t tn = lmmp_nPr_size_(p + n, n + 1, &bits);
84 tn -= bits / LIMB_BITS;
86 tn = _odd_nPr_(tp, tn, p + n, n + 1);
87
89 m >>= tz;
90 mp_size_t mpown = lmmp_pow_1_size_(m, n + 1);
91 mp_ptr restrict mpow = TALLOC_TYPE(mpown, mp_limb_t);
92 mpown = _odd_pow_(mpow, mpown, m, n + 1);
93
94 bits += tz * (n + 1);
95 mp_size_t shw = bits / LIMB_BITS;
96 bits %= LIMB_BITS;
97
98 lmmp_zero(dst, shw);
99 if (tn >= mpown)
100 lmmp_mul_(dst + shw, tp, tn, mpow, mpown);
101 else
102 lmmp_mul_(dst + shw, mpow, mpown, tp, tn);
103
104 rn = tn + mpown;
105 rn -= dst[shw + rn - 1] == 0 ? 1 : 0;
106 if (bits > 0) {
107 dst[shw + rn] = lmmp_shl_(dst + shw, dst + shw, rn, bits);
108 rn += shw + 1;
109 rn -= dst[rn - 1] == 0 ? 1 : 0;
110 } else {
111 rn += shw;
112 }
113 TEMP_FREE;
114 return rn;
115}
116
118 lmmp_param_assert(dst != NULL);
119 lmmp_param_assert(rn >= 1);
120 lmmp_param_assert(x >= 1);
121 lmmp_param_assert(n >= 1);
122 lmmp_param_assert(m > 1);
123
124 if (x % m == 0) {
125 return pow_nPr_(dst, rn, x, n, m);
126 }
127
128 mp_bitcnt_t bits = 0;
129 while ((x & 1) == 0 && (m & 1) == 0) {
130 x >>= 1;
131 m >>= 1;
132 bits++;
133 }
134 bits *= n + 1;
135
136 TEMP_DECL;
137 ulongp restrict limbs = TALLOC_TYPE((n + 1) / 2 + 1, ulong);
138 mp_size_t limbn = 0;
139 ulong t = 1, s, v;
140 mp_bitcnt_t cnt;
141 for (uint i = 0; i <= n; i++) {
142 s = x + i * m;
143 ctz_shr_u64(v, s, cnt);
144 t *= v;
145 bits += cnt;
146 if (t > MP_UINT_MAX) {
147 limbs[limbn++] = t;
148 t = 1;
149 }
150 }
151 ctz_shr_u64(v, t, cnt);
152 bits += cnt;
153 if (v != 1) {
154 limbs[limbn++] = v;
155 }
156 mp_size_t shw = bits / LIMB_BITS;
157 bits %= LIMB_BITS;
158 mp_ptr restrict b = TALLOC_TYPE(limbn * 2, mp_limb_t);
159 mp_size_t bn = lmmp_elem_mul_ulong_(b, limbs, limbn, b + limbn);
160 lmmp_zero(dst, shw);
161 dst[shw + bn] = lmmp_shl_(dst + shw, b, bn, bits); // bits=0 时函数内拷贝且返回 0
162 rn = bn + shw + 1;
163 rn -= dst[rn - 1] == 0 ? 1 : 0;
164 TEMP_FREE;
165 return rn;
166}
static mp_size_t _odd_pow_(mp_ptr restrict dst, mp_size_t rn, uint base, ulong exp)
static mp_size_t pow_nPr_(mp_ptr restrict dst, mp_size_t rn, uint x, uint n, uint m)
static mp_size_t _odd_nPr_(mp_ptr restrict dst, mp_size_t rn, ulong n, ulong r)
mp_size_t lmmp_elem_mul_ulong_(mp_ptr restrict dst, const ulongp restrict limbs, mp_size_t n, mp_ptr restrict tp)
#define bn
#define lmmp_tailing_zeros_
#define MP_UINT_MAX
#define MP_UCHAR_MAX
#define MP_USHORT_MAX
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
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 ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define t
#define tp
#define s
#define n
#define NPR_SHORT_LIMIT
mp_size_t lmmp_u4_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_pow_1_size_(mp_limb_t base, ulong exp)
计算幂次方需要的limb缓冲区长度 base ^ exp
定义 pow.c:65
mp_size_t lmmp_odd_nPr_ushort_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
mp_size_t lmmp_arith_seqprod_size_(uint x, uint n, uint m)
计算等差数列乘积 x(x+m)...(x+n*m)的 limb 缓冲区长度
mp_size_t lmmp_u32_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
uint64_t * ulongp
定义 numth.h:48
uint32_t uint
定义 numth.h:38
mp_size_t lmmp_u8_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_u16_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_nPr_size_(ulong n, ulong r, mp_bitcnt_t *bits)
计算 nPr 排列数的 limb 缓冲区长度
uint64_t ulong
定义 numth.h:39
mp_size_t lmmp_arith_seqprod_(mp_ptr dst, mp_size_t rn, uint x, uint n, uint m)
计算等差数列乘积 x(x+m)...(x+n*m)
mp_size_t lmmp_odd_nPr_uint_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)