101TEST_CASE(
"numth/nthroot", nthroot_top_random_and_powers) {
102 u64 seed = 0xF1E2D3C4B5A69788ull;
103 const ulong roots[] = {4, 5, 8, 16, 32, 100};
106 for (
size_t root_index = 0; root_index <
ARRAY_SIZE(roots); ++root_index) {
107 ulong root = roots[root_index];
110 mp_ptr numa = alloc_limbs(NAMAX), dst = alloc_limbs(64),
tp = alloc_limbs((
size_t)tpsize);
111 mp_ptr pw = alloc_limbs(NAMAX + 128), pw1 = alloc_limbs(NAMAX + 128),
112 rp1 = alloc_limbs(NAMAX + 128), sum = alloc_limbs(NAMAX + 128);
114 for (
size_t root_index = 0; root_index <
ARRAY_SIZE(roots); ++root_index) {
115 ulong root = roots[root_index];
118 mp_ptr dstr = alloc_limbs((
size_t)((root - 1) * nr + 1));
119 for (
int t = 0;
t < 6; ++
t) {
120 for (
mp_size_t i = 0; i < na; ++i) numa[i] = xorshift64(&seed);
122 numa[na - 1] = ~(
u64)0 - xorshift64(&seed) % (UINT64_MAX / 4);
124 numa[na - 1] = xorshift64(&seed) % 0x10000 + 1;
127 check_floor(numa, na, dst, nr, root, calr ? dstr : NULL, pw, pw1, rp1, sum);
133 mp_ptr S = alloc_limbs(nr);
135 mp_ptr dstr = alloc_limbs((
size_t)((root - 1) * (nr + 1) + 2));
136 for (
int t = 0;
t < 3; ++
t) {
137 random_limbs(S, nr, &seed);
138 mp_size_t cap = root * nr + root / 2 + 4;
141 if (na > NAMAX)
continue;
142 for (
int d = 0; d <= 1; ++d) {
143 if (d) sub_small_inplace(numa, na, 1);
144 if (numa[na - 1] == 0)
continue;
147 check_floor(numa, na, dst, nr2, root, dstr, pw, pw1, rp1, sum);
169TEST_CASE(
"numth/nthroot", nthroot_top_probe_construction) {
170 u64 seed = 0xA5A512349ABCDEF7ull;
171 const ulong roots[] = {4, 5, 8, 16, 32, 64, 100};
174 for (
size_t root_index = 0; root_index <
ARRAY_SIZE(roots); ++root_index) {
175 ulong root = roots[root_index];
176 for (
size_t nr_index = 0; nr_index <
ARRAY_SIZE(NRS); ++nr_index) {
182 mp_ptr numa = alloc_limbs((
size_t)cap);
183 mp_ptr dst = alloc_limbs((
size_t)(nr + 4));
184 mp_ptr dstr = alloc_limbs((
size_t)((root - 1) * (nr + 4) + 8));
185 mp_ptr tp = alloc_limbs((
size_t)tpsz);
186 mp_ptr pw = alloc_limbs((
size_t)cap),
187 pw1 = alloc_limbs((
size_t)cap),
188 rp1 = alloc_limbs((
size_t)cap),
189 sum = alloc_limbs((
size_t)cap);
190 mp_ptr Sp = alloc_limbs(nr), thr = alloc_limbs((
size_t)cap);
191 for (
int t = 0;
t < 3; ++
t) {
192 random_limbs(Sp, nr, &seed);
199 if (hi) thr[tn++] = hi;
201 struct root_case {
int kind;
long long delta; } specs[] = {
202 {0, 0}, {0, 1}, {0, -1}, {0, 2}, {0, -2},
203 {1, -1}, {1, -2}, {1, -3},
204 {2, 1}, {2, -1}, {2, 2}, {2, -2},
206 for (
size_t sp_index = 0; sp_index <
ARRAY_SIZE(specs); ++sp_index) {
207 const struct root_case sp = specs[sp_index];
211 memcpy(rp1, Sp, (
size_t)nr * 8);
212 add_small_inplace(rp1, cap, 1);
214 if (s1n == 0) s1n = 1;
216 na =
lmmp_pow_(numa, cap, rp1, s1n, root);
221 mp_ptr t2 = alloc_limbs(cap);
223 memcpy(t2, thr, (
size_t)tn * 8);
226 na = norm_len(numa, cap);
230 add_small_inplace(numa, cap, (
u64)sp.delta);
231 na = norm_len(numa, cap);
232 }
else if (sp.delta < 0) sub_small_inplace(numa, na, (
u64)(-sp.delta));
233 if (numa[na - 1] == 0)
continue;
236 check_floor(numa, na, dst, nr2, root, NULL, pw, pw1, rp1, sum);
238 check_floor(numa, na, dst, nr2, root, dstr, pw, pw1, rp1, sum);
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]
mp_size_t lmmp_pow_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算大整数幂 [dst,rn] = [base,n] ^ exp
void lmmp_nthroot_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, ulong root, mp_ptr tp)
计算算术根 [dsts,nr] = floor([numa,na]^(1/root))(任意 na/任意顶 limb)
static void check_floor(const mp_limb_t *A, mp_size_t an, const mp_limb_t *r, mp_size_t rn, ulong root, const mp_limb_t *rem, mp_ptr pw, mp_ptr pw1, mp_ptr rp1, mp_ptr sum)
static mp_ptr pad_add_value(const mp_limb_t *a, mp_size_t la, const mp_limb_t *b, mp_size_t lb, mp_size_t mx, mp_ptr sum)
Copyright (C) 2026 HJimmyK (Jericho Knox)