LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_nthroot.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/*
24 nthroot 家族验证(无 BigInt oracle):
25 1. floor 恒等式:r^root ≤ A < (r+1)^root,两端幂经 lmmp_pow_
26 (多 limb 底 × ulong 幂,由 pow 测试套独立保证)重建;
27 余数恒等式 A == r^root + rem(库加重建)
28 2. 完全幂 ±1 构造(A = S^root 经库 pow 构造)命中精确语义
29 3. 认证式窗口探针定向构造(回退带/阈值带:S^root、S^root±{1,2}、
30 (S+1)^root-{1,2,3}、S^root+root·S^(root-1)±{1,2})
31 4. 标量档 nthroot_ulong:r^k ≤ n < (r+1)^k(u64 溢出感知重建),
32 k=2/3 与 sqrt_ulong/cbrt_ulong 互比
33*/
34
35#include "lmmp/lmmpn.h"
36#include "lmmp/numth.h"
37#include "cases.h"
39
40#include <string.h>
41
42// 零垫对齐加法
43static 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,
44 mp_ptr sum) {
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}
54
55// oracle 校验:r = floor(A^(1/root)) 且(若给 rem)A == r^root + rem。
56// 幂经 lmmp_pow_(多 limb 底)重建,dst/工作区由调用方提供。
57static void check_floor(const mp_limb_t* A, mp_size_t an, const mp_limb_t* r, mp_size_t rn, ulong root,
58 const mp_limb_t* rem, mp_ptr pw, mp_ptr pw1, mp_ptr rp1, mp_ptr sum) {
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}
85
86// u64 幂(溢出感知:溢出置 *ovf,值无效)
87static u64 pow_u64_ovf(u64 r, ulong k, bool* ovf) {
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}
96
97/*
98 顶层入口:任意长度/任意顶 limb。na 步进覆盖对齐/非对齐形状,
99 root=4 行覆盖 sqrt∘sqrt 专用路线。
100*/
101TEST_CASE("numth/nthroot", nthroot_top_random_and_powers) {
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}
158
159/*
160 认证式窗口探针的定向构造输入:根长 >= 4 limb(bitlen(y) >= 256 gate
161 激活探针)下覆盖探针各判决与回退带:
162
163 - A = S^root(完全幂):必落不确定带 → 全幂回退,输出必须仍精确;
164 - A = S^root ± {1,2}:slack 在守卫带边缘;
165 - A = (S+1)^root - {1,2,3}:区间顶(e0=1 形状,dec 侧压力);
166 - A = S^root + root·S^(root-1) ± {1,2}:Bernoulli 阈值处——构造必中
167 回退带,正确性必须由定理+回退承载。
168*/
169TEST_CASE("numth/nthroot", nthroot_top_probe_construction) {
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}
247
248TEST_CASE("numth/nthroot", nthroot_ulong_scalar) {
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}
275
276void test_nthroot(void) {
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 k
#define A
#define an
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define LMMP_MAX(h, i)
返回两个数中的较大值
定义 lmmp.h:454
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
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
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 t
#define tp
#define lo
void test_nthroot(void)
mp_size_t lmmp_nthroot_size_(mp_size_t na, ulong root)
计算 lmmp_nthroot_ 所需的 tp 缓冲区长度(任意长度输入入口)
ulong lmmp_cbrt_ulong_(ulong n)
计算算数立方根 floor(cbrt(n))
ulong lmmp_sqrt_ulong_(ulong a)
计算算术平方根 floor(sqrt(a))
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
ulong lmmp_nthroot_ulong_(ulong n, ulong root)
计算 floor(n^(1/root))
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)
uint64_t ulong
定义 numth.h:39
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#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
static u64 pow_u64_ovf(u64 r, ulong k, bool *ovf)
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)