LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
test_combin_boundaries.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 "
lmmp/lmmpn.h
"
24
#include "mparam.h"
25
#include "
lmmp/numth.h
"
26
#include "
cases.h
"
27
#include "
support/lmmp_test_utils.h
"
28
29
#include <string.h>
30
31
/*
32
确定性输入回归:期望值取同函数分离缓冲调用(原地/边界形态专项,
33
算术正确性由 low/asm 系列覆盖);div 边界用重建恒等式;
34
退化组合数用已知值与 factorial 交叉。
35
*/
36
37
TEST_CASE
(
"numth/combin"
, nPr_nCr_degenerate_boundaries) {
38
const
ulong
npr_ns[] = {0ull, 1ull, 2ull, 3ull, 5ull, 10ull, 12ull};
39
for
(
size_t
n_index = 0; n_index <
ARRAY_SIZE
(npr_ns); ++n_index) {
40
ulong
n
= npr_ns[n_index];
41
const
ulong
npr_rs[] = {0ull, 1ull,
n
};
42
for
(
size_t
r_index = 0; r_index <
ARRAY_SIZE
(npr_rs); ++r_index) {
43
ulong
r = npr_rs[r_index];
44
if
(r >
n
)
continue
;
45
mp_bitcnt_t
bits = 0;
46
mp_size_t
need =
lmmp_nPr_size_
(
n
, r, &bits);
47
mp_ptr
dst = alloc_limbs(need + 2);
48
lmmp_zero
(dst, need + 2);
49
mp_size_t
rn =
lmmp_nPr_
(dst, bits, need,
n
, r);
// 实际长度
50
if
(r == 0) {
51
TEST_CHECK_EQ
(dst[0], 1ull);
52
TEST_CHECK_EQ
(rn, (
mp_size_t
)1);
53
}
else
if
(r == 1) {
54
TEST_CHECK_EQ
(dst[0], (
u64
)
n
);
// n <= 12 单 limb
55
TEST_CHECK_EQ
(rn, (
mp_size_t
)1);
56
}
else
{
57
// nPr(n, n) == n!:库 factorial 交叉(长度一律取返回值,
58
// size_ 含冗余、缓冲高位为未初始化内存)
59
mp_bitcnt_t
fb = 0;
60
mp_size_t
fn =
lmmp_factorial_size_
((
uint
)
n
, &fb);
61
mp_ptr
f = alloc_limbs(fn + 2);
62
mp_size_t
fl =
lmmp_factorial_
(f, fb, fn, (
uint
)
n
);
63
TEST_CHECK
(mpn_eq(dst, need + 2, f, fl));
// dst 已零化,容量域比较安全
64
TEST_CHECK_EQ
(rn, fl);
// 同值规范化长度必等,防高位零掩盖
65
lmmp_free
(f);
66
}
67
lmmp_free
(dst);
68
}
69
}
70
71
const
uint
ncr_ns[] = {0u, 1u, 2u, 5u, 10u, 20u};
72
for
(
size_t
n_index = 0; n_index <
ARRAY_SIZE
(ncr_ns); ++n_index) {
73
uint
n
= ncr_ns[n_index];
74
uint
half =
n
/ 2;
75
const
uint
ncr_rs[] = {0u, 1u, half};
76
for
(
size_t
r_index = 0; r_index <
ARRAY_SIZE
(ncr_rs); ++r_index) {
77
uint
r = ncr_rs[r_index];
78
if
(r > half)
continue
;
/* nCr 要求 r <= n/2 */
79
mp_bitcnt_t
bits = 0;
80
mp_size_t
need =
lmmp_nCr_size_
(
n
, r, &bits);
81
mp_ptr
dst = alloc_limbs(need + 2);
82
lmmp_zero
(dst, need + 2);
83
mp_size_t
dn =
lmmp_nCr_
(dst, bits, need,
n
, r);
// 实际长度
84
if
(r == 0) {
85
TEST_CHECK_EQ
(dst[0], 1ull);
86
}
else
if
(r == 1) {
87
TEST_CHECK_EQ
(dst[0], (
u64
)
n
);
88
}
else
{
89
// C(n,k)*k!*(n-k)! == n!(库乘 + factorial 交叉;长度取
90
// 返回值,乘法乒乓双缓冲保持 sep(dst,a,b))
91
mp_bitcnt_t
b1
= 0,
b2
= 0,
b3
= 0;
92
mp_size_t
n1 =
lmmp_factorial_size_
(r, &
b1
);
93
mp_size_t
n2 =
lmmp_factorial_size_
(
n
- r, &
b2
);
94
mp_size_t
n3 =
lmmp_factorial_size_
(
n
, &
b3
);
95
mp_ptr
f1 = alloc_limbs(n1 + 2), f2 = alloc_limbs(n2 + 2), f3 = alloc_limbs(n3 + 2),
96
prod
= alloc_limbs(need + n3 + 4), prod2 = alloc_limbs(need + n3 + 4);
97
mp_size_t
l1 =
lmmp_factorial_
(f1,
b1
, n1, r);
98
mp_size_t
l2 =
lmmp_factorial_
(f2,
b2
, n2,
n
- r);
99
mp_size_t
l3 =
lmmp_factorial_
(f3,
b3
, n3,
n
);
100
lmmp_mul_
(
prod
, dst, dn, f1, l1);
101
mp_size_t
pn = dn + l1;
102
lmmp_mul_
(prod2,
prod
, pn, f2, l2);
103
mp_size_t
p2n = pn + l2;
104
TEST_CHECK
(mpn_eq(prod2, p2n, f3, l3));
105
lmmp_free
(f1);
lmmp_free
(f2);
lmmp_free
(f3);
106
lmmp_free
(
prod
);
lmmp_free
(prod2);
107
}
108
lmmp_free
(dst);
109
}
110
}
111
112
{
113
ulong
n
= 0xffff;
114
mp_bitcnt_t
bits = 0;
115
mp_size_t
need =
lmmp_nPr_size_
(
n
, 1, &bits);
116
mp_ptr
dst = alloc_limbs(need + 2);
117
lmmp_zero
(dst, need + 2);
118
mp_size_t
rn =
lmmp_nPr_
(dst, bits, need,
n
, 1);
119
TEST_CHECK
(mpn_eq(dst, need + 2, &
n
, 1));
// nPr(n,1) == n
120
TEST_CHECK_EQ
(rn, (
mp_size_t
)1);
121
lmmp_free
(dst);
122
}
123
}
124
125
void
test_combin_boundaries
(
void
) {
126
TEST_RUN
(
"numth/combin"
, nPr_nCr_degenerate_boundaries);
127
}
prod
#define prod
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
lmmp_zero
#define lmmp_zero(dst, n)
定义
lmmp.h:476
mp_bitcnt_t
size_t mp_bitcnt_t
定义
lmmp.h:98
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
lmmp_free
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
定义
memory.c:437
lmmp_test_utils.h
u64
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
lmmp_test_utils.h:33
lmmpn.h
lmmp_mul_
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]
b1
#define b1
b2
#define b2
n
#define n
b3
#define b3
cases.h
test_combin_boundaries
void test_combin_boundaries(void)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_combin_boundaries.c:125
numth.h
uint
uint32_t uint
定义
numth.h:38
lmmp_factorial_size_
mp_size_t lmmp_factorial_size_(uint n, mp_bitcnt_t *bits)
计算 n!
lmmp_factorial_
mp_size_t lmmp_factorial_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n)
计算 n!
lmmp_nCr_size_
mp_size_t lmmp_nCr_size_(uint n, uint r, mp_bitcnt_t *bits)
计算 nCr 组合数的 limb 缓冲区长度
lmmp_nCr_
mp_size_t lmmp_nCr_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n, uint r)
计算 nCr 组合数 ( nCr = n!
lmmp_nPr_size_
mp_size_t lmmp_nPr_size_(ulong n, ulong r, mp_bitcnt_t *bits)
计算 nPr 排列数的 limb 缓冲区长度
ulong
uint64_t ulong
定义
numth.h:39
lmmp_nPr_
mp_size_t lmmp_nPr_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数 ( nPr = n!
ARRAY_SIZE
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
perf.h:40
TEST_CHECK
#define TEST_CHECK(cond)
定义
test.h:37
TEST_CASE
#define TEST_CASE(category, name)
定义
test.h:35
TEST_CHECK_EQ
#define TEST_CHECK_EQ(a, b)
定义
test.h:39
TEST_RUN
#define TEST_RUN(category, name)
定义
test.h:36
src
lmmp
numth
test
test_combin_boundaries.c
生成于
, 为 LMMP使用
1.18.0