LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
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
118static inline bool is_perfsqr_p9(uchar r) {
119 return r == 0 || r == 1 || r == 4 || r == 7;
120}
121
122static inline bool is_perfsqr_p5(uchar r) {
123 return r == 0 || r == 1 || r == 4;
124}
125
126static inline bool is_perfsqr_p7(uchar r) {
127 return r == 0 || r == 1 || r == 2 || r == 4;
128}
129
130static 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
134static 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
138static 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
146static 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
154static 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
163static 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
173static 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
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
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;
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
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;
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_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
#define a0
#define a1
#define a2
#define tp
#define n
#define c1
#define c0
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 numth.h:34
bool lmmp_perfsqr_filter_1_(mp_limb_t p)
非完全平方数过滤器
bool lmmp_perfsqr_(mp_srcptr p, mp_size_t n)
判断[p,n]是否为完全平方数
uint16_t ushort
定义 numth.h:36
mp_limb_t lmmp_mod_2p48sub1_(mp_srcptr p, mp_size_t n)
计算 [p,n] % 2^48-1
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
bool lmmp_perfsqr_filter_(mp_srcptr p, mp_size_t n)
非完全平方数过滤器
static bool is_perfsqr_p7(uchar r)
#define ADD(c, a, val)
#define MASK48
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define PARTS0(n)
static bool is_perfsqr_p241(ushort r)
static bool is_perfsqr_p17(uchar r)
static bool is_perfsqr_p256(uchar r)
static bool is_perfsqr_p673(ushort r)
static bool is_perfsqr_p13(uchar r)
#define PARTS1(n)
static bool is_perfsqr_p257(ushort r)
static bool is_perfsqr_p9(uchar r)
static bool is_perfsqr_p5(uchar r)
#define B3
static bool is_perfsqr_p97(uchar r)
#define PARTS2(n)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)