LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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"
28
29#include <string.h>
30
31/*
32 确定性输入回归:期望值取同函数分离缓冲调用(原地/边界形态专项,
33 算术正确性由 low/asm 系列覆盖);div 边界用重建恒等式;
34 退化组合数用已知值与 factorial 交叉。
35*/
36
37TEST_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);
53 } else if (r == 1) {
54 TEST_CHECK_EQ(dst[0], (u64)n); // n <= 12 单 limb
56 } else {
57 // nPr(n, n) == n!:库 factorial 交叉(长度一律取返回值,
58 // size_ 含冗余、缓冲高位为未初始化内存)
59 mp_bitcnt_t fb = 0;
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;
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
126 TEST_RUN("numth/combin", nPr_nCr_degenerate_boundaries);
127}
#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)
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]
#define b1
#define b2
#define n
#define b3
void test_combin_boundaries(void)
Copyright (C) 2026 HJimmyK (Jericho Knox)
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 缓冲区长度
uint64_t ulong
定义 numth.h:39
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_CASE(category, name)
定义 test.h:35
#define TEST_CHECK_EQ(a, b)
定义 test.h:39
#define TEST_RUN(category, name)
定义 test.h:36