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

浏览该文件的源代码.

函数

void test_binvert (void)
 TEST_CASE ("numth/binvert", binvert_2_3_4)
 TEST_CASE ("numth/binvert", binvert_n_dc)
 TEST_CASE ("numth/binvert", binvert_near_balanced)
 TEST_CASE ("numth/binvert", binvert_uint_ulong)
 TEST_CASE ("numth/binvert", binvert_unbalanced_variants)
 TEST_CASE ("numth/binvert", bninv_power2_top_limb)
static void verify_inverse (const mp_limb_t *num, mp_size_t na, const mp_limb_t *dst, mp_size_t n)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数说明

◆ test_binvert()

void test_binvert ( void )

在文件 test_binvert.c 第 210 行定义.

210 {
211 TEST_RUN("numth/binvert", binvert_uint_ulong);
212 TEST_RUN("numth/binvert", binvert_2_3_4);
213 TEST_RUN("numth/binvert", binvert_n_dc);
214 TEST_RUN("numth/binvert", binvert_near_balanced);
215 TEST_RUN("numth/binvert", bninv_power2_top_limb);
216 TEST_RUN("numth/binvert", binvert_unbalanced_variants);
217}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_binvert() , 以及 TEST_RUN.

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

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

◆ TEST_CASE() [1/6]

TEST_CASE ( "numth/binvert" ,
binvert_2_3_4  )

在文件 test_binvert.c 第 58 行定义.

58 {
59 u64 seed = 0x1020304050607080ull;
60 for (int i = 0; i < 300; ++i) {
61 mp_limb_t a2[2], inv2[2];
62 random_limbs(a2, 2, &seed);
63 a2[0] |= 1;
64 lmmp_binvert_2_(inv2, a2);
65 verify_inverse(a2, 2, inv2, 2);
66
67 mp_limb_t a3[3], inv3[3];
68 random_limbs(a3, 3, &seed);
69 a3[0] |= 1;
70 lmmp_binvert_3_(inv3, a3);
71 verify_inverse(a3, 3, inv3, 3);
72
73 mp_limb_t a4[4], inv4[4];
74 random_limbs(a4, 4, &seed);
75 a4[0] |= 1;
76 lmmp_binvert_4_(inv4, a4);
77 verify_inverse(a4, 4, inv4, 4);
78 }
79}
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define a2
#define a3
#define a4
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
void lmmp_binvert_3_(mp_ptr dst, mp_srcptr numa)
计算 [numa,3] 在 B^3 下的逆元
void lmmp_binvert_4_(mp_ptr dst, mp_srcptr numa)
计算 [numa,4] 在 B^4 下的逆元
static void verify_inverse(const mp_limb_t *num, mp_size_t na, const mp_limb_t *dst, mp_size_t n)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 a2, a3, a4, lmmp_binvert_2_(), lmmp_binvert_3_(), lmmp_binvert_4_(), TEST_CASE , 以及 verify_inverse().

函数调用图:

◆ TEST_CASE() [2/6]

TEST_CASE ( "numth/binvert" ,
binvert_n_dc  )

在文件 test_binvert.c 第 81 行定义.

81 {
82 u64 seed = 0x0f1e2d3c4b5a6978ull;
83 const mp_size_t n_values[] = {1, 2, 3, 4, 5, 10, 20, 40, 80, 120};
84 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
85 mp_size_t n = n_values[n_index];
86 mp_ptr a = alloc_limbs(n), inv = alloc_limbs(n), tp = alloc_limbs((5 * n + 5) / 2);
87 random_limbs(a, n, &seed);
88 a[0] |= 1;
89 lmmp_binvert_n_dc_(inv, a, n, tp);
90 verify_inverse(a, n, inv, n);
92 }
93}
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define tp
#define n
void lmmp_binvert_n_dc_(mp_ptr dst, mp_srcptr numa, mp_size_t n, mp_ptr tp)
计算 [numa,n] 在 B^n 下的逆元
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40

引用了 ARRAY_SIZE, lmmp_binvert_n_dc_(), lmmp_free(), n, TEST_CASE, tp , 以及 verify_inverse().

函数调用图:

◆ TEST_CASE() [3/6]

TEST_CASE ( "numth/binvert" ,
binvert_near_balanced  )

在文件 test_binvert.c 第 95 行定义.

