LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_mul.c 文件参考
#include "lmmp/lmmpn.h"
#include "impl/mul_hard.h"
#include "cases.h"
#include "support/lmmp_test_utils.h"
#include <string.h>
test_mul.c 的引用(Include)关系图:

浏览该文件的源代码.

函数

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)
 TEST_CASE ("mul/basecase", mul_basecase_mod_and_n1_exact)
 TEST_CASE ("mul/basecase", sqr_basecase_vs_mul)
 TEST_CASE ("mul/dispatch", mul_dispatch_vs_basecase_cross)
 TEST_CASE ("mul/fft", mul_fft_vs_toom8h)
 TEST_CASE ("mul/fft", sqr_fft_vs_toom8)
 TEST_CASE ("mul/hard_direct_all_sizes", mul_hard_direct_n1_to_n19)
 TEST_CASE ("mul/hard_threshold_boundary", mul_hard_boundary_vs_basecase)
 TEST_CASE ("mul/mullo", mullo_vs_mul_truncation)
 TEST_CASE ("mul/sqr_dispatch", sqr_dispatch_vs_mul)
 TEST_CASE ("mul/sqr_toom_small", sqr_toom_small_direct)
 TEST_CASE ("mul/toom_splits", toom53_toom62_integer_splits)
 TEST_CASE ("mul/unbalanced", mul_unbalanced_cross)
void test_mul (void)

函数说明

◆ check_prod_mod()

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 )
static

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

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

46 {
47 TEST_CHECK_MSG(mod_is_product(dst, na + nb, a, na, b, nb), "modular product check");
48 mp_size_t pl = norm_len(dst, na + nb);
49 TEST_CHECK(pl == na + nb || pl == na + nb - 1);
50}
uint64_t mp_size_t
定义 lmmp.h:93
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38

引用了 check_prod_mod(), TEST_CHECK , 以及 TEST_CHECK_MSG.

被这些函数引用 check_prod_mod(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

◆ limbs_same()

bool limbs_same ( const mp_limb_t * x,
const mp_limb_t * y,
mp_size_t n )
static

在文件 test_mul.c 第 53 行定义.

53 {
54 return memcmp(x, y, (size_t)n * sizeof(mp_limb_t)) == 0;
55}
uint64_t mp_limb_t
定义 lmmp.h:92
#define n

引用了 limbs_same() , 以及 n.

被这些函数引用 limbs_same(), limbs_same(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

◆ TEST_CASE() [1/12]

TEST_CASE ( "mul/basecase" ,
mul_basecase_mod_and_n1_exact  )

在文件 test_mul.c 第 57 行定义.

57 {
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);
64 lmmp_mul_basecase_(dst, a, na, b, nb);
65 check_prod_mod(a, (mp_size_t)na, b, (mp_size_t)nb, dst);
66
67 // n=1:与 mullh 精确比对
68 if (na == 1 && nb == 1) {
69 mp_limb_t ref[2];
70 lmmp_mullh_(a[0], b[0], ref);
71 TEST_CHECK_EQ(dst[0], ref[0]);
72 TEST_CHECK_EQ(dst[1], ref[1]);
73 }
74 lmmp_free(a); lmmp_free(b); lmmp_free(dst);
75 }
76 }
77 // 写死常数锚点:(2^64-1)^2(低 2 limbs)与 (2^63+1)*(2^64-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;
80 lmmp_mul_basecase_(d, a, 1, b, 1);
81 TEST_CHECK_EQ(d[0], 1ull);
82 TEST_CHECK_EQ(d[1], ~(u64)0 - 1);
83 a[0] = ((u64)1 << 63) + 1;
84 lmmp_mul_basecase_(d, a, 1, b, 1);
85 // (2^63+1)*(2^64-1) = 2^127 + 2^63 - 1
86 TEST_CHECK_EQ(d[0], 0x7FFFFFFFFFFFFFFFull);
87 TEST_CHECK_EQ(d[1], 0x8000000000000000ull);
88 lmmp_free(a); lmmp_free(b); lmmp_free(d);
89}
#define lmmp_mullh_
mp_limb_t * mp_ptr
定义 lmmp.h:96
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
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]
#define TEST_CHECK_EQ(a, b)
定义 test.h:39
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)

