LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
perfsqr.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/tmp_alloc.h
"
24
#include "
lmmp/numth.h
"
25
#include "
lmmp/lmmpn.h
"
26
27
28
#define MASK48 (0xFFFFFFFFFFFF)
29
30
#define B1 (LIMB_BITS / 4)
31
#define B2 (B1 * 2)
32
#define B3 (B1 * 3)
33
34
#define M1 ((1ULL << B1) - 1)
35
#define M2 ((1ULL << B2) - 1)
36
#define M3 ((1ULL << B3) - 1)
37
38
#define LOW0(n) ((n) & M3)
39
#define HIGH0(n) ((n) >> B3)
40
41
#define LOW1(n) (((n) & M2) << B1)
42
#define HIGH1(n) ((n) >> B2)
43
44
#define LOW2(n) (((n) & M1) << B2)
45
#define HIGH2(n) ((n) >> B1)
46
47
#define PARTS0(n) (LOW0(n) + HIGH0(n))
48
#define PARTS1(n) (LOW1(n) + HIGH1(n))
49
#define PARTS2(n) (LOW2(n) + HIGH2(n))
50
51
// a += val, if carry, add 1 to c
52
#define ADD(c, a, val) \
53
do { \
54
mp_limb_t new_a = (a) + (val); \
55
(c) += new_a < (a); \
56
(a) = new_a; \
57
} while (0)
58
59
mp_limb_t
lmmp_mod_2p48sub1_
(
mp_srcptr
p,
mp_size_t
n
) {
60
lmmp_param_assert
(
n
> 0 && p != NULL);
61
62
mp_limb_t
c0
= 0,
c1
= 0, c2 = 0;
63
mp_limb_t
a0
= 0,
a1
= 0,
a2
= 0;
64
65
while
(
n
>= 3) {
66
ADD
(
c0
,
a0
, p[0]);
67
ADD
(
c1
,
a1
, p[1]);
68
ADD
(c2,
a2
, p[2]);
69
p += 3;
70
n
-= 3;
71
}
72
if
(
n
== 2) {
73
ADD
(
c0
,
a0
, p[0]);
74
ADD
(
c1
,
a1
, p[1]);
75
}
else
if
(
n
== 1) {
76
ADD
(
c0
,
a0
, p[0]);
77
}
78
79
mp_limb_t
res =
PARTS0
(
a0
) +
PARTS1
(
a1
) +
PARTS2
(
a2
)
80
+
PARTS1
(
c0
) +
PARTS2
(
c1
) +
PARTS0
(c2);
81
82
res = (res &
MASK48
) + (res >>
B3
);
83
if
(res >=
MASK48
)
84
res -=
MASK48
;
85
return
res;
86
}
87
88
#undef B1
89
#undef B2
90
#undef B3
91
#undef M1
92
#undef M2
93
#undef M3
94
#undef LOW0
95
#undef HIGH0
96
#undef LOW1
97
#undef HIGH1
98
#undef LOW2
99
#undef HIGH2
100
#undef PARTS0
101
#undef PARTS1
102
#undef PARTS2
103
#undef ADD
104
105
/*
106
我们选择2^48-1作为模数只是因为其计算可以非常迅速,并且拥有一组非常好的因数分解
107
2^48-1 = 9 * 5 * 7 * 13 * 17 * 97 * 241 * 257 * 673
108
而下面的每个函数,都直接硬编码了完全平方数才可能具有的模数。当然也不需要担心这
109
么多的判断会导致分支预测效率很低,因为编译器通常可以很好的将其优化为位图,并且
110
由于位图很小,可能直接变成立即数。对于更长的数,我们手动计算了位图,直接计算地址,
111
取出对应的bit,可以避免编译器将其优化为多分支结构。
112
113
只有完全平方数以及部分非完全平方数可以通过,大部分非完全平方数都无法通过。
114
在模2^48-1下,完全平方数可能的结果仅占到大约 0.277%,
115
在模256下,完全平方数可能的结果仅占到大约 17.2%
116
*/
117
118
static
inline
bool
is_perfsqr_p9
(
uchar
r) {
119
return
r == 0 || r == 1 || r == 4 || r == 7;
120
}
121
122
static
inline
bool
is_perfsqr_p5
(
uchar
r) {
123
return
r == 0 || r == 1 || r == 4;
124
}
125
126
static
inline
bool
is_perfsqr_p7
(
uchar
r) {
127
return
r == 0 || r == 1 || r == 2 || r == 4;
128
}
129
130
static
inline
bool
is_perfsqr_p13
(
uchar
r) {
131
return
r == 0 || r == 1 || r == 3 || r == 4 || r == 9 || r == 10 || r == 12;
132
}
133
134
static
inline
bool
is_perfsqr_p17
(
uchar
r) {
135
return
r == 0 || r == 1 || r == 2 || r == 4 || r == 8 || r == 9 || r == 13 || r == 15 || r == 16;
136
}
137
138
static
inline
bool
is_perfsqr_p97
(
uchar
r) {
139
return
r == 0 || r == 1 || r == 2 || r == 3 || r == 4 || r == 6 || r == 8 || r == 9 || r == 11 || r == 12 ||
140
r == 16 || r == 18 || r == 22 || r == 24 || r == 25 || r == 27 || r == 31 || r == 32 || r == 33 || r == 35 ||
141
r == 36 || r == 43 || r == 44 || r == 47 || r == 48 || r == 49 || r == 50 || r == 53 || r == 54 || r == 61 ||
142
r == 62 || r == 64 || r == 65 || r == 66 || r == 70 || r == 72 || r == 73 || r == 75 || r == 79 || r == 81 ||
143
r == 85 || r == 86 || r == 88 || r == 89 || r == 91 || r == 93 || r == 94 || r == 95 || r == 96;
144
}
145
146
static
inline
bool
is_perfsqr_p241
(
ushort
r) {
147
static
const
uint64_t p241[] = {0x3C67A3116B15977F, 0x2FD21C174C8FA909, 0x98F24257C4CBA0E1, 0x0001FBA6A35A2317};
148
ushort
elem = r / 64;
149
lmmp_param_assert
(elem < 4);
150
ushort
bit = r % 64;
151
return
(p241[elem] >> bit) & 1ULL;
152
}
153
154
static
inline
bool
is_perfsqr_p257
(
ushort
r) {
155
static
const
uint64_t p257[] = {0x7E16541DE6E7AB17, 0x1F76811C93128359, 0x6B052324E205BBE3, 0xA3579D9EE0A9A1FA,
156
0x0000000000000001};
157
ushort
elem = r / 64;
158
lmmp_param_assert
(elem < 5);
159
ushort
bit = r % 64;
160
return
(p257[elem] >> bit) & 1ULL;
161
}
162
163
static
inline
bool
is_perfsqr_p673
(
ushort
r) {
164
static
const
uint64_t p673[] = {0x85F744B13FA573DF, 0xC231D5979ABA4F21, 0xE944C76E98DD0C01, 0xD20E0F2BD993E915,
165
0x616259FB225208AB, 0x7E691A18F8B7B47C, 0x53C1C12F54412913, 0xDB8C8A5EA25F266F,
166
0xA6AE310E00C2EC65, 0x348BBE8613C97567, 0x00000001EF3A97F2};
167
ushort
elem = r / 64;
168
lmmp_param_assert
(elem < 11);
169
ushort
bit = r % 64;
170
return
(p673[elem] >> bit) & 1ULL;
171
}
172
173
static
inline
bool
is_perfsqr_p256
(
uchar
r) {
174
static
const
uint64_t p256[] = {0x0202021202030213, 0x0202021202020213, 0x0202021202030212, 0x0202021202020212};
175
ushort
elem = r / 64;
176
lmmp_param_assert
(elem < 4);
177
ushort
bit = r % 64;
178
return
(p256[elem] >> bit) & 1ULL;
179
}
180
181
bool
lmmp_perfsqr_filter_1_
(
mp_limb_t
p) {
182
lmmp_param_assert
(p > 0);
183
mp_limb_t
a = p % 256;
184
if
(!
is_perfsqr_p256
(a))
return
false
;
185
p = p %
MASK48
;
186
return
is_perfsqr_p9
(p % 9) &&
is_perfsqr_p5
(p % 5) &&
is_perfsqr_p7
(p % 7) &&
is_perfsqr_p13
(p % 13) &&
187
is_perfsqr_p17
(p % 17) &&
is_perfsqr_p97
(p % 97) &&
is_perfsqr_p241
(p % 241) &&
188
is_perfsqr_p257
(p % 257) &&
is_perfsqr_p673
(p % 673);
189
}
190
191
bool
lmmp_perfsqr_filter_
(
mp_srcptr
p,
mp_size_t
n
) {
192
lmmp_param_assert
(
n
> 0 && p != NULL);
193
lmmp_param_assert
(p[
n
- 1] > 0);
194
if
(
n
== 1)
return
lmmp_perfsqr_filter_1_
(p[0]);
195
mp_limb_t
a = p[0] % 256;
196
if
(!
is_perfsqr_p256
(a))
197
return
false
;
198
mp_limb_t
r =
lmmp_mod_2p48sub1_
(p,
n
);
199
return
is_perfsqr_p9
(r % 9) &&
is_perfsqr_p5
(r % 5) &&
is_perfsqr_p7
(r % 7) &&
is_perfsqr_p13
(r % 13) &&
200
is_perfsqr_p17
(r % 17) &&
is_perfsqr_p97
(r % 97) &&
is_perfsqr_p241
(r % 241) &&
201
is_perfsqr_p257
(r % 257) &&
is_perfsqr_p673
(r % 673);
202
}
203
204
bool
lmmp_perfsqr_
(
mp_srcptr
p,
mp_size_t
n
) {
205
lmmp_param_assert
(
n
> 0 && p != NULL);
206
lmmp_param_assert
(p[
n
- 1] > 0);
207
bool
filter, ret;
208
209
filter =
lmmp_perfsqr_filter_
(p,
n
);
210
if
(filter ==
false
)
return
false
;
211
212
TEMP_DECL
;
213
mp_ptr
restrict
tp
=
TALLOC_TYPE
(
n
+ 2,
mp_limb_t
);
214
mp_ptr
restrict
dstr =
tp
+
n
/ 2 + 1;
215
lmmp_sqrt_
(
tp
, dstr, p,
n
, 0);
216
ret =
lmmp_zero_q_
(dstr,
n
/ 2 + 1);
217
TEMP_FREE
;
218
return
ret;
219
}
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
lmmpn.h
lmmp_zero_q_
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义
cmp.c:55
a0
#define a0
a1
#define a1
a2
#define a2
tp
#define tp
n
#define n
c1
#define c1
c0
#define c0
numth.h
uchar
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
numth.h:34
lmmp_perfsqr_filter_1_
bool lmmp_perfsqr_filter_1_(mp_limb_t p)
非完全平方数过滤器
定义
perfsqr.c:181
lmmp_perfsqr_
bool lmmp_perfsqr_(mp_srcptr p, mp_size_t n)
判断[p,n]是否为完全平方数
定义
perfsqr.c:204
ushort
uint16_t ushort
定义
numth.h:36
lmmp_mod_2p48sub1_
mp_limb_t lmmp_mod_2p48sub1_(mp_srcptr p, mp_size_t n)
计算 [p,n] % 2^48-1
定义
perfsqr.c:59
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) 的平方根和余数
定义
sqrt.c:441
lmmp_perfsqr_filter_
bool lmmp_perfsqr_filter_(mp_srcptr p, mp_size_t n)
非完全平方数过滤器
定义
perfsqr.c:191
is_perfsqr_p7
static bool is_perfsqr_p7(uchar r)
定义
perfsqr.c:126
ADD
#define ADD(c, a, val)
定义
perfsqr.c:52
MASK48
#define MASK48
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
perfsqr.c:28
PARTS0
#define PARTS0(n)
定义
perfsqr.c:47
is_perfsqr_p241
static bool is_perfsqr_p241(ushort r)
定义
perfsqr.c:146
is_perfsqr_p17
static bool is_perfsqr_p17(uchar r)
定义
perfsqr.c:134
is_perfsqr_p256
static bool is_perfsqr_p256(uchar r)
定义
perfsqr.c:173
is_perfsqr_p673
static bool is_perfsqr_p673(ushort r)
定义
perfsqr.c:163
is_perfsqr_p13
static bool is_perfsqr_p13(uchar r)
定义
perfsqr.c:130
PARTS1
#define PARTS1(n)
定义
perfsqr.c:48
is_perfsqr_p257
static bool is_perfsqr_p257(ushort r)
定义
perfsqr.c:154
is_perfsqr_p9
static bool is_perfsqr_p9(uchar r)
定义
perfsqr.c:118
is_perfsqr_p5
static bool is_perfsqr_p5(uchar r)
定义
perfsqr.c:122
B3
#define B3
定义
perfsqr.c:32
is_perfsqr_p97
static bool is_perfsqr_p97(uchar r)
定义
perfsqr.c:138
PARTS2
#define PARTS2(n)
定义
perfsqr.c:49
restrict
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_powmod.c:35
tmp_alloc.h
TEMP_DECL
#define TEMP_DECL
定义
tmp_alloc.h:145
TEMP_FREE
#define TEMP_FREE
定义
tmp_alloc.h:175
TALLOC_TYPE
#define TALLOC_TYPE(n, type)
定义
tmp_alloc.h:173
src
lmmp
numth
perfsqr.c
生成于
, 为 LMMP使用
1.18.0