LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
cbrt_1.c 文件参考
#include "impl/inlines.h"
#include "impl/longlong.h"
#include "numth/log2_exp2.h"
#include "impl/mul_hard.h"
#include "lmmp/numth.h"
#include "lmmp/lmmpn.h"
cbrt_1.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define CBRT_DIVIDE_MIN   (0x6000000000000000ull)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

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_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 计算算术立方根 floor(cbrt([numa,na]))
static void lmmp_cbrt_6_est_ (mp_ptr r, mp_srcptr numa, mp_size_t n)
void lmmp_cbrt_6_fast_ (mp_ptr restrict dst, mp_ptr restrict numa, mp_ptr restrict tp)
static void lmmp_cbrt_6_fix_ (mp_ptr r, mp_srcptr a, mp_ptr t)
static void lmmp_cube_3_ (mp_ptr restrict dst, mp_limb_t a)
static void lmmp_cube_6_ (mp_ptr restrict t, mp_srcptr restrict r)
 计算 [t,6]=[r,2]^3
static mp_limb_t lmmp_div3_ (mp_ptr q, mp_srcptr a, mp_size_t n)
static mp_limb_t lmmp_shr64_ (mp_srcptr p, mp_size_t n, uint64_t s)

宏定义说明

◆ CBRT_DIVIDE_MIN

#define CBRT_DIVIDE_MIN   (0x6000000000000000ull)

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

在文件 cbrt_1.c 第 31 行定义.

函数说明

◆ lmmp_cbrt_3_()

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))

参数
a0低位 limb
a1中位 limb
a2高位 limb
警告
a1和a2应至少有一个大于0
注解
a2可以为0,但a1需要大于0,即这个数至少应有65个bit
返回
floor(cbrt(a0+a1*B+a2*B^2))

在文件 cbrt_1.c 第 63 行定义.

63 {
64 lmmp_param_assert(a1 > 0 || a2 > 0);
65 mp_limb_t x[2];
66 /* exact high 65 bits */
67 mp_limb_t a_hi;
68 mp_bitcnt_t bits;
69 if (a2 == 0) {
71 bits = LIMB_BITS + a1_bits;
72 a1_bits--;
73 if (a1_bits == 0)
74 a_hi = a0;
75 else
76 a_hi = (a1 << (LIMB_BITS - a1_bits)) | (a0 >> a1_bits);
77 } else {
79 bits = LIMB_BITS * 2 + a2_bits;
80 a2_bits--;
81 if (a2_bits == 0)
82 a_hi = a1;
83 else
84 a_hi = (a2 << (LIMB_BITS - a2_bits)) | (a1 >> a2_bits);
85 }
86 lmmp_debug_assert(bits >= 65);
87
88 x[1] = bits - 1;
89 x[0] = log2_fixed_64(a_hi);
90
91 mp_limb_t rem = lmmp_div3_(x, x, 2);
92 if (2 * rem >= 3) // round
93 lmmp_inc(x);
94
95 mp_bitcnt_t shift = x[1];
96 x[0] = exp2_fixed_64(x[0]);
97
98 lmmp_debug_assert(shift <= 64);
99 mp_limb_t r;
100 if (shift == 64)
101 r = LIMB_MAX;
102 else
103 r = (x[0] >> (64 - shift)) | (1ULL << shift);
104
105 // log2/exp2 固定精度近似存在 +-2 ulp 的误差,用单调立方比较修正
106 // 到精确 floor:先降后升,两个循环均在真值处终止。
107 mp_limb_t t[3], a[3] = {a0, a1, a2};
108 lmmp_cube_3_(t, r);
109 while (lmmp_cmp_(t, a, 3) > 0) {
110 --r;
111 lmmp_cube_3_(t, r);
112 }
113 while (r < LIMB_MAX) {
114 lmmp_cube_3_(t, r + 1);
115 if (lmmp_cmp_(t, a, 3) > 0) break;
116 ++r;
117 }
118 return r;
119}
static void lmmp_cube_3_(mp_ptr restrict dst, mp_limb_t a)
定义 cbrt.c:38
static mp_limb_t lmmp_div3_(mp_ptr q, mp_srcptr a, mp_size_t n)
#define lmmp_limb_bits_
size_t mp_bitcnt_t
定义 lmmp.h:98
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define LIMB_MAX
定义 lmmp.h:105
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define lmmp_inc(p)
加1宏(预期无进位)
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
uint64_t exp2_fixed_64(uint64_t x)
计算 floor(exp2(x/B)*B-B), B=2^64
uint64_t log2_fixed_64(uint64_t x)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define a0
#define a1
#define a2
#define t