引用了 check_prod_mod(), lmmp_free(), lmmp_mul_basecase_(), lmmp_mullh_, TEST_CASE , 以及 TEST_CHECK_EQ.

函数调用图:

◆ TEST_CASE() [2/12]

TEST_CASE ( "mul/basecase" ,
sqr_basecase_vs_mul  )

在文件 test_mul.c 第 91 行定义.

91 {
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);
96 lmmp_sqr_basecase_(dst, a, na);
97 lmmp_mul_(ref, a, na, a, na); // 交叉:平方 == 自乘
98 TEST_CHECK(limbs_same(dst, ref, 2 * na));
99 check_prod_mod(a, (mp_size_t)na, a, (mp_size_t)na, dst);
100 lmmp_free(a); lmmp_free(dst); lmmp_free(ref);
101 }
102}
void lmmp_sqr_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
基础平方运算 [dst,2*na] = [numa,na]^2
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]
static bool limbs_same(const mp_limb_t *x, const mp_limb_t *y, mp_size_t n)

引用了 check_prod_mod(), limbs_same(), lmmp_free(), lmmp_mul_(), lmmp_sqr_basecase_(), TEST_CASE , 以及 TEST_CHECK.

函数调用图:

◆ TEST_CASE() [3/12]

TEST_CASE ( "mul/dispatch" ,
mul_dispatch_vs_basecase_cross  )

在文件 test_mul.c 第 104 行定义.

104 {
105 // toom 域内分派器 vs basecase(匹配的独立参考;O(n²) 成本限规模)
106 u64 seed = 0x0123456789abcdefull;
107 const mp_size_t sizes[] = {
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
110 };
111 for (size_t na_index = 0; na_index < ARRAY_SIZE(sizes); ++na_index) {
112 mp_size_t na = sizes[na_index];
113 for (int t = 0; t < 3; ++t) {
114 mp_size_t nb = (mp_size_t)((u64)na * (t == 0 ? 1 : (t == 1 ? 2 : 3)) / (t == 0 ? 1 : (t == 1 ? 3 : 4)));
115 if (nb < 1) nb = 1;
116 if (nb > na) nb = na;
117 // basecase 为 O(n^2),限制总规模。
118 if ((u64)na * nb > 1200000ull) continue;
119
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);
124 lmmp_mul_(dst, a, na, b, nb);
125 lmmp_mul_basecase_(ref, a, na, b, nb);
126 TEST_CHECK(limbs_same(dst, ref, na + nb));
127 check_prod_mod(a, na, b, nb, dst);
128 lmmp_free(a); lmmp_free(b); lmmp_free(dst); lmmp_free(ref);
129 }
130 }
131}
#define t
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40

引用了 ARRAY_SIZE, check_prod_mod(), limbs_same(), lmmp_free(), lmmp_mul_(), lmmp_mul_basecase_(), t, TEST_CASE , 以及 TEST_CHECK.

函数调用图:

◆ TEST_CASE() [4/12]

TEST_CASE ( "mul/fft" ,
mul_fft_vs_toom8h  )

在文件 test_mul.c 第 133 行定义.

133 {
134 // FFT 域(n >= MUL_FFT_THRESHOLD 分派器选 FFT):与纯 Toom 递归直调
135 // toom8h 互比(同规模独立算法族;basecase 在该规模不匹配,禁用)。
136 // toom8h 契约:nb>=86、na<=4nb(原生比例含平衡与 4:1 不平衡)。
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},
141 };
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);
148 lmmp_mul_(dst, a, s.na, b, s.nb); // 分派器 → FFT
149 lmmp_mul_toom8h_(ref, a, s.na, b, s.nb); // 纯 Toom 递归
150 TEST_CHECK_MSG(limbs_same(dst, ref, s.na + s.nb), "fft vs toom8h");
151 check_prod_mod(a, s.na, b, s.nb, dst);
152 lmmp_free(a); lmmp_free(b); lmmp_free(dst); lmmp_free(ref);
153 }
154}
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,...
#define s

引用了 ARRAY_SIZE, check_prod_mod(), limbs_same(), lmmp_free(), lmmp_mul_(), lmmp_mul_toom8h_(), s, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [5/12]

TEST_CASE ( "mul/fft" ,
sqr_fft_vs_toom8  )

在文件 test_mul.c 第 156 行定义.

156 {
157 // FFT 域平方(n >= SQR_FFT_THRESHOLD):sqr_(→ sqr_fft)vs sqr_toom8_
158 // 直调(SQR_TOOM8_MAX ≈ 195 << SQR_FFT_THRESHOLD,子问题永不进 FFT)
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) {
162 mp_size_t n = n_values[n_index];
163 mp_ptr a = alloc_limbs(n);
164 mp_ptr dst = alloc_limbs(2 * n + 2), ref = alloc_limbs(2 * n + 2);
165 random_limbs(a, n, &seed);
166 lmmp_sqr_(dst, a, n);
167 lmmp_sqr_toom8_(ref, a, n);
168 TEST_CHECK_MSG(limbs_same(dst, ref, 2 * n), "sqr_fft vs sqr_toom8");
169 check_prod_mod(a, n, a, n, dst);
170 lmmp_free(a); lmmp_free(dst); lmmp_free(ref);
171 }
172}
#define lmmp_sqr_
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点)

引用了 ARRAY_SIZE, check_prod_mod(), limbs_same(), lmmp_free(), lmmp_sqr_, lmmp_sqr_toom8_(), n, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [6/12]

TEST_CASE ( "mul/hard_direct_all_sizes" ,
mul_hard_direct_n1_to_n19  )

在文件 test_mul.c 第 202 行定义.

202 {
203 /* 硬编码路径全规模直测: n=1..19 经顶层 lmmp_mul_n_/lmmp_sqr_ (阈值下
204 必走硬编码调度) 对照 basecase 与模检查, 覆盖随机/全 1/全 0xFF/最高位等
205 触发进位链极端的输入模式 */
206 u64 seed = 0x0d1c2b3a49586775ull;
207 for (mp_size_t n = 1; n <= LMMP_MUL_HARD_MAX_N; n++) {
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);
211 for (mp_size_t i = 0; i < n; i++) {
212 switch (pat) {
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;
219 }
220 }
221 lmmp_mul_n_(dst, a, b, n);
222 lmmp_mul_basecase_(ref, a, n, b, n);
223 TEST_CHECK(limbs_same(dst, ref, 2 * n));
224 // 模检查(pattern 输入可能非归一化,用值语义仍成立)
225 TEST_CHECK(mod_is_product(dst, 2 * n, a, n, b, n));
226
227 lmmp_sqr_(dst, a, n);
228 lmmp_mul_basecase_(ref, a, n, a, n);
229 TEST_CHECK(limbs_same(dst, ref, 2 * n));
230 TEST_CHECK(mod_is_product(dst, 2 * n, a, n, a, n));
231 lmmp_free(a); lmmp_free(b); lmmp_free(dst); lmmp_free(ref);
232 }
233 }
234}
#define lmmp_mul_n_
#define LMMP_MUL_HARD_MAX_N
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 limbs_same(), lmmp_free(), lmmp_mul_basecase_(), LMMP_MUL_HARD_MAX_N, lmmp_mul_n_, lmmp_sqr_, n, TEST_CASE , 以及 TEST_CHECK.

函数调用图:

◆ TEST_CASE() [7/12]

TEST_CASE ( "mul/hard_threshold_boundary" ,
mul_hard_boundary_vs_basecase  )

在文件 test_mul.c 第 174 行定义.

174 {
175 /* 覆盖硬编码函数(hardcoded n=1..19)经 toom 递归的边界尺寸:
176 toom22 递归子规模 n/2 恰好落在 19/20 两侧 */
177 u64 seed = 0x0f1e2d3c4b5a6978ull;
178 const mp_size_t sizes[] = {
179 19, 20, 21, 22, 37, 38, 39, 40, 41, 42, 63, 64, 65, 66
180 };
181 for (size_t n_index = 0; n_index < ARRAY_SIZE(sizes); ++n_index) {
182 mp_size_t n = 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);
188 lmmp_mul_n_(dst, a, b, n);
189 lmmp_mul_basecase_(ref, a, n, b, n);
190 TEST_CHECK(limbs_same(dst, ref, 2 * n));
191 check_prod_mod(a, n, b, n, dst);
192
193 lmmp_sqr_(dst, a, n);
194 lmmp_mul_(ref, a, n, a, n); // sqr vs 自乘交叉
195 TEST_CHECK(limbs_same(dst, ref, 2 * n));
196 check_prod_mod(a, n, a, n, dst);
197 lmmp_free(a); lmmp_free(b); lmmp_free(dst); lmmp_free(ref);
198 }
199 }
200}

引用了 ARRAY_SIZE, check_prod_mod(), limbs_same(), lmmp_free(), lmmp_mul_(), lmmp_mul_basecase_(), lmmp_mul_n_, lmmp_sqr_, n, t, TEST_CASE , 以及 TEST_CHECK.

函数调用图:

◆ TEST_CASE() [8/12]

TEST_CASE ( "mul/mullo" ,
mullo_vs_mul_truncation  )

在文件 test_mul.c 第 275 行定义.

275 {
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) {
279 mp_size_t n = 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);
283 lmmp_mul_(full, a, n, b, n); // 全积参考(库路径)
284 lmmp_mullo_(dst, a, b, n); // 低 n limbs == 全积截断
285 TEST_CHECK(limbs_same(dst, full, n));
286 lmmp_free(a); lmmp_free(b); lmmp_free(dst); lmmp_free(full);
287 }
288}
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

引用了 ARRAY_SIZE, limbs_same(), lmmp_free(), lmmp_mul_(), lmmp_mullo_(), n, TEST_CASE , 以及 TEST_CHECK.

函数调用图:

◆ TEST_CASE() [9/12]

TEST_CASE ( "mul/sqr_dispatch" ,
sqr_dispatch_vs_mul  )

在文件 test_mul.c 第 290 行定义.

290 {
291 // sqr vs 自乘(两条分派路径)至 FFT 域;toom 域附 basecase 精确
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) {
295 mp_size_t n = 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);
298 lmmp_sqr_(dst, a, n);
299 lmmp_mul_(ref, a, n, a, n);
300 TEST_CHECK(limbs_same(dst, ref, 2 * n));
301 if ((u64)n * n <= 1500000ull) {
302 lmmp_mul_basecase_(ref, a, n, a, n);
303 TEST_CHECK(limbs_same(dst, ref, 2 * n));
304 }
305 lmmp_free(a); lmmp_free(dst); lmmp_free(ref);
306 }
307}

引用了 ARRAY_SIZE, limbs_same(), lmmp_free(), lmmp_mul_(), lmmp_mul_basecase_(), lmmp_sqr_, n, TEST_CASE , 以及 TEST_CHECK.

函数调用图:

◆ TEST_CASE() [10/12]

TEST_CASE ( "mul/sqr_toom_small" ,
sqr_toom_small_direct  )

在文件 test_mul.c 第 331 行定义.

331 {
332 const struct {
333 mp_size_t min_na;
334 void (*sqr)(mp_ptr, mp_srcptr, mp_size_t);
335 } cases[] = {{4, lmmp_sqr_toom2_}, {5, lmmp_sqr_toom3_}, {10, lmmp_sqr_toom4_}};
336 u64 seed = 0x8ec2d36d49433ba9ull;
337 mp_limb_t a[32], dst[65], ref[64];
338 for (size_t i = 0; i < ARRAY_SIZE(cases); ++i) {
339 for (mp_size_t na = cases[i].min_na; na <= ARRAY_SIZE(a); ++na) {
340 random_limbs(a, na, &seed);
341 dst[2 * na] = LIMB_MAX;
342 cases[i].sqr(dst, a, na);
343 lmmp_sqr_basecase_(ref, a, na);
344 TEST_CHECK(limbs_same(dst, ref, 2 * na));
345 TEST_CHECK(dst[2 * na] == LIMB_MAX);
346 }
347 }
348}
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define LIMB_MAX
定义 lmmp.h:105
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_sqr_toom4_(mp_ptr dst, mp_srcptr numa, mp_size_t an)
Toom-4平方运算 [dst,2*na] = [numa,na]^2

