LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
mul_1.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/longlong.h
"
24
#include "
lmmp/lmmpn.h
"
25
26
27
mp_limb_t
lmmp_mul_1_
(
mp_ptr
dst,
mp_srcptr
numa,
mp_size_t
na,
mp_limb_t
x) {
28
/*
29
链式 (a_{k-1} >> 64) 进位提取使 GCC/Clang 均生成 add/adc 融合序列,
30
单 limb 链长约 2c,展开宽度 W 可将链摊薄为 (W+1)/W c:
31
- clang 会把 4 路链式源码回卷成 2 路(实测慢约 7~12%),6 路是其
32
能保持的最小宽度;
33
- gcc 恰好相反,4 路最优、6 路慢约 4%。
34
故按编译器选择展开宽度。
35
*/
36
mp_limb_t
cl = 0;
37
mp_size_t
i = 0;
38
39
#if defined(__clang__)
40
for
(; i + 6 <= na; i += 6) {
41
__uint128_t
a0
= (__uint128_t)numa[i + 0] * x + cl;
42
__uint128_t
a1
= (__uint128_t)numa[i + 1] * x + (
mp_limb_t
)(
a0
>> 64);
43
__uint128_t
a2
= (__uint128_t)numa[i + 2] * x + (
mp_limb_t
)(
a1
>> 64);
44
__uint128_t
a3
= (__uint128_t)numa[i + 3] * x + (
mp_limb_t
)(
a2
>> 64);
45
__uint128_t
a4
= (__uint128_t)numa[i + 4] * x + (
mp_limb_t
)(
a3
>> 64);
46
__uint128_t
a5
= (__uint128_t)numa[i + 5] * x + (
mp_limb_t
)(
a4
>> 64);
47
dst[i + 0] = (
mp_limb_t
)
a0
;
48
dst[i + 1] = (
mp_limb_t
)
a1
;
49
dst[i + 2] = (
mp_limb_t
)
a2
;
50
dst[i + 3] = (
mp_limb_t
)
a3
;
51
dst[i + 4] = (
mp_limb_t
)
a4
;
52
dst[i + 5] = (
mp_limb_t
)
a5
;
53
cl = (
mp_limb_t
)(
a5
>> 64);
54
}
55
#else
56
for
(; i + 4 <= na; i += 4) {
57
__uint128_t
a0
= (__uint128_t)numa[i + 0] * x + cl;
58
__uint128_t
a1
= (__uint128_t)numa[i + 1] * x + (
mp_limb_t
)(
a0
>> 64);
59
__uint128_t
a2
= (__uint128_t)numa[i + 2] * x + (
mp_limb_t
)(
a1
>> 64);
60
__uint128_t
a3
= (__uint128_t)numa[i + 3] * x + (
mp_limb_t
)(
a2
>> 64);
61
dst[i + 0] = (
mp_limb_t
)
a0
;
62
dst[i + 1] = (
mp_limb_t
)
a1
;
63
dst[i + 2] = (
mp_limb_t
)
a2
;
64
dst[i + 3] = (
mp_limb_t
)
a3
;
65
cl = (
mp_limb_t
)(
a3
>> 64);
66
}
67
#endif
68
for
(; i < na; i++) {
69
__uint128_t a = (__uint128_t)numa[i] * x + cl;
70
dst[i] = (
mp_limb_t
)a;
71
cl = (
mp_limb_t
)(a >> 64);
72
}
73
return
cl;
74
}
75
76
mp_limb_t
lmmp_addmul_1_
(
mp_ptr
numa,
mp_srcptr
numb
,
mp_size_t
n
,
mp_limb_t
b) {
77
mp_limb_t
cl = 0;
78
mp_size_t
i = 0;
79
80
for
(; i + 4 <=
n
; i += 4) {
81
__uint128_t
a0
= (__uint128_t)
numb
[i + 0] * b + numa[i + 0] + cl;
82
__uint128_t
a1
= (__uint128_t)
numb
[i + 1] * b + numa[i + 1] + (
mp_limb_t
)(
a0
>> 64);
83
__uint128_t
a2
= (__uint128_t)
numb
[i + 2] * b + numa[i + 2] + (
mp_limb_t
)(
a1
>> 64);
84
__uint128_t
a3
= (__uint128_t)
numb
[i + 3] * b + numa[i + 3] + (
mp_limb_t
)(
a2
>> 64);
85
numa[i + 0] = (
mp_limb_t
)
a0
;
86
numa[i + 1] = (
mp_limb_t
)
a1
;
87
numa[i + 2] = (
mp_limb_t
)
a2
;
88
numa[i + 3] = (
mp_limb_t
)
a3
;
89
cl = (
mp_limb_t
)(
a3
>> 64);
90
}
91
for
(; i <
n
; i++) {
92
__uint128_t a = (__uint128_t)
numb
[i] * b + numa[i] + cl;
93
numa[i] = (
mp_limb_t
)a;
94
cl = (
mp_limb_t
)(a >> 64);
95
}
96
return
cl;
97
}
98
99
mp_limb_t
lmmp_addmul_2_
(
mp_ptr
numa,
mp_srcptr
numb
,
mp_size_t
n
,
mp_srcptr
bp) {
100
mp_limb_t
b0
= bp[0],
b1
= bp[1];
101
mp_limb_t
alo = 0, ahi = 0;
102
mp_size_t
i = 0;
103
104
/* 双 limb 滚动累加器 alo*B^i + ahi*B^(i+1):t 收纳本位(含 numa[i] 与 b0 行),
105
u 收纳上位(b1 行 + t 进位),两项各 < B^2 无 u128 回绕 */
106
for
(; i <
n
; i++) {
107
__uint128_t
t
= (__uint128_t)
numb
[i] *
b0
+ numa[i] + alo;
108
__uint128_t u = (__uint128_t)
numb
[i] *
b1
+ ahi + (
mp_limb_t
)(
t
>> 64);
109
numa[i] = (
mp_limb_t
)
t
;
110
alo = (
mp_limb_t
)u;
111
ahi = (
mp_limb_t
)(u >> 64);
112
}
113
numa[
n
] = alo;
114
return
ahi;
115
}
116
117
/*
118
双借位分解(与 addmul_1 的 add/adc 结构对称,便于编译器生成短进位链):
119
120
u = numa[i] - lo(numb[i]*b) b1 = [u > o] (与 d 无关,可提前)
121
r = u - d b2 = [r > u]
122
d' = hi(numb[i]*b) + b1 + b2
123
124
正确性:r = numa[i] - lo - d (mod B);债务 d' = hi + ceil((lo + d - numa)/B)。
125
由于 lo + d <= 2B-2,ceil 项可取 0/1/2,恰为 b1 + b2(b1、b2 分别对应两次
126
减法各自的回绕,可同时为 1),故 d' <= B-1 仍为完整 limb 借位。
127
相比 128 位回绕减写法(sub/sbb/sub/sbb/neg 长串行链),本写法将
128
「hi 累积」与「借位判定」拆为两条独立链,GCC/Clang 均能更好调度。
129
展开 8 路:clang 下 4/8 路性能相同,gcc 下 4 路实测慢约 25%,故统一取 8 路。
130
*/
131
mp_limb_t
lmmp_submul_1_
(
mp_ptr
numa,
mp_srcptr
numb
,
mp_size_t
n
,
mp_limb_t
b) {
132
mp_limb_t
d = 0;
133
mp_size_t
i = 0;
134
135
#define LMMP_SUBMUL_1_STEP(k) \
136
{ \
137
__uint128_t P = (__uint128_t)numb[i + (k)] * b; \
138
mp_limb_t o = numa[i + (k)]; \
139
mp_limb_t u = o - (mp_limb_t)P; \
140
mp_limb_t r = u - d; \
141
d = (mp_limb_t)(P >> 64) + (u > o) + (r > u); \
142
numa[i + (k)] = r; \
143
}
144
145
for
(; i + 8 <=
n
; i += 8) {
146
LMMP_SUBMUL_1_STEP
(0)
147
LMMP_SUBMUL_1_STEP
(1)
148
LMMP_SUBMUL_1_STEP
(2)
149
LMMP_SUBMUL_1_STEP
(3)
150
LMMP_SUBMUL_1_STEP
(4)
151
LMMP_SUBMUL_1_STEP
(5)
152
LMMP_SUBMUL_1_STEP
(6)
153
LMMP_SUBMUL_1_STEP
(7)
154
}
155
for
(; i <
n
; i++) {
156
LMMP_SUBMUL_1_STEP
(0)
157
}
158
#undef LMMP_SUBMUL_1_STEP
159
return
d;
160
}
161
162
void
lmmp_mullo_basecase_
(
mp_ptr
restrict
dst,
mp_srcptr
restrict
numa,
mp_srcptr
restrict
numb
,
mp_size_t
n
) {
163
mp_limb_t
h;
164
h = numa[0] *
numb
[
n
- 1];
165
if
(
n
!= 1) {
166
mp_size_t
i;
167
mp_limb_t
b0
;
168
169
b0
= *
numb
++;
170
h += numa[
n
- 1] *
b0
+
lmmp_mul_1_
(dst, numa,
n
- 1,
b0
);
171
dst++;
172
173
for
(i =
n
- 2; i > 0; i--) {
174
b0
= *
numb
++;
175
h += numa[i] *
b0
+
lmmp_addmul_1_
(dst, numa, i,
b0
);
176
dst++;
177
}
178
}
179
180
dst[0] = h;
181
}
182
183
/*
184
低位平方的三角分解:U^2 = 2*T + D (mod B^n),其中
185
T = sum_{i<j} a_i*a_j*B^(i+j) (上三角交叉积,每个无序对只乘一次)
186
D = sum_i a_i^2*B^2i (对角线平方)
187
行 j 贡献 a_j*[a_{j+1},...,a_{n-1-j})*B^j,即 dst[2j+1..n-1] += a_j*a[j+1..n-1-j],
188
每条乘加链恰好终止于第 n-1 列,链尾进位落在第 n 列直接丢弃。
189
乘法量约 n^2/4(mullo(a,a) 为 n^2/2),末尾一趟融合的 2*dst+D 收尾。
190
*/
191
void
lmmp_sqrlo_basecase_
(
mp_ptr
restrict
dst,
mp_srcptr
restrict
numa,
mp_size_t
n
) {
192
lmmp_param_assert
(
n
> 0);
193
mp_size_t
j;
194
195
dst[0] = 0;
196
if
(
n
> 1)
197
(void)
lmmp_mul_1_
(dst + 1, numa + 1,
n
- 1, numa[0]);
198
for
(j = 1; 2 * j + 2 <=
n
; j++)
199
(
void
)
lmmp_addmul_1_
(dst + 2 * j + 1, numa + j + 1,
n
- 2 * j - 1, numa[j]);
200
201
// dst = 2*dst + 对角平方,截断于 n。分步累加防止 u128 回绕:
202
// a^2 + 2*d + cl 总和可达 B^2+B-1 > 2^128-1(a=d=B-1 极端值)
203
__uint128_t cl = 0;
204
for
(j = 0; 2 * j <
n
; j++) {
205
__uint128_t p = (__uint128_t)numa[j] * numa[j];
206
__uint128_t v = (
mp_limb_t
)p + cl + ((__uint128_t)dst[2 * j] << 1);
// ≤ 4B 无回绕
207
dst[2 * j] = (
mp_limb_t
)v;
208
cl = (v >> 64) + (p >> 64);
// ≤ B+1
209
if
(2 * j + 1 <
n
) {
210
v = ((__uint128_t)dst[2 * j + 1] << 1) + cl;
211
dst[2 * j + 1] = (
mp_limb_t
)v;
212
cl = v >> 64;
// ≤ 2
213
}
214
}
215
}
LMMP_SUBMUL_1_STEP
#define LMMP_SUBMUL_1_STEP(k)
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
lmmpn.h
lmmp_addmul_2_
mp_limb_t lmmp_addmul_2_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_srcptr bp)
乘以双limb并累加 [numa,n] += [numb,n] * [bp,2]
定义
mul_1.c:99
lmmp_sqrlo_basecase_
void lmmp_sqrlo_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
基础低位平方 [dst,n] = [numa,n]^2 mod B^n
lmmp_mullo_basecase_
void lmmp_mullo_basecase_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
基础低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
lmmp_addmul_1_
mp_limb_t lmmp_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
定义
mul_1.c:76
lmmp_mul_1_
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义
mul_1.c:27
lmmp_submul_1_
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
定义
mul_1.c:131
longlong.h
b0
#define b0
b1
#define b1
a0
#define a0
a1
#define a1
a2
#define a2
t
#define t
a3
#define a3
numb
#define numb
n
#define n
a4
#define a4
a5
#define a5
restrict
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_powmod.c:35
src
lmmp
lmmpn
arch
generic
mul_1.c
生成于
, 为 LMMP使用
1.18.0