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

浏览该文件的源代码.

函数

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_3_ (mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
 计算算术平方根 floor(sqrt([numa,3]))
void lmmp_sqrt_4_ (mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
 计算算术平方根 floor(sqrt([numa,4]))
ulong lmmp_sqrt_ulong_ (ulong a)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数说明

◆ lmmp_sqrt_1_()

mp_limb_t lmmp_sqrt_1_ ( mp_ptr dstr,
mp_limb_t x )

计算算术平方根 floor(sqrt(x))

参数
dstr余数指针(1个limb)
x被开方数
警告
x>=B/4, dstr!=NULL
注解
[dstr,1]=sqrtrem(x), return floor(sqrt(x))
返回
floor(sqrt(x))

在文件 sqrt_1.c 第 42 行定义.

42 {
45 *dstr = x - s * s;
46 return s;
47}
#define LIMB_B_4
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define s
ulong lmmp_sqrt_ulong_(ulong a)
计算算术平方根 floor(sqrt(a))

引用了 LIMB_B_4, lmmp_param_assert, lmmp_sqrt_1_(), lmmp_sqrt_ulong_() , 以及 s.

被这些函数引用 lmmp_remove_(), lmmp_sqrt_(), lmmp_sqrt_1_(), lmmp_sqrt_2_() , 以及 TEST_CASE().

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

◆ lmmp_sqrt_2_()

mp_limb_t lmmp_sqrt_2_ ( mp_ptr dstr,
mp_srcptr numa )

计算算术平方根 floor(sqrt([numa,2]))

参数
dstr余数指针(2个limb)
numa被开方数指针
警告
numa[1]>=B/4, dstr!=NULL, numa!=NULL, eqsep(dstr,numa)
注解
return: floor(sqrt([numa,2])), [dstr,2]=remainder
返回
floor(sqrt([numa,2]))

在文件 sqrt_1.c 第 49 行定义.

49 {
50 lmmp_param_assert(numa[1] >= LIMB_B_4);
51 mp_limb_t rl, s, q, al, u;
52 mp_slimb_t rh;
53
54 s = lmmp_sqrt_1_(&rl, numa[1]);
55 al = numa[0];
56
57 //(r:alh)/2
58 rl = rl << 31 | al >> 33;
59 q = rl / s;
60 q -= q >> 32;
61
62 u = rl - s * q;
63 s = s << 32 | q;
64 rh = u >> 31;
65 rl = (u << 33) | (al & (((mp_limb_t)1 << 33) - 1));
66
67 q *= q;
68 rh -= rl < q;
69 rl -= q;
70 if (rh < 0) {
71 rl += s;
72 rh += rl < s;
73 --s;
74 rl += s;
75 rh += rl < s;
76 }
77
78 dstr[0] = rl;
79 dstr[1] = rh;
80 return s;
81}
int64_t mp_slimb_t
定义 lmmp.h:94
mp_limb_t lmmp_sqrt_1_(mp_ptr dstr, mp_limb_t x)
计算算术平方根 floor(sqrt(x))

引用了 LIMB_B_4, lmmp_param_assert, lmmp_sqrt_1_(), lmmp_sqrt_2_() , 以及 s.

被这些函数引用 is_square_2(), lmmp_remove_(), lmmp_sqrt_(), lmmp_sqrt_2_(), lmmp_sqrt_3_(), lmmp_sqrt_4_(), lmmp_sqrt_divide_() , 以及 TEST_CASE().

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

◆ lmmp_sqrt_3_()

void lmmp_sqrt_3_ ( mp_ptr dsts,
mp_ptr dstr,
mp_srcptr numa )

计算算术平方根 floor(sqrt([numa,3]))

参数
dsts结果指针(2个limb)
dstr余数指针(3个limb,最高位补零),传 NULL 表示不计算余数
numa被开方数指针
警告
numa[2]>=B/4, dsts!=NULL, numa!=NULL, eqsep(dsts,numa), eqsep(dstr,numa)
注解
[dstr,3] = [numa,3] - [dsts,2]^2 <= 2*[dsts,2]

在文件 sqrt_1.c 第 98 行定义.

98 {
99 lmmp_param_assert(numa != NULL && dsts != NULL);
100 lmmp_param_assert(numa[2] >= LIMB_B_4);
101 mp_limb_t a0 = numa[0];
102 mp_limb_t rh[2], n1, n0, q, u, uc, s1, s0, r1, r0, p[2], neg;
103
104 // s' = sqrt([a2,a1]) >= 2^63,rh = [a2,a1] - s'^2 <= 2s'
105 mp_limb_t sh = lmmp_sqrt_2_(rh, numa + 1);
106
107 // N = rh*2^32 + (a0>>32) < 2^34*s',N/s' < 2^34,n1 = N>>64 < s'
108 n1 = (rh[1] << 32) | (rh[0] >> 32);
109 n0 = (rh[0] << 32) | (a0 >> 32);
110 mp_limb_t qh = _udiv128by64to64_(n1, n0, sh, &u);
111 // q = N div 2s',(uc,u) = N mod 2s'
112 q = qh >> 1;
113 _add_ssaaaa(uc, u, 0, u, 0, sh & (-(qh & 1)));
114
115 // s = s'*2^32 + q
116 _add_ssaaaa(s1, s0, sh >> 32, sh << 32, 0, q);
117
118 // r = u*2^32 + (a0 & M32) - q^2,|r| < 2^98(双 limb 有符号)
119 lmmp_mullh_(q, q, p);
120 _sub_ddmmss(r1, r0, (uc << 32) | (u >> 32), (u << 32) | (a0 & (((mp_limb_t)1 << 32) - 1)),
121 p[1], p[0]);
122
123 // r < 0(概率约 1/4):s -= 1,r += 2s + 1,(s0<<1)|1 = 2*s0+1 无进位
124 neg = -(r1 >> (LIMB_BITS - 1));
125 _sub_ddmmss(s1, s0, s1, s0, 0, neg & 1);
126 _add_ssaaaa(r1, r0, r1, r0, neg & ((s1 << 1) | (s0 >> (LIMB_BITS - 1))),
127 neg & ((s0 << 1) | 1));
128
129 dsts[0] = s0;
130 dsts[1] = s1;
131 if (dstr != NULL) {
132 dstr[0] = r0;
133 dstr[1] = r1;
134 dstr[2] = 0;
135 }
136}
#define lmmp_mullh_
#define LIMB_BITS
定义 lmmp.h:102
#define _sub_ddmmss(sh, sl, ah, al, bh, bl)
static uint64_t _udiv128by64to64_(uint64_t numhi, uint64_t numlo, uint64_t den, uint64_t *r)
#define _add_ssaaaa(sh, sl, ah, al, bh, bl)
#define a0
#define r1
#define r0
mp_limb_t lmmp_sqrt_2_(mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,2]))

