LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_mul_toom68.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/* Toom-6.5 / Toom-8.5 乘法与 Toom-6/8 平方测试:
24 1) 内核直调覆盖原生不平衡全比例范围((p,q) 切分阶梯各档)
25 2) basecase 精确对拍 + 模检查(独立路径;含负系数插值路径)
26 3) 新阈值边界(MUL_TOOM6H/8H、SQR_TOOM6/8 的 ±1 经完整分派)
27 4) 极端输入(全 1 / 全 FF) */
28
29#include "lmmp/lmmpn.h"
30#include "mparam.h"
31#include "cases.h"
33
34#include <string.h>
35
36static void fill_pattern(mp_ptr p, size_t n, mp_limb_t pat) {
37 for (size_t i = 0; i < n; ++i) p[i] = pat;
38}
39
40/* 与 basecase 精确对拍 + 模检查(两条独立实现路径;按契约有效长度) */
41static void check_vs_oracle(const char* tag, mp_ptr a, mp_size_t na, mp_ptr b, mp_size_t nb, void (*fn)(mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t)) {
42 mp_ptr dst = alloc_limbs(na + nb);
43 mp_ptr ref = alloc_limbs(na + nb + 1);
44 fn(dst, a, na, b, nb);
45 lmmp_mul_basecase_(ref, a, na, b, nb);
46 bool ok = memcmp(dst, ref, (size_t)(na + nb) * 8) == 0;
47 if (!ok || !mod_is_product(dst, na + nb, a, na, b, nb)) TEST_CHECK_MSG(false, tag);
48 else TEST_CHECK(true);
49 lmmp_free(dst);
50 lmmp_free(ref);
51}
52
53/* 内核直调 vs 独立分派路径(尺寸区间落在 toom44 及以下,路径独立) */
54static void check_vs_dispatch(const char* tag, mp_ptr a, mp_size_t na, mp_ptr b, mp_size_t nb, void (*kfn)(mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t)) {
55 mp_ptr r1 = alloc_limbs(na + nb);
56 mp_ptr r2 = alloc_limbs(na + nb);
57 kfn(r1, a, na, b, nb);
58 lmmp_mul_(r2, a, na, b, nb);
59 if (memcmp(r1, r2, (size_t)(na + nb) * sizeof(mp_limb_t)) != 0) TEST_CHECK_MSG(false, tag);
60 else TEST_CHECK(true);
63}
64
65/* toom6h 原生比例范围:an/bn ∈ [1, 17/6),an*3 < 8*bn 要求 bn < 46 时
66 比例 < 8/3 —— 阶梯各档代表比例 */
67const double kRatios6[] = {1.0, 1.05, 1.15, 1.3, 1.32, 1.45, 1.48, 1.8, 1.88, 2.0, 2.11, 2.4, 2.6, 2.82};
68/* toom8h 原生比例范围:an/bn ∈ [1, 4] */
69const double kRatios8[] = {1.0, 1.1, 1.22, 1.35, 1.5, 1.64, 1.8, 2.0, 2.24, 2.5, 2.85, 3.1, 3.5, 3.99};
70
71static bool in_6h_range(mp_size_t na, mp_size_t nb) {
72 /* 与内核契约一致:比例 < 17/6 且 nb>=46(原 8/3 宽限与 nb 42..45
73 保证域外区间随契约收紧移除) */
74 return na >= nb && nb >= 46 && 6 * na < 17 * nb;
75}
76
77TEST_CASE("mul/toom68", toom6h_kernel_full_range) {
78 u64 seed = 0x6c6f666572746f6dull;
79 int checked = 0;
80 for (mp_size_t nb = 43; nb <= 92; ++nb) {
81 for (size_t r_index = 0; r_index < ARRAY_SIZE(kRatios6); ++r_index) {
82 double r = kRatios6[r_index];
83 mp_size_t na = (mp_size_t)(nb * r);
84 if (na < nb || !in_6h_range(na, nb)) continue;
85 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb);
86 random_limbs(a, na, &seed);
87 random_limbs(b, nb, &seed);
88 check_vs_dispatch("toom6h vs dispatch", a, na, b, nb, lmmp_mul_toom6h_);
89 lmmp_free(a);
90 lmmp_free(b);
91 ++checked;
92 }
93 }
94 TEST_CHECK_MSG(checked > 500, "覆盖数不足");
95}
96
97TEST_CASE("mul/toom68", toom8h_kernel_full_range) {
98 u64 seed = 0x8a8f686967687475ull;
99 int checked = 0;
100 for (mp_size_t nb = 86; nb <= 140; ++nb) { /* 86=契约下界 */
101 for (size_t r_index = 0; r_index < ARRAY_SIZE(kRatios8); ++r_index) {
102 double r = kRatios8[r_index];
103 mp_size_t na = (mp_size_t)(nb * r);
104 if (na < nb || na > 4 * nb) continue;
105 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb);
106 random_limbs(a, na, &seed);
107 random_limbs(b, nb, &seed);
108 check_vs_dispatch("toom8h vs dispatch", a, na, b, nb, lmmp_mul_toom8h_);
109 lmmp_free(a);
110 lmmp_free(b);
111 ++checked;
112 }
113 }
114 TEST_CHECK_MSG(checked > 500, "覆盖数不足");
115}
116
117TEST_CASE("mul/toom68", sqr_toom6_kernel) {
118 u64 seed = 0x72713a736972716eull;
119 for (mp_size_t n = 26; n <= 120; ++n) {
120 mp_ptr a = alloc_limbs(n);
121 mp_ptr r1 = alloc_limbs(2 * n), r2 = alloc_limbs(2 * n);
122 random_limbs(a, n, &seed);
123 lmmp_sqr_toom6_(r1, a, n);
124 lmmp_sqr_(r2, a, n);
125 if (memcmp(r1, r2, (size_t)(2 * n) * sizeof(mp_limb_t)) != 0) TEST_CHECK_MSG(false, "sqr_toom6 mismatch");
126 else TEST_CHECK(true);
127 lmmp_free(a);
128 lmmp_free(r1);
129 lmmp_free(r2);
130 }
131}
132
133TEST_CASE("mul/toom68", sqr_toom8_kernel) {
134 u64 seed = 0x33362e35392e3361ull;
135 for (mp_size_t n = 51; n <= 160; ++n) {
136 if (n == 57) continue; /* 契约排除的 s=1 退化点(16 点插值需 2s>3) */
137 mp_ptr a = alloc_limbs(n);
138 mp_ptr r1 = alloc_limbs(2 * n), r2 = alloc_limbs(2 * n);
139 random_limbs(a, n, &seed);
140 lmmp_sqr_toom8_(r1, a, n);
141 lmmp_sqr_(r2, a, n);
142 if (memcmp(r1, r2, (size_t)(2 * n) * sizeof(mp_limb_t)) != 0) TEST_CHECK_MSG(false, "sqr_toom8 mismatch");
143 else TEST_CHECK(true);
144 lmmp_free(a);
145 lmmp_free(r1);
146 lmmp_free(r2);
147 }
148}
149
150TEST_CASE("mul/toom68", toom6h_oracle_balanced_and_unbalanced) {
151 u64 seed = 0x21726f74616d6f6full;
152 /* 平衡 + 阶梯代表比例(负系数插值路径由随机符号覆盖) */
153 mp_size_t sizes[] = {43, 47, 55, 64, 73, 89};
154 for (size_t nb_index = 0; nb_index < ARRAY_SIZE(sizes); ++nb_index) {
155 mp_size_t nb = sizes[nb_index];
156 const double r_values[] = {1.0, 1.32, 1.88, 2.82};
157 for (size_t r_index = 0; r_index < ARRAY_SIZE(r_values); ++r_index) {
158 double r = r_values[r_index];
159 mp_size_t na = (mp_size_t)(nb * r);
160 if (!in_6h_range(na, nb)) continue;
161 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb);
162 random_limbs(a, na, &seed);
163 random_limbs(b, nb, &seed);
164 check_vs_oracle("toom6h vs oracle", a, na, b, nb, lmmp_mul_toom6h_);
165 lmmp_free(a);
166 lmmp_free(b);
167 }
168 }
169}
170
171TEST_CASE("mul/toom68", toom8h_oracle_balanced_and_unbalanced) {
172 u64 seed = 0x386f74206d6f6f6dull;
173 mp_size_t sizes[] = {87, 95, 110, 130};
174 for (size_t nb_index = 0; nb_index < ARRAY_SIZE(sizes); ++nb_index) {
175 mp_size_t nb = sizes[nb_index];
176 const double r_values[] = {1.0, 1.64, 2.85, 3.99};
177 for (size_t r_index = 0; r_index < ARRAY_SIZE(r_values); ++r_index) {
178 double r = r_values[r_index];
179 mp_size_t na = (mp_size_t)(nb * r);
180 if (na > 4 * nb) continue;
181 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb);
182 random_limbs(a, na, &seed);
183 random_limbs(b, nb, &seed);
184 check_vs_oracle("toom8h vs oracle", a, na, b, nb, lmmp_mul_toom8h_);
185 lmmp_free(a);
186 lmmp_free(b);
187 }
188 }
189}
190
191TEST_CASE("mul/toom68", thresholds_boundary_via_dispatch) {
192 u64 seed = 0x7468726573686f6cull;
193 /* 阈值 ±1 经 lmmp_mul_n_/lmmp_sqr_ 完整分派对拍 oracle */
194 struct threshold_case {
195 mp_size_t base;
196 int is_sqr;
197 } bounds[] = {
202 };
203 for (size_t bd_index = 0; bd_index < ARRAY_SIZE(bounds); ++bd_index) {
204 const struct threshold_case bd = bounds[bd_index];
205 for (int d = -1; d <= 1; ++d) {
206 if (bd.base + (mp_size_t)d < 1) continue;
207 mp_size_t n = bd.base + d;
208 if (bd.is_sqr) {
209 mp_ptr a = alloc_limbs(n);
210 mp_ptr r = alloc_limbs(2 * n), ref = alloc_limbs(2 * n + 1);
211 random_limbs(a, n, &seed);
212 lmmp_sqr_(r, a, n);
213 lmmp_mul_basecase_(ref, a, n, a, n);
214 bool ok = memcmp(r, ref, (size_t)(2 * n) * 8) == 0;
215 if (!ok || !mod_is_product(r, 2 * n, a, n, a, n))
216 TEST_CHECK_MSG(false, "sqr threshold boundary mismatch");
217 else TEST_CHECK(true);
218 lmmp_free(a);
219 lmmp_free(r);
220 lmmp_free(ref);
221 } else {
222 mp_ptr a = alloc_limbs(n), b = alloc_limbs(n);
223 mp_ptr r = alloc_limbs(2 * n), ref = alloc_limbs(2 * n + 1);
224 random_limbs(a, n, &seed);
225 random_limbs(b, n, &seed);
226 lmmp_mul_n_(r, a, b, n);
227 lmmp_mul_basecase_(ref, a, n, b, n);
228 bool ok = memcmp(r, ref, (size_t)(2 * n) * 8) == 0;
229 if (!ok || !mod_is_product(r, 2 * n, a, n, b, n))
230 TEST_CHECK_MSG(false, "mul threshold boundary mismatch");
231 else TEST_CHECK(true);
232 lmmp_free(a);
233 lmmp_free(b);
234 lmmp_free(r);
235 lmmp_free(ref);
236 }
237 }
238 }
239}
240
241TEST_CASE("mul/toom68", extended_unbalanced_window_via_dispatch) {
242 /* 扩窗路径:nb >= MUL_TOOM6H 且比例 < 4 时经 lmmp_mul_ 走 6h/8h
243 (比例 < 17/6 走 6h,至 4 走 8h),oracle 对拍 */
244 u64 seed = 0x6e7562616c616e63ull;
246 const double r_values[] = {1.0, 1.2, 1.32, 1.6, 2.0, 2.5, 2.82, 3.2, 3.99};
247 for (size_t r_index = 0; r_index < ARRAY_SIZE(r_values); ++r_index) {
248 double r = r_values[r_index];
249 mp_size_t na = (mp_size_t)(nb0 * r);
250 if (na >= 4 * nb0) na = 4 * nb0 - 1;
251 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb0);
252 random_limbs(a, na, &seed);
253 random_limbs(b, nb0, &seed);
254 check_vs_oracle("extended window vs oracle", a, na, b, nb0, lmmp_mul_);
255 lmmp_free(a);
256 lmmp_free(b);
257 }
258}
259
260TEST_CASE("mul/toom68", extreme_patterns) {
261 u64 seed = 0x787472656d653031ull;
262 /* 全 1 / 全 FF:进位链最长的病态输入 */
263 struct limb_pattern {
264 mp_limb_t pat;
265 } pats[] = {{0x1111111111111111ull}, {LIMB_MAX}};
266 for (size_t pt_index = 0; pt_index < ARRAY_SIZE(pats); ++pt_index) {
267 const struct limb_pattern pt = pats[pt_index];
268 const mp_size_t nb_values[] = {(mp_size_t)64, (mp_size_t)100};
269 for (size_t nb_index = 0; nb_index < ARRAY_SIZE(nb_values); ++nb_index) {
270 mp_size_t nb = nb_values[nb_index];
271 const double r_values[] = {1.0, 2.0, 2.8};
272 for (size_t r_index = 0; r_index < ARRAY_SIZE(r_values); ++r_index) {
273 double r = r_values[r_index];
274 mp_size_t na = (mp_size_t)(nb * r);
275 if (!in_6h_range(na, nb)) continue;
276 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb);
277 fill_pattern(a, na, pt.pat);
278 fill_pattern(b, nb, pt.pat);
279 check_vs_oracle("toom6h extreme", a, na, b, nb, lmmp_mul_toom6h_);
280 lmmp_free(a);
281 lmmp_free(b);
282 }
283 }
284 const mp_size_t nb_values2[] = {(mp_size_t)104, (mp_size_t)160};
285 for (size_t nb_index = 0; nb_index < ARRAY_SIZE(nb_values2); ++nb_index) {
286 mp_size_t nb = nb_values2[nb_index];
287 const double r_values2[] = {1.0, 2.5, 3.9};
288 for (size_t r_index = 0; r_index < ARRAY_SIZE(r_values2); ++r_index) {
289 double r = r_values2[r_index];
290 mp_size_t na = (mp_size_t)(nb * r);
291 if (na > 4 * nb) continue;
292 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb);
293 fill_pattern(a, na, pt.pat);
294 fill_pattern(b, nb, pt.pat);
295 check_vs_oracle("toom8h extreme", a, na, b, nb, lmmp_mul_toom8h_);
296 lmmp_free(a);
297 lmmp_free(b);
298 }
299 }
300 const mp_size_t n_values[] = {(mp_size_t)60, (mp_size_t)120};
301 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
302 mp_size_t n = n_values[n_index];
303 mp_ptr a = alloc_limbs(n);
304 mp_ptr r1 = alloc_limbs(2 * n), r2 = alloc_limbs(2 * n);
305 fill_pattern(a, n, pt.pat);
306 lmmp_sqr_toom6_(r1, a, n);
307 lmmp_sqr_(r2, a, n);
308 if (memcmp(r1, r2, (size_t)(2 * n) * sizeof(mp_limb_t)) != 0) TEST_CHECK_MSG(false, "sqr6 extreme mismatch");
309 else TEST_CHECK(true);
310 lmmp_free(a);
311 lmmp_free(r1);
312 lmmp_free(r2);
313 }
314 }
315 (void)seed;
316}
317
318void test_mul_toom68(void) {
319 TEST_RUN("mul/toom68", toom6h_kernel_full_range);
320 TEST_RUN("mul/toom68", toom8h_kernel_full_range);
321 TEST_RUN("mul/toom68", sqr_toom6_kernel);
322 TEST_RUN("mul/toom68", sqr_toom8_kernel);
323 TEST_RUN("mul/toom68", toom6h_oracle_balanced_and_unbalanced);
324 TEST_RUN("mul/toom68", toom8h_oracle_balanced_and_unbalanced);
325 TEST_RUN("mul/toom68", thresholds_boundary_via_dispatch);
326 TEST_RUN("mul/toom68", extended_unbalanced_window_via_dispatch);
327 TEST_RUN("mul/toom68", extreme_patterns);
328}
#define lmmp_mul_n_
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define LIMB_MAX
定义 lmmp.h:105
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)
#define SQR_TOOM6_THRESHOLD
#define MUL_TOOM8H_THRESHOLD
#define SQR_TOOM8_THRESHOLD
#define MUL_TOOM6H_THRESHOLD
void test_mul_toom68(void)
void lmmp_mul_toom6h_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-6.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±4,...
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_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_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_sqr_toom6_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-6平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±4,±2,±1,±1/2,±1/4,0,无inf点)
#define r2
#define r1
#define n
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_RUN(category, name)
定义 test.h:36
const double kRatios8[]
static void check_vs_dispatch(const char *tag, mp_ptr a, mp_size_t na, mp_ptr b, mp_size_t nb, void(*kfn)(mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t))
const double kRatios6[]
static void fill_pattern(mp_ptr p, size_t n, mp_limb_t pat)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void check_vs_oracle(const char *tag, mp_ptr a, mp_size_t na, mp_ptr b, mp_size_t nb, void(*fn)(mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t))
static bool in_6h_range(mp_size_t na, mp_size_t nb)