LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom8h.c 文件参考
#include "impl/mul_hard.h"
#include "mparam.h"
#include "lmmpn/toom_interp.h"
mul_toom8h.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define LIMIT_den   (20)
#define LIMIT_num   (21)
#define lmmp_mul_n_(dst, numa, numb, n)
#define MAYBE_mul_basecase   (MUL_TOOM8H_THRESHOLD < 8 * MUL_TOOM22_THRESHOLD)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define MAYBE_mul_toom22   (MUL_TOOM8H_THRESHOLD < 8 * MUL_TOOM33_THRESHOLD)
#define MAYBE_mul_toom33   (MUL_TOOM8H_THRESHOLD < 8 * MUL_TOOM44_THRESHOLD)
#define MAYBE_mul_toom44   (MUL_TOOM8H_THRESHOLD < 8 * MUL_TOOM6H_THRESHOLD)
#define MAYBE_mul_toom8h   (MUL_FFT_THRESHOLD >= 8 * MUL_TOOM8H_THRESHOLD)
#define r0   (dst + 15 * n)
#define r1   (scratch + 9 * n + 3)
#define r2   (dst + 11 * n)
#define r3   (scratch + 6 * n + 2)
#define r4   (dst + 7 * n)
#define r5   (scratch + 3 * n + 1)
#define r6   (dst + 3 * n)
#define r7   (scratch)
#define v0   (dst + 11 * n)
#define v1   (dst + 12 * n + 1)
#define v2   (dst + 13 * n + 2)
#define v3   (scratch + 12 * n + 4)
#define wse   (scratch + 13 * n + 5)
#define wsi   (scratch + 12 * n + 4)

函数

void lmmp_mul_toom8h_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_srcptr restrict numb, mp_size_t nb)

宏定义说明

◆ LIMIT_den

#define LIMIT_den   (20)

◆ LIMIT_num

#define LIMIT_num   (21)

◆ lmmp_mul_n_

#define lmmp_mul_n_ ( dst,
numa,
numb,
n )
值:
lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
lmmp_mul_toom22_((dst), (numa), (n), (numb), (n)); \
lmmp_mul_toom33_((dst), (numa), (n), (numb), (n)); \
lmmp_mul_toom44_((dst), (numa), (n), (numb), (n)); \
lmmp_mul_toom6h_((dst), (numa), (n), (numb), (n)); \
else \
lmmp_mul_toom8h_((dst), (numa), (n), (numb), (n))
#define MUL_TOOM22_THRESHOLD
#define MUL_TOOM8H_THRESHOLD
#define MUL_TOOM33_THRESHOLD
#define MUL_TOOM6H_THRESHOLD
#define MUL_TOOM44_THRESHOLD
#define MAYBE_mul_toom22
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define MAYBE_mul_toom33
#define MAYBE_mul_basecase
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define numb
#define n
#define MAYBE_mul_toom44
#define MAYBE_mul_toom8h

在文件 mul_toom8h.c 第 34 行定义.

◆ MAYBE_mul_basecase

#define MAYBE_mul_basecase   (MUL_TOOM8H_THRESHOLD < 8 * MUL_TOOM22_THRESHOLD)

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

在文件 mul_toom8h.c 第 28 行定义.

◆ MAYBE_mul_toom22

#define MAYBE_mul_toom22   (MUL_TOOM8H_THRESHOLD < 8 * MUL_TOOM33_THRESHOLD)

在文件 mul_toom8h.c 第 29 行定义.

◆ MAYBE_mul_toom33

#define MAYBE_mul_toom33   (MUL_TOOM8H_THRESHOLD < 8 * MUL_TOOM44_THRESHOLD)

在文件 mul_toom8h.c 第 30 行定义.

◆ MAYBE_mul_toom44

#define MAYBE_mul_toom44   (MUL_TOOM8H_THRESHOLD < 8 * MUL_TOOM6H_THRESHOLD)

