LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
cbrt.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 "mparam.h"
24#include "impl/inlines.h"
25#include "impl/tmp_alloc.h"
26#include "impl/mul_hard.h"
27#include "lmmp/numth.h"
28#include "lmmp/lmmpn.h"
29
30
31// divide 路径(cbrt_divide_/cbrt6_fast_)的顶 limb 归一化下限:
32// 保证 cbrt(A)^2 >= B^2/2,实际最小值约 0x5A827999FCEF3242,取整为 3B/8。
33// newton 路径(invcbrt_newton_/cbrt_newton_)迭代收敛仅需顶 limb >= B/8
34// (LIMB_B_8,层误差界按 B^nr/8 论证),其基例在 [B/8,3B/8) 自动回退
35// 到 log2/exp2 估计路径
36#define CBRT_DIVIDE_MIN (0x6000000000000000ull)
37
38static inline void lmmp_cube_3_(mp_ptr restrict dst, mp_limb_t a) {
39 mp_limb_t t[2];
40 lmmp_mullh_(a, a, t);
41 lmmp_mullh_(t[0], a, dst);
42 lmmp_mullh_(t[1], a, t);
43 dst[1] += t[0];
44 dst[2] = t[1] + (dst[1] < t[0] ? 1 : 0);
45}
46
47/**
48 * @brief 计算 [t,6]=[r,2]^3
49 * @note [t+6,4]=[r,2]^2
50 */
52 lmmp_sqr_hard_2_(t + 6, r);
53 lmmp_mul_basecase_(t, t + 6, 4, r, 2);
54}
55
56/*
57 A = Ah * B^(3*lo) + Al
58
59 Ahr = floor(Ah^(1/3))
60 rk = Ah - Ahr^3
61 x_k = Ahr * B^lo
62
63 x_k+1 = (2*x_k + A / x_k^2 ) / 3
64 = x_k + (A / x_k^2 - x_k) / 3
65 = x_k + (A - x_k^3) / 3 * x_k^2
66 = Ahr * B^lo + (rk * B^(3*lo) + Al) / 3 * x_k^2
67 = Ahr * B^lo + Alr
68
69 let Alr = (rk * B^(3*lo) + Al) / 3 * x_k^2, R = (rk * B^(3*lo) + Al) mod 3 * x_k^2
70 such that (rk * B^(3*lo) + Al) = Alr * 3 * x_k^2 + R
71 ┌───────────────────────────────────────────────────────────────────────┐
72 = |Alr * 3 * Ahr^2*B^(2*lo) + R = R_correct + (Alr-1) * 3 * Ahr^2*B^(2*lo)|
73 └───────────────────────────────────────────────────────────────┬───────┘
74 r_k+1 = A - x_k+1^3 |
75 = Ah*B^(3*lo) + Al - Ahr^3*B^(3*lo) - 3*Alr*Ahr^2*B^(2*lo) - 3*Ahr*Alr^2*B^lo - Alr^3 |
76 = r_k * B^(3*lo) + Al - 3*Alr*Ahr^2*B^(2*lo) - 3*Ahr*Alr^2*B^lo - Alr^3 |
77 = R - 3*Ahr*Alr^2*B^lo - Alr^3 |
78 |
79 Alr is either correct or 1 too big. We can prove this when hi >= lo+1. |
80 |
81 ┌────────────────────────────────────────────────┐ |
82 r_k+1 = R - 3*Ahr*(Alr-1)^2*B^lo - (Alr-1)^3 + | 3*Alr*Ahr^2*B^(2*lo) - 3*(Alr-1)*Ahr^2*B^(2*lo)├─┘
83 = R - 3*Ahr*Alr^2*B^lo - Alr^3 └────────────────────────────────────────────────┘
84(adjust) + 3*Ahr^2*B^(2*lo) + 6*Ahr*Alr*B^lo - 3*Ahr*B^lo + 3*Alr^2 - 3*Alr + 1
85*/
86
87/*
88 分割需满足 hi >= lo+1,理由:
89 记 x = Ahr*B^lo,真值 S = x+t,r = A-S^3 <= 3*S^2+3*S,则 Alr 高估 2
90 当且仅当 3*x*t^2 + t^3 + r >= 6*x^2,而 (t < B^lo)
91 3*x*t^2 + t^3 + r < (9*Ahr+1)*B^(3*lo) + 3*Ahr^2*B^(2*lo) + 3*B^(2*lo) + 低阶
92 由 CBRT_DIVIDE_MIN 有 Ahr >= 0.84*B^hi,故 hi >= lo+1 时
93 3*Ahr^2 > (9*Ahr+1)*B^lo
94 上式 < 6*x^2,即 Alr 至多高估 1,下方的单次修正才是充分的。
95
96 ns=2 直接调用 lmmp_cbrt_6_fast_,
97 其余 ns>=3 时 lo = (ns-1)/2 >= 1 且 hi = ns-lo >= lo+1 恒成立。
98*/
99
101 lmmp_param_assert(ns > 0);
102 lmmp_param_assert(numa != NULL && dst != NULL && tp != NULL);
103 lmmp_param_assert(numa[3 * ns - 1] >= CBRT_DIVIDE_MIN);
104 if (ns == 1) {
105 dst[0] = lmmp_cbrt_3_(numa[0], numa[1], numa[2]);
106 if (calr) {
107 lmmp_cube_3_(tp, dst[0]);
108 lmmp_sub_n_(numa, numa, tp, 3);
109 }
110 } else if (ns == 2) {
111 lmmp_cbrt_6_fast_(dst, numa, tp);
112 } else {
113 mp_size_t lo = (ns - 1) / 2, hi = ns - lo;
114#define Ahr (dst + lo) // [dst+lo, hi]
115#define rk (numa + 3 * lo) // [numa+3*lo, 2*hi+1]
116#define R (numa) // [numa, 2*ns+1]
117#define Ahr2 (tp) // [tp, 2*hi]
118#define Alr (tp + 2 * hi) // [tp + 2*hi, lo+1]
119#define Alr2 (tp + 2 * hi + lo) // [tp + 2*hi+lo, 2*lo]
120#define scratch (tp + 2 * hi + 3 * lo) // t = [.., hi+lo+1), W = [+hi+lo+1, +ns+lo+1)
121
122 lmmp_cbrt_divide_(Ahr, rk, hi, tp, 1);
123
124 lmmp_sqr_(Ahr2, Ahr, hi);
125
126 /*
127 A / (3*x^2) = A / 3 / x^2
128 A % (3*x^2) = 3 * (A / 3 % x^2) + A % 3
129 */
130 mp_limb_t r = lmmp_div_1_(rk - lo, rk - lo, hi + 1 + ns, 3);
131 mp_limb_t qh = lmmp_div_s_(Alr, rk - lo, hi + 1 + ns, Ahr2, 2 * hi);
132 lmmp_debug_assert(qh == 0);
133 (rk - lo)[2 * hi] = lmmp_mul_1_(rk - lo, rk - lo, 2 * hi, 3);
134 lmmp_inc_1(rk - lo, r);
135 /*
136 我们根据 cbrt(A/B^3) == floor(cbrt(A)/B) 可以知道,如果Alr正确结果
137 必定被限制在B^lo以内,其至多高估1,因此Alr的最高位必定为0或1,而为1时,
138 即代表此时结果已经高估。
139 */
140 mp_limb_t adj = Alr[lo];
141 lmmp_debug_assert(adj == 0 || adj == 1);
142 if (adj > 0) {
143 // Alr[0] 仅可能为0,此时高估1
144 lmmp_debug_assert(Alr[0] == 0);
145 lmmp_fill_n(dst, lo, LIMB_MAX);
146 if (calr == 0) return;
147 /*
148 x_k+1 = Ahr * B^lo + Alr
149 = Ahr * B^lo + B^lo - 1
150
151 r_k+1 = R - 3*Ahr*(B^lo-1)^2*B^lo - (B^lo-1)^3 + 3*Alr*Ahr^2*B^(2*lo) - 3*(Alr-adj)*Ahr^2*B^(2*lo)
152 = R - 3*Ahr*B^(3*lo) + 6*Ahr*B^(2*lo) - 3*Ahr*B^lo + 3*adj*Ahr^2*B^(2*lo)
153 - B^(3*lo) + 3*B^(2*lo) - 3*B^lo + 1
154 */
155
156 // - 3*Ahr*B^(3*lo)
157 mp_limb_t cy = lmmp_submul_1_(R + 3 * lo, Ahr, hi, 3);
158 r = lmmp_sub_1_(R + 2 * lo + ns, R + 2 * lo + ns, ns + 1 - 2 * lo, cy);
159
160 // + 6*Ahr*B^(2*lo)
161 cy = lmmp_addmul_1_(R + 2 * lo, Ahr, hi, 6);
162 r -= lmmp_add_1_(R + ns + lo, R + ns + lo, hi + 1, cy);
163
164 // - 3*Ahr*B^lo
165 cy = lmmp_submul_1_(R + lo, Ahr, hi, 3);
166 r += lmmp_sub_1_(R + ns, R + ns, ns + 1, cy);
167
168 // + 3*adj*Ahr^2*B^(2*lo)
169 cy = lmmp_addmul_1_(R + 2 * lo, Ahr2, 2 * hi, 3);
170 (R + 2 * ns)[0] += cy;
171 r -= (R + 2 * ns)[0] < cy;
172
173 // - B^(3*lo)
174 r -= lmmp_sub_1_(R + 3 * lo, R + 3 * lo, 2 * ns + 1 - 3 * lo, 1);
175
176 // + 3*B^(2*lo)
177 r -= lmmp_add_1_(R + 2 * lo, R + 2 * lo, 2 * hi + 1, 3);
178
179 // - 3*B^lo
180 r += lmmp_sub_1_(R + lo, R + lo, 2 * ns + 1 - lo, 3);
181
182 // + 1
183 r -= lmmp_add_1_(R, R, 2 * ns + 1, 1);
184
185 lmmp_debug_assert(r == 0);
186 } else if (calr == 0) {
187 /*
188 calr=0 时无需维护余数,计算 Alr^3 与 3*Ahr*Alr^2*B^lo 再相减,
189 仅仅是为了判定 Alr 是否高估 1(即 R 与 W = 3*Ahr*Alr^2*B^lo + Alr^3
190 的大小),此判定无需完整平方与乘法:
191
192 Ahr = X*B^(hi-2) + Y, X = [Ahr+hi-2,2]
193 Alr = H*B^(lo-2) + L, H = [Alr+lo-2,2]
194
195 W = 3*Ahr*Alr^2*B^lo + Alr^3
196 = 3*X*H^2*B^(hi+3*lo-6) + E
197 E = 3*B^lo*(X*2*H*L*B^(hi+lo-4) + Y*H^2*B^(2*lo-4) + 低阶项) + Alr^3
198 < 10*B^(hi+3*lo-2) + B^(3*lo) <= 11*B^(hi+3*lo-2) (hi>=2)
199
200 即 W 在 B^(hi+3*lo-2) 尺度上的最高三个 limb 必落在
201 [3*X*H^2 的最高三 limb, +11] 内,于是仅需比较 R 与 3*X*H^2
202 的最高三个 limb(注意 adj=0 时 Alr < B^lo,W < 4*B^(hi+3*lo)):
203 R 高于 B^(hi+3*lo) 的 limb 非零 => R > W
204 [R] > [3*X*H^2]+12(最高三 limb 意义下) => R > W
205 [R] < [3*X*H^2] (最高三 limb 意义下) => R < W
206 其余情况(最高三 limb 落入宽度 11 的窄带,如完全立方数
207 等构造输入)回退到下方的精确路径,保证正确性。
208 */
209 if (lo >= 4) {
210 mp_size_t i = 2 * ns;
211 while (i > hi + 3 * lo && R[i] == 0) --i;
212 if (i > hi + 3 * lo) {
213 // R >= B^(hi+3*lo+1) > W,Alr 未高估
214 lmmp_copy(dst, Alr, lo);
215 return;
216 }
217 lmmp_sqr_hard_2_(Alr2, Alr + lo - 2); // [Alr2,4] = H^2
218 lmmp_mul_basecase_(scratch, Alr2, 4, Ahr + hi - 2, 2); // [scratch,6] = X*H^2
219 mp_limb_t qh2 = lmmp_mul_1_(scratch, scratch, 6, 3); // [qh:scratch,6] = 3*X*H^2
220 mp_limb_t qm = scratch[5], ql = scratch[4];
221 mp_limb_t rh = R[hi + 3 * lo], rm = R[hi + 3 * lo - 1], rl = R[hi + 3 * lo - 2];
222 // [th,tm,tl] = [3*X*H^2 的最高三 limb] + 12
223 mp_limb_t tl = ql + 12, c1 = tl < 12;
224 mp_limb_t tm = qm + c1, c2 = tm < c1;
225 mp_limb_t th = qh2 + c2;
226 if (rh > th || (rh == th && (rm > tm || (rm == tm && rl >= tl)))) {
227 // [R] > [3*X*H^2]+12
228 lmmp_copy(dst, Alr, lo);
229 return;
230 }
231 if (rh < qh2 || (rh == qh2 && (rm < qm || (rm == qm && rl < ql)))) {
232 // R < W,Alr 高估 1
233 lmmp_dec(Alr);
234 lmmp_copy(dst, Alr, lo);
235 return;
236 }
237 }
238 // 窄带或小尺寸回退:精确判定
239 lmmp_sqr_(Alr2, Alr, lo);
240 lmmp_mul_(scratch, Alr2, 2 * lo, Alr, lo);
241 r = lmmp_sub_(R, R, 2 * ns + 1, scratch, 3 * lo);
242
243 if (2 * lo >= hi)
244 lmmp_mul_(scratch, Alr2, 2 * lo, Ahr, hi);
245 else
246 lmmp_mul_(scratch, Ahr, hi, Alr2, 2 * lo);
247 mp_limb_t b = lmmp_submul_1_(R + lo, scratch, 2 * lo + hi, 3);
248 r += lmmp_sub_1_(R + 2 * lo + ns, R + 2 * lo + ns, ns + 1 - 2 * lo, b);
249 if (r > 0)
250 lmmp_dec(Alr);
251 lmmp_copy(dst, Alr, lo);
252 } else {
253 lmmp_sqr_(Alr2, Alr, lo);
254 // W = 3*Ahr*Alr^2*B^lo + Alr^3 = Alr^2*(3*Ahr*B^lo + Alr)
256 scratch[lo + hi] = lmmp_mul_1_(scratch + lo, Ahr, hi, 3);
257 lmmp_mul_(scratch + hi + lo + 2, scratch, hi + lo + 1, Alr2, 2 * lo);
258 r = lmmp_sub_(R, R, 2 * ns + 1, scratch + hi + lo + 2, 3 * lo + hi + 1);
259
260 if (r > 0) {
261 // + 3*Alr^2
262 mp_limb_t cy = lmmp_addmul_1_(R, Alr2, 2 * lo, 3);
263 r -= lmmp_add_1_(R + 2 * lo, R + 2 * lo, 2 * hi + 1, cy);
264
265 // - 3*Alr
266 cy = lmmp_submul_1_(R, Alr, lo, 3);
267 r += lmmp_sub_1_(R + lo, R + lo, 2 * ns + 1 - lo, cy);
268
269 // + 6*Ahr*Alr*B^lo
270 lmmp_mul_(scratch, Ahr, hi, Alr, lo);
271 cy = lmmp_addmul_1_(R + lo, scratch, ns, 6);
272 r -= lmmp_add_1_(R + ns + lo, R + ns + lo, ns + 1 - lo, cy);
273
274 // + 3*Ahr^2*B^(2*lo)
275 cy = lmmp_addmul_1_(R + 2 * lo, Ahr2, 2 * hi, 3);
276 // r -= lmmp_add_1_(R + 2 * ns, R + 2 * ns, 1, cy);
277 (R + 2 * ns)[0] += cy;
278 r -= (R + 2 * ns)[0] < cy;
279
280 // + 1
281 r -= lmmp_add_1_(R, R, 2 * ns + 1, 1);
282
283 // - 3*Ahr*B^lo
284 cy = lmmp_submul_1_(R + lo, Ahr, hi, 3);
285 r += lmmp_sub_1_(R + ns, R + ns, ns + 1, cy);
286
287 lmmp_debug_assert(r == 0);
288 lmmp_dec(Alr);
289 }
290 lmmp_copy(dst, Alr, lo);
291 }
292 }
293#undef Ahr
294#undef rk
295#undef R
296#undef Ahr2
297#undef Alr
298#undef Alr2
299#undef scratch
300}
301
302static inline mp_size_t lmmp_cbrt_cls_shift_(mp_size_t bl, int top2) {
303 mp_size_t r = bl % 3;
304 if (r == 1) return -1;
305 if (r == 2 && !top2) return -1;
306 mp_size_t L = (r == 0) ? (bl + 63) / 64 : (bl + 64) / 64;
307 L = (L + 2) / 3 * 3;
308 return (r == 0 ? 64 * L : 63 + 64 * (L - 1)) - bl;
309}
310
311// a2 = [src,n] << s(s < 192:置零 w = s/64 个整 limb 后按 b = s%64 移位,
312// 移位进位写入 a2[w+n],缓冲至少 n+3 limb)。knorm 的 k=1/k^3 路径与
313// snorm 的纯移位路径共用
315 mp_size_t w = s / LIMB_BITS, b = s % LIMB_BITS;
316 lmmp_zero(a2, w);
317 a2[w + n] = lmmp_shl_(a2 + w, src, n, b); // b=0 时函数内即拷贝,返回 0 落入长度外 slack
318}
319
321 lmmp_param_assert(numa != NULL && a2 != NULL && na > 0 && numa[na - 1] != 0);
322 TEMP_DECL;
323 mp_ptr xk = NULL; // numa*k^3 暂存(仅命中 k>1 时分配一次,与 a2 分离)
324 mp_limb_t hlo = na >= 2 ? numa[na - 2] : 0;
325 for (mp_limb_t k = 1; k <= 256; ++k) {
326 if (k > 1 && (k & (k - 1)) == 0) continue; // 2 的幂不改变类别
327 mp_limb_t k3 = k * k * k; // <= 256^3 < 2^24
328
329 // 预筛选:na>=2 时 q = 高128bit(numa)*k3(低位 low < B^(64*(na-2)));
330 // na==1 时 hi128 即 numa[0] 本身(无 B 因子),q = X 精确
331 mp_limb_t t0[2], t1[2];
332 lmmp_mullh_(hlo, k3, t0);
333 lmmp_mullh_(numa[na - 1], k3, t1);
334 mp_limb_t q0, q1, q2;
335 mp_size_t sh;
336 if (na == 1) {
337 q0 = t1[0];
338 q1 = t1[1];
339 q2 = 0;
340 sh = 0;
341 } else {
342 q0 = t0[0];
343 q1 = t0[1] + t1[0];
344 q2 = t1[1] + (q1 < t0[1]);
345 sh = LIMB_BITS * (na - 2);
346 }
347
348 mp_size_t wq = q2 ? 2 : (q1 ? 1 : 0);
349 mp_limb_t qtop = wq == 2 ? q2 : (wq == 1 ? q1 : q0);
350 mp_size_t hb = lmmp_limb_bits_(qtop);
351 mp_size_t bl = sh + LIMB_BITS * wq + hb; // bl(numa*k^3),精确
352 int top2 = hb >= 2 ? qtop >= 3ULL << (hb - 2)
353 : (qtop & 1) && ((wq == 2 ? q1 : q0) >> (LIMB_BITS - 1));
354 mp_size_t s = lmmp_cbrt_cls_shift_(bl, top2);
355 if (s == (mp_size_t)-1) continue; // mp_size_t 无符号,须按哨兵值比较
356
357 // 命中:唯一一次完整 mul_1
358 mp_srcptr ak;
359 mp_size_t nak;
360 if (k == 1) {
361 ak = numa;
362 nak = na;
363 } else {
364 if (!xk) xk = TALLOC_TYPE(na + 1, mp_limb_t);
365 mp_limb_t cy = lmmp_mul_1_(xk, numa, na, k3);
366 nak = na;
367 if (cy) xk[na] = cy, ++nak;
368 ak = xk;
369 // low*k3 的进位可改变完整乘积的类别:按 xk 全量复核 bl/top2/s,
370 // 类别不可达(如 r=1)则弃选该 k(预筛伪命中)
371 mp_limb_t xtop = xk[nak - 1];
372 mp_size_t xhb = lmmp_limb_bits_(xtop);
373 bl = LIMB_BITS * (nak - 1) + xhb;
374 top2 = xhb >= 2 ? xtop >= 3ULL << (xhb - 2)
375 : (nak >= 2 && (xk[nak - 2] >> (LIMB_BITS - 1)));
376 s = lmmp_cbrt_cls_shift_(bl, top2);
377 if (s == (mp_size_t)-1) continue;
378 }
379
380 // a2 = ak << s(k=1 时 ak == numa;k>1 时 ak == xk 与 a2 分离);na2 <= w+nak+1
381 mp_size_t na2 = (bl + s + LIMB_BITS - 1) / LIMB_BITS;
382 lmmp_cbrt_shapply_(ak, nak, s, a2);
383 lmmp_debug_assert(na2 % 3 == 0 && a2[na2 - 1] >= CBRT_DIVIDE_MIN);
384 *kp = k;
385 *na2p = na2;
386 TEMP_FREE;
387 return s / 3;
388 }
390 return 0;
391}
392
393/*
394 逆立方根牛顿迭代(结构与 lmmp_invsqrt_newton_ 同构,收敛率同为二次):
395
396 y' = y*(4 - a*y^3)/3
397
398 尺寸栈 ns -> (ns>>1)+1 -> ... -> 3,自 nr=2 的基例起逐层将精度翻倍
399 (下一层尺寸 na 满足 na ∈ {2*nr-2, 2*nr-1},牛顿步一轮即可)。
400 当前层近似记(an = a 的最高 naz = min(na,namax) 个 limb)
401
402 ir = [dstis-nr, nr+1] = floor(B^(4*nr/3) / cbrt(ar)) - [0|1]
403 ar = an 的最高 nr 个 limb
404
405 层不变式仅要求 ar 顶 limb >= B/8(入口 B/8 归一化逐层保持:每层 ar
406 均含 a 顶 limb):由此 ir ∈ [B^nr, 2*B^nr)(dstis[nr]=1),下方
407 d/xp/dip 的窗口宽度界均按此论证。
408
409 残差与修正(对相对残差 e = 1 - an*ir^3/B^(naz+3*nr) 二次收敛 e' ~ 2*e^2):
410
411 d = B^(naz+3*nr) - an*ir^3, -16*B^(naz+2*nr) < d < 16*B^(naz+2*nr)
412
413 x' = ir*B^(na-nr)
414 t = an*x'^3/B^(3*na+naz) = 1 - d/B^(naz+3*nr)
415 i' = x'*(4-t)/3 = x' + x'*d/(3*B^(naz+3*nr))
416 = ir*B^(na-nr) + ir*d / (3*B^(naz+4*nr-na))
417
418 xp = |d| / (3*B^naz) (取 2*nr+2 limb 窗口)
419 dip = xp * ir (3*nr+3 limb 精确乘积)
420 C = dip * B^(na-4*nr) (修正项, ~B^(na-nr))
421
422 i' 的低位 [dstis-na, dstis-nr) <- dip[4*nr-na, 3*nr),
423 边界 limb dip[3*nr] 经 inc_1/dec_1 并入 [dstis-nr] 处。
424
425 梅森变换(mod B^mn-1, mn = lmmp_mersenne_next_size_(nres), nres = naz+2*nr+2):
426 ir^3*an 高于 B^mn 的部分对 i' 无影响(|d| < 16*B^(naz+2*nr) << B^mn,
427 残差信息全部保存在模的低 nres 个 limb 内),故 an*ir^3 的三次乘链
428 (ir^2 -> *an -> *ir)均可用模乘截断计算。dp 折叠回 -d (mod B^mn-1)
429 后,d 的符号由 dp[nres-1] 是否 > 15 判定:
430 d > 0 => dp = M-d (M = B^mn-1),高位 limb 接近 B-1
431 d <= 0 => dp = |d| (< 16*B^(naz+2*nr),高位 limb <= 15)
432 d > 0 时 dp 按位取反即得 d 的窗口 limb(d <= 0 时窗口直接可得),
433 配合 div_1 除 3 与边界 +/-1 修正吸收全部截断误差,保证 ir 绝不高估。
434
435 与 sqrt 的差异:修正系数为 1/3 而非 1/2(除 3 不可移位实现,用 div_1_),
436 残差链多一跳乘法(三次乘:ir^2、*an、*ir),xp 窗口宽度倍增为 2*nr+2,
437 dip/dip 边界 limb 下移至 3*nr(C = dip*B^(na-4*nr))。
438*/
439
441 lmmp_param_assert(ns >= 3);
442 lmmp_param_assert(na > 0);
443 lmmp_param_assert(numa != NULL && dstis != NULL);
444 lmmp_param_assert(numa[na - 1] >= LIMB_B_8);
445 mp_size_t nr = ns, namax = na, mn;
446 mp_size_t sizes[LIMB_BITS], *sizp = sizes;
447
448 do {
449 *sizp = nr;
450 nr = (nr >> 1) + 1;
451 ++sizp;
452 } while (nr > 2);
453
454 numa += na;
455 dstis += ns;
456
457 /*
458 nr=2 基例(x = a 的最高 2 个 limb 组成的 2 limb 数, 契约保证 x >= B^2/8):
459
460 s = floor(cbrt(x*B^4)) in [B^2/2, B^2)
461 i2 = floor((B^4-1)/(s+1)), i2^3*x ≈ B^8, i2 ∈ (B^2, 2*B^2]
462
463 分母 +1 使基例系统性略微低估(i2 < cbrt(B^8/x) 恒成立),
464 保证后续每层迭代恒有 ir <= 目标值。cbrt_6_ 按顶 limb 分流:
465 >= 3B/8 直达除法快速路径,[B/8, 3B/8) 回退 log2/exp2 估计 +
466 单调立方修正(仅 6 limb,代价可忽略)。
467 */
468 mp_limb_t numa2[6], sval[2];
469 lmmp_zero(numa2, 4);
470 numa2[4] = na > 1 ? numa[-2] : 0;
471 numa2[5] = numa[-1];
472 lmmp_cbrt_6_(sval, numa2, 6);
473
474 if (sval[0] == LIMB_MAX && sval[1] == LIMB_MAX) {
475 // s = B^2-1,s+1 = B^2 无法作为 div_s 的归一化除数,直接给出
476 dstis[-2] = LIMB_MAX;
477 dstis[-1] = LIMB_MAX;
478 dstis[0] = 0;
479 } else {
481 lmmp_inc(sval); // s+1,最高 limb >= B/2,满足 div_s 归一化要求
482 // 商 i2 ∈ (B^2, 2*B^2) 共 3 limb:[dstis-2, dstis-1] 为主干,
483 // 返回的 qh 即最高 limb,写入 dstis[0]
484 dstis[0] = lmmp_div_s_(dstis - 2, q, 4, sval, 2);
485 lmmp_debug_assert(dstis[0] == 1);
486 }
487
488 TEMP_DECL;
489 /*
490 单层滚动区域布局(后续层相互复用已死区域):
491 R0 = [dp -> dip] max(nres+nr+1, mn+2, 3*nr+4)
492 R1 = [t2] max(2*nr+2, mn)
493 R2 = [w1 -> xp] max(max(2*nr+2, mn)+naz+1, 2*nr+3)
494 逐层求和的最大值由下方 alloc 公式覆盖(精确链最坏 ~7*nrmax+2*naz,
495 梅森链最坏 ~9*nrmax+naz,均小于 2*(ns+namax+4)+6*nrmax+16)。
496 */
497 mp_size_t nrmax = (ns >> 1) + 2;
498 mp_size_t alloc_size = 2 * (ns + namax + 4) + 6 * nrmax + 16;
499 mp_ptr restrict tb = TALLOC_TYPE(alloc_size, mp_limb_t);
500
501 do {
502 na = *--sizp;
503
504 // an = 0:[numa-naz,naz]
505 // ir = 1:[dstis-nr,nr] = floor(B^(4*nr/3)/cbrt(ar)) - [0|1]
506 // d = B^(naz+3*nr)-an*ir*ir*ir
507 // -16*B^(naz+2*nr) < d < 16*B^(naz+2*nr)
508
509 mp_size_t naz = LMMP_MIN(na, namax);
510 mp_size_t nres = naz + 2 * nr + 2;
511 mp_size_t nsqr;
512 mn = lmmp_mersenne_next_size_(nres);
513
514 // 梅森链需 mn 显著小于精确链的最大中间尺寸 3*nr+2(节省立方的完整
515 // 展开),且模折叠加法偏移 naz+3*nr-mn >= 0
516 int cmod = mn + 2 * CBRT_NEWTON_MODM_THRESHOLD < 3 * nr + 2 && mn <= naz + 3 * nr;
517
518 mp_size_t r0 = LMMP_MAX(LMMP_MAX(nres + nr + 1, mn + 2), 3 * nr + 4);
519 mp_size_t r1 = cmod ? LMMP_MAX(2 * nr + 2, mn) : 2 * nr + 2;
520 mp_ptr dp = tb, t2 = tb + r0, w1 = tb + r0 + r1, xp = w1, dip = tb;
521
522 if (cmod) {
523 // ---- 梅森链:dp = an*ir^3 mod (B^mn-1),再折叠为 -d (mod M) ----
524
525 // ir^2
526 if (2 * CBRT_NEWTON_MODM_THRESHOLD + mn >= 2 * nr + 1) {
527 lmmp_sqr_(t2, dstis - nr, nr + 1);
528 nsqr = 2 * nr + 2;
529 } else {
530 lmmp_sqr_mersenne_(t2, mn, dstis - nr, nr + 1);
531 nsqr = mn;
532 }
533
534 // w1 = t2*an mod M
535 if (naz < CBRT_NEWTON_MODM_THRESHOLD || naz * 8 < nsqr || mn >= nsqr + naz) {
536 lmmp_mul_(w1, t2, nsqr, numa - naz, naz);
537 if (nsqr + naz > mn) {
538 if (lmmp_add_(w1, w1, mn, w1 + mn, nsqr + naz - mn))
539 lmmp_inc(w1);
540 }
541 } else {
542 lmmp_mul_mersenne_(w1, mn, t2, nsqr, numa - naz, naz);
543 }
544
545 // dp = w1*ir mod M, naz+nr < mn <= naz+3*nr
546 lmmp_mul_mersenne_(dp, mn, w1, mn, dstis - nr, nr + 1);
547 //[dp,mn] -= B^(naz+3*nr) mod (B^mn-1)
548 dp[mn] = 1;
549 lmmp_dec(dp + naz + 3 * nr - mn);
550 if (dp[mn] == 0)
551 lmmp_dec(dp);
552 } else {
553 // ---- 精确截断链:dp = an*ir^3 mod B^nres ----
554 // (X*Y) mod B^k = (X mod B^k)*(Y mod B^k) mod B^k,
555 // t2 与 w1 均短于 B^nres(2*nr+2+naz = nres),无需预截断
556 lmmp_sqr_(t2, dstis - nr, nr + 1);
557 nsqr = 2 * nr + 2;
558 lmmp_mul_(w1, t2, nsqr, numa - naz, naz); // [w1, nres)
559 lmmp_mul_(dp, w1, nres, dstis - nr, nr + 1); // 低 nres limb 即 an*ir^3 mod B^nres
560 }
561
562 /*
563 dp limb nres-1 = naz+2*nr+1 编码 d 的符号:
564 d > 0 => dp = [B^nres|B^mn] - d,该 limb ∈ [B-16, B-1]
565 d <= 0 => dp = |d| < 16*B^(naz+2*nr),该 limb ∈ [0, 15]
566 */
567 mp_limb_t hi = dp[nres - 1];
568 mp_limb_t rem;
569
570 if (hi > 15) {
571 // d > 0:ir 低估,修正相加。取反得 d 的窗口 limb 后除 3 向下取整
572 if (!cmod)
573 lmmp_dec(dp); // 消除 B^nres-d 折叠借位,使取反恰为 d
574 lmmp_not_(xp, dp + naz, 2 * nr + 2);
575 rem = lmmp_div_1_(xp, xp, 2 * nr + 2, 3);
576 } else {
577 // d <= 0:ir 高估,修正相减。窗口直接可得,除 3 向上取整
578 rem = lmmp_div_1_(xp, dp + naz, 2 * nr + 2, 3);
579 if (rem != 0 || !lmmp_zero_q_(dp, naz))
580 lmmp_inc(xp);
581 }
582
583 // dip = xp*ir, C = dip*B^(na-4*nr)
584 lmmp_mul_(dip, xp, 2 * nr + 2, dstis - nr, nr + 1);
585
586 if (hi > 15) {
587 // i' = ir*B^(na-nr) + C
588 lmmp_copy(dstis - na, dip + 4 * nr - na, na - nr);
589 lmmp_inc_1(dstis - nr, dip[3 * nr]);
590 } else {
591 // i' = ir*B^(na-nr) - C,以按位取反 + 借位减实现
592 if (lmmp_zero_q_(dip, 4 * nr - na)) {
593 // C 的取模窗口低位为 0 时的两补边界
594 dip[3 * nr + 1] = 1;
595 lmmp_dec(dip + 4 * nr - na);
596 }
597 lmmp_not_(dstis - na, dip + 4 * nr - na, na - nr);
598 lmmp_dec_1(dstis - nr, dip[3 * nr] + 1);
599 }
600
601 nr = na;
602 } while (sizp != sizes);
603 TEMP_FREE;
604}
605
606/*
607 snorm:newton 路径的移位归一化(无乘子版本,供 lmmp_cbrt_ 的 newton
608 分支调用;lmmp_cbrt_newton_ 本体已改为输入契约,归一化与还原均由调用
609 处完成)。invnewton 迭代的收敛条件实际仅需顶 limb >= B/8(层误差界按
610 B^nr/8 论证,见 lmmp_invcbrt_newton_ 注释),而 B/8 恒可由 3 对齐移位
611 到达,故 newton 路径不引入 knorm 的 k^3 乘子(省去乘子搜索、numa*k^3
612 的 mul_1 遍历与还原时的 div_1(k) 遍历)。
613
614 输出 a2 = numa << s 写入调用方缓冲区(至少 na+3 limb),满足
615 limbs(a2) ≡ 0 (mod 3)(重建移位量为整 limb 的必要条件:B^(1/3) 无理,
616 cbrt 无 sqrt 的半 limb 对齐技巧)且 a2 顶 limb >= B/8,即
617 lmmp_cbrt_newton_ 的输入契约;返回
618 *na2p = a2 的 limb 数(恒为 3*ceil(na/3))
619 返回值 = t = s/3(根的右移回退量,< 64)
620
621 目标总位长 T = bl+s(bl = bitlen(numa))的解析求解:s ≡ 0 (mod 3)
622 保证根可经右移 t = s/3 bit 精确回退(floor(cbrt(X*2^(3t))) >> t ==
623 floor(cbrt(X)),由 floor(2y)>>1 == floor(y) 对 t 归纳)。记
624 L = limbs(a2) ≡ 0 (mod 3),pos = T - 64*(L-1) 为顶 limb 有效位宽,
625 由 64 ≡ 1 (mod 3) 有 T ≡ L-1+pos (mod 3),结合 T ≡ bl (mod 3) 解出
626 每 class(r = bl mod 3)唯一的 (pos, L) 组合:
627 r=0: pos=64(顶 limb MSB=1 >= B/2)
628 r=1: pos=62(顶 limb ∈ [B/8, B/4))
629 r=2: pos=63(顶 limb ∈ [B/4, B/2))
630 可达时最小 s 唯一(s 随 L 增大单调增)且 s <= 189,故 t <= 63。
631 对照 divide 路径(knorm):3B/8 仅 pos=63 且顶 2bit 为 11 或 pos=64
632 可达,约 1/2 输入(r=1 恒不可达,r=2 且顶 2bit 为 10 不可达)必须乘
633 小立方数 k^3 改类;B/8 三 class 全可达,移位永充分。
634*/
636 lmmp_param_assert(numa != NULL && a2 != NULL && na > 0 && numa[na - 1] != 0);
637 mp_bitcnt_t hb = lmmp_limb_bits_(numa[na - 1]);
638 mp_size_t bl = LIMB_BITS * (na - 1) + (mp_size_t)hb;
639 mp_size_t r = bl % 3;
640 // (pos, T mod 3) 对应关系:pos=64≡1 → T≡0;pos=62≡2 → T≡1;pos=63≡0 → T≡2
641 static const mp_size_t POS_BY_CLASS[3] = {LIMB_BITS, LIMB_BITS - 2, LIMB_BITS - 1};
642 mp_size_t pos = POS_BY_CLASS[r];
643
644 // L = 最小的满足 T = 64*(L-1)+pos >= bl 的三倍数
645 mp_size_t L = 1;
646 if (bl > pos)
647 L = (bl - pos + LIMB_BITS - 1) / LIMB_BITS + 1;
648 L = (L + 2) / 3 * 3;
649
650 mp_size_t s = LIMB_BITS * (L - 1) + pos - bl; // <= 189, ≡ 0 (mod 3)
651 lmmp_debug_assert(s % 3 == 0 && s / 3 < LIMB_BITS);
652 lmmp_cbrt_shapply_(numa, na, s, a2);
653 lmmp_debug_assert(L % 3 == 0 && L <= na + 3 && a2[L - 1] >= LIMB_B_8);
654 *na2p = L;
655 return s / 3;
656}
657
658/*
659 计算已归一化输入 x = cbrt(a*B^(3nf)) 的舍入近似 r。输入契约(由调用
660 处保证,本函数不再内部归一化):na ≡ 0 (mod 3) 且顶 limb >= B/8,
661 即 snorm 的输出形(B/8 为 invcbrt_newton_ 的收敛下限;na 整 limb 对齐
662 是重建移位量为整 limb 的必要条件——B^(1/3) 无理,cbrt 无 sqrt 的半
663 limb 对齐技巧)。归一化与 >>s/3 还原均在 lmmp_cbrt_ 分发处完成。
664
665 ic = [ns+1] limb 逆立方根(多算 1 个 guard limb),ns = na/3+nf+1
666 Q = a*ic^2(ic 先平方再一次全乘,均为精确整数乘)
667 root = round(Q / B^e0),e0 = 2*ns + 2*(na/3) - nf
668
669 记 It = cbrt(B^(3ns+na)/a)(实值),有 Q/B^e0 = x*(ic/It)^2,故
670
671 r = round(x - eps), eps = x*(1 - (ic/It)^2) >= 0
672
673 ic ∈ {I-1, I}(I = floor(It):实值截断 + 算法至多 1 ulp 低估)给出
674 It-ic ∈ [0,2),而 x/It = (a/B^na)^(2/3) / B(代入 ns = na/3+nf+1),
675 因此
676 0 <= eps = x*(It-ic)(It+ic)/It^2 < 4*x/It < 4/B
677
678 (sqrt 对照:其 eps < 2^-63/2^-31 由 na 奇偶引入 sqrt(B) 半 limb 视窗;
679 cbrt 的 B^(1/3) 无理使 na 必须整 limb 对齐,guard 恰为 1 limb)。
680 eps 非负故 r 绝不超过 round(x);仅当 frac(x) ∈ [1/2, 1/2+eps) 时得到
681 floor(x)(eps < 2^-62,随机输入概率 < 2^-61);完全立方输入(frac(x)=0,
682 eps < 1/2)恒精确命中。又 x < B^((na+3nf)/3) = B^(ns-1),结果与舍入
683 进位均不出 ns limb,直接写入 [dsts,ns)。移位问题还原(floor 复合
684 不变性):r' = floor(r >> t) ∈ {round(x')-1, round(x')}(x' = x/2^t
685 为原问题根),由分发处完成。
686*/
687
689 lmmp_param_assert(na > 0 && na % 3 == 0);
690 lmmp_param_assert(nf >= 2);
691 lmmp_param_assert(3 * nf >= 2 * na + 3);
692 lmmp_param_assert(numa != NULL && dsts != NULL);
693 lmmp_param_assert(numa[na - 1] >= LIMB_B_8);
694
695 TEMP_DECL;
696 mp_size_t ns = na / 3 + nf + 1;
697 mp_ptr ic = TALLOC_TYPE(ns + 1, mp_limb_t);
698 mp_ptr q1 = TALLOC_TYPE(2 * ns + 2, mp_limb_t);
699 mp_ptr q = TALLOC_TYPE(na + 2 * ns + 3, mp_limb_t);
700
701 lmmp_invcbrt_newton_(ic, ns, numa, na);
702
703 // Q = a*ic^2:先平方再单乘(对比 ic*a 后再乘 ic 的两次同规模乘法,
704 // 平方以约半成本替代其一;2*ns+2 >= na 满足 mul 的长操作数在前)
705 lmmp_sqr_(q1, ic, ns + 1);
706 lmmp_mul_(q, q1, 2 * ns + 2, numa, na);
707
708 // dsts = round(Q/2^e0),舍入位为 q[e0-1] 的最高位(结果 <= B^(ns-1),
709 // 进位不会越出 ns limb,无需中间缓冲)
710 mp_size_t e0 = 2 * ns + 2 * (na / 3) - nf;
711 lmmp_copy(dsts, q + e0, ns);
712 if (q[e0 - 1] >> (LIMB_BITS - 1))
713 lmmp_inc(dsts);
714 TEMP_FREE;
715}
716
717
718void lmmp_cbrt_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf) {
719 lmmp_debug_assert(na > 0);
720 lmmp_debug_assert(numa[na - 1] > 0);
721 mp_size_t nl = na + 3 * nf;
722
723 if (nl <= 6) {
724 // 小输入:任意归一化均可由基例函数族直接处理
725 mp_limb_t xb[6] = {0, 0, 0, 0, 0, 0}, r[2] = {0, 0};
726 for (mp_size_t i = 0; i < na; ++i) xb[3 * nf + i] = numa[i];
727
728 if (nl <= 2) {
729 r[0] = nl == 1 ? lmmp_cbrt_ulong_(xb[0]) : lmmp_cbrt_3_(xb[0], xb[1], 0);
730 } else if (nl == 3) {
731 r[0] = lmmp_cbrt_3_(xb[0], xb[1], xb[2]);
732 } else {
733 lmmp_cbrt_6_(r, xb, nl);
734 }
735 mp_size_t ns = (nl + 2) / 3;
736 dsts[0] = r[0];
737 if (ns > 1) dsts[1] = r[1];
738
739 if (dstr) {
740 // [dstr,2*ns+1] = X - r^3:立方由基例原语直接给出,
741 // rem < 3r^2+3r+1 < B^(2*ns+1),低段直接减无借位
742 mp_limb_t t[10];
743 if (ns == 1) {
744 lmmp_cube_3_(t, r[0]);
745 lmmp_sub_n_(dstr, xb, t, 3);
746 } else {
747 lmmp_cube_6_(t, r);
748 lmmp_sub_n_(dstr, xb, t, 5);
749 }
750 }
751 return;
752 }
753
754 /*
755 与 lmmp_sqrt_ 的分发同构:大 nf 无余数走 lmmp_cbrt_newton_ 的
756 [floor|round] 近似;其余(含全部 dstr != NULL 与精确 floor 语义)
757 统一走 knorm 归一化 + lmmp_cbrt_divide_ 精确求根,>>t 与 div_1(k)
758 的 floor 复合精确还原,无需任何修正循环。
759
760 cbrt_newton_ 为输入契约版(na ≡ 0 (mod 3),顶 limb >= B/8),
761 归一化与还原在本分发处完成:snorm 纯移位归一化(与 knorm 的 k=1
762 移位路径共用 shapply,B/8 即满足迭代收敛)+ 契约调用 + 结果 >>t
763 的 floor 复合还原。na2 = 3*ceil(na/3) 使 na2/3+nf+1 恰等于
764 (na+3nf+2)/3+1,>>t 后的写入长度与语义和内部归一化旧版一致。
765 */
766 if (!dstr && nf >= CBRT_INVNEWTON_K_THRESHOLD * na && nf >= CBRT_INVNEWTON_NF_MIN) {
767 TEMP_DECL;
768 mp_ptr a2 = TALLOC_TYPE(na + 3, mp_limb_t);
769 mp_size_t na2;
770 mp_size_t t = lmmp_cbrt_snorm_(numa, na, a2, &na2);
771 lmmp_debug_assert(na2 / 3 + nf + 1 == (na + 3 * nf + 2) / 3 + 1);
772 lmmp_cbrt_newton_(dsts, a2, na2, nf);
773 if (t)
774 lmmp_shr_(dsts, dsts, na2 / 3 + nf + 1, t);
775 TEMP_FREE;
776 return;
777 }
778
779 TEMP_DECL;
780 mp_ptr a2 = TALLOC_TYPE(na + 5, mp_limb_t);
781 mp_size_t na2;
782 mp_limb_t k;
783 mp_size_t t = lmmp_cbrt_knorm_(numa, na, a2, &na2, &k);
784
785 mp_size_t ns2 = na2 / 3 + nf; // 移位后问题根长(radicand = a2*B^(3nf))
786 mp_size_t ns0 = (nl + 2) / 3; // 原问题根长
787 mp_size_t nR = ns0 + 1; // 根工作长度(含可能的最高零 limb)
788 mp_ptr tp = TALLOC_TYPE(6 * ns2 + 4, mp_limb_t);
789 // nf==0 时被开方数即 a2 本身,rad 直接复用(knorm 后 a2 不再读取);
790 // nf>0 时 rad = a2*B^(3nf) 须另建(低位补零后拷贝)。两种形下缓冲均
791 // 覆盖 divide 的 [rad,3ns2) 与余数修正的 [rad,2ns2+3)
792 mp_ptr rad;
793 if (nf) {
794 rad = TALLOC_TYPE(3 * ns2, mp_limb_t);
795 lmmp_zero(rad, 3 * nf);
796 lmmp_copy(rad + 3 * nf, a2, na2);
797 } else {
798 rad = a2;
799 }
800
801 // divide 写满 [dsts,ns2)(根顶 limb 恒非零),仅补零可能的最高空 limb
802 lmmp_zero(dsts + ns2, nR - ns2);
803 /*
804 dstr 路径基于恒等式(K = k*2^t,radicand = X*K^3):
805
806 S = floor(K*cbrt(X)) = K*r + e, e = S mod K < K < 2^72
807 R = radicand - S^3 (divide 以 calr=1 维护)
808 K^3*rem = radicand - (S-e)^3 = R + 3*S^2*e - 3*S*e^2 + e^3
809
810 即 rem = (R + 3*S^2*e - 3*S*e^2 + e^3) / K^3,各除法/移位均精确整除。
811 注意 K^3 | R 单独不成立(e ≠ 0 一般),e 的修正项不可省略。e 的至多
812 2 个 limb 由根还原步骤的返回值免费给出:
813 e_lo = S mod 2^t (shr_ 移出低位)
814 e_hi = (S>>t) mod k(div_1 余数)
815 3*S^2*e 等项均为 e <= 2 limb 的 O(n) 小乘,唯一超线性操作是 S 的
816 平方,免去 r^3 的 sqr + mul 两次全尺寸乘法。k==1 且 t==0 时 e=0
817 且 radicand == X,R 即真余数,走直接下拷快路径。
818 */
819 int remnorm = dstr != NULL && k == 1 && t == 0;
820 lmmp_cbrt_divide_(dsts, rad, ns2, tp, dstr != NULL);
821
822 mp_ptr Sp = NULL;
823 if (dstr && !remnorm) {
824 // S 暂存:随后的还原会原地改写 dsts(>>t 与 div_1(k)),而修正项
825 // 仍需还原前的 S,故先复制(e 依赖还原返回值,无法重排避免)
826 Sp = TALLOC_TYPE(ns2, mp_limb_t);
827 lmmp_copy(Sp, dsts, ns2);
828 }
829 mp_limb_t elo = 0;
830 if (t) {
831 mp_limb_t sc = lmmp_shr_(dsts, dsts, nR, t);
832 if (Sp) elo = sc >> (LIMB_BITS - t);
833 }
834 mp_limb_t ehi = k > 1 ? lmmp_div_1_(dsts, dsts, nR, k) : 0;
835
836 if (dstr) {
837 // remnorm 时 na ≡ 0 (mod 3) 且 hb 满偏,ns2 == ns0,R 区域长度恰合
838 if (remnorm) {
839 lmmp_copy(dstr, rad, 2 * ns0 + 1);
840 TEMP_FREE;
841 return;
842 }
843 // e = ehi*2^t + elo(ehi < k <= 256, elo < 2^t,e < K < 2^72)
844 mp_limb_t e0, e1;
845 if (t == 0) {
846 e0 = ehi;
847 e1 = 0;
848 } else {
849 e0 = elo | (ehi << t);
850 e1 = ehi >> (LIMB_BITS - t);
851 }
852
853 mp_size_t L = 2 * ns2 + 3;
854 mp_ptr N = rad;
855 lmmp_zero(N + 2 * ns2 + 1, L - (2 * ns2 + 1));
856
857 if (e0 | e1) {
858 mp_ptr s2v = TALLOC_TYPE(2 * ns2, mp_limb_t);
859 mp_ptr tb = TALLOC_TYPE(2 * ns2 + 2, mp_limb_t);
860 // N += 3*S^2*e,pe = [tb, 2*ns2+2) = S^2*e
861 lmmp_sqr_(s2v, Sp, ns2);
862 mp_limb_t cy = lmmp_mul_1_(tb, s2v, 2 * ns2, e0);
863 tb[2 * ns2] = cy;
864 tb[2 * ns2 + 1] = 0;
865 if (e1) {
866 // addmul 窗口顶为 limb 2*ns2,返回进位归属 limb 2*ns2+1
867 tb[2 * ns2 + 1] = lmmp_addmul_1_(tb + 1, s2v, 2 * ns2, e1);
868 }
869 cy = lmmp_addmul_1_(N, tb, 2 * ns2 + 2, 3);
870 if (cy)
871 cy = lmmp_add_1_(N + 2 * ns2 + 2, N + 2 * ns2 + 2, L - 2 * ns2 - 2, cy);
872 lmmp_debug_assert(cy == 0);
873
874 mp_limb_t eb[2] = {e0, e1}, e2b[4], e3b[6];
875 lmmp_sqr_hard_2_(e2b, eb);
876 lmmp_mul_basecase_(e3b, e2b, 4, eb, 2);
877 cy = lmmp_add_(N, N, L, e3b, 6);
878 lmmp_debug_assert(cy == 0);
879
880 // N -= 3*S*e^2(e^2 至多 3 limb <= ns2);低窗内可能需向高位借位
881 mp_size_t ne2 = 4;
882 while (ne2 > 1 && e2b[ne2 - 1] == 0) --ne2;
883 lmmp_mul_(tb, Sp, ns2, e2b, ne2);
884 mp_limb_t bo = lmmp_submul_1_(N, tb, ns2 + ne2, 3);
885 if (bo)
886 bo = lmmp_sub_1_(N + ns2 + ne2, N + ns2 + ne2, L - ns2 - ne2, bo);
887 lmmp_debug_assert(bo == 0); // N = K^3*rem >= 0
888 }
889
890 // rem = (N/k^3) >> (3t)
891 if (k > 1)
892 lmmp_div_1_(N, N, L, k * k * k);
893 mp_size_t w = 3 * t / LIMB_BITS, b = 3 * t % LIMB_BITS;
894 mp_ptr rp = N + w;
895 if (b)
896 lmmp_shr_(rp, rp, L - w, b);
897 // w <= 2 且 ns2 >= ns0 保证 L - w >= 2*ns0 + 1,拷贝即写满余数区
898 lmmp_debug_assert(L - w >= 2 * ns0 + 1);
899 lmmp_copy(dstr, rp, 2 * ns0 + 1);
900 TEMP_FREE;
901 return;
902 }
903 TEMP_FREE;
904}
#define k
#define Ahr
#define CBRT_DIVIDE_MIN
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 cbrt.c:36
#define rk
#define Ahr2
#define R
static mp_size_t lmmp_cbrt_cls_shift_(mp_size_t bl, int top2)
定义 cbrt.c:302
static mp_size_t lmmp_cbrt_snorm_(mp_srcptr numa, mp_size_t na, mp_ptr a2, mp_size_t *na2p)
定义 cbrt.c:635
static void lmmp_cbrt_shapply_(mp_srcptr src, mp_size_t n, mp_size_t s, mp_ptr a2)
定义 cbrt.c:314
#define Alr2
static void lmmp_cube_6_(mp_ptr restrict t, mp_srcptr restrict r)
计算 [t,6]=[r,2]^3
定义 cbrt.c:51
static mp_size_t lmmp_cbrt_knorm_(mp_srcptr numa, mp_size_t na, mp_ptr a2, mp_size_t *na2p, mp_limb_t *kp)
定义 cbrt.c:320
static void lmmp_cube_3_(mp_ptr restrict dst, mp_limb_t a)
定义 cbrt.c:38
#define Alr
#define rp
#define lmmp_limb_bits_
#define lmmp_mullh_
#define lmmp_sqr_
#define LIMB_B_8
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
void lmmp_fill_n(mp_ptr dst, mp_size_t len, mp_limb_t val)
填充从dst开始的长度为len的数组,值为val
定义 fill.c:33
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define LIMB_MAX
定义 lmmp.h:105
#define LMMP_MAX(h, i)
返回两个数中的较大值
定义 lmmp.h:454
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#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)
除法运算
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
定义 div.c:137
void lmmp_mul_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
#define lmmp_dec(p)
减1宏(预期无借位)
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
void lmmp_sqr_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
#define lmmp_inc(p)
加1宏(预期无进位)
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.c:26
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]
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]
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.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_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
定义 mul_1.c:76
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
#define lmmp_dec_1(p, dec)
减指定值宏(预期无借位)
static mp_limb_t lmmp_sub_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
减单精度数静态内联函数 [dst,na]=[numa,na]-x
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
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_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
void lmmp_sqr_hard_2_(mp_ptr dst, mp_srcptr numa)
#define xp
#define r1
#define a2
#define r0
#define t
#define tp
#define s
#define n
#define scratch
#define lo
#define c1
#define CBRT_INVNEWTON_K_THRESHOLD
#define CBRT_INVNEWTON_NF_MIN
#define CBRT_NEWTON_MODM_THRESHOLD
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_newton_(mp_ptr dsts, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算近似立方根 [dsts,na/3+nf+1]=[floor|round](cbrt([numa,na]*B^(3*nf))), 输入须已归一化:na ≡ 0 (mod 3) 且顶 limb >= B...
定义 cbrt.c:688
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_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,...
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 restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)