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

浏览该文件的源代码.

宏定义

#define Ahr   (dst + lo)
#define Ahr2   (tp)
#define Alr   (tp + 2 * hi)
#define Alr2   (tp + 2 * hi + lo)
#define CBRT_DIVIDE_MIN   (0x6000000000000000ull)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define R   (numa)
#define rk   (numa + 3 * lo)
#define scratch   (tp + 2 * hi + 3 * lo)

函数

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) 的立方根和余数
static mp_size_t lmmp_cbrt_cls_shift_ (mp_size_t bl, int top2)
void lmmp_cbrt_divide_ (mp_ptr restrict dst, mp_ptr restrict numa, mp_size_t ns, mp_ptr restrict tp, int calr)
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)
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/8
static void lmmp_cbrt_shapply_ (mp_srcptr src, mp_size_t n, mp_size_t s, mp_ptr a2)
static mp_size_t lmmp_cbrt_snorm_ (mp_srcptr numa, mp_size_t na, mp_ptr a2, mp_size_t *na2p)
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
void lmmp_invcbrt_newton_ (mp_ptr restrict dstis, mp_size_t ns, mp_srcptr restrict numa, mp_size_t na)

宏定义说明

◆ Ahr

#define Ahr   (dst + lo)

被这些函数引用 lmmp_cbrt_divide_() , 以及 lmmp_sqrt_divide_().

◆ Ahr2

#define Ahr2   (tp)

被这些函数引用 lmmp_cbrt_divide_().

◆ Alr

#define Alr   (tp + 2 * hi)

被这些函数引用 lmmp_cbrt_divide_() , 以及 lmmp_sqrt_divide_().

◆ Alr2

#define Alr2   (tp + 2 * hi + lo)

被这些函数引用 lmmp_cbrt_divide_() , 以及 lmmp_sqrt_divide_().

◆ 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.c 第 36 行定义.

被这些函数引用 lmmp_cbrt_6_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_() , 以及 lmmp_cbrt_knorm_().

◆ R

#define R   (numa)

被这些函数引用 lmmp_cbrt_divide_() , 以及 lmmp_sqrt_divide_().

◆ rk

#define rk   (numa + 3 * lo)

被这些函数引用 check_pow1_laws(), lmmp_cbrt_divide_() , 以及 lmmp_sqrt_divide_().

◆ scratch

#define scratch   (tp + 2 * hi + 3 * lo)

函数说明

◆ lmmp_cbrt_()

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) 的立方根和余数

参数
dsts立方根结果输出指针(缓冲区长度至少 nf+na/3+3 个limb)
dstr余数结果输出指针(缓冲区长度至少 2*(nf+na/3)+3 个limb,NULL 表示不计算余数)
numa源操作数指针(长度为 na 个limb)
na操作数的 limb 长度
nf精度因子
警告
na>0, numa[na-1]!=0, eqsep(dsts,numa), eqsep(dstr,numa)
注解
if (dstr != NULL) { [dsts],[dstr] = cbrtrem([numa,na]*B^(3*nf)),即精确 floor 立方根 与余数 [numa,na]*B^(3*nf) - [dsts]^3(长度 2*ns+1,ns 为根长) } else { if (nf == 0) { [dsts] = floor(cbrt([numa,na])) } else { [dsts] = [floor|round](cbrt([numa,na]*B^(3*nf))) } }
注意
如你需要精确的floor(cbrt(x))语义,请确保nf==0或传入dstr

在文件 cbrt.c 第 718 行定义.

718 {
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
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_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 rp
#define lmmp_sqr_
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
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
定义 div.c:137
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]
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
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]
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
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
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
void lmmp_sqr_hard_2_(mp_ptr dst, mp_srcptr numa)
#define a2
#define t
#define tp
#define CBRT_INVNEWTON_K_THRESHOLD
#define CBRT_INVNEWTON_NF_MIN
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_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
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_cbrt_divide_(mp_ptr dst, mp_ptr numa, mp_size_t ns, mp_ptr tp, int calr)
计算算术立方根 floor(cbrt([numa,3*ns]))
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 a2, CBRT_INVNEWTON_K_THRESHOLD, CBRT_INVNEWTON_NF_MIN, k, LIMB_BITS, lmmp_add_(), lmmp_add_1_(), lmmp_addmul_1_(), lmmp_cbrt_(), lmmp_cbrt_3_(), lmmp_cbrt_6_(), lmmp_cbrt_divide_(), lmmp_cbrt_knorm_(), lmmp_cbrt_newton_(), lmmp_cbrt_snorm_(), lmmp_cbrt_ulong_(), lmmp_copy, lmmp_cube_3_(), lmmp_cube_6_(), lmmp_debug_assert, lmmp_div_1_(), lmmp_mul_(), lmmp_mul_1_(), lmmp_mul_basecase_(), lmmp_shr_(), lmmp_sqr_, lmmp_sqr_hard_2_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_submul_1_(), lmmp_zero, rp, t, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

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

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

◆ lmmp_cbrt_cls_shift_()

mp_size_t lmmp_cbrt_cls_shift_ ( mp_size_t bl,
int top2 )
inlinestatic

在文件 cbrt.c 第 302 行定义.

302 {
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}

引用了 lmmp_cbrt_cls_shift_().

被这些函数引用 lmmp_cbrt_cls_shift_() , 以及 lmmp_cbrt_knorm_().

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

◆ lmmp_cbrt_divide_()

void lmmp_cbrt_divide_ ( mp_ptr restrict dst,
mp_ptr restrict numa,
mp_size_t ns,
mp_ptr restrict tp,
int calr )

在文件 cbrt.c 第 100 行定义.

100 {
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}
#define Ahr
#define CBRT_DIVIDE_MIN
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 cbrt.c:36
#define rk
#define Ahr2
#define R
#define Alr2
#define Alr
void lmmp_fill_n(mp_ptr dst, mp_size_t len, mp_limb_t val)
填充从dst开始的长度为len的数组,值为val
定义 fill.c:33
#define LIMB_MAX
定义 lmmp.h:105
#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宏(预期无借位)
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]
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
#define scratch
#define lo
#define c1
void lmmp_cbrt_6_fast_(mp_ptr dst, mp_ptr numa, mp_ptr tp)
计算算术立方根 [dst,2] = floor(cbrt([numa,6]))

引用了 Ahr, Ahr2, Alr, Alr2, c1, CBRT_DIVIDE_MIN, LIMB_MAX, lmmp_add_1_(), lmmp_addmul_1_(), lmmp_cbrt_3_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_copy, lmmp_cube_3_(), lmmp_debug_assert, lmmp_dec, lmmp_div_1_(), lmmp_div_s_(), lmmp_fill_n(), lmmp_inc_1, lmmp_mul_(), lmmp_mul_1_(), lmmp_mul_basecase_(), lmmp_param_assert, lmmp_sqr_, lmmp_sqr_hard_2_(), lmmp_sub_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_submul_1_(), lo, R, restrict, rk, scratch , 以及 tp.

函数调用图:

◆ lmmp_cbrt_knorm_()

mp_size_t lmmp_cbrt_knorm_ ( mp_srcptr numa,
mp_size_t na,
mp_ptr a2,
mp_size_t * na2p,
mp_limb_t * kp )
static

在文件 cbrt.c 第 320 行定义.

320 {
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}
static mp_size_t lmmp_cbrt_cls_shift_(mp_size_t bl, int top2)
定义 cbrt.c:302
static void lmmp_cbrt_shapply_(mp_srcptr src, mp_size_t n, mp_size_t s, mp_ptr a2)
定义 cbrt.c:314
#define lmmp_limb_bits_
#define lmmp_mullh_
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define s

引用了 a2, CBRT_DIVIDE_MIN, k, LIMB_BITS, lmmp_cbrt_cls_shift_(), lmmp_cbrt_knorm_(), lmmp_cbrt_shapply_(), lmmp_debug_assert, lmmp_limb_bits_, lmmp_mul_1_(), lmmp_mullh_, lmmp_param_assert, s, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 lmmp_cbrt_() , 以及 lmmp_cbrt_knorm_().

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

◆ lmmp_cbrt_newton_()

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/8

参数
dsts目标数组(长度至少 na/3+nf+1 个limb)
numa输入数组(长度为 na 个limb,已 3 对齐归一化)
nanuma数组的 limb 长度(3 的倍数)
nf精度因子
警告
na>0, na%3==0, numa[na-1]>=B/8, nf>=2, 3*nf>=2*na+3, dsts!=NULL, numa!=NULL, sep(dsts,numa)
注解
设 x = cbrt([numa,na]*B^(3*nf))(实数),round 为四舍五入(恰为 1/2 时进位), 则结果恰为 round(x-eps),其中 0 <= eps < 2^-62。eps 非负,故结果绝不超过 round(x);仅当 x 的小数部分落在 [1/2, 1/2+eps) 时得到 floor(x) 而非 floor(x)+1(随机输入下概率 < 2^-62),此即 [floor|round] 的确切含义。

在文件 cbrt.c 第 688 行定义.

688 {
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}
#define LIMB_B_8
#define lmmp_inc(p)
加1宏(预期无进位)
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,...

引用了 LIMB_B_8, LIMB_BITS, lmmp_cbrt_newton_(), lmmp_copy, lmmp_inc, lmmp_invcbrt_newton_(), lmmp_mul_(), lmmp_param_assert, lmmp_sqr_, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 lmmp_cbrt_(), lmmp_cbrt_newton_() , 以及 lmmp_invcbrt_newton_().

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

◆ lmmp_cbrt_shapply_()

void lmmp_cbrt_shapply_ ( mp_srcptr src,
mp_size_t n,
mp_size_t s,
mp_ptr a2 )
inlinestatic

在文件 cbrt.c 第 314 行定义.

314 {
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}
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
#define n

引用了 a2, LIMB_BITS, lmmp_cbrt_shapply_(), lmmp_shl_(), lmmp_zero, n , 以及 s.

被这些函数引用 lmmp_cbrt_knorm_(), lmmp_cbrt_shapply_() , 以及 lmmp_cbrt_snorm_().

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

◆ lmmp_cbrt_snorm_()

mp_size_t lmmp_cbrt_snorm_ ( mp_srcptr numa,
mp_size_t na,
mp_ptr a2,
mp_size_t * na2p )
static

在文件 cbrt.c 第 635 行定义.

635 {
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}
size_t mp_bitcnt_t
定义 lmmp.h:98

引用了 a2, LIMB_B_8, LIMB_BITS, lmmp_cbrt_shapply_(), lmmp_cbrt_snorm_(), lmmp_debug_assert, lmmp_limb_bits_, lmmp_param_assert , 以及 s.

被这些函数引用 lmmp_cbrt_() , 以及 lmmp_cbrt_snorm_().

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

◆ lmmp_cube_3_()

void lmmp_cube_3_ ( mp_ptr restrict dst,
mp_limb_t a )
inlinestatic

在文件 cbrt.c 第 38 行定义.

38 {
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}

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

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

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

◆ 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.c 第 51 行定义.

51 {
52 lmmp_sqr_hard_2_(t + 6, r);
53 lmmp_mul_basecase_(t, t + 6, 4, r, 2);
54}

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

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

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

◆ lmmp_invcbrt_newton_()

void lmmp_invcbrt_newton_ ( mp_ptr restrict dstis,
mp_size_t ns,
mp_srcptr restrict numa,
mp_size_t na )

在文件 cbrt.c 第 440 行定义.

440 {
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}
#define LMMP_MAX(h, i)
返回两个数中的较大值
定义 lmmp.h:454
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
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
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
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
#define lmmp_dec_1(p, dec)
减指定值宏(预期无借位)
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
#define xp
#define r1
#define r0
#define CBRT_NEWTON_MODM_THRESHOLD
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 CBRT_NEWTON_MODM_THRESHOLD, LIMB_B_8, LIMB_BITS, LIMB_MAX, lmmp_add_(), lmmp_cbrt_6_(), lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_dec_1, lmmp_div_1_(), lmmp_div_s_(), lmmp_inc, lmmp_inc_1, lmmp_invcbrt_newton_(), LMMP_MAX, lmmp_mersenne_next_size_(), LMMP_MIN, lmmp_mul_(), lmmp_mul_mersenne_(), lmmp_not_(), lmmp_param_assert, lmmp_sqr_, lmmp_sqr_mersenne_(), lmmp_zero, lmmp_zero_q_(), r0, r1, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 xp.

函数调用图: