LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_cbrt.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/* cbrt 家族验证(无 BigInt oracle;sqrt 见 test_numth_sqrt.cpp):
24 1. floor 恒等式:r³ ≤ n < (r+1)³((r+1)^3 = r³+3r²+3r+1 经库乘加重建)、
25 余数恒等式 n == r³ + rem
26 2. 标量档(u64):icbrt 二分参考(64 位内)+ 完全立方角点
27 3. 入口互比:cbrt_3/cbrt_6/cbrt_divide_/cbrt_ 生产入口;完全立方构造
28 (sqr+mul 后 ±1)命中精确语义
29 4. 逆立方根语义:invcbrt 下近似区间 [I-1, I](参照经 div_+cbrt_ 库链构造)
30*/
31
32#include "lmmp/lmmpn.h"
33#include "lmmp/numth.h"
34#include "cases.h"
36
37#include <string.h>
38
39// u64 isqrt 简单参考(二分,64 位内;root=2 交叉用)
40static u64 isqrt_u64(u64 x) {
41 if (x == 0) return 0;
42 u64 lo = 1, hi = 0xffffffffull;
43 while (lo < hi) {
44 u64 mid = lo + (hi - lo + 1) / 2;
45 if (mid <= x / mid) lo = mid;
46 else hi = mid - 1;
47 }
48 return lo;
49}
50
51static u64 icbrt_u64(u64 x) {
52 if (x == 0) return 0;
53 u64 lo = 1, hi = 2642246ull; // floor(cbrt(2^64-1))
54 while (lo < hi) {
55 u64 mid = lo + (hi - lo + 1) / 2;
56 // mid*mid*mid <= x:mid <= 2642246 ⟹ 三积 < 2^64
57 if (mid <= x / (mid * mid)) lo = mid;
58 else hi = mid - 1;
59 }
60 return lo;
61}
62
63// r³ ≤ n < (r+1)³:立方经库乘两步 + 多项式展开 (r+1)³ = r³ + 3r² + 3r + 1
64static bool cbrt_floor_ok(const mp_limb_t* r, mp_size_t rn, const mp_limb_t* n, mp_size_t na) {
65 mp_size_t mx = 3 * rn + 4;
66 mp_ptr t1 = alloc_limbs(2 * rn), t2 = alloc_limbs(3 * rn), t3 = alloc_limbs(mx),
67 add = alloc_limbs(mx), r2x3 = alloc_limbs(2 * rn + 1), r3x = alloc_limbs(rn + 1);
68 lmmp_sqr_(t1, r, rn); // r^2
69 lmmp_mul_(t2, t1, 2 * rn, r, rn); // r^3
70 lmmp_zero(t3, mx);
71 memcpy(t3, t2, (size_t)(3 * rn) * 8);
72 u64 hi = lmmp_mul_1_(r2x3, t1, 2 * rn, 3); // 3r^2
73 mp_size_t l = 2 * rn;
74 if (hi) r2x3[l++] = hi;
75 lmmp_zero(add, mx);
76 memcpy(add, r2x3, (size_t)l * 8);
77 lmmp_add_n_(t3, t3, add, mx);
78 lmmp_zero(r3x, rn + 1); // 3r + 1
79 memcpy(r3x, r, (size_t)rn * 8);
80 lmmp_mul_1_(r3x, r3x, rn + 1, 3);
81 add_small_inplace(r3x, rn + 1, 1);
82 lmmp_zero(add, mx);
83 memcpy(add, r3x, (size_t)(rn + 1) * 8);
84 lmmp_add_n_(t3, t3, add, mx);
85 mp_size_t np1 = norm_len(t3, mx);
86 bool ok = mpn_cmp(t2, 3 * rn, n, na) <= 0 && mpn_cmp(n, na, t3, np1) < 0;
87 lmmp_free(t1); lmmp_free(t2); lmmp_free(t3); lmmp_free(add); lmmp_free(r2x3); lmmp_free(r3x);
88 return ok;
89}
90
91TEST_CASE("numth/cbrt", cbrt_scalar_and_cbrt_3) {
92 u64 seed = 0x0badcafef00dfaceull;
93 for (int i = 0; i < 1000; ++i) {
94 u64 x = xorshift64(&seed);
95 if (x == 0) x = 1;
99 TEST_CHECK_EQ(lmmp_nthroot_ulong_(x, 2), isqrt_u64(x)); // root=2 分派 sqrt_ulong_
100 }
102 TEST_CHECK_EQ(lmmp_cbrt_ulong_(UINT64_MAX), 2642245ull); // floor(cbrt(2^64-1))
103 // 完全立方角点(u64 内):cbrt(r³)=r、cbrt(r³-1)=r-1、cbrt(r³+1)=r
104 const u64 r_values[] = {2ull, 100ull, 2642245ull};
105 for (size_t r_index = 0; r_index < ARRAY_SIZE(r_values); ++r_index) {
106 u64 r = r_values[r_index];
107 u64 c = r * r * r;
109 TEST_CHECK_EQ(lmmp_cbrt_ulong_(c - 1), r - 1);
111 }
112 // cbrt_3:3 limb 输入 floor 恒等式((r+1)^3 经库原语重建)
113 for (int iter = 0; iter < 150; ++iter) {
114 mp_limb_t x[3];
115 random_limbs_with_top(x, 3, &seed, false);
116 if (x[1] == 0) x[1] = 1; // 契约至少 65 bit
117 u64 c = lmmp_cbrt_3_(x[0], x[1], x[2]);
118 mp_limb_t rc[1] = {c};
119 TEST_CHECK_MSG(cbrt_floor_ok(rc, 1, x, 3), "cbrt_3 floor property");
120 }
121}
122
123TEST_CASE("numth/cbrt", cbrt_6_divide_dispatcher) {
124 u64 seed = 0x3cb7135c1f2a9e11ull;
125 for (int shape = 0; shape < 3; ++shape) {
126 const mp_size_t ns_values[] = {2, 4};
127 for (size_t ns_index = 0; ns_index < ARRAY_SIZE(ns_values); ++ns_index) {
128 mp_size_t ns = ns_values[ns_index]; // 输入 3*ns limbs
129 for (int iter = 0; iter < 4; ++iter) {
130 mp_size_t na = 3 * ns;
131 mp_ptr numa = alloc_limbs(na), numa2 = alloc_limbs(na),
132 dst = alloc_limbs(ns + 1), t1 = alloc_limbs(2 * ns + 2),
133 t2 = alloc_limbs(3 * ns + 2), t3 = alloc_limbs(3 * ns + 8);
134 random_limbs(numa, na, &seed);
135 if (shape == 1) { // 完全立方:t^3(库 pow 链);t 顶三位置 1
136 mp_ptr tt = alloc_limbs(ns); // 保证 t^3 顶 limb >= 0x6000...
137 random_limbs(tt, ns, &seed);
138 tt[ns - 1] |= (u64)0xE << 60;
139 lmmp_sqr_(t1, tt, ns);
140 lmmp_mul_(numa, t1, 2 * ns, tt, ns);
141 lmmp_free(tt);
142 } else if (shape == 2) {
143 mp_ptr tt = alloc_limbs(ns);
144 random_limbs(tt, ns, &seed);
145 tt[ns - 1] |= (u64)0xE << 60;
146 lmmp_sqr_(t1, tt, ns);
147 lmmp_mul_(numa, t1, 2 * ns, tt, ns);
148 sub_small_inplace(numa, na, 1);
149 lmmp_free(tt);
150 }
151 // random 形态顶 limb 已含 bit63(>= 0x8000 > 0x6000 契约);构造形态
152 // 由 tt 顶三位保证,不得再改 numa(保持完全立方语义)
153 // cbrt_6_(3<na<=6)或 cbrt_divide_(na=3ns)
154 if (na <= 6) {
155 lmmp_cbrt_6_(dst, numa, na);
156 if (na == 6) {
157 // cbrt6_fast_ 直接入口:结果与 cbrt_6_ 一致 + 余数恒等式
158 // [numa2,5] = [numa,6] - [dst,2]^3(立方经库乘重建)
159 mp_ptr tp = alloc_limbs(8), dst2 = alloc_limbs(2);
160 memcpy(numa2, numa, (size_t)na * 8);
161 lmmp_cbrt_6_fast_(dst2, numa2, tp);
162 TEST_CHECK_MSG(dst2[0] == dst[0] && dst2[1] == dst[1],
163 "cbrt6_fast matches cbrt_6");
164 mp_ptr s2 = alloc_limbs(4), c3 = alloc_limbs(6);
165 lmmp_sqr_(s2, dst2, 2);
166 lmmp_mul_(c3, s2, 4, dst2, 2);
167 mp_ptr rem = alloc_limbs(6);
168 for (mp_size_t i = 0; i < 6; ++i)
169 rem[i] = i < na ? numa[i] : 0;
170 TEST_CHECK_MSG(lmmp_sub_(rem, rem, 6, c3, 6) == 0 &&
171 mpn_cmp(rem, 6, numa2, 5) == 0,
172 "cbrt6_fast remainder identity");
173 lmmp_free(tp); lmmp_free(dst2); lmmp_free(s2);
174 lmmp_free(c3); lmmp_free(rem);
175 }
176 } else {
177 mp_ptr tp = alloc_limbs(6 * ns + 4);
178 memcpy(numa2, numa, (size_t)na * 8);
179 lmmp_cbrt_divide_(dst, numa2, ns, tp, 1);
180 lmmp_free(tp);
181 }
182 mp_size_t rn = norm_len(dst, ns);
183 TEST_CHECK_MSG(cbrt_floor_ok(dst, rn > 0 ? rn : 1, numa, na),
184 "cbrt_6/divide floor");
185 if (shape == 1 && na > 6)
186 TEST_CHECK_MSG(norm_len(numa2, 2 * ns) == 0,
187 "perfect cube rem 0 (divide)");
188 lmmp_free(numa); lmmp_free(numa2); lmmp_free(dst);
189 lmmp_free(t1); lmmp_free(t2); lmmp_free(t3);
190 }
191 }
192 }
193 // cbrt_ 生产入口:nf=0 精确 floor;完全立方 ±1 构造;与 cbrt_ulong 互比
194 const mp_size_t na_values[] = {1, 2, 3, 5, 8, 16};
195 for (size_t na_index = 0; na_index < ARRAY_SIZE(na_values); ++na_index) {
196 mp_size_t na = na_values[na_index];
197 for (int family = 0; family < 3; ++family) {
198 mp_ptr numa = alloc_limbs(na);
199 random_limbs(numa, na, &seed);
200 if (numa[na - 1] == 0) numa[na - 1] = 1;
201 if (family > 0 && na % 3 == 0) {
202 mp_size_t nt = na / 3;
203 mp_ptr tt = alloc_limbs(nt), sq = alloc_limbs(2 * nt);
204 random_limbs(tt, nt, &seed);
205 lmmp_sqr_(sq, tt, nt);
206 lmmp_mul_(numa, sq, 2 * nt, tt, nt);
207 if (family == 2) sub_small_inplace(numa, na, 1);
208 lmmp_free(tt); lmmp_free(sq);
209 }
210 mp_size_t ns = na / 3 + 1;
211 mp_ptr dsts = alloc_limbs(ns + 4), dstr = alloc_limbs(2 * ns + 4),
212 t1 = alloc_limbs(2 * ns + 4), t2 = alloc_limbs(3 * ns + 4),
213 t3 = alloc_limbs(3 * ns + 10);
214 lmmp_zero(dsts, ns + 4); // 根/余数短于缓冲时高位不得混入垃圾
215 lmmp_zero(dstr, 2 * ns + 4);
216 lmmp_cbrt_(dsts, dstr, numa, na, 0);
217 mp_size_t rn = norm_len(dsts, ns);
218 TEST_CHECK_MSG(cbrt_floor_ok(dsts, rn > 0 ? rn : 1, numa, na),
219 "cbrt_ floor identity");
220 // 余数恒等式:n == r³ + rem
221 {
222 lmmp_sqr_(t1, dsts, rn > 0 ? rn : 1);
223 lmmp_mul_(t2, t1, 2 * rn, dsts, rn);
224 mp_ptr sum = alloc_limbs(3 * ns + 6);
225 pad_add(t2, 3 * rn, dstr, 2 * ns + 1, 3 * ns + 6, sum);
226 TEST_CHECK_MSG(mpn_eq(sum, 3 * ns + 6, numa, na), "cbrt_ n == r^3 + rem");
227 lmmp_free(sum);
228 }
229 // 单 limb 输入与 cbrt_ulong_ 互比
230 if (na == 1)
231 TEST_CHECK_EQ(dsts[0], lmmp_cbrt_ulong_(numa[0]));
232 lmmp_free(numa); lmmp_free(dsts); lmmp_free(dstr);
233 lmmp_free(t1); lmmp_free(t2); lmmp_free(t3);
234 }
235 }
236}
237
238TEST_CASE("numth/cbrt", invcbrt_newton_semantics) {
239 // I-1 <= ir <= I(绝不高估);I = floor(cbrt(B^(3ns+na)/a)) 经库链构造
240 u64 seed = 0x11c0ffee22c0ffeeull;
241 const mp_size_t na_values[] = {1, 3, 8};
242 for (size_t na_index = 0; na_index < ARRAY_SIZE(na_values); ++na_index) {
243 mp_size_t na = na_values[na_index];
244 const mp_size_t ns_values[] = {4, 8};
245 for (size_t ns_index = 0; ns_index < ARRAY_SIZE(ns_values); ++ns_index) {
246 mp_size_t ns = ns_values[ns_index];
247 if (ns == na) continue;
248 mp_ptr a = alloc_limbs(na), dstis = alloc_limbs(ns + 2), icq = alloc_limbs(ns + 2),
249 nb = alloc_limbs(3 * ns + na + 4), q = alloc_limbs(3 * ns + 4);
250 for (int f = 0; f < 3; ++f) {
251 lmmp_zero(a, na);
252 if (f < 2) {
253 random_limbs(a, na, &seed);
254 a[na - 1] |= (u64)1 << 61;
255 } else {
256 for (mp_size_t i = 0; i < na; ++i) a[i] = ~(u64)0;
257 }
258 lmmp_zero(dstis, ns + 2);
259 lmmp_invcbrt_newton_(dstis, ns, a, na);
260 TEST_CHECK_MSG(dstis[ns] >= 1, "invcbrt top limb >= 1");
261 // I = floor(cbrt(B^(3ns+na)/a))
262 mp_size_t e = 3 * ns + na;
263 mp_size_t L = e + 1;
264 lmmp_zero(nb, L);
265 nb[L - 1] = 1;
266 lmmp_div_(q, NULL, nb, L, a, na);
267 mp_size_t ql = L - na + 1;
268 while (ql > 1 && q[ql - 1] == 0) --ql;
269 lmmp_zero(icq, ns + 2); // 根短时高位不得混入垃圾
270 lmmp_cbrt_(icq, NULL, q, ql, 0);
271 mp_size_t il = (ql + 2) / 3 + 1;
272 mp_ptr im1 = alloc_limbs(ns + 2);
273 lmmp_zero(im1, ns + 2);
274 memcpy(im1, icq, (size_t)il * 8);
275 sub_small_inplace(im1, ns + 2, 1);
276 bool ok = memcmp(dstis, icq, (size_t)(ns + 1) * 8) == 0 ||
277 memcmp(dstis, im1, (size_t)(ns + 1) * 8) == 0;
278 TEST_CHECK_MSG(ok, "invcbrt in {I-1, I}");
279 lmmp_free(im1);
280 }
281 lmmp_free(a); lmmp_free(dstis); lmmp_free(icq); lmmp_free(nb); lmmp_free(q);
282 }
283 }
284}
285
286void test_cbrt(void) {
287 TEST_RUN("numth/cbrt", cbrt_scalar_and_cbrt_3);
288 TEST_RUN("numth/cbrt", cbrt_6_divide_dispatcher);
289 TEST_RUN("numth/cbrt", invcbrt_newton_semantics);
290}
#define lmmp_sqr_
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)
uint64_t mp_limb_t
定义 lmmp.h:92
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]
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]
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
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
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 tp
#define n
#define lo
void test_cbrt(void)
mp_limb_t lmmp_cbrt_3_(mp_limb_t a0, mp_limb_t a1, mp_limb_t a2)
计算算数立方根 floor(cbrt(a0+a1*B+a2*B^2))
void lmmp_cbrt_6_fast_(mp_ptr dst, mp_ptr numa, mp_ptr tp)
计算算术立方根 [dst,2] = floor(cbrt([numa,6]))
ulong lmmp_cbrt_chebyshev_(ulong n)
计算算数立方根 floor(cbrt(n))
void lmmp_cbrt_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算 [numa,na] * B^(3*nf) 的立方根和余数
定义 cbrt.c:718
ulong lmmp_cbrt_ulong_(ulong n)
计算算数立方根 floor(cbrt(n))
void lmmp_cbrt_6_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
计算算术立方根 floor(cbrt([numa,na]))
ulong lmmp_nthroot_ulong_(ulong n, ulong root)
计算 floor(n^(1/root))
void lmmp_invcbrt_newton_(mp_ptr dstis, mp_size_t ns, mp_srcptr numa, mp_size_t na)
计算逆立方根的定点下近似:记 I=floor(cbrt(B^(3*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,...
void lmmp_cbrt_divide_(mp_ptr dst, mp_ptr numa, mp_size_t ns, mp_ptr tp, int calr)
计算算术立方根 floor(cbrt([numa,3*ns]))
#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 icbrt_u64(u64 x)
static u64 isqrt_u64(u64 x)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static bool cbrt_floor_ok(const mp_limb_t *r, mp_size_t rn, const mp_limb_t *n, mp_size_t na)