LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
is_prime_2.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
/* [lo,hi] 对池(65..128bit),hi 顶位起始;按 kind 过滤 */
26
static
mp_ptr
pool_2
(
uint
bits,
mp_limb_t
seed,
PrimePool
kind) {
27
if
(bits < 65) bits = 65;
28
if
(bits > 128) bits = 128;
29
uint
hb = bits - 64;
30
mp_ptr
a = alloc_limbs(2 *
POOL
);
31
for
(
int
i = 0; i <
POOL
; i++) {
32
lmmp_seed_random_
(a + 2 * i, 2, seed + i, 1);
33
a[2 * i + 1] &= ((
mp_limb_t
)-1) >> (64 - hb);
34
a[2 * i + 1] |= (
mp_limb_t
)1 << (hb - 1);
35
a[2 * i] |= 1;
36
if
(kind ==
PRIME_POOL_COPRIME
) {
37
/* 步进只改低 limb、回绕不进位到高 limb,值恒在指定位宽内 */
38
while
(small_factor_q(a + 2 * i, 2)) a[2 * i] += 2;
39
}
else
if
(kind ==
PRIME_POOL_PRIME
) {
40
while
(
lmmp_is_prime_2_
(a[2 * i], a[2 * i + 1]) == 0) a[2 * i] += 2;
41
}
42
}
43
return
a;
44
}
45
46
static
double
bench_is_prime_2
(
uint
bits,
PrimePool
kind,
const
bench_options
*o) {
47
if
(bits < 65) bits = 65;
48
if
(bits > 128) bits = 128;
49
mp_ptr
a =
pool_2
(bits, 0xdeadbeefca01ull + bits, kind);
50
size_t
idx = 0;
51
double
us;
52
BENCH_MEASURE
(us, o,
53
bench_sink += (
mp_limb_t
)
lmmp_is_prime_2_
(a[2 * (idx & (
POOL
- 1))],
54
a[2 * (idx & (
POOL
- 1)) + 1]);
55
idx++;
56
);
57
lmmp_free
(a);
58
return
us;
59
}
60
61
static
double
bench_is_prime_2_notrial
(
uint
bits,
PrimePool
kind,
const
bench_options
*o) {
62
if
(bits < 65) bits = 65;
63
if
(bits > 128) bits = 128;
64
mp_ptr
a =
pool_2
(bits, 0xdeadbeefca02ull + bits, kind);
65
size_t
idx = 0;
66
double
us;
67
BENCH_MEASURE
(us, o,
68
bench_sink += (
mp_limb_t
)
lmmp_is_prime_2_notrial_
(a[2 * (idx & (
POOL
- 1))],
69
a[2 * (idx & (
POOL
- 1)) + 1]);
70
idx++;
71
);
72
lmmp_free
(a);
73
return
us;
74
}
75
76
/*
77
is_prime_2 档位对应 <psi_13(13 基底确定)与 >=psi_13(+强 Lucas)。
78
notrial 与带试除版本的对照差即试除腿成本(odd 池有试除早拒收益,
79
coprime/prime 池已过滤小因子,差值接近纯试除开销)。
80
*/
81
82
static
void
run_is_prime_2
(
void
) {
83
const
uint
BITS[] = {65, 82, 96, 128};
84
for
(
size_t
i = 0; i <
ARRAY_SIZE
(BITS); ++i) {
85
uint
bits = BITS[i];
86
report_bits(
"is_prime_2 odd"
, bits,
bench_is_prime_2
(bits,
PRIME_POOL_ODD
, &bench_default));
87
}
88
report_bits(
"is_prime_2 prime"
, 128,
bench_is_prime_2
(128,
PRIME_POOL_PRIME
, &bench_default));
89
}
90
91
static
void
run_is_prime_2_notrial
(
void
) {
92
const
uint
BITS[] = {65, 128};
93
for
(
size_t
i = 0; i <
ARRAY_SIZE
(BITS); ++i) {
94
uint
bits = BITS[i];
95
report_bits(
"is_prime_2_notrial odd"
, bits,
bench_is_prime_2_notrial
(bits,
PRIME_POOL_ODD
, &bench_default));
96
}
97
report_bits(
"is_prime_2_notrial coprime"
, 128,
bench_is_prime_2_notrial
(128,
PRIME_POOL_COPRIME
, &bench_default));
98
}
99
100
int
main
(
void
) {
101
setvbuf(stdout, NULL, _IONBF, 0);
102
lmmp_global_init
();
103
puts(
"[numth/prime/is_prime_2]"
);
104
run_is_prime_2
();
105
puts(
"[numth/prime/is_prime_2_notrial]"
);
106
run_is_prime_2_notrial
();
107
lmmp_global_deinit
();
108
return
0;
109
}
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 均匀分布)
lmmp_is_prime_2_notrial_
int lmmp_is_prime_2_notrial_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数(无试除法)
定义
is_prime_2.c:733
uint
uint32_t uint
定义
numth.h:38
lmmp_is_prime_2_
int lmmp_is_prime_2_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数
定义
is_prime_2.c:739
run_is_prime_2
static void run_is_prime_2(void)
定义
is_prime_2.c:82
bench_is_prime_2_notrial
static double bench_is_prime_2_notrial(uint bits, PrimePool kind, const bench_options *o)
定义
is_prime_2.c:61
bench_is_prime_2
static double bench_is_prime_2(uint bits, PrimePool kind, const bench_options *o)
定义
is_prime_2.c:46
pool_2
static mp_ptr pool_2(uint bits, mp_limb_t seed, PrimePool kind)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
is_prime_2.c:26
run_is_prime_2_notrial
static void run_is_prime_2_notrial(void)
定义
is_prime_2.c:91
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_2.c
生成于
, 为 LMMP使用
1.18.0