95 {
96 // 回归:4n < 5na 的平衡化分支曾以长度 n 拷贝 numa(实际只有 na 个 limb)而越界读
97 u64 seed = 0xc0ffee1234567890ull;
98 const mp_size_t na_values[] = {8, 40, 80};
99 for (size_t na_index = 0; na_index < ARRAY_SIZE(na_values); ++na_index) {
100 mp_size_t na = na_values[na_index];
101 mp_size_t n = na + na / 5;
102 mp_ptr a = alloc_limbs(na), inv = alloc_limbs(n);
103 random_limbs(a, na, &seed);
104 a[0] |= 1;
105 lmmp_binvert_(inv, a, na, n);
106 verify_inverse(a, na, inv, n);
107 lmmp_free(a);
108 lmmp_free(inv);
109 }
110}
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元

引用了 ARRAY_SIZE, lmmp_binvert_(), lmmp_free(), n, TEST_CASE , 以及 verify_inverse().

函数调用图:

◆ TEST_CASE() [4/6]

TEST_CASE ( "numth/binvert" ,
binvert_uint_ulong  )

在文件 test_binvert.c 第 43 行定义.

43 {
44 u64 seed = 0x123456789abcdef0ull;
45 for (int i = 0; i < 500; ++i) {
46 u32 a = (u32)(xorshift64(&seed) | 1);
47 u32 inv = lmmp_binvert_uint_(a);
48 TEST_CHECK_MSG((uint)(a * inv) == 1u, "binvert_uint inverse");
49
50 u64 b = xorshift64(&seed) | 1;
51 u64 inv64 = lmmp_binvert_ulong_(b);
52 mp_limb_t iv[2];
53 lmmp_mullh_(b, inv64, iv);
54 TEST_CHECK_EQ(iv[0], 1ull); // b*inv64 ≡ 1 (mod B):低 limb 为 1 即可
55 }
56}
#define lmmp_mullh_
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
uint32_t uint
定义 numth.h:38
uint lmmp_binvert_uint_(uint a)
计算 a 在2^32下的逆元
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#define TEST_CHECK_EQ(a, b)
定义 test.h:39

引用了 lmmp_binvert_uint_(), lmmp_binvert_ulong_(), lmmp_mullh_, TEST_CASE, TEST_CHECK_EQ , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [5/6]

TEST_CASE ( "numth/binvert" ,
binvert_unbalanced_variants  )

在文件 test_binvert.c 第 164 行定义.

164 {
165 u64 seed = 0xa1b2c3d4e5f60718ull;
166
167 // unbalance_1:单 limb 底数
168 const mp_size_t n_values[] = {2, 3, 5, 10, 30, 80};
169 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
170 mp_size_t n = n_values[n_index];
171 mp_ptr a = alloc_limbs(1), inv = alloc_limbs(n);
172 a[0] = xorshift64(&seed) | 1;
173 lmmp_binvert_unbalance_1_(inv, a[0], n);
174 verify_inverse(a, 1, inv, n);
175 lmmp_free(a); lmmp_free(inv);
176 }
177
178 // unbalance_2:双 limb 底数
179 const mp_size_t n_values2[] = {3, 4, 10, 30, 80};
180 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values2); ++n_index) {
181 mp_size_t n = n_values2[n_index];
182 mp_ptr a = alloc_limbs(2), inv = alloc_limbs(n);
183 random_limbs(a, 2, &seed);
184 a[0] |= 1;
186 verify_inverse(a, 2, inv, n);
187 lmmp_free(a); lmmp_free(inv);
188 }
189
190 // unbalance 和通用入口
191 const mp_size_t n_values3[] = {3, 5, 10, 30, 80};
192 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values3); ++n_index) {
193 mp_size_t n = n_values3[n_index];
194 mp_size_t na = (n + 1) / 2;
195 if (na < 1) na = 1;
196 if (na >= n) na = n - 1;
197 mp_ptr a = alloc_limbs(na), inv = alloc_limbs(n), tp = alloc_limbs((9 * na + 5) / 2 + 1);
198 random_limbs(a, na, &seed);
199 a[0] |= 1;
200 lmmp_binvert_unbalance_(inv, a, na, n, tp);
201 verify_inverse(a, na, inv, n);
202
203 mp_ptr inv2 = alloc_limbs(n);
204 lmmp_binvert_(inv2, a, na, n);
205 verify_inverse(a, na, inv2, n);
206 lmmp_free(a); lmmp_free(inv); lmmp_free(inv2); lmmp_free(tp);
207 }
208}
void lmmp_binvert_unbalance_1_(mp_ptr dst, mp_limb_t a, mp_size_t n)
计算 a 在 B^n 下的逆元
void lmmp_binvert_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n, mp_ptr tp)
计算 [numa,na] 在 B^n 下的逆元
void lmmp_binvert_unbalance_2_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
计算 [numa,2] 在 B^n 下的逆元