在文件 mul_toom8h.c 第 31 行定义.

◆ MAYBE_mul_toom8h

#define MAYBE_mul_toom8h   (MUL_FFT_THRESHOLD >= 8 * MUL_TOOM8H_THRESHOLD)

在文件 mul_toom8h.c 第 32 行定义.

◆ r0

#define r0   (dst + 15 * n)

◆ r1

#define r1   (scratch + 9 * n + 3)

◆ r2

#define r2   (dst + 11 * n)

◆ r3

#define r3   (scratch + 6 * n + 2)

◆ r4

#define r4   (dst + 7 * n)

◆ r5

#define r5   (scratch + 3 * n + 1)

◆ r6

#define r6   (dst + 3 * n)

◆ r7

#define r7   (scratch)

◆ v0

#define v0   (dst + 11 * n)

◆ v1

#define v1   (dst + 12 * n + 1)

◆ v2

#define v2   (dst + 13 * n + 2)

◆ v3

#define v3   (scratch + 12 * n + 4)

◆ wse

#define wse   (scratch + 13 * n + 5)

◆ wsi

#define wsi   (scratch + 12 * n + 4)

函数说明

◆ lmmp_mul_toom8h_()

void lmmp_mul_toom8h_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_size_t na,
mp_srcptr restrict numb,
mp_size_t nb )

在文件 mul_toom8h.c 第 52 行定义.

