LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
is_prime_ulong.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 "
prime_pool.h
"
24
25
/* 顶位起始的随机奇数池(<=64bit),元素个数 POOL;kind 过滤同 pool_n:
26
PRIME 素数(next_prime 构造,全基底执行)/ COPRIME 试除幸存者 */
27
static
mp_ptr
pool_bits
(
uint
bits,
mp_limb_t
seed,
PrimePool
kind) {
28
if
(bits < 2) bits = 2;
/* 1-bit 奇数仅有值 1:退化且与标注位宽不符 */
29
if
(bits > 64) bits = 64;
30
mp_ptr
a = alloc_limbs(
POOL
);
31
for
(
int
i = 0; i <
POOL
; i++) {
32
lmmp_seed_random_
(a + i, 1, seed + i, 1);
33
if
(bits < 64) a[i] &= ((
mp_limb_t
)-1) >> (64 - bits);
34
a[i] |= (
mp_limb_t
)1 << (bits - 1);
35
a[i] |= 1;
36
if
(kind ==
PRIME_POOL_COPRIME
) {
37
/* 步进不得越出指定位宽:将越界时重采样候选而非沿用更宽的值
38
(bits>=10 域内幸存者密度 ~1/7,重采样几乎不触发;bits<=9
39
域内无 >1000 素因子的幸存者,由入口拒绝) */
40
uint
tries = 0;
41
while
(small_factor_q(a + i, 1)) {
42
if
(bits < 64 && ((a[i] + 2) >> bits) != 0) {
43
lmmp_seed_random_
(a + i, 1, seed + i + 0x9e37ull * ++tries, 1);
44
a[i] &= ((
mp_limb_t
)-1) >> (64 - bits);
45
a[i] |= (
mp_limb_t
)1 << (bits - 1);
46
a[i] |= 1;
47
}
else
{
48
a[i] += 2;
49
}
50
}
51
}
else
if
(kind ==
PRIME_POOL_PRIME
) {
52
a[i] =
lmmp_next_prime_ulong_
(a[i]);
53
}
54
}
55
return
a;
56
}
57
58
static
double
bench_is_prime_ulong_notrial
(
uint
bits,
PrimePool
kind,
const
bench_options
*o) {
59
/* COPRIME 域内须存在试除幸存者(最小 1009 需 10 位):更窄位宽
60
拒绝测量,不得以更宽的值冒充请求位宽 */
61
if
(kind ==
PRIME_POOL_COPRIME
&& bits < 10)
return
0.0;
62
mp_ptr
a =
pool_bits
(bits, 0x51ce25c0ff33ull + bits, kind);
63
size_t
idx = 0;
64
double
us;
65
BENCH_MEASURE
(us, o, bench_sink += (
mp_limb_t
)
lmmp_is_prime_ulong_notrial_
(a[idx++ & (
POOL
- 1)]););
66
lmmp_free
(a);
67
return
us;
68
}
69
70
static
double
bench_is_prime_ulong
(
uint
bits,
PrimePool
kind,
const
bench_options
*o) {
71
if
(kind ==
PRIME_POOL_COPRIME
&& bits < 10)
return
0.0;
/* 同 notrial:域宽下界 */
72
mp_ptr
a =
pool_bits
(bits, 0x13579bdf0246ull + bits, kind);
73
size_t
idx = 0;
74
double
us;
75
BENCH_MEASURE
(us, o, bench_sink += (
mp_limb_t
)
lmmp_is_prime_ulong_
(a[idx++ & (
POOL
- 1)]););
76
lmmp_free
(a);
77
return
us;
78
}
79
80
/*
81
64bit 内档位对应 notrial 家族内部分支:40bit(双基底分支)、
82
56bit(三基底 mont63 分支)、64bit 顶(三基底 mont64 分支);
83
*/
84
85
static
void
run_notrial
(
void
) {
86
const
uint
BITS[] = {40, 56, 64};
87
for
(
size_t
i = 0; i <
ARRAY_SIZE
(BITS); ++i) {
88
uint
bits = BITS[i];
89
report_bits(
"notrial odd"
, bits,
bench_is_prime_ulong_notrial
(bits,
PRIME_POOL_ODD
, &bench_default));
90
report_bits(
"notrial prime"
, bits,
bench_is_prime_ulong_notrial
(bits,
PRIME_POOL_PRIME
, &bench_default));
91
}
92
}
93
94
static
void
run_is_prime_ulong
(
void
) {
95
const
uint
BITS[] = {40, 56, 64};
96
for
(
size_t
i = 0; i <
ARRAY_SIZE
(BITS); ++i) {
97
uint
bits = BITS[i];
98
report_bits(
"is_prime_ulong odd"
, bits,
bench_is_prime_ulong
(bits,
PRIME_POOL_ODD
, &bench_default));
99
report_bits(
"is_prime_ulong prime"
, bits,
bench_is_prime_ulong
(bits,
PRIME_POOL_PRIME
, &bench_default));
100
}
101
}
102
103
int
main
(
void
) {
104
setvbuf(stdout, NULL, _IONBF, 0);
105
lmmp_global_init
();
106
puts(
"[numth/prime/notrial]"
);
107
run_notrial
();
108
puts(
"[numth/prime/is_prime_ulong]"
);
109
run_is_prime_ulong
();
110
lmmp_global_deinit
();
111
return
0;
112
}
main
int main(void)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
main.c:26
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
lmmp_free
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
定义
memory.c:437
lmmp_global_init
void lmmp_global_init(void)
全局初始化函数(线程局部的)
定义
global.c:58
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmp_global_deinit
void lmmp_global_deinit(void)
全局释放函数(线程局部的)
定义
global.c:65
lmmp_seed_random_
mp_size_t lmmp_seed_random_(mp_ptr dst, mp_size_t n, mp_limb_t seed, unsigned seed_type)
生成随机大整数(0 - B^n-1 均匀分布)
uint
uint32_t uint
定义
numth.h:38
lmmp_is_prime_ulong_notrial_
bool lmmp_is_prime_ulong_notrial_(ulong n)
判断素数(无试除法,单 limb 档)
定义
is_prime_ulong.c:257
lmmp_is_prime_ulong_
bool lmmp_is_prime_ulong_(ulong n)
判断素数
定义
is_prime_ulong.c:345
lmmp_next_prime_ulong_
ulong lmmp_next_prime_ulong_(ulong n)
大于n的下一个素数
定义
is_prime_ulong.c:375
run_notrial
static void run_notrial(void)
定义
is_prime_ulong.c:85
bench_is_prime_ulong_notrial
static double bench_is_prime_ulong_notrial(uint bits, PrimePool kind, const bench_options *o)
定义
is_prime_ulong.c:58
run_is_prime_ulong
static void run_is_prime_ulong(void)
定义
is_prime_ulong.c:94
pool_bits
static mp_ptr pool_bits(uint bits, mp_limb_t seed, PrimePool kind)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
is_prime_ulong.c:27
bench_is_prime_ulong
static double bench_is_prime_ulong(uint bits, PrimePool kind, const bench_options *o)
定义
is_prime_ulong.c:70
ARRAY_SIZE
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
perf.h:40
BENCH_MEASURE
#define BENCH_MEASURE(result, options,...)
定义
perf.h:93
bench_options
定义
perf.h:44
prime_pool.h
PrimePool
PrimePool
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
prime_pool.h:41
PRIME_POOL_PRIME
@ PRIME_POOL_PRIME
定义
prime_pool.h:41
PRIME_POOL_ODD
@ PRIME_POOL_ODD
定义
prime_pool.h:41
PRIME_POOL_COPRIME
@ PRIME_POOL_COPRIME
定义
prime_pool.h:41
POOL
@ POOL
定义
prime_pool.h:43
src
lmmp
numth
perf
is_prime_ulong.c
生成于
, 为 LMMP使用
1.18.0