LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom44.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#define MAYBE_mul_basecase (MUL_TOOM44_THRESHOLD < 4 * MUL_TOOM22_THRESHOLD)
28#define MAYBE_mul_toom22 (MUL_TOOM44_THRESHOLD < 4 * MUL_TOOM33_THRESHOLD)
29#define MAYBE_mul_toom44 (MUL_TOOM6H_THRESHOLD >= 4 * MUL_TOOM44_THRESHOLD)
30
31#define lmmp_mul_n_(dst, numa, numb, n) \
32 if (MAYBE_mul_basecase && (n) < MUL_TOOM22_THRESHOLD) \
33 lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
34 else if (MAYBE_mul_toom22 && (n) < MUL_TOOM33_THRESHOLD) \
35 lmmp_mul_toom22_((dst), (numa), (n), (numb), (n)); \
36 else if (!MAYBE_mul_toom44 || (n) < MUL_TOOM44_THRESHOLD) \
37 lmmp_mul_toom33_((dst), (numa), (n), (numb), (n)); \
38 else \
39 lmmp_mul_toom44_((dst), (numa), (n), (numb), (n))
40
41/*
42Evaluate in: 0, +1, -1, +2, -2, 1/2, +inf
43
44 <-s--><--n--><--n--><--n-->
45 |-a3-|--a2--|--a1--|--a0--|
46 |b3-|--b2--|--b1--|--b0--|
47 <-t-><--n--><--n--><--n-->
48
49 v0 = a0 * b0 # A(0)*B(0)
50 v1 = ( a0+ a1+ a2+ a3)*( b0+ b1+ b2+ b3) # A(1)*B(1) ah <= 3 bh <= 3
51 vm1 = ( a0- a1+ a2- a3)*( b0- b1+ b2- b3) # A(-1)*B(-1) |ah| <= 1 |bh| <= 1
52 v2 = ( a0+2a1+4a2+8a3)*( b0+2b1+4b2+8b3) # A(2)*B(2) ah <= 14 bh <= 14
53 vm2 = ( a0-2a1+4a2-8a3)*( b0-2b1+4b2-8b3) # A(2)*B(2) ah <= 9 |bh| <= 9
54 vh = (8a0+4a1+2a2+ a3)*(8b0+4b1+2b2+ b3) # A(1/2)*B(1/2) ah <= 14 bh <= 14
55 vinf= a3 * b2 # A(inf)*B(inf)
56*/
57
59 lmmp_param_assert(na >= nb);
60 lmmp_param_assert(4 * nb > 3 * na);
61 mp_size_t n, s, t;
62 mp_limb_t cy;
63 enum toom7_flags flags;
64
65#define a0 numa
66#define a1 (numa + n)
67#define a2 (numa + 2 * n)
68#define a3 (numa + 3 * n)
69#define b0 numb
70#define b1 (numb + n)
71#define b2 (numb + 2 * n)
72#define b3 (numb + 3 * n)
73
74 n = (na + 3) >> 2;
77
78 s = na - 3 * n;
79 t = nb - 3 * n;
80
81 lmmp_param_assert(0 < s && s <= n);
82 lmmp_param_assert(0 < t && t <= n);
84
85 /* NOTE: The multiplications to v2, vm2, vh and vm1 overwrites the
86 * following limb, so these must be computed in order, and we need a
87 * one limb gap to tp. */
88#define v0 dst /* 2n */
89#define v1 (dst + 2 * n) /* 2n+1 */
90#define vinf (dst + 6 * n) /* s+t */
91#define v2 scratch /* 2n+1 */
92#define vm2 (scratch + 2 * n + 1) /* 2n+1 */
93#define vh (scratch + 4 * n + 2) /* 2n+1 */
94#define vm1 (scratch + 6 * n + 3) /* 2n+1 */
95#define tp (scratch + 8 * n + 5)
96
97 /* apx and bpx must not overlap with v1 */
98#define apx dst /* n+1 */
99#define amx (dst + n + 1) /* n+1 */
100#define bmx (dst + 2 * n + 2) /* n+1 */
101#define bpx (dst + 4 * n + 2) /* n+1 */
102
103 /* Total scratch need: 8*n + 5 + scratch for recursive calls. This
104 gives roughly 32 n/3 + log term. */
105
106 /* Compute apx = a0 + 2 a1 + 4 a2 + 8 a3 and amx = a0 - 2 a1 + 4 a2 - 8 a3. */
107 flags = (enum toom7_flags)(toom7_w1_neg & lmmp_toom_eval_dgr3_pm2_(apx, amx, numa, n, s, tp));
108
109 /* Compute bpx = b0 + 2 b1 + 4 b2 + 8 b3 and bmx = b0 - 2 b1 + 4 b2 - 8 b3. */
110 flags = (enum toom7_flags)(flags ^ (toom7_w1_neg & lmmp_toom_eval_dgr3_pm2_(bpx, bmx, numb, n, t, tp)));
111
112 lmmp_mul_n_(v2, apx, bpx, n + 1); /* v2, 2n+1 limbs */
113 lmmp_mul_n_(vm2, amx, bmx, n + 1); /* vm2, 2n+1 limbs */
114
115 /* Compute apx = 8 a0 + 4 a1 + 2 a2 + a3 = (((2*a0 + a1) * 2 + a2) * 2 + a3 */
116
117 cy = lmmp_addshl1_n_(apx, a1, a0, n);
118 cy = 2 * cy + lmmp_addshl1_n_(apx, a2, apx, n);
119 if (s < n) {
120 mp_limb_t cy2;
121 cy2 = lmmp_addshl1_n_(apx, a3, apx, s);
122 apx[n] = 2 * cy + lmmp_shl_(apx + s, apx + s, n - s, 1);
123 lmmp_inc_1(apx + s, cy2);
124 } else
125 apx[n] = 2 * cy + lmmp_addshl1_n_(apx, a3, apx, n);
126
127 /* Compute bpx = 8 b0 + 4 b1 + 2 b2 + b3 = (((2*b0 + b1) * 2 + b2) * 2 + b3 */
128
129 cy = lmmp_addshl1_n_(bpx, b1, b0, n);
130 cy = 2 * cy + lmmp_addshl1_n_(bpx, b2, bpx, n);
131 if (t < n) {
132 mp_limb_t cy2;
133 cy2 = lmmp_addshl1_n_(bpx, b3, bpx, t);
134 bpx[n] = 2 * cy + lmmp_shl_(bpx + t, bpx + t, n - t, 1);
135 lmmp_inc_1(bpx + t, cy2);
136 } else
137 bpx[n] = 2 * cy + lmmp_addshl1_n_(bpx, b3, bpx, n);
138
139 lmmp_debug_assert(apx[n] < 15);
140 lmmp_debug_assert(bpx[n] < 15);
141
142 lmmp_mul_n_(vh, apx, bpx, n + 1); /* vh, 2n+1 limbs */
143
144 /* Compute apx = a0 + a1 + a2 + a3 and amx = a0 - a1 + a2 - a3. */
145 flags = (enum toom7_flags)(flags | (toom7_w3_neg & lmmp_toom_eval_dgr3_pm1_(apx, amx, numa, n, s, tp)));
146
147 /* Compute bpx = b0 + b1 + b2 + b3 and bmx = b0 - b1 + b2 - b3. */
148 flags = (enum toom7_flags)(flags ^ (toom7_w3_neg & lmmp_toom_eval_dgr3_pm1_(bpx, bmx, numb, n, t, tp)));
149
150 lmmp_mul_n_(vm1, amx, bmx, n + 1); /* vm1, 2n+1 limbs */
151 /* Clobbers amx, bmx. */
152 lmmp_mul_n_(v1, apx, bpx, n + 1); /* v1, 2n+1 limbs */
153
154 lmmp_mul_n_(v0, a0, b0, n);
155 if (s > t)
156 lmmp_mul_(vinf, a3, s, b3, t);
157 else
158 lmmp_mul_n_(vinf, a3, b3, s);
159
160 lmmp_toom_interp7_(dst, n, flags, vm2, vm1, v2, vh, s + t, tp);
161
163}
#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
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_mul_toom44_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-44乘法运算 [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]
mp_limb_t lmmp_addshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
定义 shl.c:53
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
#define b0
#define b1
#define a0
#define a1
#define v0
#define vinf
#define vm1
#define a2
#define v1
#define v2
#define b2
#define t
#define a3
#define numb
#define tp
#define s
#define n
#define vm2
#define apx
#define vh
#define bmx
#define b3
#define bpx
#define amx
#define scratch
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_dgr3_pm2_(mp_ptr xp2, mp_ptr xm2, mp_srcptr xp, mp_size_t n, mp_size_t x3n, mp_ptr tp)
Toom-3 专用:3次多项式在 x = +2 和 x = -2 处求值 计算 P(+2) 和 P(-2),其中 P(x) 是一个3次多项式(4段系数)。
void lmmp_toom_interp7_(mp_ptr dst, mp_size_t n, enum toom7_flags flags, mp_ptr w1, mp_ptr w3, mp_ptr w4, mp_ptr w5, mp_size_t w6n, mp_ptr tp)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define SALLOC_TYPE(n, type)
#define TEMP_S_DECL
#define TEMP_S_FREE
toom7_flags
@ toom7_w1_neg
@ toom7_w3_neg