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

浏览该文件的源代码.

宏定义

#define ADD(c, a, val)
#define B1   (LIMB_BITS / 4)
#define B2   (B1 * 2)
#define B3   (B1 * 3)
#define HIGH0(n)
#define HIGH1(n)
#define HIGH2(n)
#define LOW0(n)
#define LOW1(n)
#define LOW2(n)
#define M1   ((1ULL << B1) - 1)
#define M2   ((1ULL << B2) - 1)
#define M3   ((1ULL << B3) - 1)
#define MASK48   (0xFFFFFFFFFFFF)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define PARTS0(n)
#define PARTS1(n)
#define PARTS2(n)

函数

static bool is_perfsqr_p13 (uchar r)
static bool is_perfsqr_p17 (uchar r)
static bool is_perfsqr_p241 (ushort r)
static bool is_perfsqr_p256 (uchar r)
static bool is_perfsqr_p257 (ushort r)
static bool is_perfsqr_p5 (uchar r)
static bool is_perfsqr_p673 (ushort r)
static bool is_perfsqr_p7 (uchar r)
static bool is_perfsqr_p9 (uchar r)
static bool is_perfsqr_p97 (uchar r)
mp_limb_t lmmp_mod_2p48sub1_ (mp_srcptr p, mp_size_t n)
 计算 [p,n] % 2^48-1
bool lmmp_perfsqr_ (mp_srcptr p, mp_size_t n)
 判断[p,n]是否为完全平方数
bool lmmp_perfsqr_filter_ (mp_srcptr p, mp_size_t n)
 非完全平方数过滤器
bool lmmp_perfsqr_filter_1_ (mp_limb_t p)
 非完全平方数过滤器

宏定义说明

◆ ADD

#define ADD ( c,
a,
val )
值:
do { \
mp_limb_t new_a = (a) + (val); \
(c) += new_a < (a); \
(a) = new_a; \
} while (0)
uint64_t mp_limb_t
定义 lmmp.h:92

在文件 perfsqr.c 第 52 行定义.

被这些函数引用 lmmp_mod_2p48sub1_().

◆ B1

#define B1   (LIMB_BITS / 4)

在文件 perfsqr.c 第 30 行定义.

◆ B2

#define B2   (B1 * 2)

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

◆ B3

#define B3   (B1 * 3)

在文件 perfsqr.c 第 32 行定义.

被这些函数引用 lmmp_mod_2p48sub1_().

◆ HIGH0

#define HIGH0 ( n)
值:
((n) >> B3)
#define n
#define B3

在文件 perfsqr.c 第 39 行定义.

◆ HIGH1

#define HIGH1 ( n)
值:
((n) >> B2)
#define B2

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

◆ HIGH2

#define HIGH2 ( n)
值:
((n) >> B1)
#define B1

在文件 perfsqr.c 第 45 行定义.

◆ LOW0

#define LOW0 ( n)
值:
((n) & M3)
#define M3

在文件 perfsqr.c 第 38 行定义.

◆ LOW1

#define LOW1 ( n)
值:
(((n) & M2) << B1)
#define M2

在文件 perfsqr.c 第 41 行定义.

◆ LOW2

#define LOW2 ( n)
值:
(((n) & M1) << B2)
#define M1

在文件 perfsqr.c 第 44 行定义.

◆ M1

#define M1   ((1ULL << B1) - 1)

◆ M2

#define M2   ((1ULL << B2) - 1)

在文件 perfsqr.c 第 35 行定义.

◆ M3

#define M3   ((1ULL << B3) - 1)

在文件 perfsqr.c 第 36 行定义.

◆ MASK48

#define MASK48   (0xFFFFFFFFFFFF)

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

在文件 perfsqr.c 第 28 行定义.

被这些函数引用 lmmp_mod_2p48sub1_() , 以及 lmmp_perfsqr_filter_1_().

◆ PARTS0

#define PARTS0 ( n)
值:
(LOW0(n) + HIGH0(n))
#define HIGH0(n)
#define LOW0(n)

在文件 perfsqr.c 第 47 行定义.

被这些函数引用 lmmp_mod_2p48sub1_().

◆ PARTS1

#define PARTS1 ( n)
值:
(LOW1(n) + HIGH1(n))
#define HIGH1(n)
#define LOW1(n)

在文件 perfsqr.c 第 48 行定义.

被这些函数引用 lmmp_mod_2p48sub1_().

◆ PARTS2

#define PARTS2 ( n)
值:
(LOW2(n) + HIGH2(n))
#define HIGH2(n)
#define LOW2(n)

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

被这些函数引用 lmmp_mod_2p48sub1_().

函数说明

◆ is_perfsqr_p13()

bool is_perfsqr_p13 ( uchar r)
inlinestatic

在文件 perfsqr.c 第 130 行定义.

130 {
131 return r == 0 || r == 1 || r == 3 || r == 4 || r == 9 || r == 10 || r == 12;
132}

引用了 is_perfsqr_p13().

被这些函数引用 is_perfsqr_p13(), lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

◆ is_perfsqr_p17()

bool is_perfsqr_p17 ( uchar r)
inlinestatic

在文件 perfsqr.c 第 134 行定义.

134 {
135 return r == 0 || r == 1 || r == 2 || r == 4 || r == 8 || r == 9 || r == 13 || r == 15 || r == 16;
136}

引用了 is_perfsqr_p17().

被这些函数引用 is_perfsqr_p17(), lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

◆ is_perfsqr_p241()

bool is_perfsqr_p241 ( ushort r)
inlinestatic

在文件 perfsqr.c 第 146 行定义.

146 {
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}
#define lmmp_param_assert(x)
定义 lmmp.h:509
uint16_t ushort
定义 numth.h:36

引用了 is_perfsqr_p241() , 以及 lmmp_param_assert.

被这些函数引用 is_perfsqr_p241(), lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

◆ is_perfsqr_p256()

bool is_perfsqr_p256 ( uchar r)
inlinestatic

在文件 perfsqr.c 第 173 行定义.

173 {
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}

引用了 is_perfsqr_p256() , 以及 lmmp_param_assert.

被这些函数引用 is_perfsqr_p256(), lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

◆ is_perfsqr_p257()

bool is_perfsqr_p257 ( ushort r)
inlinestatic

在文件 perfsqr.c 第 154 行定义.

154 {
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}

引用了 is_perfsqr_p257() , 以及 lmmp_param_assert.

被这些函数引用 is_perfsqr_p257(), lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

◆ is_perfsqr_p5()

bool is_perfsqr_p5 ( uchar r)
inlinestatic

在文件 perfsqr.c 第 122 行定义.

122 {
123 return r == 0 || r == 1 || r == 4;
124}

引用了 is_perfsqr_p5().

被这些函数引用 is_perfsqr_p5(), lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

◆ is_perfsqr_p673()

bool is_perfsqr_p673 ( ushort r)
inlinestatic

在文件 perfsqr.c 第 163 行定义.

163 {
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}

引用了 is_perfsqr_p673() , 以及 lmmp_param_assert.

被这些函数引用 is_perfsqr_p673(), lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

◆ is_perfsqr_p7()

bool is_perfsqr_p7 ( uchar r)
inlinestatic

在文件 perfsqr.c 第 126 行定义.

126 {
127 return r == 0 || r == 1 || r == 2 || r == 4;
128}

引用了 is_perfsqr_p7().

被这些函数引用 is_perfsqr_p7(), lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

◆ is_perfsqr_p9()

bool is_perfsqr_p9 ( uchar r)
inlinestatic

在文件 perfsqr.c 第 118 行定义.

118 {
119 return r == 0 || r == 1 || r == 4 || r == 7;
120}

引用了 is_perfsqr_p9().

被这些函数引用 is_perfsqr_p9(), lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

◆ is_perfsqr_p97()

bool is_perfsqr_p97 ( uchar r)
inlinestatic

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

138 {
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}

引用了 is_perfsqr_p97().

被这些函数引用 is_perfsqr_p97(), lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

◆ lmmp_mod_2p48sub1_()

mp_limb_t lmmp_mod_2p48sub1_ ( mp_srcptr p,
mp_size_t n )

计算 [p,n] % 2^48-1

参数
p被除数指针
n被除数的 limb 长度
警告
p!=NULL, n>0
返回
[numa,na] % 2^48-1

在文件 perfsqr.c 第 59 行定义.

59 {
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}
#define a0
#define a1
#define a2
#define c1
#define c0
#define ADD(c, a, val)
#define MASK48
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define PARTS0(n)
#define PARTS1(n)
#define PARTS2(n)

引用了 a0, a1, a2, ADD, B3, c0, c1, lmmp_mod_2p48sub1_(), lmmp_param_assert, MASK48, n, PARTS0, PARTS1 , 以及 PARTS2.

被这些函数引用 lmmp_invcbrt_newton_(), lmmp_mod_2p48sub1_() , 以及 lmmp_perfsqr_filter_().

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

◆ lmmp_perfsqr_()

bool lmmp_perfsqr_ ( mp_srcptr p,
mp_size_t n )

判断[p,n]是否为完全平方数

参数
p输入指针
n输入的 limb 长度
警告
p!=NULL, n>0, p[n-1]>0
返回
为完全平方数返回 true,否则返回 false

在文件 perfsqr.c 第 204 行定义.

204 {
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
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
#define tp
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)
非完全平方数过滤器
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 lmmp_param_assert, lmmp_perfsqr_(), lmmp_perfsqr_filter_(), lmmp_sqrt_(), lmmp_zero_q_(), n, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

被这些函数引用 ipn_lucas_i_(), lmmp_invcbrt_newton_(), lmmp_perfsqr_() , 以及 TEST_CASE().

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

◆ lmmp_perfsqr_filter_()

bool lmmp_perfsqr_filter_ ( mp_srcptr p,
mp_size_t n )

非完全平方数过滤器

参数
p输入指针
n输入的 limb 长度
警告
p!=NULL, n>0, p[n-1]>0
返回
false 意味着必定为非完全平方数,所有完全平方数和部分非完全平方数会返回 true
注解
此过滤器主要针对随机输入情况,对于大概率是完全平方数的输入,可以无需此函数。

在文件 perfsqr.c 第 191 行定义.

191 {
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}
bool lmmp_perfsqr_filter_1_(mp_limb_t p)
非完全平方数过滤器
mp_limb_t lmmp_mod_2p48sub1_(mp_srcptr p, mp_size_t n)
计算 [p,n] % 2^48-1
static bool is_perfsqr_p7(uchar r)
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)
static bool is_perfsqr_p257(ushort r)
static bool is_perfsqr_p9(uchar r)
static bool is_perfsqr_p5(uchar r)
static bool is_perfsqr_p97(uchar r)

引用了 is_perfsqr_p13(), is_perfsqr_p17(), is_perfsqr_p241(), is_perfsqr_p256(), is_perfsqr_p257(), is_perfsqr_p5(), is_perfsqr_p673(), is_perfsqr_p7(), is_perfsqr_p9(), is_perfsqr_p97(), lmmp_mod_2p48sub1_(), lmmp_param_assert, lmmp_perfsqr_filter_(), lmmp_perfsqr_filter_1_() , 以及 n.

被这些函数引用 lmmp_invcbrt_newton_(), lmmp_perfsqr_(), lmmp_perfsqr_filter_() , 以及 TEST_CASE().

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

◆ lmmp_perfsqr_filter_1_()

bool lmmp_perfsqr_filter_1_ ( mp_limb_t p)

非完全平方数过滤器

参数
p输入数
警告
p>0
返回
false 意味着必定为非完全平方数,所有完全平方数和部分非完全平方数会返回 true
注解
此过滤器主要针对随机输入情况,对于大概率是完全平方数的输入,可以无需此函数。

在文件 perfsqr.c 第 181 行定义.

181 {
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}

引用了 is_perfsqr_p13(), is_perfsqr_p17(), is_perfsqr_p241(), is_perfsqr_p256(), is_perfsqr_p257(), is_perfsqr_p5(), is_perfsqr_p673(), is_perfsqr_p7(), is_perfsqr_p9(), is_perfsqr_p97(), lmmp_param_assert, lmmp_perfsqr_filter_1_() , 以及 MASK48.

被这些函数引用 lmmp_invcbrt_newton_(), lmmp_perfsqr_filter_(), lmmp_perfsqr_filter_1_() , 以及 TEST_CASE().

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