引用了 _add_ssaaaa, _sub_ddmmss, _udiv128by64to64_(), a0, LIMB_B_4, LIMB_BITS, lmmp_mullh_, lmmp_param_assert, lmmp_sqrt_2_(), lmmp_sqrt_3_(), r0 , 以及 r1.

被这些函数引用 lmmp_remove_(), lmmp_sqrt_(), lmmp_sqrt_3_() , 以及 TEST_CASE().

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

◆ lmmp_sqrt_4_()

void lmmp_sqrt_4_ ( mp_ptr dsts,
mp_ptr dstr,
mp_srcptr numa )

计算算术平方根 floor(sqrt([numa,4]))

参数
dsts结果指针(2个limb)
dstr余数指针(3个limb),传 NULL 表示不计算余数
numa被开方数指针
警告
numa[3]>=B/4, dsts!=NULL, numa!=NULL, eqsep(dsts,numa), eqsep(dstr,numa)
注解
[dstr,3] = [numa,4] - [dsts,2]^2 <= 2*[dsts,2]

在文件 sqrt_1.c 第 138 行定义.

138 {
139 lmmp_param_assert(numa != NULL && dsts != NULL);
140 lmmp_param_assert(numa[3] >= LIMB_B_4);
141 mp_limb_t x0 = numa[0], x1 = numa[1];
142 mp_limb_t rh[2], qh, ql, u, uc, t, s1, s0, r2, r1, r0, p[2], b, neg;
143
144 // s' = sqrt([x3,x2]) >= 2^63,rh = [x3,x2] - s'^2 <= 2s'
145 mp_limb_t sh = lmmp_sqrt_2_(rh, numa + 2);
146
147 // N = rh*B + x1 除以 s':先把顶 limb 归约到 s' 以下(至多两次),商计入学 qh
148 qh = rh[1];
149 rh[0] -= sh & (-(mp_limb_t)(rh[1] != 0));
150 t = (rh[0] >= sh);
151 rh[0] -= sh & (-(mp_limb_t)t);
152 qh += t;
153 ql = _udiv128by64to64_(rh[0], x1, sh, &u);
154
155 // N div s' = qh*B + ql = 2*s_low + (ql&1),N mod 2s' = u + (ql&1)*s'
156 s0 = (ql >> 1) | (qh << (LIMB_BITS - 1));
157 qh >>= 1;
158 _add_ssaaaa(uc, u, 0, u, 0, sh & (-(ql & 1)));
159
160 // r = (uc,u)*B + x0 - s_low^2,s_low = qh*B + s0 <= B(qh=1 时 s0=0)
161 lmmp_mullh_(s0, s0, p);
162 _sub_ddmmss(r1, r0, u, x0, p[1], p[0]);
163 b = (u < p[1]) | ((u == p[1]) & (x0 < p[0]));
164 r2 = uc - qh - b;
165
166 // s = s'*B + s_low;sh = B-1 且 s_low = B 时 s1 回绕为 0,r < 0 修正时解开
167 s1 = sh + qh;
168 neg = -(r2 >> (LIMB_BITS - 1));
169 _sub_ddmmss(s1, s0, s1, s0, 0, neg & 1);
170 // r += 2s + 1:低位 (s0<<1)|1 = 2*s0+1 无进位,进位链并入 r2
171 {
172 mp_limb_t al = neg & ((s0 << 1) | 1);
173 mp_limb_t ah = neg & ((s1 << 1) | (s0 >> (LIMB_BITS - 1)));
174 __uint128_t tc;
175
176 tc = (__uint128_t)r0 + al;
177 r0 = (mp_limb_t)tc;
178 tc = (__uint128_t)r1 + ah + (mp_limb_t)(tc >> 64);
179 r1 = (mp_limb_t)tc;
180 r2 += (neg & (s1 >> (LIMB_BITS - 1))) + (mp_limb_t)(tc >> 64);
181 }
182
183 dsts[0] = s0;
184 dsts[1] = s1;
185 if (dstr != NULL) {
186 dstr[0] = r0;
187 dstr[1] = r1;
188 dstr[2] = r2;
189 }
190}
#define r2
#define t

