LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
cbrt_ulong.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#include "impl/inlines.h"
24#include "lmmp/numth.h"
25
26
27static const float factor_table[] = {1.000000, 1.259921, 1.587401}; /* {1^(1/3), 2^(1/3), 4^(1/3)} */
28
29/* c0 c1 c2 range */
30static const float coeff[16][3] = {{0.445434042, 0.864136635, -0.335205926}, /* [0.50000, 0.53125] */
31 {0.454263239, 0.830878907, -0.303884962}, /* [0.53125, 0.56250] */
32 {0.462761624, 0.800647514, -0.276997626}, /* [0.56250, 0.59375] */
33 {0.470958569, 0.773024522, -0.253724515}, /* [0.59375, 0.62500] */
34 {0.478879482, 0.747667468, -0.233429710}, /* [0.62500, 0.65625] */
35 {0.486546506, 0.724292830, -0.215613166}, /* [0.65625, 0.68750] */
36 {0.493979069, 0.702663686, -0.199877008}, /* [0.68750, 0.71875] */
37 {0.501194325, 0.682580388, -0.185901247}, /* [0.71875, 0.75000] */
38 {0.508207500, 0.663873398, -0.173426009}, /* [0.75000, 0.78125] */
39 {0.515032183, 0.646397742, -0.162238357}, /* [0.78125, 0.81250] */
40 {0.521680556, 0.630028647, -0.152162376}, /* [0.81250, 0.84375] */
41 {0.528163588, 0.614658092, -0.143051642}, /* [0.84375, 0.87500] */
42 {0.534491194, 0.600192044, -0.134783425}, /* [0.87500, 0.90625] */
43 {0.540672371, 0.586548233, -0.127254189}, /* [0.90625, 0.93750] */
44 {0.546715310, 0.573654340, -0.120376066}, /* [0.93750, 0.96875] */
45 {0.552627494, 0.561446514, -0.114074068}}; /* [0.96875, 1.00000] */
46
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}
117
118static inline double lmmp_cbrt_estimate(double a) {
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}
138
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)
static const float coeff[16][3]
static const float factor_table[]
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define lmmp_mulh_
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define s
#define n
ulong lmmp_cbrt_chebyshev_(ulong n)
计算算数立方根 floor(cbrt(n))
uint32_t uint
定义 numth.h:38
ulong lmmp_cbrt_ulong_(ulong n)
计算算数立方根 floor(cbrt(n))
int64_t slong
定义 numth.h:41
uint64_t ulong
定义 numth.h:39