LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_sqrt.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/* sqrt 家族验证(无 BigInt oracle;cbrt 见 test_numth_cbrt.cpp):
24 1. floor 恒等式:r² ≤ n < (r+1)²((r+1)^2 经库 sqr 重建),余数恒等式
25 n == r^2 + rem(库加重建)
26 2. 标量档(u64):isqrt 二分参考(64 位内)
27 3. 入口互比:sqrt_1/2/3/4、sqrt_divide_(强制分治)、sqrt_newton_、
28 sqrt_ 生产入口彼此一致;完全平方构造(sqr 后 ±1)命中精确语义
29 4. 逆根语义:invsqrt 下近似区间 [I-1, I](参照经 div_+sqrt_ 库链构造)
30 5. perfsqr:完全平方必过过滤器、sqrtrem 余数为零判据一致
31*/
32
33#include "lmmp/lmmpn.h"
34#include "lmmp/numth.h"
35#include "cases.h"
37
38#include <string.h>
39
40// u64 isqrt 简单参考(二分,64 位内)
41static u64 isqrt_u64(u64 x) {
42 if (x == 0) return 0;
43 u64 lo = 1, hi = 0xffffffffull;
44 while (lo < hi) {
45 u64 mid = lo + (hi - lo + 1) / 2;
46 // mid*mid <= x ?mid <= 2^32-1 ⟹ mid*mid 不溢出
47 if (mid <= x / mid) lo = mid;
48 else hi = mid - 1;
49 }
50 return lo;
51}
52
53// r² ≤ n < (r+1)²(r 为 [rs,rn])。sqr_ 契约 sep(dst,numa):独立缓冲;
54// 长度取写入长度(mul/sqr 恒写满 na+nb/2na),比较走归一化 mpn_cmp。
55static bool sqrt_floor_ok(const mp_limb_t* r, mp_size_t rn, const mp_limb_t* n, mp_size_t na) {
56 mp_ptr r2 = alloc_limbs(2 * rn);
57 mp_ptr rp1 = alloc_limbs(rn + 2);
58 mp_ptr p1 = alloc_limbs(2 * rn + 4);
59 lmmp_sqr_(r2, r, rn); // r^2
60 lmmp_zero(rp1, rn + 2);
61 memcpy(rp1, r, (size_t)rn * 8);
62 add_small_inplace(rp1, rn + 2, 1); // r+1
63 mp_size_t r1n = norm_len(rp1, rn + 2);
64 if (r1n == 0) r1n = 1;
65 lmmp_sqr_(p1, rp1, r1n); // (r+1)^2(独立缓冲)
66 bool ok = mpn_cmp(r2, 2 * rn, n, na) <= 0 && mpn_cmp(n, na, p1, 2 * r1n) < 0;
68 lmmp_free(rp1);
69 lmmp_free(p1);
70 return ok;
71}
72
73// n == r^2 + rem(sqrtrem 余数恒等式)
74static bool rem_sum_ok(const mp_limb_t* r, mp_size_t rn, const mp_limb_t* rem, mp_size_t remlen,
75 const mp_limb_t* n, mp_size_t na, mp_size_t mx) {
76 mp_ptr sq = alloc_limbs(2 * rn + 2), sum = alloc_limbs(mx);
77 lmmp_sqr_(sq, r, rn);
78 pad_add(sq, 2 * rn, rem, remlen, mx, sum);
79 bool ok = mpn_eq(sum, mx, n, na);
80 lmmp_free(sq);
81 lmmp_free(sum);
82 return ok;
83}
84
85TEST_CASE("numth/sqrt", sqrt_ulong_sqrt_1_sqrt_2) {
86 u64 seed = 0x0bad1dea0bad2deaull;
87 for (int i = 0; i < 2000; ++i) {
88 u64 x = xorshift64(&seed);
90 // sqrt_1 契约域 x >= B/4:强制顶两位置后随机
91 u64 x1 = x | ((u64)3 << 62);
92 mp_ptr r1 = alloc_limbs(1);
94 TEST_CHECK_MSG(s == isqrt_u64(x1) && r1[0] == x1 - s * s, "sqrt_1 floor+rem");
96 }
97 // 写死角点
102 TEST_CHECK_EQ(lmmp_sqrt_ulong_(UINT64_MAX), 0xffffffffull);
103 {
104 mp_ptr r1 = alloc_limbs(1);
105 u64 m = UINT64_MAX;
106 TEST_CHECK_MSG(lmmp_sqrt_1_(r1, m) == 0xffffffffull, "sqrt_1 max");
107 // (2^32-1)^2 = 2^64 - 2^33 + 1 → rem = m - s²
108 TEST_CHECK_MSG(r1[0] == m - 0xffffffffull * 0xffffffffull, "sqrt_1 max rem");
109 lmmp_free(r1);
110 }
111 // sqrt_2:随机双 limb(顶 limb >= B/4)
112 for (int i = 0; i < 500; ++i) {
113 mp_ptr x = alloc_limbs(2), r2 = alloc_limbs(2);
114 random_limbs(x, 2, &seed);
115 x[1] |= (u64)1 << 62;
117 // 契约 x >= B^2/4 ⟹ s >= 2^63;x < B^2 ⟹ s < B
118 TEST_CHECK_MSG(s >= (1ull << 63), "sqrt_2 range");
119 // (s+1)^2 > x >= s^2(mullh 全积比较;s 顶值时 (s+1)^2 = B^2 > x 恒真)
120 mp_limb_t p[2], q[2];
121 lmmp_mullh_(s, s, p);
122 bool ok = lmmp_cmp_(p, x, 2) <= 0;
123 if (ok) {
124 if (s == UINT64_MAX) ok = true;
125 else {
126 lmmp_mullh_(s + 1, s + 1, q);
127 ok = lmmp_cmp_(x, q, 2) < 0;
128 }
129 }
130 TEST_CHECK_MSG(ok, "sqrt_2 floor identity");
131 // 余数 = x - s^2(借位减后与 sqrt_2 写出的余数一致)
132 lmmp_sub_n_(p, x, p, 2);
133 TEST_CHECK_MSG(memcmp(p, r2, 16) == 0, "sqrt_2 rem value");
134 lmmp_free(x);
135 lmmp_free(r2);
136 }
137}
138
139TEST_CASE("numth/sqrt", sqrt_3_sqrt_4_and_divide) {
140 u64 seed = 0x2d7a3f1b9e5c8247ull;
141 for (int shape = 0; shape < 3; ++shape) {
142 const mp_size_t ns_values[] = {2, 4, 8};
143 for (size_t ns_index = 0; ns_index < ARRAY_SIZE(ns_values); ++ns_index) {
144 mp_size_t ns = ns_values[ns_index]; // 输入 2*ns limbs
145 for (int iter = 0; iter < 4; ++iter) {
146 mp_size_t na = 2 * ns;
147 mp_ptr numa = alloc_limbs(na), numa2 = alloc_limbs(na),
148 dst = alloc_limbs(ns),
149 t1 = alloc_limbs(2 * ns + 2), t2 = alloc_limbs(2 * ns + 2);
150 random_limbs(numa, na, &seed);
151 if (shape == 1) { // 完全平方:numa = t^2(t 顶两位置 1 保证
152 // t^2 顶 >= B/4 契约,构造后不得再改 numa)
153 mp_ptr tt = alloc_limbs(ns);
154 random_limbs(tt, ns, &seed);
155 tt[ns - 1] |= (u64)3 << 62;
156 lmmp_sqr_(numa, tt, ns);
157 lmmp_free(tt);
158 } else if (shape == 2) { // t^2 - 1
159 mp_ptr tt = alloc_limbs(ns);
160 random_limbs(tt, ns, &seed);
161 tt[ns - 1] |= (u64)3 << 62;
162 lmmp_sqr_(numa, tt, ns);
163 sub_small_inplace(numa, na, 1);
164 lmmp_free(tt);
165 }
166 memcpy(numa2, numa, (size_t)na * 8);
167
168 lmmp_sqrt_divide_(dst, numa2, ns, t1, 1); // 余数在 [numa2, ns+1]
169 TEST_CHECK_MSG(sqrt_floor_ok(dst, ns, numa, na), "sqrt_divide floor");
170 if (shape == 1)
171 TEST_CHECK_MSG(norm_len(numa2, ns) == 0, "perfect square rem 0");
172 else
173 TEST_CHECK_MSG(norm_len(numa2, ns) > 0, "non-square rem > 0");
174 // 余数恒等式 n == s² + rem
176 rem_sum_ok(dst, ns, numa2, ns + 1, numa, na, 2 * ns + 4),
177 "sqrt_divide n == s^2 + rem");
178 lmmp_free(numa); lmmp_free(numa2); lmmp_free(dst);
179 lmmp_free(t1); lmmp_free(t2);
180 }
181 }
182 }
183
184 // sqrt_3_ / sqrt_4_ 特化直调:3/4 limb 输入,floor 恒等式 + 余数
185 u64 seed34 = 0x34c0ffee34c0ffeeull;
186 const mp_size_t na_values[] = {3, 4};
187 for (size_t na_index = 0; na_index < ARRAY_SIZE(na_values); ++na_index) {
188 mp_size_t na = na_values[na_index];
189 for (int iter = 0; iter < 8; ++iter) {
190 mp_ptr numa = alloc_limbs(na), dsts = alloc_limbs(2), dstr = alloc_limbs(4),
191 t1 = alloc_limbs(8), t2 = alloc_limbs(8);
192 random_limbs(numa, na, &seed34);
193 numa[na - 1] |= (u64)1 << 62;
194 if (na == 3) lmmp_sqrt_3_(dsts, dstr, numa);
195 else lmmp_sqrt_4_(dsts, dstr, numa);
196 TEST_CHECK_MSG(sqrt_floor_ok(dsts, 2, numa, na), "sqrt_3/4 floor");
197 TEST_CHECK_MSG(rem_sum_ok(dsts, 2, dstr, 3, numa, na, 12), "sqrt_3/4 rem identity");
198 lmmp_free(numa); lmmp_free(dsts); lmmp_free(dstr); lmmp_free(t1); lmmp_free(t2);
199 }
200 }
201}
202
203TEST_CASE("numth/sqrt", sqrt_dispatcher_fractional) {
204 // 生产入口 lmmp_sqrt_(nf=0 精确 floor;nf>0 [floor|round])与强制分治互比;
205 // 完全平方族(库 sqr 构造)在任意 nf 下必须精确命中 t(floor==round)
206 u64 seed = 0x77aa55cc33ee1199ull;
207 const mp_size_t na_values[] = {1, 2, 3, 5, 8, 16, 33};
208 for (size_t na_index = 0; na_index < ARRAY_SIZE(na_values); ++na_index) {
209 mp_size_t na = na_values[na_index];
210 for (int family = 0; family < 3; ++family) {
211 bool constructed_square = false; // 偶数长度才可构造 t^2 恰 na limb
212 mp_ptr numa = alloc_limbs(na);
213 mp_ptr tt = alloc_limbs(na / 2 + 1);
214 if (family == 0 || (na & 1) == 1) {
215 random_limbs(numa, na, &seed);
216 } else {
217 // t^2 / t^2-1(库 sqr 构造;偶数长度才恰为 na limb)
218 random_limbs(tt, na / 2, &seed);
219 lmmp_sqr_(numa, tt, na / 2);
220 if (family == 1) constructed_square = true;
221 if (family == 2) sub_small_inplace(numa, na, 1);
222 }
223 if (norm_len(numa, na) == 0) numa[0] = 1;
224 if (numa[na - 1] == 0) numa[na - 1] = 1; // 契约 numa[na-1]!=0
225
226 const mp_size_t nf_values[] = {0, 2, 7};
227 for (size_t nf_index = 0; nf_index < ARRAY_SIZE(nf_values); ++nf_index) {
228 mp_size_t nf = nf_values[nf_index];
229 mp_size_t ns = nf + na / 2 + 1;
230 mp_ptr ref = alloc_limbs(ns + 2), rem = alloc_limbs(ns + 2), dst = alloc_limbs(ns + 2);
231 lmmp_sqrt_(ref, rem, numa, na, nf); // 精确 sqrtrem 参考
232 { // 余数界 rem < 2*root+1((s+1)^2 = s^2+2s+1)
233 mp_ptr two_s = alloc_limbs(ns + 2);
234 lmmp_zero(two_s, ns + 2);
235 memcpy(two_s, ref, (size_t)ns * 8);
236 lmmp_add_n_(two_s, two_s, two_s, ns + 2); // 2s(零垫域内翻倍)
237 add_small_inplace(two_s, ns + 2, 1);
238 TEST_CHECK_MSG(mpn_cmp(rem, ns, two_s, ns + 2) < 0, "sqrt_ rem < 2s+1");
239 lmmp_free(two_s);
240 }
241 // floor 恒等式:ref² ≤ numa*B^(2nf) < (ref+1)²
242 {
243 mp_ptr sq = alloc_limbs(2 * ns + 2), rp1 = alloc_limbs(ns + 2),
244 big = alloc_limbs(na + 2 * nf + 2), t1 = alloc_limbs(2 * ns + 4),
245 t2 = alloc_limbs(2 * ns + 4);
246 mp_size_t rn = norm_len(ref, ns);
247 lmmp_sqr_(sq, ref, rn);
248 lmmp_zero(rp1, ns + 2);
249 memcpy(rp1, ref, (size_t)rn * 8);
250 add_small_inplace(rp1, ns + 2, 1);
251 mp_size_t r1n = norm_len(rp1, ns + 2);
252 lmmp_sqr_(t2, rp1, r1n);
253 // big = numa * B^(2nf)
254 lmmp_zero(big, na + 2 * nf + 2);
255 memcpy(big + 2 * nf, numa, (size_t)na * 8);
256 TEST_CHECK_MSG(mpn_cmp(sq, 2 * rn, big, na + 2 * nf) <= 0 &&
257 mpn_cmp(big, na + 2 * nf, t2, 2 * r1n) < 0,
258 "sqrt_ floor identity");
259 // 余数恒等式:big == ref² + rem
260 mp_ptr sum = alloc_limbs(2 * ns + 4);
261 pad_add(sq, 2 * rn, rem, ns, 2 * ns + 4, sum);
262 TEST_CHECK_MSG(mpn_eq(sum, 2 * ns + 4, big, na + 2 * nf),
263 "sqrt_ n == s^2 + rem");
264 lmmp_free(sq); lmmp_free(rp1); lmmp_free(big);
265 lmmp_free(t1); lmmp_free(t2); lmmp_free(sum);
266 }
267 // dstr=NULL 路径与带余数同值
268 lmmp_sqrt_(dst, NULL, numa, na, nf);
269 TEST_CHECK_MSG(memcmp(dst, ref, (size_t)ns * 8) == 0, "sqrt_ null rem");
270 // nf>=2:sqrt_newton_ ∈ {floor, floor+1};完全平方必须精确
271 if (nf >= 2) {
272 mp_ptr nw = alloc_limbs(ns + 2);
273 lmmp_sqrt_newton_(nw, numa, na, nf);
274 bool ok = memcmp(nw, ref, (size_t)ns * 8) == 0;
275 if (!ok) { // 允许恰 +1(round 语义;完全平方除外)
276 mp_ptr rp1 = alloc_limbs(ns + 2);
277 lmmp_zero(rp1, ns + 2);
278 memcpy(rp1, ref, (size_t)ns * 8);
279 add_small_inplace(rp1, ns + 2, 1);
280 ok = memcmp(nw, rp1, (size_t)ns * 8) == 0;
281 lmmp_free(rp1);
282 }
283 bool must_exact = constructed_square;
284 if (must_exact) TEST_CHECK_MSG(memcmp(nw, ref, (size_t)ns * 8) == 0,
285 "newton perfect square exact");
286 else TEST_CHECK_MSG(ok, "newton in {floor, floor+1}");
287 lmmp_free(nw);
288 }
289 lmmp_free(ref); lmmp_free(rem); lmmp_free(dst);
290 }
291 lmmp_free(numa);
292 lmmp_free(tt);
293 }
294 }
295}
296
297TEST_CASE("numth/sqrt", invsqrt_newton_semantics) {
298 // I-1 <= ir <= I(绝不高估);I 经 div_+sqrt_ 库链构造
299 u64 seed = 0x5eed1dea5eed1deaull;
300 const mp_size_t na_values[] = {1, 3, 8};
301 for (size_t na_index = 0; na_index < ARRAY_SIZE(na_values); ++na_index) {
302 mp_size_t na = na_values[na_index];
303 const mp_size_t ns_values[] = {4, 8};
304 for (size_t ns_index = 0; ns_index < ARRAY_SIZE(ns_values); ++ns_index) {
305 mp_size_t ns = ns_values[ns_index];
306 if (ns == na) continue;
307 mp_ptr a = alloc_limbs(na), dstis = alloc_limbs(ns + 2), isq = alloc_limbs(ns + 2),
308 nb = alloc_limbs(2 * ns + na + 4), q = alloc_limbs(2 * ns + 4);
309 for (int f = 0; f < 4; ++f) {
310 lmmp_zero(a, na);
311 if (f < 2) {
312 random_limbs(a, na, &seed);
313 a[na - 1] |= (u64)1 << 61;
314 } else if (f == 2) {
315 a[na - 1] = 0x4000000000000000ull; // a = B^na/4 边界
316 } else {
317 for (mp_size_t i = 0; i < na; ++i) a[i] = ~(u64)0; // B^na-1
318 }
319 lmmp_zero(dstis, ns + 2);
320 lmmp_invsqrt_newton_(dstis, ns, a, na);
321 TEST_CHECK_MSG(dstis[ns] == 1, "invsqrt top limb == 1");
322 // I 参照:ns>=na 时 I = floor(sqrt(B^(2ns+na)/a));
323 // ns<na 时语义不同(仅用 a 的最高 ns limb,结果量纲差
324 // B^((ns-na)/2)):改为 floor(sqrt(B^(3ns)/a_top))
325 mp_size_t e, adiv;
326 const mp_limb_t* ap;
327 if (ns >= na) {
328 e = 2 * ns + na;
329 ap = a;
330 adiv = na;
331 } else {
332 e = 3 * ns;
333 ap = a + (na - ns);
334 adiv = ns;
335 }
336 mp_size_t L = e + 1;
337 lmmp_zero(nb, L);
338 nb[L - 1] = 1;
339 lmmp_div_(q, NULL, nb, L, ap, adiv);
340 mp_size_t ql = L - adiv + 1;
341 while (ql > 1 && q[ql - 1] == 0) --ql;
342 lmmp_zero(isq, ns + 2); // 根短于 ns+1 时高位不得混入垃圾
343 lmmp_sqrt_(isq, NULL, q, ql, 0);
344 // ir ∈ {I-1, I}(等长 ns+1 比较)
345 mp_ptr im1 = alloc_limbs(ns + 2);
346 lmmp_zero(im1, ns + 2);
347 memcpy(im1, isq, (size_t)(ns + 1) * 8);
348 sub_small_inplace(im1, ns + 2, 1);
349 bool ok = memcmp(dstis, isq, (size_t)(ns + 1) * 8) == 0 ||
350 memcmp(dstis, im1, (size_t)(ns + 1) * 8) == 0;
351 TEST_CHECK_MSG(ok, "invsqrt in {I-1, I}");
352 lmmp_free(im1);
353 }
354 lmmp_free(a); lmmp_free(dstis); lmmp_free(isq); lmmp_free(nb); lmmp_free(q);
355 }
356 }
357}
358
359TEST_CASE("numth/perfsqr", perfsqr_filter_perfsqr) {
360 u64 seed = 0x1deafbee1deafbeeull;
361 // filter_1:单 limb 契约域。完全平方(u64 内 r²)必过
362 for (int i = 0; i < 200; ++i) {
363 u64 r = 1 + (xorshift64(&seed) & 0xffffffffull); // r <= 2^32-1 ⟹ r² < B
364 TEST_CHECK_MSG(lmmp_perfsqr_filter_1_(r * r), "filter_1 square pass");
365 }
366 // 完全平方必过过滤器;perfsqr_ 判据与 sqrtrem 余数一致
367 const mp_size_t nt_values[] = {1, 2, 5, 17};
368 for (size_t nt_index = 0; nt_index < ARRAY_SIZE(nt_values); ++nt_index) {
369 mp_size_t nt = nt_values[nt_index];
370 for (int iter = 0; iter < 6; ++iter) {
371 mp_ptr tt = alloc_limbs(nt), sq = alloc_limbs(2 * nt), dstr = alloc_limbs(nt + 2);
372 random_limbs(tt, nt, &seed);
373 lmmp_sqr_(sq, tt, nt);
374 TEST_CHECK_MSG(lmmp_perfsqr_filter_(sq, 2 * nt), "filter square pass");
375 TEST_CHECK_MSG(lmmp_perfsqr_(sq, 2 * nt), "perfsqr square true");
376 // 非平方(平方 ±1,顶 limb 非零时):perfsqr_ 必假;过滤器允许过
377 if (sq[0] >= 2) {
378 sq[0] -= 1;
379 if (norm_len(sq, 2 * nt) > 0) {
380 TEST_CHECK_MSG(!lmmp_perfsqr_(sq, 2 * nt), "perfsqr square-1 false");
381 }
382 sq[0] += 2;
383 if (sq[0] != 0) {
384 TEST_CHECK_MSG(!lmmp_perfsqr_(sq, 2 * nt), "perfsqr square+1 false");
385 }
386 sq[0] -= 1;
387 }
388 lmmp_free(tt); lmmp_free(sq); lmmp_free(dstr);
389 }
390 }
391 // 随机非平方:perfsqr_ 与 sqrtrem 余数判据一致
392 const mp_size_t n_values[] = {1, 3, 8, 20};
393 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
394 mp_size_t n = n_values[n_index];
395 for (int iter = 0; iter < 20; ++iter) {
396 mp_ptr x = alloc_limbs(n), dstr = alloc_limbs(n + 2);
397 random_limbs(x, n, &seed);
398 bool isp = lmmp_perfsqr_(x, n);
399 lmmp_sqrt_(dstr, NULL, x, n, 0);
400 mp_size_t sn = n / 2 + 1;
401 mp_ptr sq = alloc_limbs(2 * sn + 2);
402 mp_size_t rn = norm_len(dstr, sn);
403 lmmp_sqr_(sq, dstr, rn);
404 bool rem_zero = mpn_eq(sq, 2 * rn, x, n);
405 TEST_CHECK_MSG(isp == rem_zero, "perfsqr matches sqrtrem criterion");
406 lmmp_free(x); lmmp_free(dstr); lmmp_free(sq);
407 }
408 }
409}
410
411void test_sqrt(void) {
412 TEST_RUN("numth/sqrt", sqrt_ulong_sqrt_1_sqrt_2);
413 TEST_RUN("numth/sqrt", sqrt_3_sqrt_4_and_divide);
414 TEST_RUN("numth/sqrt", sqrt_dispatcher_fractional);
415 TEST_RUN("numth/sqrt", invsqrt_newton_semantics);
416 TEST_RUN("numth/perfsqr", perfsqr_filter_perfsqr);
417}
#define lmmp_mullh_
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
#define r2
#define r1
#define s
#define n
#define lo
void test_sqrt(void)
void lmmp_sqrt_3_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,3]))
void lmmp_sqrt_newton_(mp_ptr dsts, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算近似平方根 [dsts,nf+na/2+1]=[floor|round](sqrt([numa,na]*B^(2*nf)))
定义 sqrt.c:392
void lmmp_sqrt_divide_(mp_ptr dst, mp_ptr numa, mp_size_t ns, mp_ptr tp, int calr)
计算算术平方根 floor(sqrt([numa,2*ns]))
bool lmmp_perfsqr_filter_1_(mp_limb_t p)
非完全平方数过滤器
mp_limb_t lmmp_sqrt_1_(mp_ptr dstr, mp_limb_t x)
计算算术平方根 floor(sqrt(x))
ulong lmmp_sqrt_ulong_(ulong a)
计算算术平方根 floor(sqrt(a))
mp_limb_t lmmp_sqrt_2_(mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,2]))
bool lmmp_perfsqr_(mp_srcptr p, mp_size_t n)
判断[p,n]是否为完全平方数
void lmmp_sqrt_4_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,4]))
void lmmp_invsqrt_newton_(mp_ptr dstis, mp_size_t ns, mp_srcptr numa, mp_size_t na)
计算逆平方根的定点下近似:记 I=floor(sqrt(B^(2*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,...
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 ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_CHECK_EQ(a, b)
定义 test.h:39
#define TEST_RUN(category, name)
定义 test.h:36
static u64 isqrt_u64(u64 x)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static bool sqrt_floor_ok(const mp_limb_t *r, mp_size_t rn, const mp_limb_t *n, mp_size_t na)
static bool rem_sum_ok(const mp_limb_t *r, mp_size_t rn, const mp_limb_t *rem, mp_size_t remlen, const mp_limb_t *n, mp_size_t na, mp_size_t mx)