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

浏览该文件的源代码.

宏定义

#define Ahr   (dst + lo)
#define Alr   (tp)
#define Alr2   (tp + lo + 1)
#define R   (numa)
#define rk   (numa + 2 * lo)

函数

void lmmp_invsqrt_newton_ (mp_ptr restrict dstis, mp_size_t ns, mp_srcptr restrict numa, mp_size_t na)
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) 的平方根和余数
void lmmp_sqrt_divide_ (mp_ptr restrict dst, mp_ptr restrict numa, mp_size_t ns, mp_ptr restrict tp, int calr)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_sqrt_newton_ (mp_ptr dsts, mp_srcptr numa, mp_size_t na, mp_size_t nf)
 计算近似平方根 [dsts,nf+na/2+1]=[floor|round](sqrt([numa,na]*B^(2*nf)))

宏定义说明

◆ Ahr

#define Ahr   (dst + lo)

◆ Alr

#define Alr   (tp)

◆ Alr2

#define Alr2   (tp + lo + 1)

◆ R

#define R   (numa)

◆ rk

#define rk   (numa + 2 * lo)

函数说明

◆ lmmp_invsqrt_newton_()

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

在文件 sqrt.c 第 242 行定义.

242 {
243 lmmp_param_assert(ns >= 3);
244 lmmp_param_assert(na > 0);
245 lmmp_param_assert(numa != NULL && dstis != NULL);
246 lmmp_param_assert(numa[na - 1] >= LIMB_B_4);
247 mp_size_t nr = ns, namax = na, mn;
248 mp_size_t sizes[LIMB_BITS], *sizp = sizes;
249
250 do {
251 *sizp = nr;
252 nr = (nr >> 1) + 1;
253 ++sizp;
254 } while (nr > 2);
255
256 numa += na;
257 dstis += ns;
258
259 // nr=2
260 // i2=floor((B^5-1)/(1+floor(sqrt(x*B^4))))
261 mp_limb_t numa2[6], sval[3], tp[4];
262 lmmp_zero(numa2, 4);
263 numa2[5] = numa[-1];
264 if (na > 1)
265 numa2[4] = numa[-2];
266 else
267 numa2[4] = 0;
268
269 lmmp_sqrt_divide_(sval, numa2, 3, tp, 0);
270 lmmp_inc(sval);
271
272 for (mp_size_t i = 0; i < 5; ++i) numa2[i] = LIMB_MAX;
273 dstis[0] = lmmp_div_s_(dstis - 2, numa2, 5, sval, 3);
274
275 TEMP_DECL;
276 mp_limb_t alloc_size = na + 2 * ns + 6;
277 mp_ptr restrict xp = TALLOC_TYPE(alloc_size, mp_limb_t);
278 do {
279 na = *--sizp;
280
281 // ar = 0:[numa-nr,nr]
282 // an = 0:[numa-na,na]
283 // ir = 1:[dst-nr,nr] = floor(B^(3*nr/2)/sqrt(ar)) - [0|1]
284 // d = B^(na+2*nr)-an*ir*ir
285 // -4*B^(na+nr) < d < 4*B^(na+nr)
286
287 mp_size_t naz = LMMP_MIN(na, namax);
288 // mp_size_t zeros = na - naz;
289 mp_size_t nsqr, nres = naz + nr + 1;
290 mp_ptr dp = xp + 2 * nr + 1, dip = xp + nr + 1;
291 int cmod; // 1=mod b^mn-1, 0=mod b^(naz+nr+1)
292 int sign; // 1:d<0, 0:d>=0
293 mn = lmmp_mersenne_next_size_(nres);
294
295 // ir^2
296 if (2 * SQRT_NEWTON_MODM_THRESHOLD + mn >= nr * 2 + 1) {
297 cmod = 0;
298 lmmp_sqr_(xp, dstis - nr, nr + 1);
299 nsqr = 2 * nr + 1;
300 } else {
301 cmod = 1;
302 lmmp_sqr_mersenne_(xp, mn, dstis - nr, nr + 1);
303 nsqr = mn;
304 }
305
306 // ir^2*an
307 if (naz < SQRT_NEWTON_MODM_THRESHOLD || naz * 8 < nsqr || mn >= nsqr + naz) {
308 if (cmod == 0)
309 nsqr = LMMP_MIN(nsqr, nres);
310 lmmp_mul_(dp, xp, nsqr, numa - naz, naz);
311 if (cmod == 1) {
312 if (lmmp_add_(dp, dp, mn, dp + mn, naz))
313 lmmp_inc(dp);
314 }
315 } else {
316 if (nsqr > mn) { // cmod==0
317 if (lmmp_add_(xp, xp, mn, xp + mn, nsqr - mn))
318 lmmp_inc(xp);
319 }
320 lmmp_mul_mersenne_(dp, mn, xp, nsqr, numa - naz, naz);
321 cmod = 1;
322 }
323
324 if (cmod == 1) {
325 // naz+nr < mn <= naz+2*nr
326 //[dp,mn] -= B^(naz+2*nr) mod (B^mn-1)
327 dp[mn] = 1;
328 lmmp_dec(dp + naz + 2 * nr - mn);
329 if (dp[mn] == 0)
330 lmmp_dec(dp);
331 }
332
333 if (dp[nres - 1] > 3) { //-d<0
334 if (cmod == 0)
335 lmmp_dec(dp); // for neg to not
336 // else (neg to not) compensate (mod transfer)
337 dp += naz;
338 lmmp_shlnot_(xp, dp + 1, nr, LIMB_BITS - 1);
339 xp[0] ^= dp[0] >> 1;
340 xp[nr] = ~dp[nr] >> 1;
341 sign = 0;
342 } else { //-d>0
343 lmmp_shr_(xp, dp + naz, nr + 1, 1);
344 if ((dp[naz] & 1) || !lmmp_zero_q_(dp, naz))
345 lmmp_inc(xp);
346 sign = 1;
347 }
348
349 lmmp_mul_n_(dip, xp, dstis - nr, nr + 1);
350
351 if (sign) {
352 if (lmmp_zero_q_(dip, 3 * nr - na)) {
353 // a limit for dec
354 dip[2 * nr + 1] = 1;
355 lmmp_dec(dip + 3 * nr - na);
356 }
357 lmmp_not_(dstis - na, dip + 3 * nr - na, na - nr);
358 lmmp_dec_1(dstis - nr, dip[2 * nr] + 1);
359 } else {
360 lmmp_copy(dstis - na, dip + 3 * nr - na, na - nr);
361 lmmp_inc_1(dstis - nr, dip[2 * nr]);
362 }
363
364 nr = na;
365 } while (sizp != sizes);
366 TEMP_FREE;
367}
#define lmmp_mul_n_
#define lmmp_sqr_
#define LIMB_B_4
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 LIMB_MAX
定义 lmmp.h:105
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_shlnot_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移后按位取反操作 [dst,na] = ~([numa,na] << shl),dst的低shl位填充1
mp_limb_t lmmp_div_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法运算
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宏(预期无借位)
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_(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
#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
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
#define xp
#define tp
#define SQRT_NEWTON_MODM_THRESHOLD
void lmmp_sqrt_divide_(mp_ptr dst, mp_ptr numa, mp_size_t ns, mp_ptr tp, int calr)
计算算术平方根 floor(sqrt([numa,2*ns]))
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 LIMB_B_4, LIMB_BITS, LIMB_MAX, lmmp_add_(), lmmp_copy, lmmp_dec, lmmp_dec_1, lmmp_div_s_(), lmmp_inc, lmmp_inc_1, lmmp_invsqrt_newton_(), lmmp_mersenne_next_size_(), LMMP_MIN, lmmp_mul_(), lmmp_mul_mersenne_(), lmmp_mul_n_, lmmp_not_(), lmmp_param_assert, lmmp_shlnot_(), lmmp_shr_(), lmmp_sqr_, lmmp_sqr_mersenne_(), lmmp_sqrt_divide_(), lmmp_zero, lmmp_zero_q_(), restrict, SQRT_NEWTON_MODM_THRESHOLD, TALLOC_TYPE, TEMP_DECL, TEMP_FREE, tp , 以及 xp.

函数调用图:

◆ lmmp_sqrt_()

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

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

在文件 sqrt.c 第 441 行定义.

441 {
442 lmmp_debug_assert(na > 0);
443 lmmp_debug_assert(numa[na - 1] > 0);
444 mp_limb_t high = numa[na - 1];
445 int nsh = lmmp_leading_zeros_(high) / 2;
446 mp_size_t nl = na + 2 * nf;
447 if (nl == 1) {
448 mp_limb_t r;
449 mp_limb_t srt = lmmp_sqrt_1_(&r, high << nsh * 2);
450 srt >>= nsh;
451 dsts[0] = srt;
452 if (dstr)
453 dstr[0] = high - srt * srt;
454 } else if (nl <= 4) {
455 mp_limb_t tmp[4], rr[3], s, t, b;
456 mp_ptr src = (mp_ptr)numa;
457
458 if (nf) {
459 lmmp_zero(tmp, 2 * nf);
460 lmmp_shl_(tmp + 2 * nf, numa, na, 2 * nsh); // nsh=0 时函数内即整段拷贝
461 src = tmp;
462 } else if (nsh) {
463 lmmp_shl_(tmp, numa, na, 2 * nsh);
464 src = tmp;
465 }
466
467 if (nl == 2) {
468 s = lmmp_sqrt_2_(rr, src);
469 if (dstr && nsh) {
470 // rr[0..1] += 2*t*s - t^2
471 t = s & (((mp_limb_t)1 << nsh) - 1);
472 rr[1] += lmmp_addmul_1_(rr, &s, 1, 2 * t);
473 b = lmmp_submul_1_(rr, &t, 1, t);
474 lmmp_sub_1_(rr + 1, rr + 1, 1, b);
475 }
476 dsts[0] = s >> nsh;
477 dsts[1] = 0;
478 if (dstr)
479 lmmp_shr_(dstr, rr, 2, 2 * nsh);
480 } else if (nl == 3) {
481 lmmp_sqrt_3_(dsts, dstr ? rr : NULL, src);
482 if (dstr && nsh) {
483 // rr[0..2] += 2*t*[dsts,2] - t^2
484 t = dsts[0] & (((mp_limb_t)1 << nsh) - 1);
485 rr[2] += lmmp_addmul_1_(rr, dsts, 2, 2 * t);
486 b = lmmp_submul_1_(rr, &t, 1, t);
487 lmmp_sub_1_(rr + 1, rr + 1, 2, b);
488 }
489 if (nsh)
490 lmmp_shr_(dsts, dsts, 2, nsh);
491 if (dstr) {
492 lmmp_shr_(rr, rr, 3, 2 * nsh);
493 lmmp_copy(dstr, rr, 2);
494 }
495 } else {
496 lmmp_sqrt_4_(dsts, dstr ? rr : NULL, src);
497 if (dstr && nsh) {
498 // rr[0..2] += 2*t*[dsts,2] - t^2
499 t = dsts[0] & (((mp_limb_t)1 << nsh) - 1);
500 rr[2] += lmmp_addmul_1_(rr, dsts, 2, 2 * t);
501 b = lmmp_submul_1_(rr, &t, 1, t);
502 lmmp_sub_1_(rr + 1, rr + 1, 2, b);
503 }
504 dsts[2] = 0;
505 if (nsh)
506 lmmp_shr_(dsts, dsts, 2, nsh);
507 if (dstr)
508 lmmp_shr_(dstr, rr, 3, 2 * nsh);
509 }
510 } else if (!dstr && nf >= SQRT_INVNEWTON_K_THRESHOLD * na) {
511 lmmp_sqrt_newton_(dsts, numa, na, nf);
512 } else {
513 TEMP_DECL;
514 mp_limb_t ns = (nl + 1) / 2;
515 mp_ptr restrict numa2 = TALLOC_TYPE(2 * ns, mp_limb_t);
516 mp_ptr restrict tp = TALLOC_TYPE(3 * ns / 2 + 1, mp_limb_t);
517 lmmp_zero(numa2, 2 * nf);
518 lmmp_shl_(numa2 + 2 * ns - na, numa, na, nsh * 2); // nsh=0 时函数内即整段拷贝
519 if (nl & 1) {
520 numa2[2 * nf] = 0;
521 nsh += LIMB_BITS / 2;
522 } else {
523 dsts[ns] = 0;
524 }
525
526 lmmp_sqrt_divide_(dsts, numa2, ns, tp, dstr ? 1: 0);
527 if (nsh) {
528 /*
529 let
530 s = sqrt(A*T^2), r = sqrtrem(A*T^2)
531 such that
532 s = T*a + t, where a = sqrt(A) = s // T
533 then
534 sqrtrem(A) = (r + 2*T*a*t + t^2) // T^2
535 = (r + 2*t*(s-t) + t^2) // T^2
536 = (r + 2*t*s - t^2) // T^2
537 */
538 if (dstr) {
539 mp_limb_t t = dsts[0] & (((mp_limb_t)1 << nsh) - 1);
540 numa2[ns] += lmmp_addmul_1_(numa2, dsts, ns, 2 * t);
541 mp_limb_t b = lmmp_submul_1_(numa2, &t, 1, t);
542 lmmp_sub_1_(numa2 + 1, numa2 + 1, ns, b);
543 }
544 lmmp_shr_(dsts, dsts, ns, nsh);
545 }
546 if (dstr) {
547 nsh *= 2;
548 if (nsh >= LIMB_BITS) {
549 nsh -= LIMB_BITS;
550 ++numa2;
551 } else
552 ++ns;
553 lmmp_shr_(dstr, numa2, ns, nsh); // nsh=0 时函数内即整段拷贝
554 }
555
556 TEMP_FREE;
557 }
558}
#define lmmp_leading_zeros_
#define lmmp_debug_assert(x)
定义 lmmp.h:498
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
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
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
#define t
#define s
#define tmp
#define SQRT_INVNEWTON_K_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_sqrt_3_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,3]))
void lmmp_sqrt_newton_(mp_ptr dsts, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算近似平方根 [dsts,nf+na/2+1]=[floor|round](sqrt([numa,na]*B^(2*nf)))
定义 sqrt.c:392
mp_limb_t lmmp_sqrt_1_(mp_ptr dstr, mp_limb_t x)
计算算术平方根 floor(sqrt(x))
mp_limb_t lmmp_sqrt_2_(mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,2]))
void lmmp_sqrt_4_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,4]))