引用了 ARRAY_SIZE, lmmp_binvert_(), lmmp_binvert_unbalance_(), lmmp_binvert_unbalance_1_(), lmmp_binvert_unbalance_2_(), lmmp_free(), n, TEST_CASE, tp , 以及 verify_inverse().

函数调用图:

◆ TEST_CASE() [6/6]

TEST_CASE ( "numth/binvert" ,
bninv_power2_top_limb  )

在文件 test_binvert.c 第 112 行定义.

112 {
113 // 回归:顶 limb 为 2 的幂时,归一化后顶 limb 恰为 2^63,曾触发
114 // appr_newton 的严格大于断言失败(发布版为 assume UB)
115 u64 seed = 0x9d1f2e3c4b5a6978ull;
116 const mp_size_t na_values[] = {3, 8, 40};
117 for (size_t na_index = 0; na_index < ARRAY_SIZE(na_values); ++na_index) {
118 mp_size_t na = na_values[na_index];
119 const u64 top_values[] = {1ull, 4ull, 1ull << 32, 1ull << 63};
120 for (size_t top_index = 0; top_index < ARRAY_SIZE(top_values); ++top_index) {
121 u64 top = top_values[top_index];
122 const mp_size_t ni0_values[] = {na, na / 2};
123 for (size_t ni0_index = 0; ni0_index < ARRAY_SIZE(ni0_values); ++ni0_index) {
124 mp_size_t ni0 = ni0_values[ni0_index];
125 mp_size_t ni = ni0 < 1 ? 1 : ni0;
126 mp_ptr a = alloc_limbs(na);
127 mp_ptr q = alloc_limbs(na + ni + 2);
128 random_limbs(a, na, &seed);
129 a[0] |= 1;
130 a[na - 1] = top;
131 lmmp_bninv_(q, a, na, ni);
132
133 // 参照(库内构造):ref = B^(2*(na+ni)) / (numa * B^ni),
134 // 文档误差 +[0|1],放宽到 2
135 mp_size_t dn = na + ni;
136 mp_ptr den = alloc_limbs(dn);
137 lmmp_zero(den, dn);
138 memcpy(den + ni, a, (size_t)na * 8); // numa * B^ni
139 mp_size_t nn = 2 * dn + 1;
140 mp_ptr numer = alloc_limbs(nn);
141 lmmp_zero(numer, nn);
142 numer[2 * dn] = 1; // B^(2*(na+ni))
143 mp_ptr quot = alloc_limbs(nn - dn + 1), rem = alloc_limbs(dn);
144 lmmp_div_(quot, rem, numer, nn, den, dn);
145
146 // |got - ref| <= 2
147 mp_size_t ln = dn + 1;
148 mp_ptr diff = alloc_limbs(ln + 1);
149 mp_limb_t bw = lmmp_sub_(diff, q, ln, quot, ln);
150 bool small = true;
151 if (bw) { // got < ref,反向相减
152 lmmp_sub_(diff, quot, ln, q, ln);
153 }
154 for (mp_size_t i = 1; i < ln; ++i) small = small && (diff[i] == 0);
155 TEST_CHECK_MSG(small && diff[0] <= 2, "bninv close to reference quotient");
156
157 lmmp_free(a); lmmp_free(q); lmmp_free(den); lmmp_free(numer);
158 lmmp_free(quot); lmmp_free(rem); lmmp_free(diff);
159 }
160 }
161 }
162}
#define lmmp_zero(dst, n)
定义 lmmp.h:476
void lmmp_bninv_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_size_t ni)
近似逆元计算 [dstq,na+ni+2] = B^(2*(na+ni)) / ([numa,na] * B^ni) + [0|-ept]
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85

引用了 ARRAY_SIZE, lmmp_bninv_(), lmmp_div_(), lmmp_free(), lmmp_sub_(), lmmp_zero, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ verify_inverse()

void verify_inverse ( const mp_limb_t * num,
mp_size_t na,
const mp_limb_t * dst,
mp_size_t n )
static

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_binvert.c 第 31 行定义.

31 {
32 mp_ptr t = alloc_limbs(n + na + 1);
33 if (na == 1) {
34 lmmp_mul_1_(t, dst, n, num[0]);
35 } else {
36 lmmp_mul_(t, dst, n, num, na); // 契约 na_dst=n >= na
37 }
38 TEST_CHECK_EQ(t[0], 1ull);
39 for (mp_size_t i = 1; i < n; ++i) TEST_CHECK_EQ(t[i], 0ull);
40 lmmp_free(t);
41}
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_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义 mul_1.c:27
#define t

引用了 lmmp_free(), lmmp_mul_(), lmmp_mul_1_(), n, t, TEST_CHECK_EQ , 以及 verify_inverse().

被这些函数引用 TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 verify_inverse().

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