LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
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
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
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*/
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) {
154 }
155 for (; i < n; i++) {
157 }
158#undef LMMP_SUBMUL_1_STEP
159 return d;
160}
161
163 mp_limb_t h;
164 h = numa[0] * numb[n - 1];
165 if (n != 1) {
166 mp_size_t i;
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*/
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}
#define LMMP_SUBMUL_1_STEP(k)
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
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
void lmmp_sqrlo_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
基础低位平方 [dst,n] = [numa,n]^2 mod B^n
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
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
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
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
#define b0
#define b1
#define a0
#define a1
#define a2
#define t
#define a3
#define numb
#define n
#define a4
#define a5
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)