140 u64 seed = 0x2d7a3f1b9e5c8247ull;
141 for (
int shape = 0; shape < 3; ++shape) {
143 for (
size_t ns_index = 0; ns_index <
ARRAY_SIZE(ns_values); ++ns_index) {
145 for (
int iter = 0; iter < 4; ++iter) {
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);
153 mp_ptr tt = alloc_limbs(ns);
154 random_limbs(tt, ns, &seed);
155 tt[ns - 1] |= (
u64)3 << 62;
158 }
else if (shape == 2) {
159 mp_ptr tt = alloc_limbs(ns);
160 random_limbs(tt, ns, &seed);
161 tt[ns - 1] |= (
u64)3 << 62;
163 sub_small_inplace(numa, na, 1);
166 memcpy(numa2, numa, (
size_t)na * 8);
176 rem_sum_ok(dst, ns, numa2, ns + 1, numa, na, 2 * ns + 4),
177 "sqrt_divide n == s^2 + rem");
185 u64 seed34 = 0x34c0ffee34c0ffeeull;
187 for (
size_t na_index = 0; na_index <
ARRAY_SIZE(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;
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) {
210 for (
int family = 0; family < 3; ++family) {
211 bool constructed_square =
false;
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);
218 random_limbs(tt, na / 2, &seed);
220 if (family == 1) constructed_square =
true;
221 if (family == 2) sub_small_inplace(numa, na, 1);
223 if (norm_len(numa, na) == 0) numa[0] = 1;
224 if (numa[na - 1] == 0) numa[na - 1] = 1;
227 for (
size_t nf_index = 0; nf_index <
ARRAY_SIZE(nf_values); ++nf_index) {
230 mp_ptr ref = alloc_limbs(ns + 2), rem = alloc_limbs(ns + 2), dst = alloc_limbs(ns + 2);
233 mp_ptr two_s = alloc_limbs(ns + 2);
235 memcpy(two_s, ref, (
size_t)ns * 8);
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");
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);
249 memcpy(rp1, ref, (
size_t)rn * 8);
250 add_small_inplace(rp1, ns + 2, 1);
255 memcpy(big + 2 * nf, numa, (
size_t)na * 8);
257 mpn_cmp(big, na + 2 * nf, t2, 2 * r1n) < 0,
258 "sqrt_ floor identity");
260 mp_ptr sum = alloc_limbs(2 * ns + 4);
261 pad_add(sq, 2 * rn, rem, ns, 2 * ns + 4, sum);
263 "sqrt_ n == s^2 + rem");
269 TEST_CHECK_MSG(memcmp(dst, ref, (
size_t)ns * 8) == 0,
"sqrt_ null rem");
272 mp_ptr nw = alloc_limbs(ns + 2);
274 bool ok = memcmp(nw, ref, (
size_t)ns * 8) == 0;
276 mp_ptr rp1 = alloc_limbs(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;
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");
299 u64 seed = 0x5eed1dea5eed1deaull;
301 for (
size_t na_index = 0; na_index <
ARRAY_SIZE(na_values); ++na_index) {
304 for (
size_t ns_index = 0; ns_index <
ARRAY_SIZE(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) {
312 random_limbs(a, na, &seed);
313 a[na - 1] |= (
u64)1 << 61;
315 a[na - 1] = 0x4000000000000000ull;
341 while (ql > 1 && q[ql - 1] == 0) --ql;
345 mp_ptr im1 = alloc_limbs(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;
360 u64 seed = 0x1deafbee1deafbeeull;
362 for (
int i = 0; i < 200; ++i) {
363 u64 r = 1 + (xorshift64(&seed) & 0xffffffffull);
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) {
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);
379 if (norm_len(sq, 2 * nt) > 0) {
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) {
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);
401 mp_ptr sq = alloc_limbs(2 * sn + 2);
404 bool rem_zero = mpn_eq(sq, 2 * rn, x,
n);
405 TEST_CHECK_MSG(isp == rem_zero,
"perfsqr matches sqrtrem criterion");
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]
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]
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,...