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

浏览该文件的源代码.

函数

ulong lmmp_cbrt_chebyshev_ (ulong n)
 计算算数立方根 floor(cbrt(n))
static double lmmp_cbrt_estimate (double a)
ulong lmmp_cbrt_ulong_ (ulong n)
 计算算数立方根 floor(cbrt(n))

变量

static const float coeff [16][3]
static const float factor_table [] = {1.000000, 1.259921, 1.587401}
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数说明

◆ lmmp_cbrt_chebyshev_()

ulong lmmp_cbrt_chebyshev_ ( ulong n)

计算算数立方根 floor(cbrt(n))

参数
n被开方数
返回
floor(cbrt(n))
警告
n>0
注解
使用Chebyshev估计,当n较大时,此算法更占优势

在文件 cbrt_ulong.c 第 47 行定义.

47 {
49 typedef union {
50 ulong uword_val;
51 double double_val;
52 } uni;
53
54 int rem, mul;
55 double factor, root, dec, dec2;
56 ulong ret, expo, table_index;
57 uni alias;
58
59 /* upper_limit is the max cube root possible for one word */
60
61 const ulong upper_limit = 2642245; /* 2642245 < (2^64)^(1/3) */
62 const ulong expo_mask = 0x7FF0000000000000; /* exponent bits in double */
63 const ulong mantissa_mask = 0x000FFFFFFFFFFFFF; /* mantissa bits in float */
64 const ulong table_mask = 0x000F000000000000; /* first 4 bits of mantissa */
65 const uint mantissa_bits = 52;
66 const ulong bias_hex = 0x3FE0000000000000;
67 const uint bias = 1022;
68 alias.double_val = (double)n;
69
70 expo = alias.uword_val & expo_mask; /* extracting exponent */
71 expo >>= mantissa_bits;
72 expo -= bias; /* Subtracting bias */
73
74 /* extracting first 4 bits of mantissa, this will help select correct poly */
75 /* note mantissa of 0.5 is 0x0000000000000 not 0x1000000000000 */
76
77 table_index = alias.uword_val & table_mask;
78 table_index >>= (mantissa_bits - 4);
79
80 /* extracting decimal part, 0.5 <= dec <= 1 */
81 ret = alias.uword_val & mantissa_mask;
82 ret |= bias_hex;
83 alias.uword_val = ret;
84 dec = alias.double_val;
85
86 rem = expo % 3;
87 expo /= 3;
88 factor = factor_table[rem];
89
90 /* Calculating cube root of dec using chebyshev approximation polynomial */
91
92 dec2 = dec * dec;
93 root = (coeff[table_index][0] + coeff[table_index][1] * dec);
94 root += (coeff[table_index][2] * dec2);
95
96 mul = (ulong)1 << expo; /* mul = 2^expo */
97 root *= mul; /* dec^(1/3) * 2^(expo/3) */
98 root *= factor; /* root*= (expo%3)^(1/3) */
99 ret = root;
100
101 /* In case ret^3 or (ret+1)^3 will cause overflow */
102
103 if (ret >= upper_limit) {
104 if (n >= upper_limit * upper_limit * upper_limit)
105 return upper_limit;
106 ret = upper_limit - 1;
107 }
108 while (ret * ret * ret <= n) {
109 (ret) += 1;
110 if (ret == upper_limit)
111 break;
112 }
113 while (ret * ret * ret > n) (ret) -= 1;
114
115 return ret;
116}
static const float coeff[16][3]
static const float factor_table[]
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define n
uint32_t uint
定义 numth.h:38
uint64_t ulong
定义 numth.h:39

引用了 coeff, factor_table, lmmp_cbrt_chebyshev_(), lmmp_param_assert , 以及 n.

被这些函数引用 lmmp_cbrt_chebyshev_(), lmmp_cbrt_ulong_(), lmmp_invsqrt_newton_() , 以及 TEST_CASE().

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

◆ lmmp_cbrt_estimate()

double lmmp_cbrt_estimate ( double a)
inlinestatic

在文件 cbrt_ulong.c 第 118 行定义.

