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

浏览该文件的源代码.

函数

static void check_floor (const mp_limb_t *A, mp_size_t an, const mp_limb_t *r, mp_size_t rn, ulong root, const mp_limb_t *rem, mp_ptr pw, mp_ptr pw1, mp_ptr rp1, mp_ptr sum)
static mp_ptr pad_add_value (const mp_limb_t *a, mp_size_t la, const mp_limb_t *b, mp_size_t lb, mp_size_t mx, mp_ptr sum)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
static u64 pow_u64_ovf (u64 r, ulong k, bool *ovf)
 TEST_CASE ("numth/nthroot", nthroot_top_probe_construction)
 TEST_CASE ("numth/nthroot", nthroot_top_random_and_powers)
 TEST_CASE ("numth/nthroot", nthroot_ulong_scalar)
void test_nthroot (void)

函数说明

◆ check_floor()

void check_floor ( const mp_limb_t * A,
mp_size_t an,
const mp_limb_t * r,
mp_size_t rn,
ulong root,
const mp_limb_t * rem,
mp_ptr pw,
mp_ptr pw1,
mp_ptr rp1,
mp_ptr sum )
static

在文件 test_nthroot.c 第 57 行定义.

58 {
59 mp_size_t cap = root * rn + root + 4;
60 // r^root(pow_ 契约 [base,n]>1:r==1 时直接写 1;长度一律取返回值,
61 // pow_ 试探性进位写会使缓冲高位残留垃圾)
62 mp_size_t pl;
63 if (rn == 1 && r[0] == 1) {
64 lmmp_zero(pw, cap);
65 pw[0] = 1;
66 pl = 1;
67 } else {
68 pl = lmmp_pow_(pw, cap, r, rn, root);
69 }
70 // (r+1)^root
71 lmmp_zero(rp1, cap);
72 memcpy(rp1, r, (size_t)rn * 8);
73 add_small_inplace(rp1, cap, 1);
74 mp_size_t r1n = norm_len(rp1, cap);
75 if (r1n == 0) r1n = 1;
76 lmmp_zero(pw1, cap);
77 mp_size_t p1l = lmmp_pow_(pw1, cap, rp1, r1n, root);
78 TEST_CHECK_MSG(mpn_cmp(pw, pl, A, an) <= 0, "r^root <= A");
79 TEST_CHECK_MSG(mpn_cmp(A, an, pw1, p1l) < 0, "A < (r+1)^root");
80 if (rem) {
81 pad_add_value(pw, pl, rem, (root - 1) * rn + 1, cap, sum);
82 TEST_CHECK_MSG(mpn_eq(sum, cap, A, an), "A == r^root + rem");
83 }
84}
#define A
#define an
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
mp_size_t lmmp_pow_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算大整数幂 [dst,rn] = [base,n] ^ exp
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
static mp_ptr pad_add_value(const mp_limb_t *a, mp_size_t la, const mp_limb_t *b, mp_size_t lb, mp_size_t mx, mp_ptr sum)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 A, an, check_floor(), lmmp_pow_(), lmmp_zero, pad_add_value() , 以及 TEST_CHECK_MSG.

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

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

◆ pad_add_value()

mp_ptr pad_add_value ( const mp_limb_t * a,
mp_size_t la,
const mp_limb_t * b,
mp_size_t lb,
mp_size_t mx,
mp_ptr sum )
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_nthroot.c 第 43 行定义.

44 {
45 lmmp_zero(sum, mx);
46 memcpy(sum, a, (size_t)la * 8);
47 mp_ptr pad = alloc_limbs(mx);
48 lmmp_zero(pad, mx);
49 memcpy(pad, b, (size_t)lb * 8);
50 lmmp_add_n_(sum, sum, pad, mx);
51 lmmp_free(pad);
52 return sum;
53}
mp_limb_t * mp_ptr
定义 lmmp.h:96
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
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

引用了 lmmp_add_n_(), lmmp_free(), lmmp_zero , 以及 pad_add_value().

被这些函数引用 check_floor() , 以及 pad_add_value().

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

◆ pow_u64_ovf()

u64 pow_u64_ovf ( u64 r,
ulong k,
bool * ovf )
static

在文件 test_nthroot.c 第 87 行定义.

87 {
88 *ovf = false;
89 u64 acc = 1;
90 for (ulong i = 0; i < k; ++i) {
91 if (acc != 0 && r > UINT64_MAX / acc) *ovf = true;
92 acc *= r;
93 }
94 return acc;
95}
#define k
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
uint64_t ulong
定义 numth.h:39