引用了 a0, a1, a2, exp2_fixed_64(), LIMB_BITS, LIMB_MAX, lmmp_cbrt_3_(), lmmp_cmp_(), lmmp_cube_3_(), lmmp_debug_assert, lmmp_div3_(), lmmp_inc, lmmp_limb_bits_, lmmp_param_assert, log2_fixed_64() , 以及 t.

被这些函数引用 lmmp_cbrt_(), lmmp_cbrt_3_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_invsqrt_newton_() , 以及 TEST_CASE().

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

◆ lmmp_cbrt_6_()

void lmmp_cbrt_6_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

计算算术立方根 floor(cbrt([numa,na]))

参数
dst结果指针(2个limb)
numa被开方数指针
na被开方数的 limb 长度
警告
3<na<=6, numa[na-1]!=0, dst!=NULL, numa!=NULL, sep(dst,numa)

在文件 cbrt_1.c 第 274 行定义.

274 {
275 lmmp_param_assert(na > 3 && na <= 6);
276 lmmp_param_assert(dst != NULL && numa != NULL);
277 lmmp_param_assert(numa[na - 1] != 0);
278 mp_limb_t a[6] = {0, 0, 0, 0, 0, 0};
279 for (mp_size_t i = 0; i < na; i++) a[i] = numa[i];
280 if (na == 6 && a[5] >= CBRT_DIVIDE_MIN) {
281 // cbrt_3 种子 + 除法修正:比 log2/exp2 估计更快(条件与
282 // cbrt_divide_ 相同,保证 div_s 的 MSB 归一化要求)
283 mp_limb_t tp[10];
284 lmmp_cbrt_6_fast_(dst, a, tp);
285 return;
286 }
287 mp_limb_t t[10];
288 lmmp_cbrt_6_est_(dst, numa, na);
289 lmmp_cbrt_6_fix_(dst, a, t);
290}
#define CBRT_DIVIDE_MIN
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 cbrt.c:36
static void lmmp_cbrt_6_est_(mp_ptr r, mp_srcptr numa, mp_size_t n)
static void lmmp_cbrt_6_fix_(mp_ptr r, mp_srcptr a, mp_ptr t)
uint64_t mp_size_t
定义 lmmp.h:93
#define tp
void lmmp_cbrt_6_fast_(mp_ptr dst, mp_ptr numa, mp_ptr tp)
计算算术立方根 [dst,2] = floor(cbrt([numa,6]))

引用了 CBRT_DIVIDE_MIN, lmmp_cbrt_6_(), lmmp_cbrt_6_est_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_6_fix_(), lmmp_param_assert, t , 以及 tp.

被这些函数引用 lmmp_cbrt_(), lmmp_cbrt_6_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_() , 以及 TEST_CASE().

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

◆ lmmp_cbrt_6_est_()

void lmmp_cbrt_6_est_ ( mp_ptr r,
mp_srcptr numa,
mp_size_t n )
static

在文件 cbrt_1.c 第 152 行定义.

152 {
153 mp_bitcnt_t hb = lmmp_limb_bits_(numa[n - 1]);
154 uint64_t bits = LIMB_BITS * (n - 1) + hb; // in [193,384]
155 uint64_t s0 = bits - 129; // 最高 129bit 的起始位
156
157 mp_limb_t x[3];
158 log2_fixed_128(x, lmmp_shr64_(numa, n, s0 + 64), lmmp_shr64_(numa, n, s0));
159 x[2] = bits - 1;
160
161 mp_limb_t rem = lmmp_div3_(x, x, 3);
162 if (2 * rem >= 3) // round
163 lmmp_inc(x);
164
165 uint64_t s = x[2]; // in [64,128]
166 mp_limb_t e[2];
167 exp2_fixed_128(e, x[1], x[0]);
168
169 if (s >= 128) {
170 // 舍入进位到 2^128,钳位后交给修正循环
171 r[0] = r[1] = LIMB_MAX;
172 return;
173 }
174 // r = 2^s + (e >> (128-s)),总 < 2^(s+1) <= 2^128 不溢出
175 mp_limb_t d = 128 - s; // in [1,64]
176 if (d == 64) {
177 r[0] = e[1];
178 r[1] = 1;
179 } else {
180 r[0] = (e[1] << (64 - d)) | (e[0] >> d);
181 r[1] = (e[1] >> d) | (1ULL << (s - 64));
182 }
183}
static mp_limb_t lmmp_shr64_(mp_srcptr p, mp_size_t n, uint64_t s)
void exp2_fixed_128(uint64_t *dst, uint64_t high, uint64_t low)
计算 floor(exp2(x/B)*B-B), B=2^128
void log2_fixed_128(uint64_t *dst, uint64_t high, uint64_t low)
计算 floor(log2(1+x/B)*B), B=2^128
#define s
#define n

