LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
sqrt_1.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 <math.h>
24
25
#include "
impl/inlines.h
"
26
#include "
impl/longlong.h
"
27
#include "mparam.h"
28
#include "
lmmp/numth.h
"
29
30
31
ulong
lmmp_sqrt_ulong_
(
ulong
a) {
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
}
41
42
mp_limb_t
lmmp_sqrt_1_
(
mp_ptr
dstr,
mp_limb_t
x) {
43
lmmp_param_assert
(x >=
LIMB_B_4
);
44
mp_limb_t
s
=
lmmp_sqrt_ulong_
(x);
45
*dstr = x -
s
*
s
;
46
return
s
;
47
}
48
49
mp_limb_t
lmmp_sqrt_2_
(
mp_ptr
dstr,
mp_srcptr
numa) {
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
}
82
83
/*
84
以 4 limb 为例,x = x3*B^3 + x2*B^2 + x1*B + x0(x3 >= B/4):
85
86
(s', rh) = sqrtrem(x3*B + x2) 2 limb 根,rh <= 2s'
87
N = rh*B + x1
88
(Q2, u) = divrem(N, s') 顶 limb 先归约至 s' 以下
89
s_low = Q2 >> 1 s = s'*B + s_low
90
r = (N mod 2s')*B + x0 - s_low^2
91
92
r < 0 时 s -= 1、r += 2s+1 一步修正(Karatsuba 平方根保证 Q2 至多
93
高估 2,修正至多一步);修正后 r = x - s^2 <= 2s 恒成立。
94
3 limb 输入采用 beta = 2^32 的非均衡分割(s = s'*2^32 + q,商 33
95
bit),其余同理。
96
*/
97
98
void
lmmp_sqrt_3_
(
mp_ptr
dsts,
mp_ptr
dstr,
mp_srcptr
numa) {
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
}
137
138
void
lmmp_sqrt_4_
(
mp_ptr
dsts,
mp_ptr
dstr,
mp_srcptr
numa) {
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
}
inlines.h
lmmp_mullh_
#define lmmp_mullh_
定义
inlines.h:166
LIMB_B_4
#define LIMB_B_4
定义
mparam.h:42
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_slimb_t
int64_t mp_slimb_t
定义
lmmp.h:94
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
LIMB_BITS
#define LIMB_BITS
定义
lmmp.h:102
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
longlong.h
_sub_ddmmss
#define _sub_ddmmss(sh, sl, ah, al, bh, bl)
定义
longlong.h:503
_udiv128by64to64_
static uint64_t _udiv128by64to64_(uint64_t numhi, uint64_t numlo, uint64_t den, uint64_t *r)
定义
longlong.h:386
_add_ssaaaa
#define _add_ssaaaa(sh, sl, ah, al, bh, bl)
定义
longlong.h:495
a0
#define a0
r2
#define r2
r1
#define r1
r0
#define r0
t
#define t
s
#define s
numth.h
lmmp_sqrt_3_
void lmmp_sqrt_3_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,3]))
定义
sqrt_1.c:98
lmmp_sqrt_1_
mp_limb_t lmmp_sqrt_1_(mp_ptr dstr, mp_limb_t x)
计算算术平方根 floor(sqrt(x))
定义
sqrt_1.c:42
lmmp_sqrt_ulong_
ulong lmmp_sqrt_ulong_(ulong a)
计算算术平方根 floor(sqrt(a))
定义
sqrt_1.c:31
lmmp_sqrt_2_
mp_limb_t lmmp_sqrt_2_(mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,2]))
定义
sqrt_1.c:49
lmmp_sqrt_4_
void lmmp_sqrt_4_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,4]))
定义
sqrt_1.c:138
ulong
uint64_t ulong
定义
numth.h:39
src
lmmp
numth
sqrt_1.c
生成于
, 为 LMMP使用
1.18.0