LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
sqr_toom6.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#include "impl/mul_hard.h"
24#include "mparam.h"
25#include "lmmpn/toom_interp.h"
26
27/* sqr_toom6 递归可达的最大子问题规模(sqr8 接管前) */
28#define SQR_TOOM6_MAX ((SQR_TOOM8_THRESHOLD + 6 * 2 - 1 + 5) / 6)
29#define MAYBE_sqr_basecase (SQR_TOOM6_THRESHOLD < 6 * SQR_TOOM22_THRESHOLD)
30#define MAYBE_sqr_above_basecase (SQR_TOOM6_MAX >= SQR_TOOM22_THRESHOLD)
31#define MAYBE_sqr_toom2 (SQR_TOOM6_THRESHOLD < 6 * SQR_TOOM33_THRESHOLD)
32#define MAYBE_sqr_above_toom2 (SQR_TOOM6_MAX >= SQR_TOOM33_THRESHOLD)
33#define MAYBE_sqr_toom3 (SQR_TOOM6_THRESHOLD < 6 * SQR_TOOM44_THRESHOLD)
34#define MAYBE_sqr_above_toom3 (SQR_TOOM6_MAX >= SQR_TOOM44_THRESHOLD)
35#define MAYBE_sqr_above_toom4 (SQR_TOOM6_MAX >= SQR_TOOM6_THRESHOLD)
36
37#define lmmp_sqr_(dst, numa, n) \
38 if (MAYBE_sqr_basecase && (!MAYBE_sqr_above_basecase || (n) < SQR_TOOM22_THRESHOLD)) \
39 lmmp_sqr_hard_n_((dst), (numa), (n)); \
40 else if (MAYBE_sqr_toom2 && (!MAYBE_sqr_above_toom2 || (n) < SQR_TOOM33_THRESHOLD)) \
41 lmmp_sqr_toom2_((dst), (numa), (n)); \
42 else if (MAYBE_sqr_toom3 && (!MAYBE_sqr_above_toom3 || (n) < SQR_TOOM44_THRESHOLD)) \
43 lmmp_sqr_toom3_((dst), (numa), (n)); \
44 else if (!MAYBE_sqr_above_toom4 || (n) < SQR_TOOM6_THRESHOLD) \
45 lmmp_sqr_toom4_((dst), (numa), (n)); \
46 else \
47 lmmp_sqr_toom6_((dst), (numa), (n))
48
49/*
50Evaluate in: +4, -4, +2, -2, +1, -1, +1/2, -1/2, +1/4, -1/4, 0
51(平方无 inf 点:(-v)^2 = v^2,符号恒正)
52*/
53
55 lmmp_param_assert(na > 0);
56 lmmp_param_assert(dst != NULL);
57 lmmp_param_assert(numa != NULL);
58 lmmp_param_assert(na > 25);
59 mp_size_t n, s;
60
61 n = 1 + (na - 1) / 6;
62 s = na - 5 * n;
63
64 lmmp_debug_assert(0 < s && s <= n);
65
66#define r4 (dst + 3 * n) /* 3n+1 */
67#define r2 (dst + 7 * n) /* 3n+1 */
68#define r0 (dst + 11 * n) /* 2s */
69#define r5 (scratch) /* 3n+1 */
70#define r3 (scratch + 3 * n + 1) /* 3n+1 */
71#define r1 (scratch + 6 * n + 2) /* 3n+1 */
72#define v0 (dst + 7 * n) /* n+1 */
73#define v2 (dst + 9 * n + 2) /* n+1 */
74#define wse (scratch + 9 * n + 3) /* 3n+1 */
75
76 /* scratch 总需求 12n+6 limbs;TALLOC 双轨(>32KiB 落池/堆) */
79
80 /* ±1/2 */
81 lmmp_toom_eval_pm2rexp_(v2, v0, 5, numa, n, s, 1, dst);
82 lmmp_sqr_(dst, v0, n + 1);
83 lmmp_sqr_(r5, v2, n + 1);
84 lmmp_toom_couple_handling_(r5, 2 * n + 1, dst, 0, n, 1, 0);
85
86 /* ±1 */
87 lmmp_toom_eval_pm1_(v2, v0, 5, numa, n, s, dst);
88 lmmp_sqr_(dst, v0, n + 1);
89 lmmp_sqr_(r3, v2, n + 1);
90 lmmp_toom_couple_handling_(r3, 2 * n + 1, dst, 0, n, 0, 0);
91
92 /* ±4 */
93 lmmp_toom_eval_pm2exp_(v2, v0, 5, numa, n, s, 2, dst);
94 lmmp_sqr_(dst, v0, n + 1);
95 lmmp_sqr_(r1, v2, n + 1);
96 lmmp_toom_couple_handling_(r1, 2 * n + 1, dst, 0, n, 2, 4);
97
98 /* ±1/4 */
99 lmmp_toom_eval_pm2rexp_(v2, v0, 5, numa, n, s, 2, dst);
100 lmmp_sqr_(dst, v0, n + 1);
101 lmmp_sqr_(r4, v2, n + 1);
102 lmmp_toom_couple_handling_(r4, 2 * n + 1, dst, 0, n, 2, 0);
103
104 /* ±2 */
105 lmmp_toom_eval_pm2_(v2, v0, 5, numa, n, s, dst);
106 lmmp_sqr_(dst, v0, n + 1);
107 lmmp_sqr_(r2, v2, n + 1);
108 lmmp_toom_couple_handling_(r2, 2 * n + 1, dst, 0, n, 1, 2);
109
110#undef v0
111#undef v2
112
113 /* A(0)^2 */
114 lmmp_sqr_(dst, numa, n);
115
116 lmmp_toom_interp12_(dst, r1, r3, r5, n, 2 * s, 0, wse);
117
118#undef r0
119#undef r1
120#undef r2
121#undef r3
122#undef r4
123#undef r5
124
125 TEMP_FREE;
126}
127
128#undef lmmp_sqr_
129#undef MAYBE_sqr_basecase
130#undef MAYBE_sqr_above_basecase
131#undef MAYBE_sqr_toom2
132#undef MAYBE_sqr_above_toom2
133#undef MAYBE_sqr_toom3
134#undef MAYBE_sqr_above_toom3
135#undef MAYBE_sqr_above_toom4
136#undef SQR_TOOM6_MAX
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
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 v0
#define r2
#define r1
#define r3
#define v2
#define s
#define n
#define scratch
#define wse
#define r4
#define r5
void lmmp_toom_couple_handling_(mp_ptr pp, mp_size_t n, mp_ptr np, int nsign, mp_size_t off, int ps, int ns)
Copyright (C) 2026 HJimmyK (Jericho Knox)
int lmmp_toom_eval_pm2exp_(mp_ptr xp2, mp_ptr xm2, unsigned k, mp_srcptr xp, mp_size_t n, mp_size_t hn, unsigned shift, mp_ptr tp)
通用高阶 Toom 求值:k次多项式在 x = +2^shift 和 x = -2^shift 处求值 (toom6h 的 ±4 / toom8h 的 ±4、±8 点)
int lmmp_toom_eval_pm2_(mp_ptr xp2, mp_ptr xm2, unsigned k, mp_srcptr xp, mp_size_t n, mp_size_t hn, mp_ptr tp)
通用高阶 Toom 求值:k次多项式在 x = +2 和 x = -2 处求值
int lmmp_toom_eval_pm2rexp_(mp_ptr rp, mp_ptr rm, unsigned q, mp_srcptr ap, mp_size_t n, mp_size_t t, unsigned s, mp_ptr ws)
通用高阶 Toom 求值:q次多项式在 x = +1/2^s 和 x = -1/2^s 处求值, 结果放大 2^(s*q)(toom6h 的 ±1/2、±1/4 / toom8h 的 ±1/2、±1/4...
int lmmp_toom_eval_pm1_(mp_ptr xp1, mp_ptr xm1, unsigned k, mp_srcptr xp, mp_size_t n, mp_size_t hn, mp_ptr tp)
通用高阶 Toom 求值:k次多项式在 x = +1 和 x = -1 处求值
void lmmp_toom_interp12_(mp_ptr dst, mp_ptr r1, mp_ptr r3, mp_ptr r5, mp_size_t n, mp_size_t spt, int half, mp_ptr tp)
Toom插值计算(12点插值):用于 Toom-6.5(toom6h/toom6 平方)乘法 评估点:inf(仅 half), ±4, ±2, ±1, ±1/2, ±1/4,...
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)