LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_mul_mersenne.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 "lmmp/lmmpn.h"
24#include "impl/mul_cache.h"
25#include "mparam.h"
26#include "cases.h"
28
29#include <string.h>
30
31/*
32 梅森域乘法(B^rn - 1 卷绕)验证:oracle = 全积(lmmp_mul_,大尺寸走
33 FFT,与被测分治/数论路径算法族独立)+ 循环折叠 + 全 1 零类归一化
34 (B^rn-1 ≡ 0)——全库内路径,无自建算法。
35*/
36
37/* oracle:全积 + 循环折叠 + 零类归一化(B^rn-1 -> 0)——全库内路径 */
39 mp_ptr full) {
40 lmmp_zero(full, 2 * rn + 2);
41 if (na >= nb)
42 lmmp_mul_(full, a, na, b, nb);
43 else
44 lmmp_mul_(full, b, nb, a, na);
45 mp_size_t pn = na + nb;
46 if (pn <= rn) {
47 lmmp_copy(r, full, pn);
48 lmmp_zero(r + pn, rn - pn);
49 } else {
50 mp_limb_t cy = lmmp_add_(r, full, rn, full + rn, pn - rn);
51 lmmp_inc_1(r, cy);
52 }
53 mp_size_t i = 0;
54 while (i < rn && r[i] == ~(mp_limb_t)0) ++i;
55 if (i == rn) lmmp_zero(r, rn);
56}
57
58static bool limbs_same(const mp_limb_t* x, const mp_limb_t* y, mp_size_t n) {
59 return memcmp(x, y, (size_t)n * sizeof(mp_limb_t)) == 0;
60}
61
62TEST_CASE("mul/mersenne_dc", mersenne_dc_vs_oracle) {
63 u64 seed = 0x51ce5eed1a2b3c4dull;
64 const mp_size_t sizes[] = {2, 3, 5, 8, 13, 14, 16, 17, 31, 32, 64, 100, 256,
65 511, 512, 768, 1000, 1024, 1721, 2048, 3442};
66 for (size_t rn_index = 0; rn_index < ARRAY_SIZE(sizes); ++rn_index) {
67 mp_size_t rn = sizes[rn_index];
68 mp_size_t shapes[6][2] = {{rn, rn}, {rn, rn / 2 + 1}, {rn, 1},
69 {rn / 2 + 1, rn / 2 + 1}, {3 * rn / 4 + 1, rn / 4 + 1},
70 {rn / 2, rn / 4 + 1}}; // 末形 na+nb<=rn:无卷绕路径
71 for (size_t sh_index = 0; sh_index < ARRAY_SIZE(shapes); ++sh_index) {
72 const mp_size_t *sh = shapes[sh_index];
73 mp_size_t na = sh[0], nb = sh[1];
74 if (nb > na || na > rn || na + nb <= rn / 2) continue;
75 for (int mode = 0; mode < 3; ++mode) { // 0 随机 / 1 全 1(零类卷绕)/ 2 全 0
76 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb);
77 if (mode == 0) {
78 random_limbs(a, na, &seed);
79 random_limbs(b, nb, &seed);
80 } else if (mode == 1) {
81 for (mp_size_t i = 0; i < na; ++i) a[i] = ~(mp_limb_t)0;
82 for (mp_size_t i = 0; i < nb; ++i) b[i] = ~(mp_limb_t)0;
83 } else {
84 lmmp_zero(a, na);
85 lmmp_zero(b, nb);
86 }
87 mp_ptr r = alloc_limbs(rn), ro = alloc_limbs(rn), full = alloc_limbs(2 * rn + 2);
88 lmmp_mul_mersenne_dc_(r, rn, a, na, b, nb);
89 mersenne_oracle(ro, rn, a, na, b, nb, full);
90 TEST_CHECK(limbs_same(ro, r, rn));
91
92 lmmp_free(a); lmmp_free(b); lmmp_free(r); lmmp_free(ro); lmmp_free(full);
93 }
94 }
95
96 /* 平方:满长 / 3/4 长(2an>rn 路径)/ rn/4+1(2an<rn 路径,须 4an>rn)
97 / rn/2(2an==rn 边界);满长另走分派入口(fft 分支仅 an==rn 满足
98 rn = fft_next_size((2an+1)>>1) 前置,rn 不可行时回落 dc 亦被覆盖) */
99 mp_size_t ans[4] = {rn, 3 * rn / 4 + 1, rn > 2 ? rn / 4 + 1 : rn, rn / 2};
100 for (size_t an_index = 0; an_index < ARRAY_SIZE(ans); ++an_index) {
101 mp_size_t an = ans[an_index];
102 if (an > rn || 4 * an <= rn) continue;
103 for (int mode = 0; mode < 3; ++mode) { // 0 随机 / 1 全 1 / 2 全 0
104 mp_ptr a = alloc_limbs(an);
105 if (mode == 0)
106 random_limbs(a, an, &seed);
107 else if (mode == 1)
108 for (mp_size_t i = 0; i < an; ++i) a[i] = ~(mp_limb_t)0;
109 else
110 lmmp_zero(a, an);
111 mp_ptr r = alloc_limbs(rn), ro = alloc_limbs(rn), full = alloc_limbs(2 * rn + 2);
112 lmmp_sqr_mersenne_dc_(r, rn, a, an);
113 mersenne_oracle(ro, rn, a, an, a, an, full);
114 TEST_CHECK(limbs_same(ro, r, rn));
115 if (an == rn) {
116 /* 毒化 r:防分派入口未写/部分写时沿用 dc 结果通过 */
117 for (mp_size_t i = 0; i < rn; ++i) r[i] = ~ro[i];
118 lmmp_sqr_mersenne_(r, rn, a, an);
119 TEST_CHECK(limbs_same(ro, r, rn));
120 }
121 lmmp_free(a); lmmp_free(r); lmmp_free(ro); lmmp_free(full);
122 }
123 }
124 }
125}
126
127TEST_CASE("mul/mersenne_next_size", mersenne_next_size_props) {
128 for (mp_size_t n = 1; n <= 5000; ++n) {
130 TEST_CHECK(m >= n);
131 }
132 /* fft 档(nh 越过 MODF 阈值)输出 = 2*fft_next_size(nh):钉住对齐意图,
133 若退化为直接返回 n,分发入口在 rn>=FFT 阈值时回落 dc(性能回归
134 不可见于正确性用例)。不断言 m 本身 fft 可行——倍乘不保可行性
135 (nh=2171 可行而 2*2171=4342 不可行,fns(4342)=4344) */
136 for (mp_size_t n = 8 * (MUL_MERSENNE_DC_THRESHOLD - 1) + 1; n <= 5000; n += 97) {
137 if ((n + 1) >> 1 < MUL_FFT_MODF_THRESHOLD) continue;
139 }
140 /* 分发入口与 next_size 尺寸下的正确性 */
141 u64 seed = 0x2f6e1d5a9c83b701ull;
142 for (int t = 0; t < 16; ++t) {
143 mp_size_t n = 3 + (mp_size_t)(xorshift64(&seed) % 900);
144 mp_size_t rn = lmmp_mersenne_next_size_((n + n + 1) >> 1);
145 mp_ptr a = alloc_limbs(n), b = alloc_limbs(n);
146 mp_ptr r = alloc_limbs(rn), ro = alloc_limbs(rn), full = alloc_limbs(2 * rn + 2);
147 random_limbs(a, n, &seed);
148 random_limbs(b, n, &seed);
149 if (n + n > rn / 2) {
150 lmmp_mul_mersenne_(r, rn, a, n, b, n);
151 mersenne_oracle(ro, rn, a, n, b, n, full);
152 TEST_CHECK(limbs_same(ro, r, rn));
153 }
154 lmmp_free(a); lmmp_free(b); lmmp_free(r); lmmp_free(ro); lmmp_free(full);
155 }
156}
157
158TEST_CASE("mul/mersenne_fft", mersenne_fft_single_limb) {
159 const mp_limb_t a[] = {LIMB_MAX, 0, 1, 0x8123456789abcdefull};
160 const mp_limb_t b = 0xfedcba9876543210ull;
161 mp_limb_t dst[2] = {0, LIMB_MAX}, ref, full[4];
162 fft_gr_cache cache;
163 lmmp_mul_mersenne_cache_init_(dst, 1, a, 1, &b, 1, &cache);
164 mersenne_oracle(&ref, 1, a, 1, &b, 1, full);
165 TEST_CHECK(dst[0] == ref && dst[1] == LIMB_MAX);
166
167 for (size_t i = 0; i < ARRAY_SIZE(a); ++i) {
168 mersenne_oracle(&ref, 1, a + i, 1, &b, 1, full);
169 dst[0] = ~ref;
170 lmmp_mul_mersenne_cache_(dst, a + i, &cache);
171 TEST_CHECK(dst[0] == ref && dst[1] == LIMB_MAX);
172 dst[0] = ~ref;
173 lmmp_mul_mersenne_fft_(dst, 1, a + i, 1, &b, 1);
174 TEST_CHECK(dst[0] == ref && dst[1] == LIMB_MAX);
175 mersenne_oracle(&ref, 1, a + i, 1, a + i, 1, full);
176 dst[0] = ~ref;
177 lmmp_sqr_mersenne_fft_(dst, 1, a + i, 1);
178 TEST_CHECK(dst[0] == ref && dst[1] == LIMB_MAX);
179 }
181}
182
183TEST_CASE("mul/fermat_fft", fermat_cache_single_limb) {
184 const mp_limb_t a = 2, b = LIMB_B_2, next = 1;
185 mp_limb_t dst[3] = {LIMB_MAX, LIMB_MAX, LIMB_MAX};
186 fft_gr_cache cache;
187 lmmp_mul_fermat_cache_init_(dst, 1, &a, 1, &b, 1, &cache);
188 TEST_CHECK(dst[0] == 0 && dst[1] == 1 && dst[2] == LIMB_MAX);
189 lmmp_mul_fermat_cache_(dst, &next, &cache);
190 TEST_CHECK(dst[0] == b && dst[1] == 0 && dst[2] == LIMB_MAX);
192}
193
195 TEST_RUN("mul/mersenne_dc", mersenne_dc_vs_oracle);
196 TEST_RUN("mul/mersenne_next_size", mersenne_next_size_props);
197 TEST_RUN("mul/mersenne_fft", mersenne_fft_single_limb);
198 TEST_RUN("mul/fermat_fft", fermat_cache_single_limb);
199}
#define an
#define LIMB_B_2
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
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define LIMB_MAX
定义 lmmp.h:105
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define MUL_MERSENNE_DC_THRESHOLD
#define MUL_FFT_MODF_THRESHOLD
void test_mul_mersenne(void)
void lmmp_mul_mersenne_dc_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
分治梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mul_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
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]
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_sqr_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
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]
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
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
void lmmp_sqr_mersenne_dc_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
分治梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
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
static void lmmp_fft_gr_cache_free_(fft_gr_cache *ctx)
释放费马或梅森数模乘法缓存上下文
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_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 第二个操作数将被缓存
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define t
#define n
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_RUN(category, name)
定义 test.h:36
static bool limbs_same(const mp_limb_t *x, const mp_limb_t *y, mp_size_t n)
static void mersenne_oracle(mp_ptr r, mp_size_t rn, mp_srcptr a, mp_size_t na, mp_srcptr b, mp_size_t nb, mp_ptr full)
Copyright (C) 2026 HJimmyK (Jericho Knox)