LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
trialdiv.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/numth.h"
24#include "lmmp/lmmpn.h"
25#include "impl/inlines.h"
26#include "impl/longlong.h"
27#include "mparam.h"
28#include "impl/prime_table.h"
29#include "impl/tmp_alloc.h"
30#include "impl/trialdiv.h"
31
32#define MAX_T ((ulong)0x7fffffffffff)
33
34/* 块数的理论上限:全部奇素数的乘积不到 2^94548(θ(65535) < 65535),而每个
35 * 满块的积都不小于 2^47,所以满块至多 2011 个,再加最后一个乘不满的块,总共
36 * 不会超过 2012 个。容量翻倍时以它封顶,绝不给出超出这个数的空间 */
37#define TRIALDIV_BLK_MAX ((ushort)2012)
38
39/**
40 * 块内字段分三组、各按水位 [0,bn_x) 惰性初始化,纯小 nn 负载不付 chunk
41 * 组预处理、纯大 nn 负载不付 preinv 组预处理:
42 * 打包组 t/p0/pn 建块即得
43 * preinv 组 k/inv 首个 preinv 腿调用覆盖到该块时算
44 * chunk 组 dinv/r2/base/mi 首个 chunk 腿调用覆盖到该块时算
45 */
46typedef struct trialdiv_blk {
47 ulong t; // 块积,也即除数
48 ulong inv; // preinv 组:lmmp_inv_1_(t<<k)
49 ulong dinv; // chunk 组:t*dinv==1 mod B
50 ulong r2; // chunk 组:B^2 mod t
51 ulong base; // chunk 组:B mod t
52 ulong mi; // chunk 组:-dinv mod B
53 ushort p0; // 打包组:块首素数在 prime_short_table 的下标
54 ushort pn; // 打包组:块内素数个数
55 uchar k; // preinv 组:lmmp_leading_zeros_(t)
57
58typedef struct {
60 ushort blkc; // blks 容量
61 ushort bn; // 打包组水位:已闭块数
62 ushort bn_inv; // preinv 组已初始化容量
63 ushort bn_chunk; // chunk 组已初始化容量
64 ushort pi; // 打包游标:下一素数下标
65 ulong t; // 开块部分积(扩容后恒 1:开块总在扩容内闭掉)
67
69 .blks = NULL, .blkc = 0, .bn = 0, .bn_inv = 0,
70 .bn_chunk = 0, .pi = 1, .t = 1,
71};
72
73/**
74 * @brief 把开块落盘成 blks[bn] 里的一个新块,随后开块清空
75 * @note 新块的块首下标接在上一块末尾之后,首块从下标 1 开始(素数 2 不打包)。
76 * blks 放不下时容量翻倍,但封顶 TRIALDIV_BLK_MAX;realloc 会原样保留
77 * 旧块内容,不需要重算任何字段
78 */
79static void trialdiv_close(void) {
80 if (G.bn == G.blkc) {
81 G.blkc = G.blkc ? G.blkc * 2 : 32;
82 if (G.blkc > TRIALDIV_BLK_MAX) G.blkc = TRIALDIV_BLK_MAX;
83 G.blks = REALLOC_TYPE(G.blks, G.blkc, trialdiv_blk);
84 }
85 trialdiv_blk* b = &G.blks[G.bn];
86 ushort p0 = G.bn ? (ushort)(G.blks[G.bn - 1].p0 + G.blks[G.bn - 1].pn) : 1;
87 b->t = G.t;
88 b->p0 = p0;
89 b->pn = (ushort)(G.pi - p0);
90 ++G.bn;
91 G.t = 1;
92}
93
94/**
95 * @brief 打包素数,把下标 [1,cnt) 内的奇素数全部收进闭块
96 * @param cnt <=N 的素数个数,即 lmmp_prime_cnt16_(N) 的返回值(含素数 2)
97 * @note 素数逐个乘进开块,乘积一超过 MAX_T 就闭一块。盖住 cnt 之后,如果
98 * 开块乘积还没满,会继续乘到满块才停。故表中存储的均是完整块,块的
99 * 划分与 N 无关,扩容永远是纯追加,开块也从不跨调用留存。素数表用尽时
100 * 最后一块无法乘满,自动闭合。
101 */
102static void trialdiv_extend_(ushort cnt) {
103 while (G.pi < cnt || G.t > 1) {
104 if (G.pi == PRIME_SHORT_TABLE_SIZE) {
106 break;
107 }
108 G.t *= prime_short_table[G.pi++];
109 if (G.t > MAX_T) trialdiv_close();
110 }
111 lmmp_debug_assert(G.t == 1);
112}
113
114/**
115 * @brief 给 [bn_inv,n) 的块补算 k 和 inv
116 * @param n 要补至的块数,不超过 bn
117 */
119 for (ushort i = G.bn_inv; i < n; ++i) {
120 trialdiv_blk* b = &G.blks[i];
121 b->k = (uchar)lmmp_leading_zeros_(b->t);
122 b->inv = lmmp_inv_1_(b->t << b->k);
123 }
124 G.bn_inv = n;
125}
126
127/**
128 * @brief 给 [bn_chunk,n) 的块补算折叠腿要用的 dinv、mi、r2、base
129 * @param n 要补到的块数,不超过 bn
130 * @note dinv 是 t 模 2^64 的逆元,mi 就是它的相反数;r2 与 base 共享一次
131 * inv_1_ 未填的块顺手存进 preinv 组字段并推其水位(已填的块直接复用),
132 * 后续 preinv 腿免再算。已经算过的块不会再算
133 */
135 for (ushort i = G.bn_chunk; i < n; ++i) {
136 trialdiv_blk* b = &G.blks[i];
137 b->dinv = lmmp_binvert_ulong_(b->t);
138 b->mi = -b->dinv;
139 ulong m = b->t;
140 mp_bitcnt_t k = 0;
141 clz_shl_u64(m, m, k);
142 ulong inv;
143 if (i < G.bn_inv)
144 inv = b->inv;
145 else {
146 b->k = (uchar)k;
147 b->inv = inv = lmmp_inv_1_(m);
148 }
149 b->r2 = _bpow_preinv_(m, k, 2, inv);
150 b->base = _bpow_preinv_(m, k, 1, inv);
151 }
152 G.bn_chunk = n;
153 if (G.bn_inv < n) G.bn_inv = n;
154}
155
157
159 return lmmp_mod_preinv_1_(np, nn, b->t, b->inv, b->k);
160}
161
163 return lmmp_mod_4chunk_1_(np, nn, b->t, b->dinv, b->r2, b->base, b->mi);
164}
165
167 return lmmp_mod_8chunk_1_(np, nn, b->t, b->dinv, b->r2, b->base, b->mi);
168}
169
171 lmmp_param_assert(np != NULL);
172 lmmp_param_assert(nn > 0);
173
174 ushort cnt = lmmp_prime_cnt16_(N);
175 if (cnt <= 1) return false; /* N<3:无奇素数可试除 */
176
177 trialdiv_extend_(cnt);
178
179 /* 用满块前缀:块含 <=N 素数 ⟺ p0 < cnt(p0 升序,首块越界即停) */
180 ushort un = 0;
181 while (un < G.bn && G.blks[un].p0 < cnt) ++un;
182
183 trialdiv_leg_fn leg;
184 if (nn < TRIALDIV_PREINV_THRESHOLD) {
185 if (G.bn_inv < un) trialdiv_init_inv_(un);
187 } else if (nn < TRIALDIV_K8_THRESHOLD) {
188 if (G.bn_chunk < un) trialdiv_init_chunk_(un);
189 leg = trialdiv_leg_4_;
190 } else {
191 if (G.bn_chunk < un) trialdiv_init_chunk_(un);
192 leg = trialdiv_leg_8_;
193 }
194
195 for (ushort i = 0; i < un; ++i) {
196 const trialdiv_blk* b = &G.blks[i];
197 mp_limb_t r = leg(np, nn, b);
198 if (r == 0) return true;
199 for (ushort j = b->p0, e = (ushort)(b->p0 + b->pn); j < e; ++j)
200 if (r % prime_short_table[j] == 0) return true;
201 }
202 return false;
203}
204
206 lmmp_free(G.blks);
207 G.blks = NULL;
208 G.blkc = 0;
209 G.bn = 0;
210 G.bn_inv = 0;
211 G.bn_chunk = 0;
212 G.pi = 1;
213 G.t = 1;
214}
215
217 (mp_limb_t)(0x93cf359a5b74dee9), (mp_limb_t)(0x6badd25dadb36966), (mp_limb_t)(0x6ed3cd279e4bb4b6),
218 (mp_limb_t)(0xb66d6cd35ba6bb59), (mp_limb_t)(0xc976b2cde59a4f3c), (mp_limb_t)(0x34de792dd2f9a6b7),
219 (mp_limb_t)(0xb34d6e96ede59b4b), (mp_limb_t)(0xcf3696793ef259ad), (mp_limb_t)(0xf4b34b669add25fa),
220 (mp_limb_t)(0xfa4bb5966d2cd2f9), (mp_limb_t)(0x59a4f7c9e696cf35), (mp_limb_t)(0x2d9a7b76976b2cdb),
221 (mp_limb_t)(0xd659f4bb49e7b2cd), (mp_limb_t)(0xcf259a7b34d6e93e), (mp_limb_t)(0xadd65dacb36b66d3),
222 (mp_limb_t)(0xd2dd279e4b3cb769), (mp_limb_t)(0x696cdb5ba4bb5d66), (mp_limb_t)(0x77b2eda59acf3c96),
223 (mp_limb_t)(0x0000000000000001)};
#define k
#define MAX_T
#define lmmp_leading_zeros_
size_t mp_bitcnt_t
定义 lmmp.h:98
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 LMMP_THREAD_LOCAL
定义 lmmp.h:114
#define lmmp_param_assert(x)
定义 lmmp.h:509
mp_limb_t lmmp_mod_preinv_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x, mp_limb_t inv, mp_limb_t k)
单精度数取余(预备逆元版) [numa,na] mod x,同 lmmp_mod_1_
定义 div.c:89
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义 inv.c:124
static uint64_t _bpow_preinv_(uint64_t m, uint64_t k, int nb, uint64_t inv)
#define clz_shl_u64(r, x, cnt)
#define n
#define TRIALDIV_K8_THRESHOLD
#define TRIALDIV_PREINV_THRESHOLD
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 numth.h:34
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
uint16_t ushort
定义 numth.h:36
uint64_t ulong
定义 numth.h:39
#define G
#define PRIME_SHORT_TABLE_SIZE
const ushort prime_short_table[6542]
Copyright (C) 2026 HJimmyK (Jericho Knox)
ushort lmmp_prime_cnt16_(ushort n)
计算小于等于 n 的素数数量
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define REALLOC_TYPE(p, new_size, type)
mp_limb_t(*) trialdiv_leg_fn(mp_srcptr np, mp_size_t nn, const trialdiv_blk *b)
static void trialdiv_init_chunk_(ushort n)
给 [bn_chunk,n) 的块补算折叠腿要用的 dinv、mi、r2、base
static void trialdiv_close(void)
把开块落盘成 blks[bn] 里的一个新块,随后开块清空
static mp_limb_t trialdiv_leg_8_(mp_srcptr np, mp_size_t nn, const trialdiv_blk *b)
trialdiv_blk * blks
static void trialdiv_init_inv_(ushort n)
给 [bn_inv,n) 的块补算 k 和 inv
#define TRIALDIV_BLK_MAX
static mp_limb_t trialdiv_leg_4_(mp_srcptr np, mp_size_t nn, const trialdiv_blk *b)
static mp_limb_t trialdiv_leg_preinv_(mp_srcptr np, mp_size_t nn, const trialdiv_blk *b)
static void trialdiv_extend_(ushort cnt)
打包素数,把下标 [1,cnt) 内的奇素数全部收进闭块
块内字段分三组、各按水位 [0,bn_x) 惰性初始化,纯小 nn 负载不付 chunk 组预处理、纯大 nn 负载不付 preinv 组预处理: 打包组 t/p0/pn 建块即得 preinv 组 k...
mp_limb_t lmmp_mod_8chunk_1_(mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
8 链折叠取模:r = [numa,na] mod d
const mp_limb_t r35711_mask_map[19]
void lmmp_trialdiv_table_free_(void)
bool lmmp_trialdiv_(mp_srcptr np, mp_size_t nn, ushort N)
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_mod_4chunk_1_(mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
4 链折叠取模:r = [numa,na] mod d