LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_binom.c 文件参考
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
#include "cases.h"
#include "support/lmmp_test_utils.h"
test_binom.c 的引用(Include)关系图:

浏览该文件的源代码.

函数

void test_binom (void)
 TEST_CASE ("numth/number", nPr_nCr_multinomial_arith)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数说明

◆ test_binom()

void test_binom ( void )

在文件 test_binom.c 第 189 行定义.

189 {
190 TEST_RUN("numth/number", nPr_nCr_multinomial_arith);
191}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_binom() , 以及 TEST_RUN.

被这些函数引用 main() , 以及 test_binom().

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

◆ TEST_CASE()

TEST_CASE ( "numth/number" ,
nPr_nCr_multinomial_arith  )

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

在文件 test_binom.c 第 36 行定义.

36 {
37 // nPr == 乘积链(库 mul_1)+ 恒等式 nPr*(n-r)! == n!(库乘重建)
38 const size_t CAP = 2048;
39 mp_ptr e = alloc_limbs(CAP), f1 = alloc_limbs(CAP), f2 = alloc_limbs(CAP),
40 prod = alloc_limbs(CAP);
41 const ulong n_values[] = {0, 1, 5, 10, 20, 50, 100};
42 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
43 ulong n = n_values[n_index];
44 for (ulong r = 0; r <= n; r += (n > 20 ? 20 : 1)) {
45 // 链参考
46 e[0] = 1;
47 mp_size_t elen = 1;
48 for (u32 i = (u32)(n - r + 1); i <= n; ++i) elen = chain_mul_small(e, elen, i, CAP);
49
50 mp_bitcnt_t bits = 0;
51 mp_size_t need = lmmp_nPr_size_(n, r, &bits);
52 mp_ptr dst = alloc_limbs(need + 2);
53 lmmp_zero(dst, need + 2);
54 lmmp_nPr_(dst, bits, need, n, r);
55 TEST_CHECK(mpn_eq(dst, need + 2, e, elen));
56
57 // 恒等式:nPr * (n-r)! == n!(r>=2 时交叉)
58 if (r >= 2 && n - r >= 1) {
59 mp_bitcnt_t b1 = 0, b2 = 0;
61 mp_size_t need2 = lmmp_factorial_size_((u32)(n - r), &b2);
62 lmmp_zero(f1, need1 + 2); lmmp_zero(f2, need2 + 2);
63 lmmp_factorial_(f1, b1, need1, (u32)n);
64 lmmp_factorial_(f2, b2, need2, (u32)(n - r));
65 mp_size_t l1 = norm_len(f1, need1 + 2), l2 = norm_len(f2, need2 + 2);
66 mp_size_t ldst = norm_len(dst, need + 2);
67 mul_sorted(prod, dst, ldst, f2, l2);
68 mp_size_t lp = norm_len(prod, ldst + l2);
69 TEST_CHECK(mpn_eq(prod, lp, f1, l1)); // nPr * (n-r)! == n!
70 }
71 lmmp_free(dst);
72 }
73 }
74
75 // nCr:帕斯卡恒等式 + C(n,k)*k!*(n-k)! == n! + 写死锚点
76 {
77 struct known_result { u32 n; u32 r; u64 v; } known[] = {{10, 5, 252ull}, {52, 5, 2598960ull}};
78 for (size_t k_index = 0; k_index < ARRAY_SIZE(known); ++k_index) {
79 const struct known_result k = known[k_index];
80 mp_bitcnt_t bits = 0;
81 mp_size_t need = lmmp_nCr_size_(k.n, k.r, &bits);
82 mp_ptr dst = alloc_limbs(need + 2);
83 lmmp_zero(dst, need + 2);
84 lmmp_nCr_(dst, bits, need, k.n, k.r);
85 TEST_CHECK_EQ(dst[0], k.v);
86 TEST_CHECK_EQ(norm_len(dst + 1, need + 1), (mp_size_t)0);
87 lmmp_free(dst);
88 }
89 }
90 mp_ptr cn = alloc_limbs(CAP), cn1 = alloc_limbs(CAP), cn2 = alloc_limbs(CAP);
91 const u32 n_values2[] = {2, 5, 10, 20, 50};
92 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values2); ++n_index) {
93 u32 n = n_values2[n_index];
94 for (u32 r = 1; r <= n / 2; ++r) {
95 mp_bitcnt_t b0 = 0, b1 = 0, b2 = 0;
96 mp_size_t nd0 = lmmp_nCr_size_(n, r, &b0);
97 mp_size_t nd1 = lmmp_nCr_size_(n - 1, r - 1, &b1); // 契约 r<=n/2 → r-1<=(n-1)/2 ✓
98 mp_size_t nd2 = n - r > r ? lmmp_nCr_size_(n - 1, r, &b2) : 0; // 需 r <= (n-1)/2
99 lmmp_zero(cn, nd0 + 2);
100 lmmp_nCr_(cn, b0, nd0, n, r);
101 if (nd2) {
102 // 帕斯卡:C(n,r) == C(n-1,r-1) + C(n-1,r)
103 lmmp_zero(cn1, nd1 + 2); lmmp_zero(cn2, nd2 + 2);
104 lmmp_nCr_(cn1, b1, nd1, n - 1, r - 1);
105 lmmp_nCr_(cn2, b2, nd2, n - 1, r);
106 mp_size_t l1 = norm_len(cn1, nd1 + 2), l2 = norm_len(cn2, nd2 + 2);
107 // 零垫对齐后加
108 mp_ptr pad = alloc_limbs(CAP), sum = alloc_limbs(CAP);
109 size_t mx = (size_t)(l1 > l2 ? l1 : l2) + 1;
110 lmmp_zero(pad, mx);
111 memcpy(pad, cn1, (size_t)l1 * 8);
112 lmmp_zero(sum, mx);
113 memcpy(sum, cn2, (size_t)l2 * 8);
114 lmmp_add_n_(sum, sum, pad, mx);
115 TEST_CHECK(mpn_eq(sum, mx, cn, norm_len(cn, nd0 + 2)));
116 lmmp_free(pad);
117 lmmp_free(sum);
118 }
119
120 // 恒等式:C(n,r) * r! * (n-r)! == n!
121 if (n >= 2) {
122 mp_bitcnt_t bfr = 0, bfnr = 0, bfn = 0;
123 mp_size_t nfr = lmmp_factorial_size_(r, &bfr);
124 mp_size_t nfnr = lmmp_factorial_size_(n - r, &bfnr);
125 mp_size_t nfn = lmmp_factorial_size_(n, &bfn);
126 lmmp_zero(f1, nfr + 2); lmmp_zero(f2, nfnr + 2);
127 lmmp_factorial_(f1, bfr, nfr, r);
128 lmmp_factorial_(f2, bfnr, nfnr, n - r);
129 mp_ptr rem = alloc_limbs(nfn + 2);
130 lmmp_zero(rem, nfn + 2);
131 lmmp_factorial_(rem, bfn, nfn, n); // n!
132 mp_size_t lfr = norm_len(f1, nfr + 2), lfnr = norm_len(f2, nfnr + 2);
133 mp_size_t lcn = norm_len(cn, nd0 + 2), lfn = norm_len(rem, nfn + 2);
134 mp_ptr quot = alloc_limbs(CAP);
135 mul_sorted(prod, cn, lcn, f1, lfr);
136 mp_size_t lp = norm_len(prod, lcn + lfr);
137 mul_sorted(quot, prod, lp, f2, lfnr);
138 lp = norm_len(quot, lp + lfnr);
139 TEST_CHECK(mpn_eq(quot, lp, rem, lfn)); // C*r!*(n-r)! == n!
140 lmmp_free(quot);
141 lmmp_free(rem);
142 }
143 }
144 }
145 lmmp_free(cn); lmmp_free(cn1); lmmp_free(cn2);
146
147 // multinomial:写死锚点 6!/(1!2!3!) = 60(恒等式交叉由 nCr 的
148 // C*k!*(n-k)!==n! 覆盖,同构)
149 {
150 u32 r[] = {1, 2, 3};
151 u32 n_sum = 6;
152 ulong n = 0;
153 mp_size_t need = lmmp_multinomial_size_(r, 3, &n);
154 TEST_CHECK_EQ(n, (ulong)n_sum);
155 mp_ptr dst = alloc_limbs(need + 2);
156 lmmp_zero(dst, need + 2);
157 lmmp_multinomial_(dst, need, (uint)n, r, 3);
158 TEST_CHECK_EQ(dst[0], 60ull);
159 TEST_CHECK_EQ(norm_len(dst + 1, need + 1), (mp_size_t)0);
160 lmmp_free(dst);
161 }
162
163 // arith_seqprod: 链乘参考(库 mul_1)
164 const u32 x_values[] = {1, 3, 10};
165 for (size_t x_index = 0; x_index < ARRAY_SIZE(x_values); ++x_index) {
166 u32 x = x_values[x_index];
167 const u32 m_values[] = {2, 5, 10};
168 for (size_t m_index = 0; m_index < ARRAY_SIZE(m_values); ++m_index) {
169 u32 m = m_values[m_index];
170 const u32 n_values3[] = {1, 3, 10};
171 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values3); ++n_index) {
172 u32 n = n_values3[n_index];
173 if ((u64)x + (u64)n * m > 100000) continue;
174 e[0] = 1;
175 mp_size_t elen = 1;
176 for (u32 i = 0; i <= n; ++i) elen = chain_mul_small(e, elen, x + i * m, CAP);
178 mp_ptr dst = alloc_limbs(need + 2);
179 lmmp_zero(dst, need + 2);
180 lmmp_arith_seqprod_(dst, need, x, n, m);
181 TEST_CHECK(mpn_eq(dst, need + 2, e, elen));
182 lmmp_free(dst);
183 }
184 }
185 }
187}
#define k
#define prod
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
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
#define b0
#define b1
#define b2
#define n
mp_size_t lmmp_multinomial_size_(const uintp r, uint m, ulong *n)
计算多项式系数的 limb 缓冲区长度
mp_size_t lmmp_arith_seqprod_size_(uint x, uint n, uint m)
计算等差数列乘积 x(x+m)...(x+n*m)的 limb 缓冲区长度
uint32_t uint
定义 numth.h:38
mp_size_t lmmp_factorial_size_(uint n, mp_bitcnt_t *bits)
计算 n!
mp_size_t lmmp_factorial_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n)
计算 n!
mp_size_t lmmp_nCr_size_(uint n, uint r, mp_bitcnt_t *bits)
计算 nCr 组合数的 limb 缓冲区长度
mp_size_t lmmp_nCr_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n, uint r)
计算 nCr 组合数 ( nCr = n!
mp_size_t lmmp_nPr_size_(ulong n, ulong r, mp_bitcnt_t *bits)
计算 nPr 排列数的 limb 缓冲区长度
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
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_nPr_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数 ( nPr = n!
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CHECK_EQ(a, b)
定义 test.h:39

引用了 ARRAY_SIZE, b0, b1, b2, k, lmmp_add_n_(), lmmp_arith_seqprod_(), lmmp_arith_seqprod_size_(), lmmp_factorial_(), lmmp_factorial_size_(), lmmp_free(), lmmp_multinomial_(), lmmp_multinomial_size_(), lmmp_nCr_(), lmmp_nCr_size_(), lmmp_nPr_(), lmmp_nPr_size_(), lmmp_zero, n, prod, TEST_CASE, TEST_CHECK , 以及 TEST_CHECK_EQ.

函数调用图: