47 TEST_CHECK_MSG(mod_is_product(dst, na + nb, a, na, b, nb),
"modular product check");
49 TEST_CHECK(pl == na + nb || pl == na + nb - 1);
54 return memcmp(x, y, (
size_t)
n *
sizeof(
mp_limb_t)) == 0;
57TEST_CASE(
"mul/basecase", mul_basecase_mod_and_n1_exact) {
58 u64 seed = 0x13579bdf2468ace0ull;
59 for (
size_t na = 1; na <= 40; ++na) {
60 for (
size_t nb = 1; nb <= na; ++nb) {
61 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb), dst = alloc_limbs(na + nb + 1);
62 random_limbs(a, na, &seed);
63 random_limbs(b, nb, &seed);
68 if (na == 1 && nb == 1) {
78 mp_ptr a = alloc_limbs(1), b = alloc_limbs(1), d = alloc_limbs(3);
79 a[0] = ~(
u64)0; b[0] = ~(
u64)0;
83 a[0] = ((
u64)1 << 63) + 1;
92 u64 seed = 0x2468ace013579bdfull;
93 for (
size_t na = 1; na <= 40; ++na) {
94 mp_ptr a = alloc_limbs(na), dst = alloc_limbs(2 * na + 1), ref = alloc_limbs(2 * na + 1);
95 random_limbs(a, na, &seed);
104TEST_CASE(
"mul/dispatch", mul_dispatch_vs_basecase_cross) {
106 u64 seed = 0x0123456789abcdefull;
108 1, 2, 5, 19, 20, 21, 30, 40, 64, 65, 66, 80, 100, 120,
109 150, 180, 220, 300, 400, 580, 581, 582, 700, 900, 1200
111 for (
size_t na_index = 0; na_index <
ARRAY_SIZE(sizes); ++na_index) {
113 for (
int t = 0;
t < 3; ++
t) {
116 if (nb > na) nb = na;
118 if ((
u64)na * nb > 1200000ull)
continue;
120 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb);
121 mp_ptr dst = alloc_limbs(na + nb + 2), ref = alloc_limbs(na + nb + 2);
122 random_limbs(a, na, &seed);
123 random_limbs(b, nb, &seed);
137 u64 seed = 0xf1f2f3f4f5f6f7f8ull;
138 struct operand_sizes {
mp_size_t na, nb; } sizes[] = {
139 {2345, 2345}, {2400, 1200}, {2400, 800}, {2400, 601},
140 {3072, 3072}, {4096, 1024}, {5000, 1500}, {6000, 6000},
142 for (
size_t s_index = 0; s_index <
ARRAY_SIZE(sizes); ++s_index) {
143 const struct operand_sizes
s = sizes[s_index];
144 mp_ptr a = alloc_limbs(
s.na), b = alloc_limbs(
s.nb);
145 mp_ptr dst = alloc_limbs(
s.na +
s.nb + 2), ref = alloc_limbs(
s.na +
s.nb + 2);
146 random_limbs(a,
s.na, &seed);
147 random_limbs(b,
s.nb, &seed);
159 u64 seed = 0xe1e2e3e4e5e6e7e8ull;
160 const mp_size_t n_values[] = {1544, 1600, 2048, 3072, 5000};
161 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
164 mp_ptr dst = alloc_limbs(2 *
n + 2), ref = alloc_limbs(2 *
n + 2);
165 random_limbs(a,
n, &seed);
174TEST_CASE(
"mul/hard_threshold_boundary", mul_hard_boundary_vs_basecase) {
177 u64 seed = 0x0f1e2d3c4b5a6978ull;
179 19, 20, 21, 22, 37, 38, 39, 40, 41, 42, 63, 64, 65, 66
181 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(sizes); ++n_index) {
183 for (
int t = 0;
t < 8;
t++) {
184 mp_ptr a = alloc_limbs(
n), b = alloc_limbs(
n);
185 mp_ptr dst = alloc_limbs(2 *
n + 2), ref = alloc_limbs(2 *
n + 2);
186 random_limbs(a,
n, &seed);
187 random_limbs(b,
n, &seed);
202TEST_CASE(
"mul/hard_direct_all_sizes", mul_hard_direct_n1_to_n19) {
206 u64 seed = 0x0d1c2b3a49586775ull;
208 for (
int pat = 0; pat < 6; pat++) {
209 mp_ptr a = alloc_limbs(
n), b = alloc_limbs(
n);
210 mp_ptr dst = alloc_limbs(2 *
n + 2), ref = alloc_limbs(2 *
n + 2);
213 case 0: a[i] = b[i] = xorshift64(&seed);
break;
214 case 1: a[i] = b[i] = ~(
u64)0;
break;
215 case 2: a[i] = b[i] = 1;
break;
216 case 3: a[i] = b[i] = (
u64)1 << 63;
break;
217 case 4: a[i] = b[i] = (~(
u64)0) - (
u64)(i & 1);
break;
218 default: a[i] = b[i] = xorshift64(&seed) >> (i & 63);
break;
239 u64 seed = 0xfedcba9876543210ull;
240 typedef struct {
mp_size_t na, nb; } Case;
241 const Case toom_domain[] = {
242 {600, 3}, {600, 5}, {600, 7}, {600, 10}, {600, 30}, {600, 100},
243 {700, 100}, {800, 200}, {900, 250}, {1200, 300},
245 for (
size_t c_index = 0; c_index <
ARRAY_SIZE(toom_domain); ++c_index) {
246 const Case c = toom_domain[c_index];
247 if ((
u64)c.na * c.nb > 1500000ull)
continue;
248 mp_ptr a = alloc_limbs(c.na), b = alloc_limbs(c.nb);
249 mp_ptr dst = alloc_limbs(c.na + c.nb + 2), ref = alloc_limbs(c.na + c.nb + 2);
250 random_limbs(a, c.na, &seed);
251 random_limbs(b, c.nb, &seed);
258 const Case fft_domain[] = {
259 {2316, 800}, {2400, 900}, {3116, 800}, {4096, 1024}, {6000, 1600},
261 for (
size_t c_index = 0; c_index <
ARRAY_SIZE(fft_domain); ++c_index) {
262 const Case c = fft_domain[c_index];
263 mp_ptr a = alloc_limbs(c.na), b = alloc_limbs(c.nb);
264 mp_ptr dst = alloc_limbs(c.na + c.nb + 2), ref = alloc_limbs(c.na + c.nb + 2);
265 random_limbs(a, c.na, &seed);
266 random_limbs(b, c.nb, &seed);
276 u64 seed = 0xa53a591286afcbb5ull;
277 const mp_size_t n_values[] = {1, 2, 10, 50, 65, 83, 122, 201, 737, 1262};
278 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
280 mp_ptr a = alloc_limbs(
n), b = alloc_limbs(
n), dst = alloc_limbs(
n), full = alloc_limbs(2 *
n + 2);
281 random_limbs(a,
n, &seed);
282 random_limbs(b,
n, &seed);
292 u64 seed = 0x819821c27be91101ull;
293 const mp_size_t n_values[] = {1, 2, 19, 20, 21, 30, 65, 100, 400, 581, 800, 1200};
294 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
296 mp_ptr a = alloc_limbs(
n), dst = alloc_limbs(2 *
n + 2), ref = alloc_limbs(2 *
n + 2);
297 random_limbs(a,
n, &seed);
301 if ((
u64)
n *
n <= 1500000ull) {
309TEST_CASE(
"mul/toom_splits", toom53_toom62_integer_splits) {
317 u64 seed = 0x84f4756eb3c2ab17ull;
319 for (
size_t i = 0; i <
ARRAY_SIZE(shapes); ++i) {
320 mp_size_t na = shapes[i].na, nb = shapes[i].nb;
321 random_limbs(a, na, &seed);
322 random_limbs(b, nb, &seed);
324 shapes[i].mul(dst, a, na, b, nb);
336 u64 seed = 0x8ec2d36d49433ba9ull;
338 for (
size_t i = 0; i <
ARRAY_SIZE(cases); ++i) {
340 random_limbs(a, na, &seed);
342 cases[i].sqr(dst, a, na);
351 TEST_RUN(
"mul/basecase", mul_basecase_mod_and_n1_exact);
352 TEST_RUN(
"mul/basecase", sqr_basecase_vs_mul);
353 TEST_RUN(
"mul/dispatch", mul_dispatch_vs_basecase_cross);
354 TEST_RUN(
"mul/fft", mul_fft_vs_toom8h);
355 TEST_RUN(
"mul/fft", sqr_fft_vs_toom8);
356 TEST_RUN(
"mul/hard_threshold_boundary", mul_hard_boundary_vs_basecase);
357 TEST_RUN(
"mul/hard_direct_all_sizes", mul_hard_direct_n1_to_n19);
358 TEST_RUN(
"mul/unbalanced", mul_unbalanced_cross);
359 TEST_RUN(
"mul/mullo", mullo_vs_mul_truncation);
360 TEST_RUN(
"mul/sqr_dispatch", sqr_dispatch_vs_mul);
361 TEST_RUN(
"mul/toom_splits", toom53_toom62_integer_splits);
362 TEST_RUN(
"mul/sqr_toom_small", sqr_toom_small_direct);
const mp_limb_t * mp_srcptr
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_sqr_toom8_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-8平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±8,±4,±2,±1,±1/2,±1/4,±1/8,0,无inf点)
void lmmp_sqr_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
基础平方运算 [dst,2*na] = [numa,na]^2
void lmmp_mul_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
基础乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom62_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-62乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_toom2_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-2平方运算 [dst,2*na] = [numa,na]^2
void lmmp_sqr_toom3_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-3平方运算 [dst,2*na] = [numa,na]^2
void lmmp_mul_toom8h_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-8.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±8,...
void lmmp_mul_toom53_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-53乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mullo_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
void lmmp_sqr_toom4_(mp_ptr dst, mp_srcptr numa, mp_size_t an)
Toom-4平方运算 [dst,2*na] = [numa,na]^2
#define LMMP_MUL_HARD_MAX_N
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEST_CHECK_MSG(cond, msg)
#define TEST_CASE(category, name)
#define TEST_CHECK_EQ(a, b)
#define TEST_RUN(category, name)
static void check_prod_mod(const mp_limb_t *a, mp_size_t na, const mp_limb_t *b, mp_size_t nb, const mp_limb_t *dst)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static bool limbs_same(const mp_limb_t *x, const mp_limb_t *y, mp_size_t n)