118 {
119 typedef union {
120 slong uword_val;
121 double double_val;
122 } uni;
123
124 uni alias;
125 ulong n;
126
127 const ulong mul_factor = (ulong)6148914691236517205;
128 slong s = (slong)4607182418800017408; /* ((1 << 10) - 1) << 52 */
129
130 alias.double_val = a;
131 n = alias.uword_val;
132 n -= s;
133 n = lmmp_mulh_(n, mul_factor);
134 n += s;
135 alias.uword_val = n;
136 return alias.double_val;
137}
#define lmmp_mulh_
#define s
int64_t slong
定义 numth.h:41

引用了 lmmp_cbrt_estimate(), lmmp_mulh_, n , 以及 s.

被这些函数引用 lmmp_cbrt_estimate() , 以及 lmmp_cbrt_ulong_().

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

◆ lmmp_cbrt_ulong_()

ulong lmmp_cbrt_ulong_ ( ulong n)

计算算数立方根 floor(cbrt(n))

参数
n被开方数
返回
floor(cbrt(n))
注解
会依据n的大小,选择合适的算法

在文件 cbrt_ulong.c 第 139 行定义.

139 {
140 double val, x, xcub, num, den;
141 ulong ret, upper_limit;
142
143 if (n < 125)
144 return (n >= 1) + (n >= 8) + (n >= 27) + (n >= 64);
145 if (n < 1331)
146 return 5 + (n >= 216) + (n >= 343) + (n >= 512) + (n >= 729) + (n >= 1000);
147 if (n < 4913)
148 return 11 + (n >= 1728) + (n >= 2197) + (n >= 2744) + (n >= 3375) + (n >= 4096);
149
150 val = (double)n;
151
152 if (n >= 1ULL << 46)
153 return lmmp_cbrt_chebyshev_(n);
154
155 upper_limit = 2642245; /* 2642245 = floor((2^64)^(1/3)) */
156
157 x = lmmp_cbrt_estimate((double)n);
158
159 /* Kahan's iterations to get cube root */
160
161 xcub = x * x * x;
162 num = (xcub - val) * x;
163 den = (xcub + xcub + val);
164 x -= (num / den);
165 ret = x;
166
167 if (ret >= upper_limit) {
168 if (n >= upper_limit * upper_limit * upper_limit)
169 return upper_limit;
170 ret = upper_limit - 1;
171 }
172 while (ret * ret * ret <= n) {
173 (ret) += 1;
174 if (ret == upper_limit)
175 break;
176 }
177 while (ret * ret * ret > n) (ret) -= 1;
178
179 return ret;
180}
static double lmmp_cbrt_estimate(double a)
ulong lmmp_cbrt_chebyshev_(ulong n)
计算算数立方根 floor(cbrt(n))

引用了 lmmp_cbrt_chebyshev_(), lmmp_cbrt_estimate(), lmmp_cbrt_ulong_() , 以及 n.

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

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

变量说明

◆ coeff

const float coeff[16][3]
static
初始值:
= {{0.445434042, 0.864136635, -0.335205926},
{0.454263239, 0.830878907, -0.303884962},
{0.462761624, 0.800647514, -0.276997626},
{0.470958569, 0.773024522, -0.253724515},
{0.478879482, 0.747667468, -0.233429710},
{0.486546506, 0.724292830, -0.215613166},
{0.493979069, 0.702663686, -0.199877008},
{0.501194325, 0.682580388, -0.185901247},
{0.508207500, 0.663873398, -0.173426009},
{0.515032183, 0.646397742, -0.162238357},
{0.521680556, 0.630028647, -0.152162376},
{0.528163588, 0.614658092, -0.143051642},
{0.534491194, 0.600192044, -0.134783425},
{0.540672371, 0.586548233, -0.127254189},
{0.546715310, 0.573654340, -0.120376066},
{0.552627494, 0.561446514, -0.114074068}}

在文件 cbrt_ulong.c 第 30 行定义.

被这些函数引用 lmmp_cbrt_chebyshev_().

◆ factor_table

const float factor_table[] = {1.000000, 1.259921, 1.587401}
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

在文件 cbrt_ulong.c 第 27 行定义.

被这些函数引用 lmmp_cbrt_chebyshev_().