LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom33.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#include "lmmp/lmmpn.h"
27
28
29#define MAYBE_mul_basecase (MUL_TOOM33_THRESHOLD < 3 * MUL_TOOM22_THRESHOLD)
30#define MAYBE_mul_toom33 (MUL_TOOM44_THRESHOLD >= 3 * MUL_TOOM33_THRESHOLD)
31
32#define lmmp_mul_n_(dst, numa, numb, n) \
33 if (MAYBE_mul_basecase && (n) < MUL_TOOM22_THRESHOLD) \
34 lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
35 else if (!MAYBE_mul_toom33 || (n) < MUL_TOOM33_THRESHOLD) \
36 lmmp_mul_toom22_((dst), (numa), (n), (numb), (n)); \
37 else \
38 lmmp_mul_toom33_((dst), (numa), (n), (numb), (n))
39
40/*
41Evaluate in: -1, 0, +1, +2, +inf
42
43 <-s--><--n--><--n-->
44 |-a2-|--a1--|--a0--|
45 |b2-|--b1--|--b0--|
46 <-t-><--n--><--n-->
47
48v0 = a0 * b0 # A(0)*B(0)
49v1 = (a0+ a1+ a2)*(b0+ b1+ b2) # A(1)*B(1) ah <= 2 bh <= 2
50vm1 = (a0- a1+ a2)*(b0- b1+ b2) # A(-1)*B(-1) |ah| <= 1 bh <= 1
51v2 = (a0+2a1+4a2)*(b0+2b1+4b2) # A(2)*B(2) ah <= 6 bh <= 6
52vinf= a2 * b2 # A(inf)*B(inf)
53*/
54
56 lmmp_param_assert(nb >= 26);
57 lmmp_param_assert(na >= nb);
58 lmmp_param_assert(3 * nb > 2 * na);
60 mp_size_t n = (na + 2) / 3, s = na - 2 * n, t = nb - 2 * n;
61 int vm1_neg;
64 mp_limb_t cy, cy2, vinf0, am1h, bm1h;
66
67#define a0 numa
68#define a1 (numa + n)
69#define a2 (numa + 2 * n)
70#define b0 numb
71#define b1 (numb + n)
72#define b2 (numb + 2 * n)
73
74#define v0 dst //[dst,2*n]
75#define v1 (dst + 2 * n) //[dst+2*n,2*n+1]
76#define vinf (dst + 4 * n) //[dst+4*n,s+t]
77#define vm1 tp //[tp,2*n+1]
78#define v2 (tp + 2 * n + 2) //[tp+2*n+2,2*n+1]
79
80#define bm1 dst //[dst,n]
81#define am1 (dst + n) //[dst+n,n]
82#define ap1 tp //[tp,n+1]
83#define bp1 (tp + n + 1) //[tp+n+1,n+1]
84#define ap2 ap1 // same space
85#define bp2 bp1 // same space
86
87 // ap1, am1
88 cy = lmmp_add_(ap1, a0, n, a2, s);
89 if (cy == 0 && lmmp_cmp_(ap1, a1, n) < 0) {
90 cy = lmmp_add_n_sub_n_(ap1, am1, a1, ap1, n);
91 ap1[n] = cy >> 1;
92 am1h = 0;
93 vm1_neg = 1;
94 } else {
95 cy2 = lmmp_add_n_sub_n_(ap1, am1, ap1, a1, n);
96 ap1[n] = cy + (cy2 >> 1);
97 am1h = cy - (cy2 & 1);
98 vm1_neg = 0;
99 }
100
101 // bp1, bm1
102 cy = lmmp_add_(bp1, b0, n, b2, t);
103 if (cy == 0 && lmmp_cmp_(bp1, b1, n) < 0) {
104 cy = lmmp_add_n_sub_n_(bp1, bm1, b1, bp1, n);
105 bp1[n] = cy >> 1;
106 bm1h = 0;
107 vm1_neg ^= 1;
108 } else {
109 cy2 = lmmp_add_n_sub_n_(bp1, bm1, bp1, b1, n);
110 bp1[n] = cy + (cy2 >> 1);
111 bm1h = cy - (cy2 & 1);
112 }
113
114 // vinf
115 if (s > t)
116 lmmp_mul_(vinf, a2, s, b2, t);
117 else
118 lmmp_mul_n_(vinf, a2, b2, s);
119 vinf0 = vinf[0]; // overlap with v1
120 cy = vinf[1]; // overlap with v1
121
122 // v1
123 lmmp_mul_n_(v1, ap1, bp1, n + 1);
124 vinf[1] = cy; // restore, since v1[2*n+1]==0.
125
126 // ap2
127 cy = lmmp_addshl1_n_(ap2, a1, a2, s);
128 if (s != n)
129 cy = lmmp_add_1_(ap2 + s, a1 + s, n - s, cy);
130 cy = 2 * cy + lmmp_addshl1_n_(ap2, a0, ap2, n);
131 ap2[n] = cy;
132
133 // bp2
134 cy = lmmp_addshl1_n_(bp2, b1, b2, t);
135 if (t != n)
136 cy = lmmp_add_1_(bp2 + t, b1 + t, n - t, cy);
137 cy = 2 * cy + lmmp_addshl1_n_(bp2, b0, bp2, n);
138 bp2[n] = cy;
139
140 // v2
141 lmmp_mul_n_(v2, ap2, bp2, n + 1);
142
143 // vm1
144 lmmp_mul_n_(vm1, am1, bm1, n);
145 cy = 0;
146 if (am1h)
147 cy = bm1h + lmmp_add_n_(vm1 + n, vm1 + n, bm1, n);
148 if (bm1h)
149 cy += lmmp_add_n_(vm1 + n, vm1 + n, am1, n);
150 vm1[2 * n] = cy;
151
152 // v0
153 lmmp_mul_n_(v0, a0, b0, n);
154
155 lmmp_toom_interp5_(dst, v2, vm1, n, s + t, vm1_neg, vinf0);
157}
#define lmmp_mul_n_
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
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
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
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
mp_limb_t lmmp_add_n_sub_n_(mp_ptr dsta, mp_ptr dstb, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
void lmmp_mul_toom33_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-33乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
#define b0
#define b1
#define a0
#define a1
#define v0
#define vinf
#define am1
#define ap1
#define bp1
#define vm1
#define bm1
#define a2
#define v1
#define ap2
#define v2
#define bp2
#define b2
#define t
#define numb
#define tp
#define s
#define n
void lmmp_toom_interp5_(mp_ptr dst, mp_ptr v2, mp_ptr vm1, mp_size_t n, mp_size_t spt, int vm1_neg, mp_limb_t vinf0)
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