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

浏览该文件的源代码.

函数

static bool cbrt_floor_ok (const mp_limb_t *r, mp_size_t rn, const mp_limb_t *n, mp_size_t na)
static u64 icbrt_u64 (u64 x)
static u64 isqrt_u64 (u64 x)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
 TEST_CASE ("numth/cbrt", cbrt_6_divide_dispatcher)
 TEST_CASE ("numth/cbrt", cbrt_scalar_and_cbrt_3)
 TEST_CASE ("numth/cbrt", invcbrt_newton_semantics)
void test_cbrt (void)

函数说明

◆ cbrt_floor_ok()

bool cbrt_floor_ok ( const mp_limb_t * r,
mp_size_t rn,
const mp_limb_t * n,
mp_size_t na )
static

在文件 test_cbrt.c 第 64 行定义.

64 {
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}
#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)
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]
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 n

引用了 cbrt_floor_ok(), lmmp_add_n_(), lmmp_free(), lmmp_mul_(), lmmp_mul_1_(), lmmp_sqr_, lmmp_zero , 以及 n.

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

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

◆ icbrt_u64()

u64 icbrt_u64 ( u64 x)
static

在文件 test_cbrt.c 第 51 行定义.

51 {
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}
#define lo

引用了 icbrt_u64() , 以及 lo.

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

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

◆ isqrt_u64()

u64 isqrt_u64 ( u64 x)
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_cbrt.c 第 40 行定义.

40 {
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}

引用了 isqrt_u64() , 以及 lo.

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

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

◆ TEST_CASE() [1/3]

TEST_CASE ( "numth/cbrt" ,
cbrt_6_divide_dispatcher  )

在文件 test_cbrt.c 第 123 行定义.

123 {
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}
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]
#define tp
void lmmp_cbrt_6_fast_(mp_ptr dst, mp_ptr numa, mp_ptr tp)
计算算术立方根 [dst,2] = floor(cbrt([numa,6]))
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]))
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_CHECK_EQ(a, b)
定义 test.h:39
static bool cbrt_floor_ok(const mp_limb_t *r, mp_size_t rn, const mp_limb_t *n, mp_size_t na)

引用了 ARRAY_SIZE, cbrt_floor_ok(), lmmp_cbrt_(), lmmp_cbrt_6_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_cbrt_ulong_(), lmmp_free(), lmmp_mul_(), lmmp_sqr_, lmmp_sub_(), lmmp_zero, TEST_CASE, TEST_CHECK_EQ, TEST_CHECK_MSG , 以及 tp.

函数调用图:

◆ TEST_CASE() [2/3]

TEST_CASE ( "numth/cbrt" ,
cbrt_scalar_and_cbrt_3  )

在文件 test_cbrt.c 第 91 行定义.

91 {
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}
uint64_t mp_limb_t
定义 lmmp.h:92
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))
ulong lmmp_cbrt_chebyshev_(ulong n)
计算算数立方根 floor(cbrt(n))
ulong lmmp_nthroot_ulong_(ulong n, ulong root)
计算 floor(n^(1/root))
static u64 icbrt_u64(u64 x)
static u64 isqrt_u64(u64 x)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 ARRAY_SIZE, cbrt_floor_ok(), icbrt_u64(), isqrt_u64(), lmmp_cbrt_3_(), lmmp_cbrt_chebyshev_(), lmmp_cbrt_ulong_(), lmmp_nthroot_ulong_(), TEST_CASE, TEST_CHECK_EQ , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [3/3]

TEST_CASE ( "numth/cbrt" ,
invcbrt_newton_semantics  )

在文件 test_cbrt.c 第 238 行定义.

238 {
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}
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
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,...

引用了 ARRAY_SIZE, lmmp_cbrt_(), lmmp_div_(), lmmp_free(), lmmp_invcbrt_newton_(), lmmp_zero, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ test_cbrt()

void test_cbrt ( void )

在文件 test_cbrt.c 第 286 行定义.

286 {
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 TEST_RUN(category, name)
定义 test.h:36

引用了 test_cbrt() , 以及 TEST_RUN.

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

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