LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
cbrt_1.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 "impl/longlong.h"
25#include "numth/log2_exp2.h"
26#include "impl/mul_hard.h"
27#include "lmmp/numth.h"
28#include "lmmp/lmmpn.h"
29
30
31#define CBRT_DIVIDE_MIN (0x6000000000000000ull)
32
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}
53
54static inline void lmmp_cube_3_(mp_ptr restrict dst, mp_limb_t a) {
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}
62
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}
120
121/*
122 cbrt_6 所需的辅助:移位取位、立方与修正。
123
124 bits = bitlen(A) in [193,384]
125 y = log2(A) = (bits-1) + log2(1+f),f 取 A 的最高 129bit 中
126 去掉前导 1 后的 128bit 小数(log2_fixed_128)
127 r = floor(2^(y/3)) = 2^s + (exp2_fixed_128(y/3 的小数) >> (128-s))
128
129 估计误差主要来自 log2/exp2 各 +-2 ulp(128bit)与除 3 舍入,理论
130 上界约 +-8,典型 <= 2;随后以单调立方比较修正到精确 floor。
131*/
132
133// (p >> s) 的低 64bit,要求 0 <= s < 64*n
134static inline mp_limb_t lmmp_shr64_(mp_srcptr p, mp_size_t n, uint64_t s) {
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}
141
142/**
143 * @brief 计算 [t,6]=[r,2]^3
144 * @note [t+6,4]=[r,2]^2
145 */
147 lmmp_sqr_hard_2_(t + 6, r);
148 lmmp_mul_basecase_(t, t + 6, 4, r, 2);
149}
150
151// [r,2] = floor(cbrt([numa,n])) 的估计值,3 < n <= 6,numa[n-1] != 0
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}
184
185/*
186 基于估计值 [r,2] 做单调立方比较修正至精确 floor(cbrt([a,6])),
187 返回时 t[0..5] = r^3(供余数计算复用)。
188
189 下降循环至多降到 r = B(A > B^3 保证 r >= B),lmmp_dec 不会越过
190 region 下溢;上升循环在 r = B^2-1 处封顶(A < B^6)。
191*/
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}
213
214/*
215 cbrt_6 的快速除法路径:cbrt_3 种子 + 一次除法 + 修正循环。
216
217 A = Ah*B^3 + Al,Ahr = floor(cbrt(Ah))(cbrt_3 直接给出)
218 x = Ahr*B + Alr,Alr = [(rk*B^3+Al)/3] / Ahr^2 由 div_s 给出,
219 N = 3*x^2*Alr + R(R 为 div_s 重建余数)
220
221 Alr 至多高估 2(含 Alr=B、B+1 情形),修正循环:
222
223 N = 3*x^2*q + R(q 为除法商,R 为重建余数)
224 A < (x+u)^3 <=> rsav < W(u)
225 其中 rsav = 3*x^2*(q-u) + R 随 u 的递减同步累加,
226 W(u) = 3*Ahr*u^2*B + u^3。循环终止于 u = t,此时
227 R' = rsav - W(t) = A - (x+t)^3
228 恰为余数。由 Alr 高估至多 2 知循环至多约 3 轮。
229*/
230
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}
273
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_cube_6_(mp_ptr restrict t, mp_srcptr restrict r)
计算 [t,6]=[r,2]^3
定义 cbrt.c:51
static void lmmp_cube_3_(mp_ptr restrict dst, mp_limb_t a)
定义 cbrt.c:38
static mp_limb_t lmmp_shr64_(mp_srcptr p, mp_size_t n, uint64_t s)
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)
static mp_limb_t lmmp_div3_(mp_ptr q, mp_srcptr a, mp_size_t n)
#define lmmp_limb_bits_
#define lmmp_mullh_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#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
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宏(预期无借位)
#define lmmp_inc(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]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
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 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
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 _udiv_qrnnd_preinv(q, r, nh, nl, d, di)
void lmmp_sqr_hard_2_(mp_ptr dst, mp_srcptr numa)
#define a0
#define a1
#define a2
#define t
#define tp
#define s
#define n
#define lo
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]))
void lmmp_cbrt_6_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
计算算术立方根 floor(cbrt([numa,na]))
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)