引用了 LIMB_BITS, lmmp_addmul_1_(), lmmp_copy, lmmp_debug_assert, lmmp_leading_zeros_, lmmp_shl_(), lmmp_shr_(), lmmp_sqrt_(), lmmp_sqrt_1_(), lmmp_sqrt_2_(), lmmp_sqrt_3_(), lmmp_sqrt_4_(), lmmp_sqrt_divide_(), lmmp_sqrt_newton_(), lmmp_sub_1_(), lmmp_submul_1_(), lmmp_zero, restrict, s, SQRT_INVNEWTON_K_THRESHOLD, t, TALLOC_TYPE, TEMP_DECL, TEMP_FREE, tmp , 以及 tp.

被这些函数引用 bench_sqrt(), lmmp_invsqrt_newton_(), lmmp_nthroot_(), lmmp_perfsqr_(), lmmp_sqrt_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

◆ lmmp_sqrt_divide_()

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

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

在文件 sqrt.c 第 62 行定义.

62 {
63 lmmp_param_assert(ns > 0);
64 lmmp_param_assert(numa != NULL && dst != NULL && tp != NULL);
65 lmmp_param_assert(numa[2 * ns - 1] >= LIMB_B_4);
66 if (ns == 1) {
67 dst[0] = lmmp_sqrt_2_(numa, numa);
68 } else if (ns == 2) {
69 lmmp_sqrt_4_(dst, calr ? numa : NULL, numa);
70 } else {
71 mp_size_t lo = ns / 2, hi = ns - lo;
72#define Ahr (dst + lo) // [dst+lo, hi]
73#define rk (numa + 2 * lo) // [numa+2*lo, hi+1]
74#define R (numa) // [numa, ns+1]
75#define Alr (tp) // [tp, lo+1]
76#define Alr2 (tp + lo + 1) // [tp + lo+1, 2*lo]
77
78 lmmp_sqrt_divide_(Ahr, rk, hi, tp, 1);
79
80 /*
81 A / (2*x) = A / 2 / x
82 A % (2*x) = 2 * (A / 2 % x) + A % 2
83 */
84 mp_limb_t r = lmmp_shr_(rk - lo, rk - lo, ns + 1, 1);
85 mp_limb_t qh = lmmp_div_s_(Alr, rk - lo, ns + 1, Ahr, hi);
86 lmmp_debug_assert(qh == 0);
87 (rk - lo)[hi] = lmmp_shl_c_(rk - lo, rk - lo, hi, 1, r >> (LIMB_BITS - 1));
88 /*
89 我们根据 sqrt(A/B^2) == floor(sqrt(A)/B) 可以知道,如果Alr正确结果
90 必定被限制在B^lo以内,其至多高估1,因此Alr的最高位必定为0或1,而为1时,
91 即代表此时结果已经高估。
92 */
93 mp_limb_t adj = Alr[lo];
94 lmmp_debug_assert(adj == 0 || adj == 1);
95 if (adj > 0) {
96 lmmp_debug_assert(Alr[0] == 0);
97 lmmp_fill_n(dst, lo, LIMB_MAX);
98 if (calr == 0) return;
99 /*
100 x_k+1 = Ahr * B^lo + Alr
101 = Ahr * B^lo + B^lo - 1
102
103 r_k+1 = R - (B^lo-1)^2 + 2*Alr*Ahr*B^lo - 2*(Alr-adj)*Ahr*B^lo
104 = R - B^(2*lo) + 2*B^lo - 1 + 2*adj*Ahr*B^lo
105 */
106
107 // + 2*adj*Ahr*B^lo
108 mp_limb_t cy = lmmp_addmul_1_(R + lo, Ahr, hi, 2 * adj);
109 (R + ns)[0] += cy;
110 r = (R + ns)[0] < cy;
111
112 // - 1
113 r -= lmmp_sub_1_(R, R, ns + 1, 1);
114
115 // + 2*B^lo
116 r += lmmp_add_1_(R + lo, R + lo, hi + 1, 2);
117
118 // - B^(2*lo)
119 r -= lmmp_sub_1_(R + 2 * lo, R + 2 * lo, hi + 1 - lo, 1);
120 lmmp_debug_assert(r == 0);
121 } else if (calr == 0) {
122 /*
123 calr=0 时无需维护余数,计算 Alr^2 再相减仅仅是为了判定
124 Alr 是否高估 1(即 R 与 Alr^2 的大小),此判定无需完整平方:
125
126 Alr = H*B^(lo-2) + L, H = [Alr+lo-2,2], L < B^(lo-2)
127 Alr^2 = H^2*B^(2*lo-4) + E
128 E = 2*H*L*B^(lo-2) + L^2 < 3*B^(2*lo-2)
129
130 即 Alr^2 的最高两个 limb 必落在 [H^2 的最高两个 limb, +3] 内,
131 于是仅需比较 R 与 H^2 的最高两个 limb(注意 adj=0 时 Alr < B^lo):
132 R 高于 B^(2*lo) 的 limb 非零 => R > Alr^2
133 [R] > [H^2]+4 (最高两 limb 意义下) => R > Alr^2
134 [R] < [H^2] (最高两 limb 意义下) => R < Alr^2
135 其余情况(最高两 limb 落入宽度 4 的窄带,如完全平方数
136 等构造输入)回退到下方的精确路径,保证正确性。
137 */
138 if (lo >= 4) {
139 mp_size_t i = ns;
140 while (i >= 2 * lo && R[i] == 0) --i;
141 if (i >= 2 * lo) {
142 // R >= B^(2*lo) > Alr^2,Alr 未高估
143 lmmp_copy(dst, Alr, lo);
144 return;
145 }
146 lmmp_sqr_hard_2_(Alr2, Alr + lo - 2); // [Alr2,4] = H^2
147 mp_limb_t h2h = Alr2[3], h2l = Alr2[2]; // H^2 的最高两 limb
148 mp_limb_t rh = R[2 * lo - 1], rl = R[2 * lo - 2];
149 mp_limb_t wl = h2l + 4; // [wh,wl] = [H^2]+4
150 mp_limb_t carry = wl < 4;
151 mp_limb_t wh = h2h + carry;
152 carry = wh < carry;
153 if ((!carry) && (rh > wh || (rh == wh && rl >= wl))) {
154 // [R] > [H^2]+4
155 lmmp_copy(dst, Alr, lo);
156 return;
157 }
158 if (rh < h2h || (rh == h2h && rl < h2l)) {
159 // R < Alr^2,Alr 高估 1
160 lmmp_dec(Alr);
161 lmmp_copy(dst, Alr, lo);
162 return;
163 }
164 }
165 // 窄带或小尺寸回退:精确判定
166 lmmp_sqr_(Alr2, Alr, lo);
167 if (lmmp_sub_(R, R, ns + 1, Alr2, 2 * lo))
168 lmmp_dec(Alr);
169 lmmp_copy(dst, Alr, lo);
170 } else {
171 lmmp_sqr_(Alr2, Alr, lo);
172 mp_limb_t b = lmmp_sub_(R, R, ns + 1, Alr2, 2 * lo);
173 if (b > 0) {
174 // + 2*Ahr*B^lo
175 mp_limb_t cy = lmmp_addshl1_n_(R + lo, R + lo, Ahr, hi);
176 (R + lo)[hi] += cy;
177 b -= (R + lo)[hi] < cy;
178
179 // + 2*Alr
180 cy = lmmp_addshl1_n_(R, R, Alr, lo);
181 b -= lmmp_add_1_(R + lo, R + lo, hi + 1, cy);
182
183 // - 1
184 b += lmmp_sub_1_(R, R, ns + 1, 1);
185
186 lmmp_debug_assert(b == 0);
187 lmmp_dec(Alr);
188 }
189 lmmp_copy(dst, Alr, lo);
190 }
191 }
192#undef Ahr
193#undef rk
194#undef R
195#undef Alr
196#undef Alr2
197}
#define Ahr
#define rk
#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
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_shl_c_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl, mp_limb_t c)
带进位的左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充c的低shl位
定义 shl.c:39
mp_limb_t lmmp_addshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
定义 shl.c:53
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]
void lmmp_sqr_hard_2_(mp_ptr dst, mp_srcptr numa)
#define lo