52 {
53 lmmp_param_assert(na >= nb);
54 lmmp_param_assert(nb >= 86);
55 lmmp_param_assert(na <= 4 * nb);
56 mp_size_t n, s, t;
57 int p, q, half;
58 int sign;
59
60 /* LIMIT = 21/20:介于 (16/15)^(log6/log11) 与 (16/15)^(log8/log15)
61 之间的有理逼近(比例 < 21/20 视为近似平衡) */
62#define LIMIT_num (21)
63#define LIMIT_den (20)
64
65 if (na == nb || na * (LIMIT_den / 2) < LIMIT_num * (nb / 2)) {
66 /* 近似平衡:双侧各切 7 段 */
67 half = 0;
68 n = 1 + ((na - 1) >> 3);
69 p = q = 7;
70 s = na - 7 * n;
71 t = nb - 7 * n;
72 } else {
73 /* 不平衡阶梯:(p,q) 覆盖比例至 4 */
74 if (na * 13 < 16 * nb) {
75 p = 9;
76 q = 8;
77 } else if (na * (LIMIT_den / 2) < (LIMIT_num / 7 * 9) * (nb / 2)) {
78 p = 9;
79 q = 7;
80 } else if (na * 10 < 33 * (nb / 2)) {
81 p = 10;
82 q = 7;
83 } else if (na * (LIMIT_den / 5) < (LIMIT_num / 3) * nb) {
84 p = 10;
85 q = 6;
86 } else if (na * 6 < 13 * nb) {
87 p = 11;
88 q = 6;
89 } else if (na * 4 < 9 * nb) {
90 p = 11;
91 q = 5;
92 } else if (na * (LIMIT_num / 3) < LIMIT_den * nb) {
93 p = 12;
94 q = 5;
95 } else if (na * 9 < 28 * nb) {
96 p = 12;
97 q = 4;
98 } else {
99 p = 13;
100 q = 4;
101 }
102
103 half = (p + q) & 1;
104 n = 1 + (q * na >= p * nb ? (na - 1) / p : (nb - 1) / q);
105 p--;
106 q--;
107
108 s = na - p * n;
109 t = nb - q * n;
110
111 /* 恢复不良切分。mp_size_t 无符号,s/t 为负时回绕,
112 须按 na<=p*n / nb<=q*n 判定 */
113 if (half) {
114 if (na <= (mp_size_t)p * n) {
115 p--;
116 s += n;
117 half = 0;
118 } else if (nb <= (mp_size_t)q * n) {
119 q--;
120 t += n;
121 half = 0;
122 }
123 }
124 }
125#undef LIMIT_num
126#undef LIMIT_den
127
128 lmmp_debug_assert(0 < s && s <= n);
129 lmmp_debug_assert(0 < t && t <= n);
130 lmmp_debug_assert(s + t + 3 * (mp_size_t)half > 3);
131 lmmp_debug_assert(n > 2);
132
133#define r6 (dst + 3 * n) /* 3n+1 */
134#define r4 (dst + 7 * n) /* 3n+1 */
135#define r2 (dst + 11 * n) /* 3n+1 */
136#define r0 (dst + 15 * n) /* s+t <= 2n */
137#define r7 (scratch) /* 3n+1 */
138#define r5 (scratch + 3 * n + 1) /* 3n+1 */
139#define r3 (scratch + 6 * n + 2) /* 3n+1 */
140#define r1 (scratch + 9 * n + 3) /* 3n+1 */
141#define v0 (dst + 11 * n) /* n+1 */
142#define v1 (dst + 12 * n + 1) /* n+1 */
143#define v2 (dst + 13 * n + 2) /* n+1 */
144#define v3 (scratch + 12 * n + 4) /* n+1 */
145#define wsi (scratch + 12 * n + 4) /* 3n+1,与 v3 复用(生命周期不交) */
146#define wse (scratch + 13 * n + 5) /* 2n+1 */
147
148 /* scratch 总需求 15n+6 limbs;TALLOC 双轨(>32KiB 落池/堆) */
149 TEMP_DECL;
151
152 /* ±1/8 */
153 sign = lmmp_toom_eval_pm2rexp_(v2, v0, p, numa, n, s, 3, dst) ^ lmmp_toom_eval_pm2rexp_(v3, v1, q, numb, n, t, 3, dst);
154 lmmp_mul_n_(dst, v0, v1, n + 1);
155 lmmp_mul_n_(r7, v2, v3, n + 1);
156 lmmp_toom_couple_handling_(r7, 2 * n + 1, dst, sign, n, 3 * (1 + half), 3 * half);
157
158 /* ±1/4 */
159 sign = lmmp_toom_eval_pm2rexp_(v2, v0, p, numa, n, s, 2, dst) ^ lmmp_toom_eval_pm2rexp_(v3, v1, q, numb, n, t, 2, dst);
160 lmmp_mul_n_(dst, v0, v1, n + 1);
161 lmmp_mul_n_(r5, v2, v3, n + 1);
162 lmmp_toom_couple_handling_(r5, 2 * n + 1, dst, sign, n, 2 * (1 + half), 2 * half);
163
164 /* ±2 */
165 sign = lmmp_toom_eval_pm2_(v2, v0, p, numa, n, s, dst) ^ lmmp_toom_eval_pm2_(v3, v1, q, numb, n, t, dst);
166 lmmp_mul_n_(dst, v0, v1, n + 1);
167 lmmp_mul_n_(r3, v2, v3, n + 1);
168 lmmp_toom_couple_handling_(r3, 2 * n + 1, dst, sign, n, 1, 2);
169
170 /* ±8 */
171 sign = lmmp_toom_eval_pm2exp_(v2, v0, p, numa, n, s, 3, dst) ^ lmmp_toom_eval_pm2exp_(v3, v1, q, numb, n, t, 3, dst);
172 lmmp_mul_n_(dst, v0, v1, n + 1);
173 lmmp_mul_n_(r1, v2, v3, n + 1);
174 lmmp_toom_couple_handling_(r1, 2 * n + 1, dst, sign, n, 3, 6);
175
176 /* ±1/2 */
177 sign = lmmp_toom_eval_pm2rexp_(v2, v0, p, numa, n, s, 1, dst) ^ lmmp_toom_eval_pm2rexp_(v3, v1, q, numb, n, t, 1, dst);
178 lmmp_mul_n_(dst, v0, v1, n + 1);
179 lmmp_mul_n_(r6, v2, v3, n + 1);
180 lmmp_toom_couple_handling_(r6, 2 * n + 1, dst, sign, n, 1 + half, half);
181
182 /* ±1 */
183 sign = lmmp_toom_eval_pm1_(v2, v0, p, numa, n, s, dst);
184 if (q == 3)
185 sign ^= lmmp_toom_eval_dgr3_pm1_(v3, v1, numb, n, t, dst);
186 else
187 sign ^= lmmp_toom_eval_pm1_(v3, v1, q, numb, n, t, dst);
188 lmmp_mul_n_(dst, v0, v1, n + 1);
189 lmmp_mul_n_(r4, v2, v3, n + 1);
190 lmmp_toom_couple_handling_(r4, 2 * n + 1, dst, sign, n, 0, 0);
191
192 /* ±4 */
193 sign = lmmp_toom_eval_pm2exp_(v2, v0, p, numa, n, s, 2, dst) ^ lmmp_toom_eval_pm2exp_(v3, v1, q, numb, n, t, 2, dst);
194 lmmp_mul_n_(dst, v0, v1, n + 1);
195 lmmp_mul_n_(r2, v2, v3, n + 1);
196 lmmp_toom_couple_handling_(r2, 2 * n + 1, dst, sign, n, 2, 4);
197
198#undef v0
199#undef v1
200#undef v2
201#undef v3
202#undef wse
203
204 /* A(0)*B(0) */
205 lmmp_mul_n_(dst, numa, numb, n);
206
207 /* 无穷远点 */
208 if (half != 0) {
209 if (s > t)
210 lmmp_mul_(r0, numa + p * n, s, numb + q * n, t);
211 else
212 lmmp_mul_(r0, numb + q * n, t, numa + p * n, s);
213 }
214
215 lmmp_toom_interp16_(dst, r1, r3, r5, r7, n, s + t, half, wsi);
216
217#undef r0
218#undef r1
219#undef r2
220#undef r3
221#undef r4
222#undef r5
223#undef r6
224#undef r7
225#undef wsi
226
227 TEMP_FREE;
228}
#define lmmp_mul_n_
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
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]
#define v0
#define r2
#define r1
#define v1
#define r3
#define r0
#define v2
#define t
#define s
#define scratch
#define LIMIT_den
#define wsi
#define v3
#define r4
#define LIMIT_num
#define r5
#define r6
#define r7
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 处求值
LMMP_VECT_CONSERVATIVE int lmmp_toom_eval_dgr3_pm1_(mp_ptr xp1, mp_ptr xm1, mp_srcptr xp, mp_size_t n, mp_size_t x3n, mp_ptr tp)
Copyright (C) 2026 HJimmyK (Jericho Knox)
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_interp16_(mp_ptr dst, mp_ptr r1, mp_ptr r3, mp_ptr r5, mp_ptr r7, mp_size_t n, mp_size_t spt, int half, mp_ptr tp)
Toom插值计算(16点插值):用于 Toom-8.5(toom8h/toom8 平方)乘法 评估点:inf(仅 half), ±8, ±4, ±2, ±1, ±1/2,...
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 LIMIT_den, LIMIT_num, lmmp_debug_assert, lmmp_mul_(), lmmp_mul_n_, lmmp_mul_toom8h_(), lmmp_param_assert, lmmp_toom_couple_handling_(), lmmp_toom_eval_dgr3_pm1_(), lmmp_toom_eval_pm1_(), lmmp_toom_eval_pm2_(), lmmp_toom_eval_pm2exp_(), lmmp_toom_eval_pm2rexp_(), lmmp_toom_interp16_(), n, numb, r0, r1, r2, r3, r4, r5, r6, r7, restrict, s, scratch, t, TALLOC_TYPE, TEMP_DECL, TEMP_FREE, v0, v1, v2, v3 , 以及 wsi.

函数调用图: