LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
nthroot.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 "numth/log2_exp2.h"
25#include "lmmp/lmmpn.h"
26#include "lmmp/numth.h"
27
28
29/**
30 * @brief 取 [p,n] >> s 的低 64bit(自 cbrt.c 同名辅助移植)
31 * @param p 源操作数指针
32 * @param n 源操作数的 limb 长度
33 * @param s 右移位数
34 * @return (p >> s) 的低 64bit
35 * @warning n>0, 0 <= s < 64*n
36 */
38 mp_size_t w = (mp_size_t)(s >> 6);
39 ulong b = s & 63;
40 mp_limb_t lo = p[w];
41 mp_limb_t hi = (w + 1 < n) ? p[w + 1] : 0;
42 return b ? ((lo >> b) | (hi << (64 - b))) : lo;
43}
44
45/*
46 窗口截断幂链的截断+归一化:v(*plen limb)截至顶 wlimbs limb 并把
47 顶 bit 左移到 limb 顶(MSB=1),丢弃位数(bit 计)累入 *dr。
48 语义不变量:v_stored·2^dr ≈ 真值。
49*/
50/**
51 * @brief 截断幂链的逐层截断+归一化(nthroot_pow_trunc_ 的层内步骤)
52 * @param v 值缓冲(原地覆写为截断结果)
53 * @param plen 输入 v 的有效长度,输出截断后长度
54 * @param dr 丢弃位数(bit 计)的累计记账(输出累入本次截断量)
55 * @param wlimbs 窗口宽度(limb)
56 * @warning plen!=NULL, dr!=NULL
57 * @note 不变量 [v,*plen]·2^(*dr) ≈ 调用前的真值;顶 limb 恒 MSB=1
58 * (或 *plen==0),供后续截断/除法使用。
59 * 顶零 limb 至多 1 个(值界:入口/sqr 顶恒非零;mul 积
60 * ≥ 2^(64l-65) ⟹ bitlen ≥ 64(l-1)),单次顶 limb 探测即精确。
61 */
62static void nthroot_chop_(mp_ptr v, mp_size_t *plen, slong *dr, mp_size_t wlimbs) {
63 mp_size_t l = *plen;
64 if (l > wlimbs) {
65 *dr += 64 * (slong)(l - wlimbs);
66 lmmp_copy(v, v + (l - wlimbs), wlimbs); // memmove 前向安全
67 l = wlimbs;
68 }
69 if (l > 0 && v[l - 1] == 0) --l;
70 if (l > 0) {
71 unsigned b = (unsigned)lmmp_limb_bits_(v[l - 1]);
72 if (b < 64) {
73 lmmp_shl_(v, v, l, 64 - b); // 顶 bit 移至 63,进位恒 0
74 *dr -= 64 - b;
75 }
76 }
77 *plen = l;
78}
79
80/*
81 截断幂链:dst(归一化,≤ wlimbs limb)≈ base^exp / 2^(*drop)
82
83 左扫二进制幂,每次 sqr 后先截断再乘 base(乘积 ≤ wlimbs+bn ≤
84 2·wlimbs limb),bufa/bufb 乒乓(各 2·wlimbs+8 limb)。相对误差
85 ≤ (2·log2(exp)+4)·2^-(64·wlimbs),由层的守卫 limb 吸收。
86*/
87/**
88 * @brief 计算窗口截断幂链 [dst] ≈ [base,bn]^exp / 2^(*drop)
89 * @param dst 结果指针(归一化,≤ wlimbs limb)
90 * @param drop 输出:为匹配窗口而丢弃的位数(bit 计,精确记账)
91 * @param wlimbs 窗口宽度(limb)
92 * @param base 底数指针(顶 limb 允许为 0,内部截断时归一)
93 * @param bn 底数的 limb 长度(≤ wlimbs 或顶 limb 为 0 等价归一后 ≤ wlimbs)
94 * @param exp 指数
95 * @param bufa 幂链乒乓缓冲(≥ 2·wlimbs+8 limb)
96 * @param bufb 同 bufa,sep(bufa,bufb)
97 * @return dst 长度
98 * @warning exp >= 2, sep(dst,bufa,bufb), base 与两缓冲 sep
99 * @note 不变量 [dst,返回值]·2^(*drop) = base^exp·(1±ε),
100 * ε ≤ (2·log2(exp)+4)·2^-(64·wlimbs),由调用方的守卫 limb 吸收。
101 */
103 mp_ptr dst, slong *drop, mp_size_t wlimbs,
104 mp_srcptr base, mp_size_t bn, ulong exp, mp_ptr bufa, mp_ptr bufb
105) {
106 mp_ptr P = bufa;
107 mp_size_t pl = bn < wlimbs ? bn : wlimbs;
108 lmmp_copy(P, base + (bn - pl), pl); // 底数超窗时取顶 pl limb(低位 64·(bn-pl) bit 计入 dr)
109 slong dr = 64 * (slong)(bn - pl);
110 nthroot_chop_(P, &pl, &dr, wlimbs);
111
112 int hb = lmmp_limb_bits_(exp) - 1;
113 for (int i = hb - 1; i >= 0; --i) {
114 mp_ptr Q = (P == bufa) ? bufb : bufa; // sqr 目标(P 旧值即死)
115 lmmp_sqr_(Q, P, pl);
116 mp_size_t ql = 2 * pl;
117 dr *= 2; // (P·2^dr)² = P²·2^(2dr):平方使累积 drop 翻倍(乘 base 不变)
118 nthroot_chop_(Q, &ql, &dr, wlimbs);
119 if ((exp >> i) & 1) {
120 // 乘回 base:写回 P 旧缓冲(长操作数在前)
121 if (ql >= bn) lmmp_mul_(P, Q, ql, base, bn);
122 else lmmp_mul_(P, base, bn, Q, ql);
123 pl = ql + bn;
124 nthroot_chop_(P, &pl, &dr, wlimbs);
125 } else {
126 P = Q;
127 pl = ql;
128 }
129 }
130 lmmp_copy(dst, P, pl);
131 *drop = dr;
132 return pl;
133}
134
135/*
136 Nseg 提取:A 的顶 nlimbs 个 limb(左补零语义)
137
138 值 = floor(A / 2^s),s = bl - 64·nlimbs(s < 0 时为 A·2^(-s))
139
140 即把 A 视作左端补零到恰 nlimbs limb 的整体;值域恰 [2^(64·nlimbs-1),
141 2^(64·nlimbs)) 的截断情形顶 bit 为 A 的顶 bit。
142*/
143/**
144 * @brief 提取 [numa,na] 的顶 nlimbs 个 limb(左补零语义)
145 * @param dst 结果指针(容量 ≥ nlimbs+1)
146 * @param nlimbs 提取的 limb 数
147 * @param numa 源操作数指针
148 * @param na 源操作数的 limb 长度
149 * @param bl bitlen([numa,na])(调用方已算好,避免重扫)
150 * @warning na>0, numa[na-1]!=0, sep(dst,numa)
151 * @note 值 = floor(A/2^s),s = bl-64·nlimbs(s<0 时为 A·2^(-s));
152 * s>0 且移出 bit 非零时值暂占 nlimbs+1 limb,顶 limb 恒 0。
153 */
155 mp_ptr dst, mp_size_t nlimbs, mp_srcptr numa, mp_size_t na, ulong bl
156) {
157 slong s = (slong)bl - 64 * (slong)nlimbs;
158 if (s >= 0) {
159 mp_size_t off = (mp_size_t)(s >> 6);
160 unsigned bit = (unsigned)(s & 63);
161 if (off >= na) {
162 lmmp_zero(dst, nlimbs);
163 return;
164 }
165 mp_size_t m = na - off; // ≤ nlimbs+1(bit>0 时顶 limb 移位后恒 0)
166 lmmp_copy(dst, numa + off, m);
167 lmmp_zero(dst + m, nlimbs + 1 - m);
168 if (bit) lmmp_shr_(dst, dst, m, bit); // 原地右移(契约允许)
169 } else {
170 mp_size_t loff = (mp_size_t)((-s) >> 6);
171 unsigned bit = (unsigned)((-s) & 63);
172 lmmp_zero(dst, nlimbs);
173 mp_size_t m = na;
174 if (m > nlimbs - loff) m = nlimbs - loff;
175 mp_limb_t cy = lmmp_shl_(dst + loff, numa, m, bit); // bit=0 时函数内即拷贝
176 if (loff + m < nlimbs) dst[loff + m] = cy; // 进位必 0(bitlen 恒等)
177 }
178}
179
180/**
181 * @brief 零扩展比较:把 [a,an] 与 [b,bn] 视作等长后比较
182 * @param a 左操作数指针
183 * @param an 左操作数的比较长度(高位允许 0)
184 * @param b 右操作数指针
185 * @param bn 右操作数的比较长度(高位允许 0)
186 * @return 比较结果(<0 / 0 / >0 对应 a < / = / > b)
187 * @warning an>0, bn>0
188 * @note 高位段非零者大,再比较公共低位段——避免为 cmp_ 反复 trim。
189 */
191 for (mp_size_t i = an; i-- > bn;) if (a[i]) return 1;
192 for (mp_size_t i = bn; i-- > an;) if (b[i]) return -1;
194 if (a[i] != b[i]) return a[i] < b[i] ? -1 : 1;
195 return 0;
196}
197
198/**
199 * @brief [y,yn] += 1 并维护精确长度
200 * @param y 值指针(原地)
201 * @param yn 值的精确 limb 长度(顶 limb 非零)
202 * @return 加 1 后的精确 limb 长度
203 * @warning yn>0, y 容量 ≥ yn+1
204 * @note 全 1 形态进位写到 y[yn](长度 +1),其余形态长度不变——
205 * 判定不读 y[yn],缓冲上方残留垃圾不影响。
206 */
208 mp_size_t i = 0;
209 while (i < yn && y[i] == LIMB_MAX) y[i++] = 0;
210 if (i == yn) {
211 y[yn] = 1;
212 return yn + 1;
213 }
214 ++y[i];
215 return yn;
216}
217
218/**
219 * @brief [y,yn] -= 1 并维护精确长度
220 * @param y 值指针(原地)
221 * @param yn 值的精确 limb 长度(顶 limb 非零)
222 * @return 减 1 后的精确 limb 长度
223 * @warning yn>0, 值 ≥ 2(减后非零)
224 * @note 仅 2^(64k) 精确形态缩短 1 limb(bitlen ≥ 64(yn-1)+2 的值减 1
225 * 后 bitlen ≥ 64(yn-1)+1,顶 limb 恒非零)——单次顶 limb 探测。
226 */
228 lmmp_dec(y);
229 if (y[yn - 1] == 0) --yn;
230 return yn;
231}
232
233/**
234 * @brief [p,n] += c0 + c1·B(探针证书的小常数增量)
235 * @param p 值指针(原地)
236 * @param n 值的 limb 长度
237 * @param c0 低 limb 增量
238 * @param c1 次 limb 增量
239 * @warning n >= 2
240 * @note 调用方值域保证无 p[n] 溢出,debug 断言为绊线。
241 */
243 mp_limb_t cc = c0 ? lmmp_add_1_(p, p, n, c0) : 0;
244 lmmp_debug_assert(cc == 0);
245 mp_limb_t cc2 = lmmp_add_1_(p + 1, p + 1, n - 1, c1 + cc);
246 lmmp_debug_assert(cc2 == 0);
247}
248
249/**
250 * @brief [p,n] -= c0 + c1·B(探针证书的小常数量减)
251 * @param p 值指针(原地)
252 * @param n 值的 limb 长度
253 * @param c0 低 limb 减量
254 * @param c1 次 limb 减量
255 * @warning n >= 2
256 * @note 调用方值域保证无下借,debug 断言为绊线。
257 */
259 mp_limb_t bb = c0 ? lmmp_sub_1_(p, p, n, c0) : 0;
260 lmmp_debug_assert(bb == 0);
261 mp_limb_t bb2 = lmmp_sub_1_(p + 1, p + 1, n - 1, c1);
262 lmmp_debug_assert(bb2 == 0);
263}
264
265/*
266 tp 需求(nr = ceil(na/root),nq = nr+1 ≥ ceil(L'/64)):
267
268 Y, Y2 终点幂/试探幂 2·Ycap
269 work 余数中转 na + 4
270 xb/asmb/qb/a1/t2 精化 5·(nq + 8)
271 Db 除数 2·nq + 18
272 bufa/bufb 幂链乒乓 2·(2·nq + 16)
273 Nseg 被除数段/移位 2·nq + 13
274
275 Ycap = max(root·nr+8, na+root/64+4):全幂端点幂的值界
276 y^root < 2^(bl+root+1)(y ≤ T+8,层域 T ≥ 2^128 ⟹ (1+8·root/T)^root
277 ≤ 1+2^-9,增值至多 1 bit)需 na+root/64+4 limb——对齐大 root 形状
278 (root=10^6、na=root、nr=1)可比 root·nr+8 大 ~root/64,取 max。
279 root=4 专用路线的分段(q1/r1/r2 各 na/2+2、sum na/2+3、S nr+2、
280 prd 3·nr+4,合计 2·na+4·nr+16 ≤ 2·Ycap+na+4·nr+4,由 na ≤ 4·nr
281 恒被覆盖)。合计 2·Ycap + na + 13·nq + 127。
282*/
284 lmmp_param_assert(na > 0);
285 lmmp_param_assert(root >= 4 && root <= (1ull << 56));
286 mp_size_t nr = (na + (mp_size_t)root - 1) / (mp_size_t)root;
287 mp_size_t nq = nr + 1; // ceil(L'/64) ≤ ceil((64na+root)/(64root)) + 0 ≤ nr+1
288 mp_size_t ycap = (mp_size_t)root * nr + 8;
289 mp_size_t yneed = na + (mp_size_t)(root >> 6) + 4;
290 if (ycap < yneed) ycap = yneed;
291 return 2 * ycap + na + 4 + 13 * nq + 123;
292}
293
294void lmmp_nthroot_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, ulong root, mp_ptr tp) {
295 lmmp_param_assert(na > 0 && numa != NULL && numa[na - 1] != 0);
296 lmmp_param_assert(root >= 4 && root <= (1ull << 56));
297 lmmp_param_assert(dsts != NULL && tp != NULL);
298 mp_size_t nr = (na + (mp_size_t)root - 1) / (mp_size_t)root; // 根长
299
300 // 平凡域:A < 2^(64na) <= 2^root → 根为 1
301 // 除法形式等价于 (ulong)na * LIMB_BITS <= root 且避免大 na 乘法回绕
302 if (na <= root / LIMB_BITS) {
303 dsts[0] = 1;
304 if (dstr) {
305 lmmp_copy(dstr, numa, na);
306 lmmp_dec(dstr); // rem = A - 1(A >= 1,无下借)
307 lmmp_zero(dstr + na, (root - 1) * nr + 1 - na);
308 }
309 return;
310 }
311 if (na == 1) {
312 dsts[0] = lmmp_nthroot_ulong_(numa[0], root);
313 if (dstr) {
314 ulong acc = 1;
315 for (ulong i = 0; i < root; ++i) acc *= dsts[0];
316 dstr[0] = numa[0] - acc;
317 lmmp_zero(dstr + 1, (root - 1) * nr); // 契约区 [0, root) 余 [1, root)
318 }
319 return;
320 }
321
322 // 位长上限 2^64:na < 2^58 时无回绕(2^58 limb = 2^61 字节,现实不可分配)
323 ulong bl = LIMB_BITS * (ulong)(na - 1) + (ulong)lmmp_limb_bits_(numa[na - 1]);
324
325 /*
326 root=4 专用路线:sqrt∘sqrt 嵌套 floor 恒等式(与顶入口的
327 Ã = A·2^root 恢复同族定理)
328
329 floor(sqrt(floor(sqrt(A)))) = floor(A^(1/4))
330
331 双向夹逼:S = floor(A^(1/4)) ⟹ S² ≤ floor(sqrt(A)) ⟹ S⁴ ≤ A;
332 反向 (S+1)² > floor(sqrt(A)) ⟹ (S+1)² ≥ floor(sqrt(A))+1 ⟹
333 (S+1)⁴ > A。余数由两级 sqrtrem 展开:
334 A = q1² + r1 = (S²+r2)² + r1 ⟹ A - S⁴ = r2·(q1+S²) + r1
335 (q1 = floor(sqrt A),(S,r2) = sqrtrem(q1))。
336
337 长度全解析(免 trim 扫描):精确定理
338 bitlen(floor(sqrt(A))) = ceil(bl/2)、bitlen(S) = ceil(bl/4)
339 (2^(bl-1) ≤ A < 2^bl 两端开方夹逼,嵌套 ceil 复合),故两级
340 sqrt 的输入/输出长度均由 bl 推出;r1/r2 取 sqrt_ 写满的余数区
341 (含顶零)直接作 mul/add 操作数(加减乘不要求归一化),输出
342 先清零 dstr 再拷贝乘积容器全长(顶零拷入零区无害)。
343
344 tp 分段(值域 na ≤ 4·nr 保证覆盖):
345 q1/r1/r2 各 na/2+2,sum na/2+3,S nr+2,prd 3·nr+4。
346 */
347 if (root == 4) {
348 mp_ptr q1 = tp, r1 = q1 + na / 2 + 2, S = r1 + na / 2 + 2, r2v = S + nr + 2,
349 sum = r2v + na / 2 + 2, prd = sum + na / 2 + 3;
350 lmmp_sqrt_(q1, dstr ? r1 : NULL, numa, na, 0);
351 mp_size_t nq1 = (mp_size_t)(((bl + 1) / 2 + 63) >> 6); // bitlen(q1)=ceil(bl/2)
352 lmmp_sqrt_(S, dstr ? r2v : NULL, q1, nq1, 0);
353 mp_size_t sn = (mp_size_t)(((bl + 3) / 4 + 63) >> 6); // bitlen(S)=ceil(bl/4)(= nr)
354 if (dstr) {
355 // rem = r2·(q1 + S²) + r1
356 lmmp_sqr_(sum, S, sn);
357 mp_size_t s2n = 2 * sn;
358 mp_size_t un = nq1 > s2n ? nq1 : s2n; // q1+S² 容器长(add 长在前)
359 if (un > s2n) lmmp_zero(sum + s2n, un - s2n); // sqr 只写 [0,2sn),补零
360 mp_limb_t cy = lmmp_add_(sum, sum, un, q1, nq1);
361 if (cy) sum[un++] = cy;
362 mp_size_t r2n = nq1 / 2 + 1; // r2 余数区(sqrt_ 写满含零)
363 mp_size_t r1n = na / 2 + 1; // r1 余数区(sqrt_ 写满含零)
364 lmmp_mul_(prd, sum, un, r2v, r2n); // 长在前:un ≥ nq1 ≥ nq1/2+1
365 mp_size_t pn = un + r2n; // 乘积容器长(顶零 limb 无害)
366 lmmp_debug_assert(pn >= r1n); // un ≥ nq1 ≥ ceil(na/2)-1,+r2n ≥ r1n
367 mp_limb_t cy2 = lmmp_add_(prd, prd, pn, r1, r1n);
368 if (cy2) prd[pn++] = cy2; // 值界 rem < 2^(192·nr+3):pn ≥ 3nr 时进位恒 0
369 mp_size_t outr = (root - 1) * nr + 1;
370 if (pn > outr) pn = outr; // 值界保证 [pn, outr) 段恒零
371 lmmp_copy(dstr, prd, pn); // 拷贝容器长(含值上方的零 limb)
372 lmmp_zero(dstr + pn, outr - pn);
373 }
374 lmmp_copy(dsts, S, sn); // sn == nr(bl ∈ (64(na-1), 64na] 双侧夹逼)
375 return;
376 }
377
378 ulong B = bl + root; // bitlen(Ã)
379 ulong Lp = (B + root - 1) / root; // L' = bitlen(T)
380 slong shx; // x ≈ T·2^-shx(scale 记账)
381
382 // ---- scratch 布局(单块手动分段,生命周期接力;注释 [p,n):p 段首,n 段长)----
383 mp_size_t nqf = nr + 1;
384 const mp_size_t XW = nqf + 8; // 精化窗宽:xb/asmb/qb/a1/t2 五段共用
385 const mp_size_t DW = 2 * nqf + 18; // Db 段长(截断幂链结果/除数)
386 const mp_size_t BW = 2 * (nqf + 4) + 8; // 幂链乒乓单段长
387 const mp_size_t NW = 2 * nqf + 13; // Nseg 段长(被除数段/移位暂存)
388 mp_size_t Ycap = (mp_size_t)root * nr + 8;
389 {
390 mp_size_t yneed = na + (mp_size_t)(root >> 6) + 4;
391 if (Ycap < yneed) Ycap = yneed; // 全幂端点幂值界(见 size_ 注)
392 }
393 mp_ptr Y = tp; // [Y, Ycap] 终点幂/试探幂(回退)
394 mp_ptr Y2 = Y + Ycap; // [Y2, Ycap] 试探幂 (y+1)^root(回退)
395 mp_ptr work = Y2 + Ycap; // [work, na+4] 余数中转
396 mp_ptr xb = work + na + 4; // [xb, XW] 精化状态 x / 探针链结果 V
397 mp_ptr asmb = xb + XW; // [asmb, XW] 商/装配累加器 / 探针 Wc·L
398 mp_ptr qb = asmb + XW; // [qb, XW] q·root 移位段 / 探针 slack·Sh / 回退 y+1
399 mp_ptr a1 = qb + XW; // [a1, XW] (root-1)·x 暂存 / y 候选
400 mp_ptr t2 = a1 + XW; // [t2, XW] q·root·2^-X 段 / 探针 M 低位
401 mp_ptr Db = t2 + XW; // [Db, DW] 截断幂链结果/除数 D
402 mp_ptr bufa = Db + DW; // [bufa, BW] 幂链乒乓 a
403 mp_ptr bufb = bufa + BW; // [bufb, BW] 幂链乒乓 b
404 mp_ptr Nseg = bufb + BW; // [Nseg, NW] 被除数段/移位暂存(探针 M 高位接力)
405
406 // ---- 1) 种子:x0 ≈ T·2^(127-I),shx = I-127;xn/bx 显式(xb 高段无读者,不清零)----
408 ulong bx;
409 {
410 // y = log2(Ã) = (B-1) + log2(1+f),f 取 A 顶 129bit 去前导 1 的
411 // 128bit 小数(Ã 顶 bit 同 A)。y/root = I + (rem+f)/root,
412 // rem = (B-1) mod root(< 2^56 独占第 3 limb):
413 // 3 limb 定点 [f | rem] 除 root 得 128bit 商,exp2 后取 128bit
414 // 归一化尾数。
415 ulong flo, fhi;
416 if (bl >= 129) {
417 ulong s0 = bl - 129;
418 flo = lmmp_shr64_(numa, na, s0);
419 fhi = lmmp_shr64_(numa, na, s0 + 64);
420 } else {
421 mp_limb_t w[3] = {0, 0, 0};
422 mp_size_t m = na < 3 ? na : 3; // bl < 129 ⟹ na ≤ 3
423 lmmp_copy(w, numa, m);
424 unsigned sh = (unsigned)(129 - bl);
425 if (sh == 64) {
426 // bl=65(恰 2 limb、顶 limb=1):整 limb 上移,越过 shl_ 的
427 // [0,63] 契约域(asm 掩码行为未定义,须显式处理)
428 w[2] = w[1];
429 w[1] = w[0];
430 w[0] = 0;
431 } else {
432 mp_limb_t cy = lmmp_shl_(w, w, 3, sh);
433 (void)cy; // 高于 129bit 的进位即前导 1 之上,弃
434 }
435 flo = w[0];
436 fhi = w[1];
437 }
438 mp_limb_t fr[3];
439 log2_fixed_128(fr, fhi, flo); // fr = log2(1+f) 的 128bit 定点
440 fr[2] = (mp_limb_t)((B - 1) % root);
441 lmmp_div_1_(fr, fr, 3, root); // (rem·2^128 + f)/root,商 ≤ 2^128
442 mp_limb_t e[2];
443 exp2_fixed_128(e, fr[1], fr[0]); // 2^frac 的 128bit 小数
444 xb[0] = (e[0] >> 1) | (e[1] << 63);
445 xb[1] = (1ULL << 63) | (e[1] >> 1); // x0 = 2^127 + (e >> 1)
446 xn = 2;
447 bx = 128; // x0 ∈ [2^127, 2^128) 恰 128 bit
448 shx = (slong)((B - 1) / root) - 127;
449 }
450
451 // ---- 2) 位窗牛顿精化:e_eff = L'-shx → L'(全程显式长度,零 trim 扫描/零全段清零)----
452 slong lambda = (slong)lmmp_limb_bits_(root - 1) + 12;
453 for (;;) {
454 slong e_eff = (slong)Lp - shx;
455 if (e_eff >= (slong)Lp) break; // 种子直达域(shx ≤ 0);层出口恒 shx=0
456 slong e2 = 2 * e_eff - lambda; // e_eff ≥ 128 > λ ⟹ e2 > e_eff
457 int final_stage = 0;
458 if (e2 >= (slong)Lp) {
459 e2 = (slong)Lp;
460 final_stage = 1; // 终层后无条件退出(renorm ±1 不再依赖 e_eff 判定)
461 }
462 slong shx2 = (slong)Lp - e2;
463 slong delta = e2 - e_eff;
464
465 mp_size_t nq = (mp_size_t)((e2 + 63) / 64) + 1;
466 mp_size_t Lseg = 2 * nq + 3;
467 mp_size_t w = nq + 4;
468
469 // D = root·P,P = x^(root-1) 截断至 w limb(drop 为丢弃 bit 数)
470 slong drop;
471 mp_size_t pl = nthroot_pow_trunc_(Db, &drop, w, xb, xn, root - 1, bufa, bufb);
472 mp_limb_t cy = lmmp_mul_1_(Db, Db, pl, root);
473 mp_size_t dl = pl;
474 if (cy) Db[dl++] = cy;
475 // 除数取 D 的顶 nd limb [Db+dl-nd, nd)(nd ≤ nq+3;顶 limb 恒非零),
476 // 低位截断量 64·(dl-nd) 由尺度恒等式吸收。lmmp_div_ 内部归一化并
477 // 支持仅算商(dstr=NULL):div_s 的 MSB 契约、手工提窗移位与
478 // 商顶 limb 回收一并免去
479 mp_size_t nd = dl < nq + 3 ? dl : nq + 3;
480
481 // Nseg = A 的顶 Lseg limb(左补零语义)
482 nthroot_top_limbs_(Nseg, Lseg, numa, na, bl);
483
484 // q_seg = floor(Nseg/Dseg)(仅商;[asmb, Lseg-nd+1],顶 limb 可为 0,
485 // mul_1/移位不要求归一化,容器长直传)
486 lmmp_div_(asmb, NULL, Nseg, Lseg, Db + dl - nd, nd);
487 mp_size_t ql = Lseg - nd + 1;
488
489 /*
490 尺度恒等式(层核心):q_true := N_{e2}/y^(root-1) ≈ q_seg·root·2^-X,
491
492 X = 64·(dl-nd) + 64·Lseg - bl + root·shx2 - root + (root-1)·delta + drop
493
494 推导:Nseg = A·2^(64Lseg-bl)·(1±2^-64Lseg),
495 Dseg = floor(D/2^(64(dl-nd))) = root·P·2^-(64(dl-nd)),
496 P = x^(root-1)·2^-drop,y^(root-1) = x^(root-1)·2^((root-1)·delta),
497 N_{e2} = A·2^(root-root·shx2);代入相消即得(各 floor 误差
498 ≤ 1 ulp 由守卫吸收)。root>=5 时恒 dl >= nq+3(首层 bitlen(D)
499 >= 64(nq+3),之后 (root-1)e_eff 增速快于 e2),min 为防御。
500 */
501 slong X = 64 * (slong)(dl - nd) + 64 * (slong)Lseg - (slong)bl + (slong)root * shx2
502 - (slong)root + (slong)(root - 1) * delta + drop;
503
504 // t2 = (q_seg·root)·2^-X(值底对齐;X<0 时左移暂驻 Nseg,
505 // 与 a1 的相加直接消费驻留形态,不回拷)
506 mp_ptr tq;
507 mp_size_t tl;
508 {
509 mp_limb_t cy2 = lmmp_mul_1_(t2, asmb, ql, root);
510 tl = ql;
511 if (cy2) t2[tl++] = cy2;
512 if (X > 0) {
513 mp_size_t loff = (mp_size_t)(X >> 6);
514 if (loff >= tl) {
515 tl = 0; // 商整体低于窗(早层)→ t2 = 0
516 } else {
517 // shr_ 允许 dst<numa 重叠(含 shr=0 的整段拷贝分支)
518 lmmp_shr_(t2, t2 + loff, tl - loff, (mp_size_t)(X & 63));
519 tl -= loff;
520 }
521 tq = t2;
522 } else if (X < 0) {
523 mp_size_t loff = (mp_size_t)((-X) >> 6);
524 unsigned bit = (unsigned)((-X) & 63);
525 lmmp_zero(Nseg, loff);
526 mp_limb_t cy3 = lmmp_shl_(Nseg + loff, t2, tl, bit); // bit=0 时函数内即拷贝
527 tl += loff;
528 if (cy3) Nseg[tl++] = cy3;
529 lmmp_debug_assert(tl <= NW);
530 tq = Nseg;
531 } else {
532 tq = t2;
533 }
534 }
535
536 // a1 = (root-1)·x·2^delta 落位 asmb:[asmb, dloff) 清零 + 乘积左移
537 mp_size_t al;
538 {
539 mp_size_t dloff = (mp_size_t)(delta >> 6);
540 unsigned dbit = (unsigned)(delta & 63);
541 al = xn;
542 mp_limb_t cy4 = lmmp_mul_1_(asmb + dloff, xb, xn, root - 1);
543 if (cy4) asmb[dloff + al++] = cy4;
544 if (dbit) {
545 mp_limb_t cy5 = lmmp_shl_(asmb + dloff, asmb + dloff, al, dbit);
546 if (cy5) asmb[dloff + al++] = cy5;
547 }
548 lmmp_zero(asmb, dloff);
549 al += dloff;
550 }
551 lmmp_debug_assert(al <= XW);
552
553 // x' = floor((a1 + t2)/root):长者在前的单次 add + 原地单limb除
554 {
555 mp_ptr np;
556 mp_size_t nl;
557 mp_limb_t c = 0;
558 if (tl == 0) {
559 np = asmb;
560 nl = al;
561 } else if (al >= tl) {
562 c = lmmp_add_(asmb, asmb, al, tq, tl);
563 np = asmb;
564 nl = al;
565 } else {
566 c = lmmp_add_(tq, tq, tl, asmb, al);
567 np = tq;
568 nl = tl;
569 }
570 if (c) np[nl++] = c;
571 lmmp_div_1_(np, np, nl, root); // 原地(契约 eqsep),商高位补零
572
573 /*
574 x' 精确长度(免 trim 扫描):记 t = bx+delta(x·2^delta 的
575 位长,v := x·2^delta ≥ 2^(t-1))。num ≥ (root-1)·v ⟹
576 x' ≥ (root-1)/root·v - 1 ≥ (4/5)v - 1 ≥ 2^(t-2)(root≥5、
577 t ≥ 4)⟹ bitlen(x') ≥ t-1;层误差定理(e2 = 2·e_eff-λ
578 排程)给 x' ≤ v·(1+2^-59) < 2·v < 2^(t+1) ⟹ bitlen ≤ t+1。
579 两界跨 ≤2 bit ⟹ xn ∈ {limbs(t+1), limbs(t+1)-1},
580 单次顶 limb 探测即精确。
581 */
582 xn = (mp_size_t)((bx + (ulong)delta + 64) >> 6);
583 if (np[xn - 1] == 0) --xn;
584 bx = 64 * (ulong)(xn - 1) + (ulong)lmmp_limb_bits_(np[xn - 1]);
585 lmmp_copy(xb, np, xn);
586 }
587 // 不做 mantissa 归一化:shx ← shx2 保持排程精度语义(x' 的 bitlen
588 // 允许略低于 64·nq——牛顿准确度由 e2 = 2·e_eff-λ 的排程保证,
589 // 若按 limb 归一化上移会把"scale"虚标为"精度",下层排程基于虚标
590 // 精度直接 e2 → L' 会越过牛顿的二次收敛保证,终值误差 ~2^(L'-2e+λ))
591 shx = shx2;
592 if (final_stage) break;
593 }
594
595 // ---- 3) 终点:y0 = x·2^-shx ≈ T;S_cand = y0 >> 1,A 域先降后升 ----
596 // 层出口恒 shx=0(终层 e2=L' 钳制)→ 纯拷贝;种子直达域 shx<0
597 // (|shx| ≤ 126,x0 恰 128bit ⟹ 移后 bitlen = 128+shx 精确已知)
598 mp_ptr y = a1; // [y, XW)
599 mp_size_t yn;
600 if (shx < 0) {
601 mp_size_t loff = (mp_size_t)((-shx) >> 6);
602 unsigned bit = (unsigned)((-shx) & 63);
603 lmmp_shr_(y, xb + loff, xn - loff, bit); // bit=0 时函数内即拷贝
604 yn = xn - loff; // bitlen 恰 128+shx ≥ 2,顶 limb 非零
605 } else {
606 lmmp_debug_assert(shx == 0);
607 lmmp_copy(y, xb, xn);
608 yn = xn;
609 }
610 lmmp_shr_(y, y, yn, 1); // S_cand = y0 >> 1(库移位,原地)
611 if (y[yn - 1] == 0) --yn; // 仅 2^(64k) 精确形态掉 1 limb
612
613 /*
614 认证式窗口探针避免在终点计算全尺寸幂。
615
616 以截断幂链 V·2^dr ≈ P(P = y^root;drop 精确记账,相对误差
617 ε ≤ 2^(hb+66-64·w),V 恰 pl limb 且 MSB=1)与 A 的同尺度顶窗
618 Wc 做单侧认证比较。尺度对齐是精确的:C := A·2^-dr 为实值,
619 bitlen(C) = bl - dr 恰已知,shift = bitlen(C) - 64·pl ∈ {-1,0,1}
620 (由 C = V·(1±ε) 与 bitlen(V) = 64·pl 推出),Wc 取
621 nthroot_top_limbs_ 的 64·pl bit 顶窗后按 shift 移位,恒有
622 Wc ≤ C < Wc + 2。结合 P 的双侧界 P ∈ [(V-δ0)·2^dr,
623 (V+δ0)·2^dr](δ0 = 2^(hb+68) ≥ 4·ε·2^64·pl)与 A 的界
624 A ∈ [Wc·2^dr, (Wc+2)·2^dr),四项判决均为无条件定理:
625
626 dec-cert V - Wc >= 2^(hb+69) ⟹ P > A
627 le-cert Wc - V >= 2^(hb+69) ⟹ P <= A
628 done-cert (V-δ0)·root >= (Wc-V+δ0+2)·(ȳ+1)·2^s ⟹ (y+1)^root > A
629 inc-cert (V+δ0)·root·(1+2^-c1) <= (Wc-V-δ0)·ȳ·2^s ⟹ (y+1)^root <= A
630
631 done/inc 由二项式首项 (y+1)^root >= P + root·y^(root-1)(整数、
632 精确)与 (1+1/y)^root <= 1+u(1+u)(u = root/y <= 2^-c1,
633 c1 = bitlen(y)-58)承载不等式方向;ȳ = floor(y/2^s),
634 s = bitlen(y)-128(gate bitlen(y) >= 256 保证 2 limb ȳ 与富余)。
635 le-cert + done-cert ⟹ y = S(定理),无需任何幂。
636
637 落入不确定带(|V-Wc| < 2^(hb+69),或两证书均失败;随机输入
638 概率 ~2^-(hb+69),完全幂/区间顶构造必中)或预算耗尽时回退
639 全幂端点(先降后升单调循环,从任意起点收敛)。概率只决定
640 快路径命中率,正确性由定理 + 精确回退承载。rem 口径在 y
641 认证后仍需一次全幂(余数需要精确 y^root),root-only 免。
642
643 y 的 ±1 调整经 nthroot_inc_len_/nthroot_dec_len_ 维护精确长度
644 (yn 全程有效,探针/回退的后续读者不再扫描)。
645 */
646 int settled = 0;
647 for (int iter = 0; iter < 4 && !settled; ++iter) {
648 if (yn < 4 || 64 * (yn - 1) + lmmp_limb_bits_(y[yn - 1]) < 256) break;
649 unsigned hb = lmmp_limb_bits_(root) - 1; // root <= 2^56 ⟹ hb <= 55
650 mp_limb_t d0hi = 1ULL << (hb + 4); // δ0 = 2^(hb+68) 的 limb 对 {0, d0hi}
651 slong dr;
652 mp_ptr V = xb; // 链结果(pl limb,MSB=1)
653 mp_size_t pl = nthroot_pow_trunc_(V, &dr, nr + 5, y, yn, root, bufa, bufb);
654 lmmp_debug_assert(pl >= 8);
655 slong shift = (slong)bl - dr - 64 * (slong)pl;
656 if (shift < -1 || shift > 1) break; // 定理域外(不可能):回退
657 mp_ptr Wc = asmb; // W0 → 按 shift 移位后的比较窗
658 nthroot_top_limbs_(Wc, pl, numa, na, bl);
659 mp_size_t wl = pl;
660 if (shift > 0) {
661 // C = ÷2^shift(à ∈ [W0, W0+1))⟹ shift=+1: C ∈ [2W0, 2W0+2)
662 mp_limb_t wc = lmmp_shl_(Wc, Wc, pl, 1); // W0 MSB=1 ⟹ 恒产生第 pl limb
663 lmmp_debug_assert(wc == 1);
664 Wc[pl] = wc;
665 wl = pl + 1;
666 } else if (shift < 0) {
667 // shift=-1: C = Ã/2 ∈ [W0/2, W0/2 + 1/2) ⟹ C ∈ [W0>>1, (W0>>1)+1)
668 lmmp_shr_(Wc, Wc, pl, 1); // 顶 limb ≥ 2^62,wl 不变
669 }
670 // slack = |V - Wc|(SPL limb 容器,高位清零),方向 vgtw
671 mp_size_t SPL = pl + 1;
672 mp_ptr slk = qb;
673 lmmp_zero(slk + wl, SPL - wl);
674 int vgtw = nthroot_cmp_ext_(V, pl, Wc, wl) >= 0;
675 if (vgtw) lmmp_sub_(slk, V, pl, Wc, wl);
676 else lmmp_sub_(slk, Wc, wl, V, pl);
677 mp_size_t sn = SPL;
678 while (sn > 0 && slk[sn - 1] == 0) --sn; // 数据依赖(slack 值任意小)
679 // 守卫带宽判定:slack >= 2^(hb+69) ⟺ bitlen(slack) >= hb+70
680 if (sn < 2 || lmmp_limb_bits_(slk[sn - 1]) + 64 * (unsigned)(sn - 1) < hb + 70)
681 break; // 不确定带 → 回退全幂端点
682 if (vgtw) {
683 yn = nthroot_dec_len_(y, yn); // dec-cert:P > A(y 过高,牛顿 +1 残余)
684 continue;
685 }
686 // le-cert 成立:P <= A。done-cert / inc-cert 判定
687 unsigned tb = lmmp_limb_bits_(y[yn - 1]);
688 mp_size_t s = 64 * (yn - 1) + (mp_size_t)tb - 128;
689 mp_limb_t alo = lmmp_shr64_(y, yn, (ulong)s);
690 mp_limb_t ahi = lmmp_shr64_(y, yn, (ulong)s + 64);
691 mp_size_t loff = s >> 6;
692 unsigned sbit = (unsigned)(s & 63);
693 // L = (V-δ0)·root;M = (slack+δ0+2)·(ȳ+1)·2^s(落位 t2+loff 再原地位移)
694 mp_ptr L = asmb; // Wc 已消费(slack 物化于 slk)
695 lmmp_copy(L, V, pl);
696 nthroot_sub_small_(L, pl, 0, d0hi);
697 mp_limb_t lcy = lmmp_mul_1_(L, L, pl, (mp_limb_t)root);
698 mp_size_t ln = pl;
699 if (lcy) {
700 L[ln] = lcy;
701 ++ln;
702 }
703 nthroot_add_small_(slk, SPL, 2, d0hi);
704 mp_limb_t bp1[3] = {alo + 1, ahi + (alo + 1 == 0), 0};
705 bp1[2] = (bp1[0] == 0 && bp1[1] == 0); // ȳ+1 进位到 2^128 的形态
706 mp_size_t bpn = 2 + (bp1[2] != 0);
707 lmmp_zero(t2, loff); // M = 乘积 << (64·loff):低位 loff limb 必须显式清零
708 lmmp_mul_(t2 + loff, slk, SPL, bp1, bpn);
709 mp_size_t mn = loff + SPL + bpn;
710 if (sbit) {
711 mp_limb_t mcy = lmmp_shl_(t2 + loff, t2 + loff, SPL + bpn, sbit);
712 if (mcy) {
713 t2[loff + SPL + bpn] = mcy;
714 ++mn;
715 }
716 }
717 if (nthroot_cmp_ext_(L, ln, t2, mn) >= 0) {
718 settled = 1; // done-cert:(y+1)^root > A,结合 le-cert 得 y = S
719 break;
720 }
721 // L2 = (V+δ0)·root;M2 = (slack-δ0)·ȳ·2^s;判 L2·(1+2^-c1) <= M2
722 lmmp_copy(L, V, pl);
723 nthroot_add_small_(L, pl, 0, d0hi);
724 lcy = lmmp_mul_1_(L, L, pl, (mp_limb_t)root);
725 ln = pl;
726 if (lcy) {
727 L[ln] = lcy;
728 ++ln;
729 }
730 nthroot_sub_small_(slk, SPL, 2, 2 * d0hi); // (slack+δ0+2)-(2+2δ0) = slack-δ0 >= 0(le-cert 守卫 slack >= 2δ0)
731 mp_limb_t ybar[2] = {alo, ahi};
732 lmmp_zero(t2, loff); // 同上:低位清零
733 lmmp_mul_(t2 + loff, slk, SPL, ybar, 2);
734 mn = loff + SPL + 2;
735 if (sbit) {
736 mp_limb_t mcy = lmmp_shl_(t2 + loff, t2 + loff, SPL + 2, sbit);
737 if (mcy) {
738 t2[loff + SPL + 2] = mcy;
739 ++mn;
740 }
741 }
742 // L2 += L2 >> c1 再 +1(整数化 L2·(1+2^-c1) 的上界)
743 mp_size_t c1 = s + 70;
744 mp_size_t l2 = c1 >> 6;
745 unsigned b2 = (unsigned)(c1 & 63);
746 mp_size_t shn = ln - l2;
747 mp_ptr Sh = qb; // slack 已消费(M2 已物化于 t2)
748 lmmp_shr_(Sh, L + l2, shn, b2); // b2=0 时函数内即拷贝
749 mp_limb_t acy = lmmp_add_(L, L, ln, Sh, shn);
750 if (acy) {
751 L[ln] = acy;
752 ++ln;
753 }
754 acy = lmmp_add_1_(L, L, ln, 1);
755 if (acy) {
756 L[ln] = acy;
757 ++ln;
758 }
759 if (nthroot_cmp_ext_(L, ln, t2, mn) <= 0) {
760 yn = nthroot_inc_len_(y, yn); // inc-cert:(y+1)^root <= A,y+1 成为新候选
761 continue;
762 }
763 break; // 不确定带 → 回退全幂端点
764 }
765
766 mp_size_t tn = 0; // Y = y^root 的精确长度(回退/认证幂共用)
767 if (!settled) {
768 // 全幂回退端点(不确定带 / 小根 / bitlen(y) < 256 / 预算耗尽):
769 // 先降后升单调修正(降循环至 y^root <= A,升循环至 (y+1)^root > A),
770 // 从任意起点收敛于真值;Y 恒持有 y^root 供余数。注意与上方探针的
771 // 区别:早轮被否决的 wcmp 以未认证的截断比较直接作循环条件(无尺度
772 // 恒等式、无双侧界、误判即失控);现行探针的每次判决都是单侧定理 +
773 // 精确回退。y 长度经 inc/dec 助手维护,幂比较用 cmp_ext 直接吃
774 // 精确长度(无零填充)。
775 int dec_cnt = 0, inc_cnt = 0;
776 for (;;) {
777 tn = lmmp_pow_(Y, Ycap, y, yn, root);
778 if (nthroot_cmp_ext_(Y, tn, numa, na) <= 0) break;
779 yn = nthroot_dec_len_(y, yn);
780 ++dec_cnt;
781 }
782 for (;;) {
783 lmmp_copy(qb, y, yn);
784 mp_size_t qn = nthroot_inc_len_(qb, yn);
785 mp_size_t tn2 = lmmp_pow_(Y2, Ycap, qb, qn, root);
786 if (nthroot_cmp_ext_(Y2, tn2, numa, na) > 0) break;
787 lmmp_copy(y, qb, qn);
788 yn = qn;
789 mp_ptr sw = Y;
790 Y = Y2;
791 Y2 = sw; // Y 恒持有 y^root(供余数)
792 tn = tn2;
793 ++inc_cnt;
794 }
795 lmmp_debug_assert(dec_cnt <= 8 && inc_cnt <= 8); // 误差预算绊线(定理 ≤ ~4)
796 } else if (dstr) {
797 // y = S 已由定理认证;余数需要精确 y^root,付一次全幂(root-only 免)
798 tn = lmmp_pow_(Y, Ycap, y, yn, root);
799 int yle = nthroot_cmp_ext_(Y, tn, numa, na); // le-cert 绊线(cmp 先算局部变量)
800 lmmp_debug_assert(yle <= 0);
801 }
802
803 // 输出根:yn ≤ nr 恒成立(y = S 精确,S < 2^(64nr)),min 为防御
804 lmmp_copy(dsts, y, yn < nr ? yn : nr);
805 if (yn < nr) lmmp_zero(dsts + yn, nr - yn);
806 if (dstr) {
807 // rem = A - y^root:值 < A < 2^(64na) ⟹ 差在 [work, na) 内;
808 // 契约区 [(root-1)nr+1] 的顶零直接写 dstr(勿经 work 补零——
809 // nr=1 大 root 形状 outr ≫ na+13nq 会越出 tp 末端)
810 mp_size_t yl = tn > na ? na : tn;
811 mp_limb_t bo = lmmp_sub_(work, numa, na, Y, yl);
812 lmmp_debug_assert(bo == 0);
813 mp_size_t outr = (root - 1) * nr + 1;
814 mp_size_t on = outr < na ? outr : na;
815 lmmp_copy(dstr, work, on);
816 lmmp_zero(dstr + on, outr - on);
817 }
818}
#define xn
static mp_limb_t lmmp_shr64_(mp_srcptr p, mp_size_t n, uint64_t s)
#define B
#define an
#define bn
#define lmmp_limb_bits_
#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
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_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]
#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
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_(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_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_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
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
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
#define a1
#define bp1
#define r1
#define b2
#define tp
#define s
#define n
#define lo
#define c1
#define c0
static mp_size_t nthroot_inc_len_(mp_ptr y, mp_size_t yn)
[y,yn] += 1 并维护精确长度
static void nthroot_top_limbs_(mp_ptr dst, mp_size_t nlimbs, mp_srcptr numa, mp_size_t na, ulong bl)
提取 [numa,na] 的顶 nlimbs 个 limb(左补零语义)
static void nthroot_add_small_(mp_ptr p, mp_size_t n, mp_limb_t c0, mp_limb_t c1)
[p,n] += c0 + c1·B(探针证书的小常数增量)
static mp_size_t nthroot_pow_trunc_(mp_ptr dst, slong *drop, mp_size_t wlimbs, mp_srcptr base, mp_size_t bn, ulong exp, mp_ptr bufa, mp_ptr bufb)
计算窗口截断幂链 [dst] ≈ [base,bn]^exp / 2^(*drop)
static void nthroot_sub_small_(mp_ptr p, mp_size_t n, mp_limb_t c0, mp_limb_t c1)
[p,n] -= c0 + c1·B(探针证书的小常数量减)
static int nthroot_cmp_ext_(mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)
零扩展比较:把 [a,an] 与 [b,bn] 视作等长后比较
static void nthroot_chop_(mp_ptr v, mp_size_t *plen, slong *dr, mp_size_t wlimbs)
截断幂链的逐层截断+归一化(nthroot_pow_trunc_ 的层内步骤)
static mp_size_t nthroot_dec_len_(mp_ptr y, mp_size_t yn)
[y,yn] -= 1 并维护精确长度
mp_size_t lmmp_nthroot_size_(mp_size_t na, ulong root)
计算 lmmp_nthroot_ 所需的 tp 缓冲区长度(任意长度输入入口)
int64_t slong
定义 numth.h:41
mp_size_t lmmp_pow_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算大整数幂 [dst,rn] = [base,n] ^ exp
ulong lmmp_nthroot_ulong_(ulong n, ulong root)
计算 floor(n^(1/root))
void lmmp_nthroot_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, ulong root, mp_ptr tp)
计算算术根 [dsts,nr] = floor([numa,na]^(1/root))(任意 na/任意顶 limb)
uint64_t ulong
定义 numth.h:39
void lmmp_sqrt_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算 [numa,na] * B^(2*nf) 的平方根和余数
定义 sqrt.c:441