LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
trialdiv.c 文件参考
#include "lmmp/numth.h"
#include "lmmp/lmmpn.h"
#include "impl/inlines.h"
#include "impl/longlong.h"
#include "mparam.h"
#include "impl/prime_table.h"
#include "impl/tmp_alloc.h"
#include "impl/trialdiv.h"
trialdiv.c 的引用(Include)关系图:

浏览该文件的源代码.

结构体

struct  trialdiv_blk
 块内字段分三组、各按水位 [0,bn_x) 惰性初始化,纯小 nn 负载不付 chunk 组预处理、纯大 nn 负载不付 preinv 组预处理: 打包组 t/p0/pn 建块即得 preinv 组 k/inv 首个 preinv 腿调用覆盖到该块时算 chunk 组 dinv/r2/base/mi 首个 chunk 腿调用覆盖到该块时算 更多...
struct  trialdiv_table

宏定义

#define MAX_T   ((ulong)0x7fffffffffff)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TRIALDIV_BLK_MAX   ((ushort)2012)

类型定义

typedef struct trialdiv_blk trialdiv_blk
 块内字段分三组、各按水位 [0,bn_x) 惰性初始化,纯小 nn 负载不付 chunk 组预处理、纯大 nn 负载不付 preinv 组预处理: 打包组 t/p0/pn 建块即得 preinv 组 k/inv 首个 preinv 腿调用覆盖到该块时算 chunk 组 dinv/r2/base/mi 首个 chunk 腿调用覆盖到该块时算
typedef mp_limb_t(*) trialdiv_leg_fn(mp_srcptr np, mp_size_t nn, const trialdiv_blk *b)

函数

bool lmmp_trialdiv_ (mp_srcptr restrict np, mp_size_t nn, ushort N)
void lmmp_trialdiv_table_free_ (void)
static void trialdiv_close (void)
 把开块落盘成 blks[bn] 里的一个新块,随后开块清空
static void trialdiv_extend_ (ushort cnt)
 打包素数,把下标 [1,cnt) 内的奇素数全部收进闭块
static void trialdiv_init_chunk_ (ushort n)
 给 [bn_chunk,n) 的块补算折叠腿要用的 dinv、mi、r2、base
static void trialdiv_init_inv_ (ushort n)
 给 [bn_inv,n) 的块补算 k 和 inv
static mp_limb_t trialdiv_leg_4_ (mp_srcptr np, mp_size_t nn, const trialdiv_blk *b)
static mp_limb_t trialdiv_leg_8_ (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 __thread trialdiv_table G
const mp_limb_t r35711_mask_map [19]

结构体说明

◆ trialdiv_blk

struct trialdiv_blk

块内字段分三组、各按水位 [0,bn_x) 惰性初始化,纯小 nn 负载不付 chunk 组预处理、纯大 nn 负载不付 preinv 组预处理: 打包组 t/p0/pn 建块即得 preinv 组 k/inv 首个 preinv 腿调用覆盖到该块时算 chunk 组 dinv/r2/base/mi 首个 chunk 腿调用覆盖到该块时算

在文件 trialdiv.c 第 46 行定义.

trialdiv_blk 的协作图:
成员变量
ulong base
ulong dinv
ulong inv
uchar k
ulong mi
ushort p0
ushort pn
ulong r2
ulong t

◆ trialdiv_table

struct trialdiv_table

在文件 trialdiv.c 第 58 行定义.

trialdiv_table 的协作图:
成员变量
ushort blkc
trialdiv_blk * blks
ushort bn
ushort bn_chunk
ushort bn_inv
ushort pi
ulong t

宏定义说明

◆ MAX_T

#define MAX_T   ((ulong)0x7fffffffffff)

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 trialdiv.c 第 32 行定义.

◆ TRIALDIV_BLK_MAX

#define TRIALDIV_BLK_MAX   ((ushort)2012)

在文件 trialdiv.c 第 37 行定义.

被这些函数引用 trialdiv_close().

类型定义说明

◆ trialdiv_blk

typedef struct trialdiv_blk trialdiv_blk

块内字段分三组、各按水位 [0,bn_x) 惰性初始化,纯小 nn 负载不付 chunk 组预处理、纯大 nn 负载不付 preinv 组预处理: 打包组 t/p0/pn 建块即得 preinv 组 k/inv 首个 preinv 腿调用覆盖到该块时算 chunk 组 dinv/r2/base/mi 首个 chunk 腿调用覆盖到该块时算

◆ trialdiv_leg_fn

typedef mp_limb_t(*) trialdiv_leg_fn(mp_srcptr np, mp_size_t nn, const trialdiv_blk *b)

在文件 trialdiv.c 第 156 行定义.

函数说明

◆ lmmp_trialdiv_()

bool lmmp_trialdiv_ ( mp_srcptr restrict np,
mp_size_t nn,
ushort N )

在文件 trialdiv.c 第 170 行定义.

170 {
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}
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define TRIALDIV_K8_THRESHOLD
#define TRIALDIV_PREINV_THRESHOLD
uint16_t ushort
定义 numth.h:36
#define G
const ushort prime_short_table[6542]
Copyright (C) 2026 HJimmyK (Jericho Knox)
ushort lmmp_prime_cnt16_(ushort n)
计算小于等于 n 的素数数量
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 mp_limb_t trialdiv_leg_8_(mp_srcptr np, mp_size_t nn, const trialdiv_blk *b)
static void trialdiv_init_inv_(ushort n)
给 [bn_inv,n) 的块补算 k 和 inv
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...

引用了 G, lmmp_param_assert, lmmp_prime_cnt16_(), lmmp_trialdiv_(), trialdiv_blk::p0, trialdiv_blk::pn, prime_short_table, restrict, trialdiv_extend_(), trialdiv_init_chunk_(), trialdiv_init_inv_(), TRIALDIV_K8_THRESHOLD, trialdiv_leg_4_(), trialdiv_leg_8_(), trialdiv_leg_preinv_() , 以及 TRIALDIV_PREINV_THRESHOLD.

函数调用图:

◆ lmmp_trialdiv_table_free_()

void lmmp_trialdiv_table_free_ ( void )

在文件 trialdiv.c 第 205 行定义.

205 {
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}
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)

引用了 G, lmmp_free() , 以及 lmmp_trialdiv_table_free_().

被这些函数引用 lmmp_trialdiv_() , 以及 lmmp_trialdiv_table_free_().

函数调用图:
这是这个函数的调用关系图:

◆ trialdiv_close()

void trialdiv_close ( void )
static

把开块落盘成 blks[bn] 里的一个新块,随后开块清空

注解
新块的块首下标接在上一块末尾之后,首块从下标 1 开始(素数 2 不打包)。 blks 放不下时容量翻倍,但封顶 TRIALDIV_BLK_MAX;realloc 会原样保留 旧块内容,不需要重算任何字段

在文件 trialdiv.c 第 79 行定义.

79 {
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}
#define REALLOC_TYPE(p, new_size, type)
#define TRIALDIV_BLK_MAX

引用了 G, trialdiv_blk::p0, trialdiv_blk::pn, REALLOC_TYPE, trialdiv_blk::t, TRIALDIV_BLK_MAX , 以及 trialdiv_close().

被这些函数引用 trialdiv_close() , 以及 trialdiv_extend_().

函数调用图:
这是这个函数的调用关系图:

◆ trialdiv_extend_()

void trialdiv_extend_ ( ushort cnt)
static

打包素数,把下标 [1,cnt) 内的奇素数全部收进闭块

参数
cnt<=N 的素数个数,即 lmmp_prime_cnt16_(N) 的返回值(含素数 2)
注解
素数逐个乘进开块,乘积一超过 MAX_T 就闭一块。盖住 cnt 之后,如果 开块乘积还没满,会继续乘到满块才停。故表中存储的均是完整块,块的 划分与 N 无关,扩容永远是纯追加,开块也从不跨调用留存。素数表用尽时 最后一块无法乘满,自动闭合。

在文件 trialdiv.c 第 102 行定义.

102 {
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}
#define MAX_T
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define PRIME_SHORT_TABLE_SIZE
static void trialdiv_close(void)
把开块落盘成 blks[bn] 里的一个新块,随后开块清空

引用了 G, lmmp_debug_assert, MAX_T, prime_short_table, PRIME_SHORT_TABLE_SIZE, trialdiv_close() , 以及 trialdiv_extend_().

被这些函数引用 lmmp_trialdiv_() , 以及 trialdiv_extend_().

函数调用图:
这是这个函数的调用关系图:

◆ trialdiv_init_chunk_()

void trialdiv_init_chunk_ ( ushort n)
static

给 [bn_chunk,n) 的块补算折叠腿要用的 dinv、mi、r2、base

参数
n要补到的块数,不超过 bn
注解
dinv 是 t 模 2^64 的逆元,mi 就是它的相反数;r2 与 base 共享一次 inv_1_ 未填的块顺手存进 preinv 组字段并推其水位(已填的块直接复用), 后续 preinv 腿免再算。已经算过的块不会再算

在文件 trialdiv.c 第 134 行定义.

134 {
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}
#define k
size_t mp_bitcnt_t
定义 lmmp.h:98
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
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 numth.h:34
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
uint64_t ulong
定义 numth.h:39

引用了 _bpow_preinv_(), trialdiv_blk::base, clz_shl_u64, trialdiv_blk::dinv, G, trialdiv_blk::inv, k, trialdiv_blk::k, lmmp_binvert_ulong_(), lmmp_inv_1_(), trialdiv_blk::mi, n, trialdiv_blk::r2, trialdiv_blk::t , 以及 trialdiv_init_chunk_().

被这些函数引用 lmmp_trialdiv_() , 以及 trialdiv_init_chunk_().

函数调用图:
这是这个函数的调用关系图:

◆ trialdiv_init_inv_()

void trialdiv_init_inv_ ( ushort n)
static

给 [bn_inv,n) 的块补算 k 和 inv

参数
n要补至的块数,不超过 bn

在文件 trialdiv.c 第 118 行定义.

118 {
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}
#define lmmp_leading_zeros_

引用了 G, trialdiv_blk::inv, trialdiv_blk::k, lmmp_inv_1_(), lmmp_leading_zeros_, n, trialdiv_blk::t , 以及 trialdiv_init_inv_().

被这些函数引用 lmmp_trialdiv_() , 以及 trialdiv_init_inv_().

函数调用图:
这是这个函数的调用关系图:

◆ trialdiv_leg_4_()

mp_limb_t trialdiv_leg_4_ ( mp_srcptr np,
mp_size_t nn,
const trialdiv_blk * b )
static

在文件 trialdiv.c 第 162 行定义.

162 {
163 return lmmp_mod_4chunk_1_(np, nn, b->t, b->dinv, b->r2, b->base, b->mi);
164}
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

引用了 trialdiv_blk::base, trialdiv_blk::dinv, lmmp_mod_4chunk_1_(), trialdiv_blk::mi, trialdiv_blk::r2, trialdiv_blk::t , 以及 trialdiv_leg_4_().

被这些函数引用 lmmp_trialdiv_() , 以及 trialdiv_leg_4_().

函数调用图:
这是这个函数的调用关系图:

◆ trialdiv_leg_8_()

mp_limb_t trialdiv_leg_8_ ( mp_srcptr np,
mp_size_t nn,
const trialdiv_blk * b )
static

在文件 trialdiv.c 第 166 行定义.

166 {
167 return lmmp_mod_8chunk_1_(np, nn, b->t, b->dinv, b->r2, b->base, b->mi);
168}
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

引用了 trialdiv_blk::base, trialdiv_blk::dinv, lmmp_mod_8chunk_1_(), trialdiv_blk::mi, trialdiv_blk::r2, trialdiv_blk::t , 以及 trialdiv_leg_8_().

被这些函数引用 lmmp_trialdiv_() , 以及 trialdiv_leg_8_().

函数调用图:
这是这个函数的调用关系图:

◆ trialdiv_leg_preinv_()

mp_limb_t trialdiv_leg_preinv_ ( mp_srcptr np,
mp_size_t nn,
const trialdiv_blk * b )
static

在文件 trialdiv.c 第 158 行定义.

158 {
159 return lmmp_mod_preinv_1_(np, nn, b->t, b->inv, b->k);
160}
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

引用了 trialdiv_blk::inv, trialdiv_blk::k, lmmp_mod_preinv_1_(), trialdiv_blk::t , 以及 trialdiv_leg_preinv_().

被这些函数引用 lmmp_trialdiv_() , 以及 trialdiv_leg_preinv_().

函数调用图:
这是这个函数的调用关系图:

变量说明

◆ G

__thread trialdiv_table G
static
初始值:
= {
.blks = NULL, .blkc = 0, .bn = 0, .bn_inv = 0,
.bn_chunk = 0, .pi = 1, .t = 1,
}

在文件 trialdiv.c 第 68 行定义.

◆ r35711_mask_map

const mp_limb_t r35711_mask_map[19]
初始值:
= {
(mp_limb_t)(0x93cf359a5b74dee9), (mp_limb_t)(0x6badd25dadb36966), (mp_limb_t)(0x6ed3cd279e4bb4b6),
(mp_limb_t)(0xb66d6cd35ba6bb59), (mp_limb_t)(0xc976b2cde59a4f3c), (mp_limb_t)(0x34de792dd2f9a6b7),
(mp_limb_t)(0xb34d6e96ede59b4b), (mp_limb_t)(0xcf3696793ef259ad), (mp_limb_t)(0xf4b34b669add25fa),
(mp_limb_t)(0xfa4bb5966d2cd2f9), (mp_limb_t)(0x59a4f7c9e696cf35), (mp_limb_t)(0x2d9a7b76976b2cdb),
(mp_limb_t)(0xd659f4bb49e7b2cd), (mp_limb_t)(0xcf259a7b34d6e93e), (mp_limb_t)(0xadd65dacb36b66d3),
(mp_limb_t)(0xd2dd279e4b3cb769), (mp_limb_t)(0x696cdb5ba4bb5d66), (mp_limb_t)(0x77b2eda59acf3c96),
(mp_limb_t)(0x0000000000000001)}

在文件 trialdiv.c 第 216 行定义.

被这些函数引用 lmmp_trialdiv_() , 以及 trial_div35711().