LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
sqr_fft.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 "lmmpn/fft_ssa.h"
27#include "lmmp/lmmpn.h"
28
29
31 mp_ptr push_temp_coef = ms->temp_coef;
32 mp_size_t rn = ms->lenw;
33
34 if (rn < MUL_FFT_MODF_THRESHOLD) {
35 mp_ptr temp_mul = (mp_ptr)lmmp_fft_memstack_(ms, (rn + 1) * 2 * LIMB_BYTES);
36 for (mp_size_t i = 0; i < K0; ++i) {
37 lmmp_sqr_(temp_mul, pc1[i], rn + 1);
38
39 // 模 B^rn+1 归一化:temp_mul - temp_mul[rn ...]
40 mp_limb_t maxc = lmmp_sub_n_(pc1[i], temp_mul, temp_mul + rn, rn) + temp_mul[rn * 2];
41 pc1[i][rn] = 0;
42 lmmp_inc_1(pc1[i], maxc);
43 }
44 lmmp_fft_memstack_(ms, 0);
45 } else {
46 mp_size_t N = rn * LIMB_BITS;
48 mp_size_t K = ((mp_size_t)1) << k;
49 lmmp_debug_assert(!(N & (K - 1)));
50 mp_size_t M = N >> k;
51 mp_size_t n = 2 * M + k + 2;
52
53 n = (n + LIMB_BITS - 1) & (-LIMB_BITS);
54 n = (((n - 1) >> k) + 1) << k;
55
56 ms->lenw = n / LIMB_BITS;
57 mp_size_t nlen = ms->lenw + 1;
58
59 ms->temp_coef = (mp_ptr)lmmp_fft_memstack_(ms, (((nlen + 1) << k) + nlen) * LIMB_BYTES);
60 mp_ptr *pfca = (mp_ptr*)(ms->temp_coef + nlen);
61 for (mp_size_t i = 0; i < K; ++i) pfca[i] = (mp_ptr)(pfca + K) + i * nlen;
62
63 for (mp_size_t j = 0; j < K0; ++j) {
64 mp_ptr numa = pc1[j];
65
66 for (mp_size_t i = 0; i < K; ++i) {
67 lmmp_fft_extract_coef_(pfca[i], numa, M * i, M + (i == K - 1), ms->lenw);
68 if (i > 0)
69 lmmp_fft_shl_coef_(ms, pfca + i, i * n >> k);
70 }
71 lmmp_fft_(ms, pfca, k, n >> (k - 1));
72
73 // dot product
74 lmmp_sqr_fermat_recurse_(ms, pfca, K);
75
76 lmmp_ifft_(ms, pfca, k, n >> (k - 1));
77
78 lmmp_mul_fermat_recombine_(ms, numa, pfca, K, k, n, M, rn);
79 }
80 lmmp_fft_memstack_(ms, 0);
81 }
82
83 ms->temp_coef = push_temp_coef;
84 ms->lenw = rn;
85}
86
88 mp_size_t N = rn * LIMB_BITS;
90 mp_size_t K = ((mp_size_t)1) << k;
91 lmmp_debug_assert(!(N & (K - 1)));
92 mp_size_t M = N >> k;
93 mp_size_t n = 2 * M + k + 2;
94
95 n = (n + LIMB_BITS - 1) & (-LIMB_BITS);
96 n = (((n - 1) >> k) + 1) << k;
97
98 fft_memstack msr;
99 msr.maxdepth = -1;
100 msr.tempdepth = -1;
101 msr.lenw = n / LIMB_BITS;
102 mp_size_t nlen = msr.lenw + 1;
103
104 msr.temp_coef = (mp_ptr)lmmp_fft_memstack_(&msr, (((nlen + 1) << k) + nlen) * LIMB_BYTES);
105
106 mp_ptr *pfca = (mp_ptr*)(msr.temp_coef + nlen);
107 mp_size_t narest = na * LIMB_BITS;
108
109 for (mp_size_t i = 0; i < K; ++i) {
110 mp_size_t coeflen;
111 pfca[i] = (mp_ptr)(pfca + K) + i * nlen;
112 if (narest > 0) {
113 coeflen = M + (i == K - 1);
114 coeflen = LMMP_MIN(narest, coeflen);
115 narest -= coeflen;
116 lmmp_fft_extract_coef_(pfca[i], numa, M * i, coeflen, msr.lenw);
117 if (i > 0)
118 lmmp_fft_shl_coef_(&msr, pfca + i, i * n >> k);
119 } else {
120 lmmp_zero(pfca[i], nlen);
121 }
122 }
123 lmmp_fft_(&msr, pfca, k, n >> (k - 1));
124
125 lmmp_sqr_fermat_recurse_(&msr, pfca, K);
126
127 lmmp_ifft_(&msr, pfca, k, n >> (k - 1));
128
129 lmmp_mul_fermat_recombine_(&msr, dst, pfca, K, k, n, M, rn);
130
131 if (dst[rn] && !lmmp_zero_q_(dst, rn)) {
132 dst[rn] = 0;
133 lmmp_dec(dst);
134 }
135
136 lmmp_fft_memstack_(&msr, 0);
137}
138
140 mp_size_t N = rn * LIMB_BITS;
142 mp_size_t K = ((mp_size_t)1) << k;
143
144 lmmp_debug_assert(!(N & (K - 1)));
145 mp_size_t M = N >> k;
146 mp_size_t n = 2 * M + k;
147
148 n = (n + LIMB_BITS - 1) & (-LIMB_BITS);
149 n = (((n - 1) >> (k - 1)) + 1) << (k - 1);
150
151 fft_memstack msr;
152 msr.maxdepth = -1;
153 msr.tempdepth = -1;
154 msr.lenw = n / LIMB_BITS;
155 mp_size_t nlen = msr.lenw + 1;
156
157 msr.temp_coef = (mp_ptr)lmmp_fft_memstack_(&msr, (((nlen + 1) << k) + nlen) * LIMB_BYTES);
158
159 mp_ptr *pfca = (mp_ptr*)(msr.temp_coef + nlen);
160 mp_size_t narest = na * LIMB_BITS;
161
162 for (mp_size_t i = 0; i < K; ++i) {
163 mp_size_t coeflen;
164 pfca[i] = (mp_ptr)(pfca + K) + i * nlen;
165 if (narest > 0) {
166 coeflen = LMMP_MIN(narest, M);
167 narest -= coeflen;
168 lmmp_fft_extract_coef_(pfca[i], numa, M * i, coeflen, msr.lenw);
169 } else {
170 lmmp_zero(pfca[i], nlen);
171 }
172 }
173 lmmp_fft_(&msr, pfca, k, n >> (k - 1));
174
175 lmmp_sqr_fermat_recurse_(&msr, pfca, K);
176
177 lmmp_ifft_(&msr, pfca, k, n >> (k - 1));
178
179 mp_size_t rhead = 0, maxc = 0;
180 for (mp_size_t i = 0; i < K; ++i) {
181 lmmp_fft_shr_coef_(&msr, pfca + i, k);
182 mp_ptr nums = pfca[i];
183
184 if (nums[nlen - 1]) {
185 lmmp_dec(nums);
186 lmmp_debug_assert(nums[nlen - 1] == 1);
187 nums[nlen - 1] = 0;
188 }
189
190 mp_size_t roffset = i * M;
191 mp_size_t shl = roffset & (LIMB_BITS - 1);
192 roffset /= LIMB_BITS;
193
194 if (shl)
195 lmmp_shl_(nums, nums, nlen, shl);
196
197 if (i == 0) {
198 rhead = LMMP_MIN(nlen, rn);
199 lmmp_copy(dst, nums, rhead);
200 } else if (roffset + nlen <= rn) {
201 lmmp_add_(dst + roffset, nums, nlen, dst + roffset, rhead - roffset);
202 rhead = roffset + nlen;
203 } else {
204 maxc += lmmp_add_(dst + roffset, nums, rn - roffset, dst + roffset, rhead - roffset);
205 maxc += lmmp_add_(dst, dst, rn, nums + rn - roffset, nlen + roffset - rn);
206 rhead = rn;
207 }
208 }
209
210 if (!lmmp_add_1_(dst, dst, rn, 1 + maxc))
211 lmmp_dec(dst);
212
213 lmmp_fft_memstack_(&msr, 0);
214}
215
217 lmmp_param_assert(na > 0);
218 lmmp_param_assert(dst != NULL && numa != NULL);
220 lmmp_debug_assert(na <= hn);
221 mp_ptr tp = ALLOC_TYPE(hn + 1, mp_limb_t);
222
223 lmmp_sqr_mersenne_fft_(dst, hn, numa, na);
224 lmmp_sqr_fermat_(tp, hn, numa, na);
225
226 mp_limb_t cy = lmmp_shr1add_nc_(dst, dst, tp, hn, tp[hn]);
227 cy <<= LIMB_BITS - 1;
228 dst[hn - 1] += cy;
229 if (dst[hn - 1] < cy)
230 lmmp_inc(dst);
231
232 if (na == hn) {
233 cy = tp[hn] + lmmp_sub_n_(dst + hn, dst, tp, hn);
234 // cy==1 means [tp,hn+1]!=0, then [dst,hn]!=0
235 // cy==2 is impossible since [tp,hn+1] is normalized.
236 // so the following dec won't overflow.
237 lmmp_dec_1(dst, cy);
238 } else {
239 cy = lmmp_sub_n_(dst + hn, dst, tp, 2 * na - hn);
240 cy = tp[hn] + lmmp_sub_nc_(tp + 2 * na - hn, dst + 2 * na - hn, tp + 2 * na - hn, 2 * hn - (2 * na), cy);
241 cy = lmmp_sub_1_(dst, dst, 2 * na, cy);
242 }
243 lmmp_free(tp);
244}
#define k
mp_size_t lmmp_fft_best_k_(mp_size_t n)
查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
void lmmp_fft_shr_coef_(fft_memstack *ms, mp_ptr *coef, mp_size_t shr)
对模 2^n+1 的系数执行右移操作 右移shr位 = 左移(2n - shr)位(mod 2^n+1的循环特性)
void lmmp_fft_shl_coef_(fft_memstack *ms, mp_ptr *coef, mp_size_t shl)
对模 2^n+1 的系数执行左移操作
void lmmp_mul_fermat_recombine_(fft_memstack *ms, mp_ptr dst, mp_ptr *pfca, mp_size_t K, mp_size_t k, mp_size_t n, mp_size_t M, mp_size_t rn)
费马变换 模 B^n+1 乘法的结果合并
void * lmmp_fft_memstack_(fft_memstack *ms, mp_size_t size)
FFT内存栈的分配/释放接口
void lmmp_ifft_(fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
void lmmp_fft_extract_coef_(mp_ptr dst, mp_srcptr numa, mp_size_t bitoffset, mp_size_t bits, mp_size_t lenw)
[dst,lenw+1] = [(bit*)numa+bitoffset, bits]
void lmmp_fft_(fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
mp_ssize_t maxdepth
mp_ssize_t tempdepth
mp_size_t lenw
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
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_BYTES
定义 lmmp.h:103
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define MUL_FFT_MODF_THRESHOLD
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]
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
#define lmmp_dec(p)
减1宏(预期无借位)
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
#define lmmp_inc(p)
加1宏(预期无进位)
void lmmp_sqr_fft_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
FFT平方运算 [dst,2*na] = [numa,na]^2
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_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_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
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_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
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
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
#define tp
#define n
static void lmmp_sqr_fermat_recurse_(fft_memstack *ms, mp_ptr *pc1, mp_size_t K0)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define ALLOC_TYPE(n, type)