引用了 ARRAY_SIZE, LIMB_MAX, limbs_same(), lmmp_sqr_basecase_(), lmmp_sqr_toom2_(), lmmp_sqr_toom3_(), lmmp_sqr_toom4_(), TEST_CASE , 以及 TEST_CHECK.

函数调用图:

◆ TEST_CASE() [11/12]

TEST_CASE ( "mul/toom_splits" ,
toom53_toom62_integer_splits  )

在文件 test_mul.c 第 309 行定义.

309 {
310 const struct {
311 mp_size_t na, nb;
313 } shapes[] = {
314 {13, 7, lmmp_mul_toom53_}, {14, 9, lmmp_mul_toom53_},
315 {11, 3, lmmp_mul_toom62_}, {18, 4, lmmp_mul_toom62_},
316 };
317 u64 seed = 0x84f4756eb3c2ab17ull;
318 mp_limb_t a[18], b[9], dst[24], ref[23];
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);
323 dst[na + nb] = LIMB_MAX;
324 shapes[i].mul(dst, a, na, b, nb);
325 lmmp_mul_basecase_(ref, a, na, b, nb);
326 TEST_CHECK(limbs_same(dst, ref, na + nb));
327 TEST_CHECK(dst[na + nb] == LIMB_MAX);
328 }
329}
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_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]

引用了 ARRAY_SIZE, LIMB_MAX, limbs_same(), lmmp_mul_basecase_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), TEST_CASE , 以及 TEST_CHECK.

函数调用图:

◆ TEST_CASE() [12/12]

TEST_CASE ( "mul/unbalanced" ,
mul_unbalanced_cross  )

在文件 test_mul.c 第 236 行定义.

236 {
237 // 不平衡输入:toom 域用 basecase(匹配),FFT 域用 toom8h(匹配,
238 // 契约 na<=4nb);均附模检查
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},
244 };
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);
252 lmmp_mul_(dst, a, c.na, b, c.nb);
253 lmmp_mul_basecase_(ref, a, c.na, b, c.nb);
254 TEST_CHECK(limbs_same(dst, ref, c.na + c.nb));
255 check_prod_mod(a, c.na, b, c.nb, dst);
256 lmmp_free(a); lmmp_free(b); lmmp_free(dst); lmmp_free(ref);
257 }
258 const Case fft_domain[] = {
259 {2316, 800}, {2400, 900}, {3116, 800}, {4096, 1024}, {6000, 1600},
260 };
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);
267 lmmp_mul_(dst, a, c.na, b, c.nb); // 分派器(FFT 侧)
268 lmmp_mul_toom8h_(ref, a, c.na, b, c.nb); // Toom 侧(na<=4nb ✓)
269 TEST_CHECK_MSG(limbs_same(dst, ref, c.na + c.nb), "unbalanced fft vs toom8h");
270 check_prod_mod(a, c.na, b, c.nb, dst);
271 lmmp_free(a); lmmp_free(b); lmmp_free(dst); lmmp_free(ref);
272 }
273}

引用了 ARRAY_SIZE, check_prod_mod(), limbs_same(), lmmp_free(), lmmp_mul_(), lmmp_mul_basecase_(), lmmp_mul_toom8h_(), TEST_CASE, TEST_CHECK , 以及 TEST_CHECK_MSG.

函数调用图:

◆ test_mul()

void test_mul ( void )

在文件 test_mul.c 第 350 行定义.

350 {
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);
363}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_mul() , 以及 TEST_RUN.

被这些函数引用 main() , 以及 test_mul().

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