引用了 exp2_fixed_128(), LIMB_BITS, LIMB_MAX, lmmp_cbrt_6_est_(), lmmp_div3_(), lmmp_inc, lmmp_limb_bits_, lmmp_shr64_(), log2_fixed_128(), n , 以及 s.

被这些函数引用 lmmp_cbrt_6_() , 以及 lmmp_cbrt_6_est_().

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

◆ lmmp_cbrt_6_fast_()

void lmmp_cbrt_6_fast_ ( mp_ptr restrict dst,
mp_ptr restrict numa,
mp_ptr restrict tp )

在文件 cbrt_1.c 第 231 行定义.

231 {
232 lmmp_param_assert(numa != NULL && dst != NULL && tp != NULL);
234
235 dst[1] = lmmp_cbrt_3_(numa[3], numa[4], numa[5]);
236 lmmp_cube_3_(tp, dst[1]);
237 lmmp_sub_n_(numa + 3, numa + 3, tp, 3); // rk = Ah - Ahr^3
238
239 lmmp_mullh_((dst + 1)[0], (dst + 1)[0], tp + 3); // Ahr2 = [tp+3,2]
240 /*
241 A / (3*x^2) = A / 3 / x^2
242 A % (3*x^2) = 3 * (A / 3 % x^2) + A % 3
243 */
244 mp_limb_t r = lmmp_div3_(numa + 2, numa + 2, 4);
245 mp_limb_t qh = lmmp_div_s_(tp + 5, numa + 2, 4, tp + 3, 2); // Alr = [tp+5,3)
246 lmmp_debug_assert(qh == 0);
247 numa[4] = lmmp_mul_1_(numa + 2, numa + 2, 2, 3);
248 lmmp_inc_1(numa + 2, r);
249
250 mp_limb_t rsav[6], w[6], u2[4], u3[5], x3sq[6];
251 rsav[5] = 0;
252 lmmp_copy(rsav, numa, 5);
253 x3sq[0] = 0;
254 x3sq[1] = 0;
255 x3sq[5] = 0;
256 lmmp_mullh_((dst + 1)[0], (dst + 1)[0], u2); // u2 = Ahr^2
257 x3sq[4] = lmmp_mul_1_(x3sq + 2, u2, 2, 3); // 3*x^2 = 3*Ahr^2*B^2 占 [2,5)
258 for (;;) {
259 w[0] = 0;
260 lmmp_sqr_hard_2_(u2, tp + 5); // u^2
261 w[4] = lmmp_mul_1_(w + 1, u2, 3, (dst + 1)[0]); // Ahr*u^2 占 [1,5)
262 w[5] = lmmp_mul_1_(w + 1, w + 1, 4, 3); // 3*Ahr*u^2*B
263 lmmp_mul_basecase_(u3, u2, 3, tp + 5, 2); // u^3
264 w[5] += lmmp_add_n_(w, w, u3, 5); // W < 4*B^5,w[5] <= 4 不溢出
265 if (lmmp_sub_(numa, rsav, 6, w, 6) == 0)
266 break;
267 lmmp_dec(tp + 5);
268 mp_limb_t ca = lmmp_add_n_(rsav, rsav, x3sq, 6); // rsav < 12*B^4,无进位
269 lmmp_debug_assert(ca == 0);
270 }
271 dst[0] = tp[5];
272}
#define lmmp_mullh_
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
mp_limb_t lmmp_div_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法运算
#define lmmp_dec(p)
减1宏(预期无借位)
void lmmp_mul_basecase_(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
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
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
void lmmp_sqr_hard_2_(mp_ptr dst, mp_srcptr numa)
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))

引用了 CBRT_DIVIDE_MIN, lmmp_add_n_(), lmmp_cbrt_3_(), lmmp_cbrt_6_fast_(), lmmp_copy, lmmp_cube_3_(), lmmp_debug_assert, lmmp_dec, lmmp_div3_(), lmmp_div_s_(), lmmp_inc_1, lmmp_mul_1_(), lmmp_mul_basecase_(), lmmp_mullh_, lmmp_param_assert, lmmp_sqr_hard_2_(), lmmp_sub_(), lmmp_sub_n_(), restrict , 以及 tp.

函数调用图:

◆ lmmp_cbrt_6_fix_()

void lmmp_cbrt_6_fix_ ( mp_ptr r,
mp_srcptr a,
mp_ptr t )
static

在文件 cbrt_1.c 第 192 行定义.

