LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mullo.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/inlines.h"
24#include "mparam.h"
25#include "impl/tmp_alloc.h"
26#include "impl/mul_cache.h"
27#include "lmmp/lmmpn.h"
28
29
30/**
31 * @brief mullo 双域 CRT 尾部:由梅森域积与费马域积重构低位乘积
32 * [dst,n] = P mod B^n,其中 P = [numa,n]*[numb,n] mod B^(2n),
33 * [lp,hn] = P mod B^hn-1(梅森域结果),[hp,hn+1] = P mod B^hn+1(费马域结果)
34 * @param dst 输出结果(n 个 limb)
35 * @param lp 输入输出:梅森域结果,兼作重构工作区(需 2*n 个 limb 容量;
36 * n==hn 时写入 [hn,2hn),n<hn 时写入 [hn,2n))
37 * @param hp 输入输出:费马域结果(hn+1 个 limb;n<hn 时 [2n-hn,hn) 段被复写)
38 * @param n 低位乘积截断长度
39 * @param hn 变换阶数,hn = lmmp_fft_next_size_(n)
40 * @warning n>0, n<=hn, sep(dst,[lp|hp]), lp 容量 >= 2*n, hp 容量 >= hn+1
41 * @note 先以 shr1add 组合两域残差得 X = ([lp,hn]+[hp,hn+1])/2 的环内表示
42 * (B^hn 在 B^hn-1 意义下 ≡ 1,故 hp 顶 limb 以进位并入),随后按
43 * n==hn(全积重构)或 n<hn(2n 位部分重构)执行分段减法链完成精确 CRT,
44 * 减法链的借位在 [lp,2n) 工作区内闭合,不会越界
45 */
46static void lmmp_mullo_crt_(mp_ptr dst, mp_ptr lp, mp_ptr hp, mp_size_t n, mp_size_t hn) {
47 mp_limb_t cy = lmmp_shr1add_nc_(lp, lp, hp, hn, hp[hn]);
48 cy <<= LIMB_BITS - 1;
49 lp[hn - 1] += cy;
50 if (lp[hn - 1] < cy)
51 lmmp_inc(lp);
52
53 if (n == hn) {
54 cy = hp[hn] + lmmp_sub_n_(lp + hn, lp, hp, hn);
55 // cy==1 means [hp,hn+1]!=0, then [lp,hn]!=0
56 // cy==2 is impossible since [hp,hn+1] is normalized.
57 // so the following dec won't overflow.
58 lmmp_dec_1(lp, cy);
59 } else {
60 mp_size_t n2 = 2 * n;
61 cy = lmmp_sub_n_(lp + hn, lp, hp, n2 - hn);
62 cy = hp[hn] + lmmp_sub_nc_(hp + n2 - hn, lp + n2 - hn, hp + n2 - hn, 2 * hn - n2, cy);
63 cy = lmmp_sub_1_(lp, lp, n2, cy);
64 }
65 lmmp_copy(dst, lp, n);
66}
67
71 lmmp_debug_assert(n <= hn);
72 mp_ptr tp = ALLOC_TYPE(hn + 1, mp_limb_t);
73
74 if (numa == numb) {
76 lmmp_sqr_fermat_(tp, hn, numa, n);
77 } else {
79 lmmp_mul_fermat_(tp, hn, numa, n, numb, n);
80 }
81
82 lmmp_mullo_crt_(dst, scratch, tp, n, hn);
84}
85
87 fft_mullo_cache* ctx) {
89 lmmp_param_assert(dst != NULL && numa != NULL && numb != NULL);
90 lmmp_param_assert(scratch != NULL && ctx != NULL);
92 lmmp_debug_assert(n <= hn);
93 ctx->n = n;
94 ctx->hn = hn;
95 ctx->mul.hn = hn;
96 ctx->mul.na = n;
97 ctx->mul.nb = n;
98 ctx->mul.tp = ALLOC_TYPE(hn + 1, mp_limb_t);
99
101 lmmp_mul_fermat_cache_init_(ctx->mul.tp, hn, numa, n, numb, n, &ctx->mul.fermat);
102 lmmp_mullo_crt_(dst, scratch, ctx->mul.tp, n, hn);
103}
104
106 lmmp_param_assert(dst != NULL && numa != NULL);
107 lmmp_param_assert(scratch != NULL && ctx != NULL);
109 lmmp_mul_fermat_cache_(ctx->mul.tp, numa, &ctx->mul.fermat);
110 lmmp_mullo_crt_(dst, scratch, ctx->mul.tp, ctx->n, ctx->hn);
111}
112
113/*
114 <---t---><---m--->
115 |--a1---|---a0---|
116 |--b1---|---b0---|
117
118 ,
119 |\
120 | \
121 | \
122 +-----,
123 | |
124 | |\
125 | | \
126 | | \
127 +-----+---`
128 ^ m ^ t ^
129
130 此算法是一种不平衡分块的算法,朴素的想法是计算平衡分块,计算一次完整的乘法,然后两次递归的调用此函数计算低位,
131 事实上,我们也可以不平衡的分块,以减少递归深度,具体分析如下:
132 取a和b的低位一定宽度为m,高位宽度为t,则有:
133 计算一次完整的平衡乘法m,然后递归调用计算mullo,长度为t
134 复杂度模型:
135 ML(n) = 2*ML(a*n) + M((1-a)*n)
136 其中ML为mullo的复杂度,M为mul_n的复杂度
137 我们可以假定 M(n)=O(n^e) 即多项式复杂度
138 则有:
139 ML(n) = C(a) * n^e
140 C(a) = a^e / (1-2*(1-a)^e)
141 我们希望C(a)尽可能小,即希望ML(n)尽可能小,则有:
142 a_opt = 1 - 2^(-1/(e-1))
143 e=log(3)/log(2) [Toom-2] -> a ~= 0.694
144 e=log(5)/log(3) [Toom-3] -> a ~= 0.775
145 e=log(7)/log(4) [Toom-4] -> a ~= 0.820
146 e=log(11)/log(6) [Toom-6] -> a ~= 0.871
147 e=log(15)/log(8) [Toom-8] -> a ~= 0.899
148*/
149
151 mp_ptr restrict dst,
152 mp_srcptr restrict numa,
156) {
158 lmmp_mullo_basecase_(dst, numa, numb, n);
159 return;
160 } else {
161 mp_size_t m, t;
162 if (n < MUL_TOOM33_THRESHOLD) {
163 m = 25 * n / 36;
164 } else if (n < MUL_TOOM44_THRESHOLD) {
165 m = 31 * n / 40;
166 } else if (n < MUL_TOOM6H_THRESHOLD) {
167 m = 32 * n / 39;
168 } else if (n < MUL_TOOM8H_THRESHOLD) {
169 m = 27 * n / 31;
170 } else {
171 m = 9 * n / 10;
172 }
173 t = n - m;
174 lmmp_debug_assert(2 * n > 4 * t);
175
176#define a0 (numa) // [numa, m]
177#define a1 (numa + m) // [numa+m, t]
178#define b0 (numb) // [numb, m]
179#define b1 (numb + m) // [numb+m, t]
180#define c0 (dst) // [dst, m]
181#define c1 (dst + m) // [dst+m, t]
182#define lo1 (tp) // [tp, t]
183#define lo2 (tp + t) // [tp+t, t]
184#define scratch (tp + 2 * t) // [tp+2*t, 2*t]
185 lmmp_mul_n_(tp, a0, b0, m);
186 lmmp_copy(c0, tp, n);
189 lmmp_add_n_(c1, c1, lo1, t);
190 lmmp_add_n_(c1, c1, lo2, t);
191 return;
192 }
193#undef a0
194#undef a1
195#undef b0
196#undef b1
197#undef c0
198#undef c1
199#undef lo1
200#undef lo2
201#undef scratch
202}
203
206 lmmp_sqrlo_basecase_(dst, numa, n);
207 return;
208 } else {
209 mp_size_t m, t;
210 if (n < MUL_TOOM33_THRESHOLD) {
211 m = 25 * n / 36;
212 } else if (n < MUL_TOOM44_THRESHOLD) {
213 m = 31 * n / 40;
214 } else if (n < MUL_TOOM6H_THRESHOLD) {
215 m = 32 * n / 39;
216 } else if (n < MUL_TOOM8H_THRESHOLD) {
217 m = 27 * n / 31;
218 } else {
219 m = 9 * n / 10;
220 }
221 t = n - m;
222
223#define a0 (numa)
224#define a1 (numa + m)
225#define c0 (dst)
226#define c1 (dst + m)
227#define lo (tp) // [tp, t]
228#define scratch (tp + t) // [tp+t, 2*t]
229 lmmp_sqr_(tp, a0, m);
230 lmmp_copy(c0, tp, n);
233 }
234#undef a0
235#undef a1
236#undef c0
237#undef c1
238#undef lo
239#undef scratch
240}
241
243 lmmp_param_assert(n > 0);
244 if (n < MULLO_DC_THRESHOLD) {
245 if (numa == numb) {
246 TEMP_DECL;
248 lmmp_sqrlo_dc_(dst, numa, tp, n);
249 TEMP_FREE;
250 return;
251 }
252 TEMP_DECL;
254 lmmp_mullo_dc_(dst, numa, numb, tp, n);
255 TEMP_FREE;
256 return;
257 } else {
258 TEMP_DECL;
260 lmmp_mullo_fft_(dst, numa, numb, n, tp);
261 TEMP_FREE;
262 return;
263 }
264}
#define lmmp_mul_n_
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
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
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define MUL_TOOM8H_THRESHOLD
#define MULLO_BASECASE_THRESHOLD
#define MUL_TOOM33_THRESHOLD
#define MUL_TOOM6H_THRESHOLD
#define MULLO_DC_THRESHOLD
#define MUL_TOOM44_THRESHOLD
mp_limb_t lmmp_shr1add_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带进位加法后右移1位 [dst,n] = ([numa,n] + [numb,n] + c) >> 1
定义 shr.c:53
void lmmp_sqrlo_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
基础低位平方 [dst,n] = [numa,n]^2 mod B^n
void lmmp_mul_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mullo_dc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_ptr tp, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] 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
#define lmmp_inc(p)
加1宏(预期无进位)
void lmmp_sqr_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
FFT 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
void lmmp_mul_fermat_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
费马数模乘法 [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
void lmmp_sqr_fermat_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
SSA FFT 版费马数模平方 [dst,rn+1]=[numa,na]^2 mod B^rn+1
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_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
void lmmp_sqrlo_dc_(mp_ptr dst, mp_srcptr numa, mp_ptr tp, mp_size_t n)
低位平方 [dst,n] = [numa,n]^2 mod B^n
void lmmp_mullo_fft_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch)
低位FFT乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
定义 mullo.c:68
#define lmmp_dec_1(p, dec)
减指定值宏(预期无借位)
static mp_limb_t lmmp_sub_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
减单精度数静态内联函数 [dst,na]=[numa,na]-x
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
void lmmp_mullo_(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_sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
定义 sub_n.c:67
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
mp_size_t na
void lmmp_mul_mersenne_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
fft_gr_cache mersenne
mp_size_t nb
mp_size_t hn
void lmmp_mullo_fft_cache_(mp_ptr dst, mp_srcptr numa, mp_ptr scratch, fft_mullo_cache *ctx)
低位乘法(缓存版) [dst,n] = [numa,n] * 缓存numb mod B^n
fft_gr_cache fermat
void lmmp_mul_fermat_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
void lmmp_mul_fermat_cache_init_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1 第二个操作数将被缓存
void lmmp_mullo_fft_cache_init_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch, fft_mullo_cache *ctx)
低位乘法(缓存版) [dst,n] = [numa,n] * [numb,n] mod B^n 第二个操作数将被缓存
定义 mullo.c:86
void lmmp_mul_mersenne_cache_init_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1 第二个操作数将被缓存
#define b0
#define b1
#define a0
#define a1
#define t
#define numb
#define tp
#define n
#define scratch
#define lo
#define lo2
static void lmmp_mullo_crt_(mp_ptr dst, mp_ptr lp, mp_ptr hp, mp_size_t n, mp_size_t hn)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 mullo.c:46
#define c1
#define c0
#define lo1
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define ALLOC_TYPE(n, type)
#define TEMP_FREE
#define TALLOC_TYPE(n, type)