引用了 Ahr, Alr, Alr2, LIMB_B_4, LIMB_BITS, LIMB_MAX, lmmp_add_1_(), lmmp_addmul_1_(), lmmp_addshl1_n_(), lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_div_s_(), lmmp_fill_n(), lmmp_param_assert, lmmp_shl_c_(), lmmp_shr_(), lmmp_sqr_, lmmp_sqr_hard_2_(), lmmp_sqrt_2_(), lmmp_sqrt_4_(), lmmp_sqrt_divide_(), lmmp_sub_(), lmmp_sub_1_(), lo, R, restrict, rk , 以及 tp.

函数调用图:

◆ lmmp_sqrt_newton_()

void lmmp_sqrt_newton_ ( mp_ptr dsts,
mp_srcptr numa,
mp_size_t na,
mp_size_t nf )

计算近似平方根 [dsts,nf+na/2+1]=[floor|round](sqrt([numa,na]*B^(2*nf)))

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

在文件 sqrt.c 第 392 行定义.

392 {
393 lmmp_param_assert(na > 0);
394 lmmp_param_assert(nf >= 2);
395 lmmp_param_assert(numa != NULL && dsts != NULL);
396 mp_limb_t high = numa[na - 1];
397 int nsh = lmmp_leading_zeros_(high) / 2;
398 mp_size_t ns = na / 2 + 1 + nf;
399
400 TEMP_DECL;
401 mp_limb_t alloc_size = (nsh ? na : 0) + ns + 1;
402 mp_ptr tp = TALLOC_TYPE(alloc_size, mp_limb_t), numa2;
403 if (nsh) {
404 numa2 = tp;
405 lmmp_shl_(numa2, numa, na, nsh * 2);
406 tp += na;
407 } else
408 numa2 = (mp_ptr)numa;
409
410 lmmp_invsqrt_newton_(tp, ns, numa2, na);
411
412 mp_ptr restrict msqr = TALLOC_TYPE(na + ns + 1, mp_limb_t);
413
414 if (ns + 1 > na)
415 lmmp_mul_(msqr, tp, ns + 1, numa2, na);
416 else
417 lmmp_mul_(msqr, numa2, na, tp, ns + 1);
418
419 mp_limb_t cceil;
420 if (na & 1) {
421 nsh += LIMB_BITS / 2;
422 lmmp_shr_(dsts, msqr + na, ns, nsh);
423 cceil = msqr[na] >> (nsh - 1);
424 } else {
425 if (nsh) {
426 lmmp_shr_(dsts, msqr + na + 1, ns - 1, nsh);
427 cceil = msqr[na + 1] >> (nsh - 1);
428 } else {
429 lmmp_copy(dsts, msqr + na + 1, ns - 1);
430 cceil = msqr[na] >> (LIMB_BITS - 1);
431 }
432 dsts[ns - 1] = 0;
433 }
434
435 if (cceil & 1)
436 lmmp_inc(dsts);
437
438 TEMP_FREE;
439}
void lmmp_invsqrt_newton_(mp_ptr dstis, mp_size_t ns, mp_srcptr numa, mp_size_t na)
计算逆平方根的定点下近似:记 I=floor(sqrt(B^(2*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,...

引用了 LIMB_BITS, lmmp_copy, lmmp_inc, lmmp_invsqrt_newton_(), lmmp_leading_zeros_, lmmp_mul_(), lmmp_param_assert, lmmp_shl_(), lmmp_shr_(), lmmp_sqrt_newton_(), restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

被这些函数引用 lmmp_invsqrt_newton_(), lmmp_sqrt_(), lmmp_sqrt_newton_() , 以及 TEST_CASE().

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