引用了 k , 以及 pow_u64_ovf().

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

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

◆ TEST_CASE() [1/3]

TEST_CASE ( "numth/nthroot" ,
nthroot_top_probe_construction  )

在文件 test_nthroot.c 第 169 行定义.

169 {
170 u64 seed = 0xA5A512349ABCDEF7ull;
171 const ulong roots[] = {4, 5, 8, 16, 32, 64, 100};
172 const mp_size_t NRS[] = {4, 5};
173
174 for (size_t root_index = 0; root_index < ARRAY_SIZE(roots); ++root_index) {
175 ulong root = roots[root_index];
176 for (size_t nr_index = 0; nr_index < ARRAY_SIZE(NRS); ++nr_index) {
177 mp_size_t nr = NRS[nr_index];
178 /* 统一工作容量:S^root 与 S^root+root·S^(root-1) 均不超过
179 (S+1)^root < B^(root*(nr+1)),cap 含冗余 */
180 mp_size_t cap = (mp_size_t)root * (nr + 1) + 8;
181 mp_size_t tpsz = lmmp_nthroot_size_(cap, root);
182 mp_ptr numa = alloc_limbs((size_t)cap);
183 mp_ptr dst = alloc_limbs((size_t)(nr + 4));
184 mp_ptr dstr = alloc_limbs((size_t)((root - 1) * (nr + 4) + 8));
185 mp_ptr tp = alloc_limbs((size_t)tpsz);
186 mp_ptr pw = alloc_limbs((size_t)cap),
187 pw1 = alloc_limbs((size_t)cap),
188 rp1 = alloc_limbs((size_t)cap),
189 sum = alloc_limbs((size_t)cap);
190 mp_ptr Sp = alloc_limbs(nr), thr = alloc_limbs((size_t)cap);
191 for (int t = 0; t < 3; ++t) {
192 random_limbs(Sp, nr, &seed);
193 lmmp_zero(numa, cap);
194 lmmp_pow_(numa, cap, Sp, nr, root); // 恢复 S^root(d 循环借用了 numa)
195 // 阈值项 root·S^(root-1)
196 lmmp_zero(thr, cap);
197 mp_size_t tn = lmmp_pow_(thr, cap, Sp, nr, root - 1);
198 u64 hi = lmmp_mul_1_(thr, thr, tn, root);
199 if (hi) thr[tn++] = hi;
200
201 struct root_case { int kind; long long delta; } specs[] = {
202 {0, 0}, {0, 1}, {0, -1}, {0, 2}, {0, -2},
203 {1, -1}, {1, -2}, {1, -3}, // (S+1)^root - d
204 {2, 1}, {2, -1}, {2, 2}, {2, -2}, // S^root + root·S^(root-1) ± d
205 };
206 for (size_t sp_index = 0; sp_index < ARRAY_SIZE(specs); ++sp_index) {
207 const struct root_case sp = specs[sp_index];
208 mp_size_t na;
209 if (sp.kind == 1) {
210 lmmp_zero(rp1, cap);
211 memcpy(rp1, Sp, (size_t)nr * 8);
212 add_small_inplace(rp1, cap, 1);
213 mp_size_t s1n = norm_len(rp1, cap);
214 if (s1n == 0) s1n = 1;
215 lmmp_zero(numa, cap);
216 na = lmmp_pow_(numa, cap, rp1, s1n, root);
217 } else {
218 lmmp_zero(numa, cap);
219 na = lmmp_pow_(numa, cap, Sp, nr, root);
220 if (sp.kind == 2) {
221 mp_ptr t2 = alloc_limbs(cap);
222 lmmp_zero(t2, cap);
223 memcpy(t2, thr, (size_t)tn * 8);
224 lmmp_add_n_(numa, numa, t2, cap); // numa += root·S^(root-1)
225 lmmp_free(t2);
226 na = norm_len(numa, cap);
227 }
228 }
229 if (sp.delta > 0) {
230 add_small_inplace(numa, cap, (u64)sp.delta);
231 na = norm_len(numa, cap); // 进位可能延长(缓冲已零化)
232 } else if (sp.delta < 0) sub_small_inplace(numa, na, (u64)(-sp.delta));
233 if (numa[na - 1] == 0) continue;
234 mp_size_t nr2 = (na + (mp_size_t)root - 1) / (mp_size_t)root;
235 lmmp_nthroot_(dst, NULL, numa, na, root, tp); // NULL 余数路径同输入
236 check_floor(numa, na, dst, nr2, root, NULL, pw, pw1, rp1, sum);
237 lmmp_nthroot_(dst, dstr, numa, na, root, tp);
238 check_floor(numa, na, dst, nr2, root, dstr, pw, pw1, rp1, sum);
239 }
240 }
241 lmmp_free(numa); lmmp_free(dst); lmmp_free(dstr); lmmp_free(tp);
242 lmmp_free(pw); lmmp_free(pw1); lmmp_free(rp1); lmmp_free(sum);
243 lmmp_free(Sp); lmmp_free(thr);
244 }
245 }
246}
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
#define tp
mp_size_t lmmp_nthroot_size_(mp_size_t na, ulong root)
计算 lmmp_nthroot_ 所需的 tp 缓冲区长度(任意长度输入入口)
void lmmp_nthroot_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, ulong root, mp_ptr tp)
计算算术根 [dsts,nr] = floor([numa,na]^(1/root))(任意 na/任意顶 limb)
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
static void check_floor(const mp_limb_t *A, mp_size_t an, const mp_limb_t *r, mp_size_t rn, ulong root, const mp_limb_t *rem, mp_ptr pw, mp_ptr pw1, mp_ptr rp1, mp_ptr sum)

引用了 ARRAY_SIZE, check_floor(), lmmp_add_n_(), lmmp_free(), lmmp_mul_1_(), lmmp_nthroot_(), lmmp_nthroot_size_(), lmmp_pow_(), lmmp_zero, t, TEST_CASE , 以及 tp.

函数调用图:

◆ TEST_CASE() [2/3]

TEST_CASE ( "numth/nthroot" ,
nthroot_top_random_and_powers  )

在文件 test_nthroot.c 第 101 行定义.

101 {
102 u64 seed = 0xF1E2D3C4B5A69788ull;
103 const ulong roots[] = {4, 5, 8, 16, 32, 100};
104 const mp_size_t NAMAX = 520;
105 mp_size_t tpsize = 0;
106 for (size_t root_index = 0; root_index < ARRAY_SIZE(roots); ++root_index) {
107 ulong root = roots[root_index];
108 tpsize = LMMP_MAX(tpsize, lmmp_nthroot_size_(NAMAX, root));
109 }
110 mp_ptr numa = alloc_limbs(NAMAX), dst = alloc_limbs(64), tp = alloc_limbs((size_t)tpsize);
111 mp_ptr pw = alloc_limbs(NAMAX + 128), pw1 = alloc_limbs(NAMAX + 128),
112 rp1 = alloc_limbs(NAMAX + 128), sum = alloc_limbs(NAMAX + 128);
113
114 for (size_t root_index = 0; root_index < ARRAY_SIZE(roots); ++root_index) {
115 ulong root = roots[root_index];
116 for (mp_size_t na = 1; na <= 5 * (mp_size_t)root && na <= 64; na += (mp_size_t)root / 4 + 1) {
117 mp_size_t nr = (na + (mp_size_t)root - 1) / (mp_size_t)root;
118 mp_ptr dstr = alloc_limbs((size_t)((root - 1) * nr + 1));
119 for (int t = 0; t < 6; ++t) {
120 for (mp_size_t i = 0; i < na; ++i) numa[i] = xorshift64(&seed);
121 if (t & 1)
122 numa[na - 1] = ~(u64)0 - xorshift64(&seed) % (UINT64_MAX / 4); // 高顶
123 else
124 numa[na - 1] = xorshift64(&seed) % 0x10000 + 1; // 低顶
125 int calr = t & 2;
126 lmmp_nthroot_(dst, calr ? dstr : NULL, numa, na, root, tp);
127 check_floor(numa, na, dst, nr, root, calr ? dstr : NULL, pw, pw1, rp1, sum);
128 }
129 lmmp_free(dstr);
130 }
131 // 完全幂/±1(任意长度边界):S 经库 pow 构造 S^root
132 for (mp_size_t nr = 1; nr <= 3; ++nr) {
133 mp_ptr S = alloc_limbs(nr);
134 // 余数缓冲按根长 +1 档取(S^root 可恰好多一个根 limb,nr2 = nr+1)
135 mp_ptr dstr = alloc_limbs((size_t)((root - 1) * (nr + 1) + 2));
136 for (int t = 0; t < 3; ++t) {
137 random_limbs(S, nr, &seed);
138 mp_size_t cap = root * nr + root / 2 + 4;
139 lmmp_zero(numa, cap);
140 mp_size_t na = lmmp_pow_(numa, cap, S, nr, root); // 长度取返回值
141 if (na > NAMAX) continue;
142 for (int d = 0; d <= 1; ++d) {
143 if (d) sub_small_inplace(numa, na, 1); // A = S^root - 1
144 if (numa[na - 1] == 0) continue;
145 mp_size_t nr2 = (na + (mp_size_t)root - 1) / (mp_size_t)root;
146 lmmp_nthroot_(dst, dstr, numa, na, root, tp);
147 check_floor(numa, na, dst, nr2, root, dstr, pw, pw1, rp1, sum);
148 }
149 // 恢复 S^root(d 循环借用了 numa),下一 t 重建
150 }
151 lmmp_free(S);
152 lmmp_free(dstr);
153 }
154 }
155 lmmp_free(numa); lmmp_free(dst); lmmp_free(tp);
156 lmmp_free(pw); lmmp_free(pw1); lmmp_free(rp1); lmmp_free(sum);
157}
#define LMMP_MAX(h, i)
返回两个数中的较大值
定义 lmmp.h:454

引用了 ARRAY_SIZE, check_floor(), lmmp_free(), LMMP_MAX, lmmp_nthroot_(), lmmp_nthroot_size_(), lmmp_pow_(), lmmp_zero, t, TEST_CASE , 以及 tp.

函数调用图:

◆ TEST_CASE() [3/3]

TEST_CASE ( "numth/nthroot" ,
nthroot_ulong_scalar  )

在文件 test_nthroot.c 第 248 行定义.

248 {
249 u64 seed = 0x97531eca86420975ull;
250 for (int i = 0; i < 1500; ++i) {
251 u64 x = xorshift64(&seed);
252 if (x == 0) x = 1;
253 const ulong k_values[] = {2ul, 3ul, 4ul, 5ul, 7ul, 17ul, 63ul};
254 for (size_t k_index = 0; k_index < ARRAY_SIZE(k_values); ++k_index) {
255 ulong k = k_values[k_index];
256 u64 r = lmmp_nthroot_ulong_(x, k);
257 if (k == 2) TEST_CHECK_EQ(r, lmmp_sqrt_ulong_(x));
258 if (k == 3) TEST_CHECK_EQ(r, lmmp_cbrt_ulong_(x));
259 bool o1, o2;
260 u64 lo = pow_u64_ovf(r, k, &o1);
261 u64 hi = pow_u64_ovf(r + 1, k, &o2);
262 // r^k ≤ x(r^k 溢出即失败:x < 2^64 不可能容纳)
263 TEST_CHECK_MSG(!o1 && lo <= x, "r^k <= x");
264 // (r+1)^k > x(溢出即天然大于)
265 TEST_CHECK_MSG(o2 || hi > x, "x < (r+1)^k");
266 }
267 }
268 // 角点:0/1/全 1 与 root=0
271 TEST_CHECK_EQ(lmmp_nthroot_ulong_(UINT64_MAX, 2), 0xffffffffull);
272 TEST_CHECK_EQ(lmmp_nthroot_ulong_(UINT64_MAX, 3), 2642245ull);
273 TEST_CHECK_EQ(lmmp_nthroot_ulong_(12345, 0), 0u);
274}
#define lo
ulong lmmp_cbrt_ulong_(ulong n)
计算算数立方根 floor(cbrt(n))
ulong lmmp_sqrt_ulong_(ulong a)
计算算术平方根 floor(sqrt(a))
ulong lmmp_nthroot_ulong_(ulong n, ulong root)
计算 floor(n^(1/root))
#define TEST_CHECK_EQ(a, b)
定义 test.h:39
static u64 pow_u64_ovf(u64 r, ulong k, bool *ovf)

引用了 ARRAY_SIZE, k, lmmp_cbrt_ulong_(), lmmp_nthroot_ulong_(), lmmp_sqrt_ulong_(), lo, pow_u64_ovf(), TEST_CASE, TEST_CHECK_EQ , 以及 TEST_CHECK_MSG.

函数调用图:

◆ test_nthroot()

void test_nthroot ( void )

在文件 test_nthroot.c 第 276 行定义.

276 {
277 TEST_RUN("numth/nthroot", nthroot_top_random_and_powers);
278 TEST_RUN("numth/nthroot", nthroot_top_probe_construction);
279 TEST_RUN("numth/nthroot", nthroot_ulong_scalar);
280}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_nthroot() , 以及 TEST_RUN.

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

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