192 {
193 mp_limb_t u[2], ut[10];
194 lmmp_cube_6_(t, r);
195 while (lmmp_cmp_(t, a, 6) > 0) {
196 lmmp_dec(r);
197 lmmp_cube_6_(t, r);
198 }
199 if (r[0] == LIMB_MAX && r[1] == LIMB_MAX) return;
200 u[0] = r[0] + 1;
201 u[1] = r[1] + (u[0] == 0);
202 lmmp_cube_6_(ut, u);
203 while (lmmp_cmp_(ut, a, 6) <= 0) {
204 r[0] = u[0];
205 r[1] = u[1];
206 lmmp_copy(t, ut, 6);
207 if (u[0] == LIMB_MAX && u[1] == LIMB_MAX) return; // A < B^6,不会到达
208 u[0] += 1;
209 u[1] += (u[0] == 0);
210 lmmp_cube_6_(ut, u);
211 }
212}
static void lmmp_cube_6_(mp_ptr restrict t, mp_srcptr restrict r)
计算 [t,6]=[r,2]^3
定义 cbrt.c:51

引用了 LIMB_MAX, lmmp_cbrt_6_fix_(), lmmp_cmp_(), lmmp_copy, lmmp_cube_6_(), lmmp_dec , 以及 t.

被这些函数引用 lmmp_cbrt_6_() , 以及 lmmp_cbrt_6_fix_().

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

◆ lmmp_cube_3_()

void lmmp_cube_3_ ( mp_ptr restrict dst,
mp_limb_t a )
inlinestatic

在文件 cbrt_1.c 第 54 行定义.

54 {
55 mp_limb_t t[2];
56 lmmp_mullh_(a, a, t);
57 lmmp_mullh_(t[0], a, dst);
58 lmmp_mullh_(t[1], a, t);
59 dst[1] += t[0];
60 dst[2] = t[1] + (dst[1] < t[0] ? 1 : 0);
61}

引用了 lmmp_cube_3_(), lmmp_mullh_, restrict , 以及 t.

函数调用图:

◆ lmmp_cube_6_()

void lmmp_cube_6_ ( mp_ptr restrict t,
mp_srcptr restrict r )
inlinestatic

计算 [t,6]=[r,2]^3

注解
[t+6,4]=[r,2]^2

在文件 cbrt_1.c 第 146 行定义.

146 {
147 lmmp_sqr_hard_2_(t + 6, r);
148 lmmp_mul_basecase_(t, t + 6, 4, r, 2);
149}

引用了 lmmp_cube_6_(), lmmp_mul_basecase_(), lmmp_sqr_hard_2_(), restrict , 以及 t.

函数调用图:

◆ lmmp_div3_()

mp_limb_t lmmp_div3_ ( mp_ptr q,
mp_srcptr a,
mp_size_t n )
inlinestatic

在文件 cbrt_1.c 第 33 行定义.

33 {
34 const mp_limb_t dn = 0xC000000000000000ull; // 3<<62
35 const mp_limb_t di = 0x5555555555555555ull; // lmmp_inv_1_(3<<62)
36 mp_limb_t ah, al, qq, r;
37 ah = a[n - 1] >> 2;
38 al = (a[n - 1] << 62) | (a[n - 2] >> 2);
39 _udiv_qrnnd_preinv(qq, r, ah, al, dn, di);
40 q[n - 1] = qq;
41 for (mp_size_t i = n - 2; i > 0; i--) {
42 ah = r;
43 al = (a[i] << 62) | (a[i - 1] >> 2);
44 _udiv_qrnnd_preinv(qq, r, ah, al, dn, di);
45 q[i] = qq;
46 }
47 ah = r;
48 al = a[0] << 62;
49 _udiv_qrnnd_preinv(qq, r, ah, al, dn, di);
50 q[0] = qq;
51 return r >> 62;
52}
#define _udiv_qrnnd_preinv(q, r, nh, nl, d, di)

引用了 _udiv_qrnnd_preinv, lmmp_div3_() , 以及 n.

被这些函数引用 lmmp_cbrt_3_(), lmmp_cbrt_6_est_(), lmmp_cbrt_6_fast_() , 以及 lmmp_div3_().

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

◆ lmmp_shr64_()

mp_limb_t lmmp_shr64_ ( mp_srcptr p,
mp_size_t n,
uint64_t s )
inlinestatic

在文件 cbrt_1.c 第 134 行定义.

134 {
135 mp_size_t w = (mp_size_t)(s >> 6);
136 uint64_t b = s & 63;
137 mp_limb_t lo = p[w];
138 mp_limb_t hi = (w + 1 < n) ? p[w + 1] : 0;
139 return b ? ((lo >> b) | (hi << (64 - b))) : lo;
140}
#define lo

引用了 lmmp_shr64_(), lo, n , 以及 s.

被这些函数引用 lmmp_cbrt_6_est_(), lmmp_nthroot_(), lmmp_shr64_() , 以及 lmmp_shr64_().

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