引用了 _add_ssaaaa, _sub_ddmmss, _udiv128by64to64_(), LIMB_B_4, LIMB_BITS, lmmp_mullh_, lmmp_param_assert, lmmp_sqrt_2_(), lmmp_sqrt_4_(), r0, r1, r2 , 以及 t.

被这些函数引用 lmmp_remove_(), lmmp_sqrt_(), lmmp_sqrt_4_(), lmmp_sqrt_divide_() , 以及 TEST_CASE().

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

◆ lmmp_sqrt_ulong_()

ulong lmmp_sqrt_ulong_ ( ulong a)

Copyright (C) 2026 HJimmyK (Jericho Knox)

计算算术平方根 floor(sqrt(a))

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

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
a被开方数
返回
floor(sqrt(a))

在文件 sqrt_1.c 第 31 行定义.

31 {
32 ulong is;
33
34 is = (ulong)sqrt((double)a);
35
36 is -= (is * is > a);
37 if (is == (1ULL << 32))
38 is--;
39 return is;
40}
uint64_t ulong
定义 numth.h:39

引用了 lmmp_sqrt_ulong_().

被这些函数引用 lmmp_nthroot_ulong_(), lmmp_remove_(), lmmp_sqrt_1_(), lmmp_sqrt_ulong_(), TEST_CASE() , 以及 TEST_CASE().

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