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

浏览该文件的源代码.

函数

 TEST_CASE ("numth/prime", is_prime_u32_tiers)
 TEST_CASE ("numth/prime", is_prime_uint_ulong_notrial)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
 TEST_CASE ("numth/prime", mulmod_powmod)
 TEST_CASE ("numth/prime", next_prev_prime)
void test_prime_uint (void)

函数说明

◆ TEST_CASE() [1/4]

TEST_CASE ( "numth/prime" ,
is_prime_u32_tiers  )

在文件 test_prime_uint.c 第 54 行定义.

54 {
55 u64 seed = 0xc0ffee123456789ull;
56
57 /* 2^31 档界两侧稠密扫描 */
58 for (u32 n = 0x7ffffc00u; n <= 0x80000400u; n += 2) {
59 u32 m = n | 1;
60 bool expect = ref_is_prime32(m);
61 TEST_CHECK_MSG(lmmp_is_prime_uint_(m) == expect, "is_prime_uint 2^31 tier");
62 TEST_CHECK_MSG(lmmp_is_prime_ulong_(m) == expect, "is_prime_ulong 2^31 tier");
63 }
64
65 /* u32 顶部(n>=2^31 档上端;计数式循环避免 u32 回绕死循环) */
66 for (u32 j = 0; j < 128; ++j) {
67 u32 m = 0xffffff01u + 2 * j;
68 bool expect = ref_is_prime32(m);
69 TEST_CHECK_MSG(lmmp_is_prime_uint_(m) == expect, "is_prime_uint top tier");
70 TEST_CHECK_MSG(lmmp_is_prime_ulong_(m) == expect, "is_prime_ulong top tier");
71 }
72
73 /* 短表界与 next_prime 拐角 */
74 for (u32 n = 65400; n <= 65700; ++n) {
75 bool expect = ref_is_prime32(n);
76 TEST_CHECK_MSG(lmmp_is_prime_uint_(n) == expect, "is_prime_uint short-table edge");
77 TEST_CHECK_MSG(lmmp_is_prime_ulong_(n) == expect, "is_prime_ulong short-table edge");
78 }
79
80 /* d 退化:n-1 = 2^t(ebits=1),含 Fermat 素数 3/5/17/257/65537 与合数 2^31+1 */
81 for (u32 t = 1; t <= 31; ++t) {
82 u32 m = (1u << t) + 1;
83 bool expect = ref_is_prime32(m);
84 TEST_CHECK_MSG(lmmp_is_prime_uint_(m) == expect, "is_prime_uint d=1");
85 TEST_CHECK_MSG(lmmp_is_prime_ulong_(m) == expect, "is_prime_ulong d=1");
86 }
87
88 /* notrial 直调小奇数(覆盖 n==hash 基底、b>=n 起步路径;契约域 n>2 奇) */
89 for (u32 m = 3; m <= 3001; m += 2) {
90 bool expect = ref_is_prime32(m);
91 TEST_CHECK_MSG(lmmp_is_prime_ulong_notrial_(m) == expect, "notrial small direct");
92 }
93
94 /* 随机 u32 大样本 + 档界邻域加密 */
95 for (int i = 0; i < 20000; ++i) {
96 u32 m = (u32)(xorshift64(&seed) >> (i % 2 ? 32 : 0));
97 if (i % 3 == 0) m = 0x7fffffffu - (m & 0xffffu);
98 if (i % 3 == 1) m = 0xffffffffu - (m & 0xffffu);
99 m |= 1;
100 if (m < 3) m = 3;
101 bool expect = ref_is_prime32(m);
102 TEST_CHECK_MSG(lmmp_is_prime_uint_(m) == expect, "is_prime_uint random u32");
103 TEST_CHECK_MSG(lmmp_is_prime_ulong_(m) == expect, "is_prime_ulong random u32");
104 TEST_CHECK_MSG(lmmp_is_prime_ulong_notrial_(m) == expect, "notrial random u32");
105 }
106
107 /* next_prime u32 区段拐角:返回值与间隔无素数 */
108 const u32 starts[] = {65521, 65522, 0x7ffffff0u, 0xfffff000u};
109 for (size_t s_index = 0; s_index < ARRAY_SIZE(starts); ++s_index) {
110 u32 s = starts[s_index];
112 TEST_CHECK_MSG(p > s && ref_is_prime32(p), "next_prime u32 corner hit");
113 for (u32 m = (s + 1) | 1; m < p; m += 2)
114 TEST_CHECK_MSG(!ref_is_prime32(m), "next_prime u32 corner gap");
115 }
116}
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define t
#define s
#define n
bool lmmp_is_prime_uint_(uint n)
判断素数
bool lmmp_is_prime_ulong_notrial_(ulong n)
判断素数(无试除法,单 limb 档)
bool lmmp_is_prime_ulong_(ulong n)
判断素数
ulong lmmp_next_prime_ulong_(ulong n)
大于n的下一个素数
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
static bool ref_is_prime32(u32 n)
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38

引用了 ARRAY_SIZE, lmmp_is_prime_uint_(), lmmp_is_prime_ulong_(), lmmp_is_prime_ulong_notrial_(), lmmp_next_prime_ulong_(), n, ref_is_prime32(), s, t, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [2/4]

TEST_CASE ( "numth/prime" ,
is_prime_uint_ulong_notrial  )

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

在文件 test_prime_uint.c 第 38 行定义.

38 {
39 u64 seed = 0xfeed0912eadc23aeull;
40 for (u32 n = 0; n < 10000; ++n) {
41 bool expect = ref_is_prime32(n);
42 TEST_CHECK_MSG(lmmp_is_prime_uint_(n) == expect, "is_prime_uint small");
43 TEST_CHECK_MSG(lmmp_is_prime_ulong_(n) == expect, "is_prime_ulong small");
44 }
45
46 for (int i = 0; i < 2000; ++i) {
47 u64 n = xorshift64(&seed);
48 bool expect = ref_is_prime64(n);
49 TEST_CHECK_MSG(lmmp_is_prime_ulong_(n) == expect, "is_prime_ulong random");
50 if (n > 2) TEST_CHECK_MSG(lmmp_is_prime_ulong_notrial_(n) == expect, "is_prime_notrial random");
51 }
52}
static bool ref_is_prime64(u64 n)

引用了 lmmp_is_prime_uint_(), lmmp_is_prime_ulong_(), lmmp_is_prime_ulong_notrial_(), n, ref_is_prime32(), ref_is_prime64(), TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [3/4]

TEST_CASE ( "numth/prime" ,
mulmod_powmod  )

在文件 test_prime_uint.c 第 163 行定义.

163 {
164 u64 seed = 0x2cbea9127ca8019full;
165 for (int i = 0; i < 400; ++i) {
166 ulong mod = xorshift64(&seed) | 3; // 避免过小且保证奇
167 ulong a = xorshift64(&seed) % mod;
168 ulong b = xorshift64(&seed) % mod;
169 ulong q = 0;
170 ulong r = lmmp_mulmod_ulong_(a, b, mod, &q);
171 /* q*mod + r == a*b(mullh 独立重建全积与商积) */
172 mp_limb_t prod[2], qm[2];
173 lmmp_mullh_(a, b, prod);
174 lmmp_mullh_(q, mod, qm);
175 mp_limb_t lo = qm[0] + r;
176 mp_limb_t cy = lo < qm[0] ? 1 : 0;
177 mp_limb_t hi = qm[1] + cy;
178 TEST_CHECK_MSG(hi == prod[1] && lo == prod[0], "mulmod relation");
179 TEST_CHECK_MSG(r < mod, "mulmod rem bound");
180 }
181
182 for (int i = 0; i < 300; ++i) {
183 u32 mod = (u32)(xorshift64(&seed) | 3);
184 u32 base = (u32)(xorshift64(&seed) % mod);
185 ulong exp = xorshift64(&seed) & 0xffff;
186 u32 r = lmmp_powmod_uint_odd_(base, exp, mod);
187 TEST_CHECK_EQ(r, (u32)mod_pow64(base, exp, mod));
188 }
189
190 for (int i = 0; i < 300; ++i) {
191 ulong mod = xorshift64(&seed) | 3;
192 ulong base = xorshift64(&seed) % mod;
193 ulong exp = xorshift64(&seed) & 0xffff;
194 ulong r = lmmp_powmod_ulong_odd_(base, exp, mod);
195 TEST_CHECK_EQ(r, mod_pow64(base, exp, mod));
196 }
197}
#define prod
#define lmmp_mullh_
uint64_t mp_limb_t
定义 lmmp.h:92
#define lo
uint lmmp_powmod_uint_odd_(uint base, ulong exp, uint mod)
计算 base^exp 对 mod 取模
ulong lmmp_powmod_ulong_odd_(ulong base, ulong exp, ulong mod)
计算 base^exp 对 mod 取模
ulong lmmp_mulmod_ulong_(ulong a, ulong b, ulong mod, ulongp q)
计算两个无符号整数的乘积,对mod取模,商放入 q 中
uint64_t ulong
定义 numth.h:39
static u64 mod_pow64(u64 a, u64 e, u64 mod)
#define TEST_CHECK_EQ(a, b)
定义 test.h:39

引用了 lmmp_mullh_, lmmp_mulmod_ulong_(), lmmp_powmod_uint_odd_(), lmmp_powmod_ulong_odd_(), lo, mod_pow64(), prod, TEST_CASE, TEST_CHECK_EQ , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [4/4]

TEST_CASE ( "numth/prime" ,
next_prev_prime  )

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

118 {
119 // 小范围穷举
120 for (ulong n = 0; n < 1200; ++n) {
122 if (n < 2) {
123 TEST_CHECK_EQ(next, 2u);
124 } else {
125 bool found = false;
126 for (ulong k = n + 1; k < 100000; ++k) {
127 if (ref_is_prime64(k)) { TEST_CHECK_EQ(next, k); found = true; break; }
128 }
129 TEST_CHECK(found);
130 }
132 if (n < 2) TEST_CHECK_EQ(p, 0u);
133 else {
134 bool found = false;
135 for (ulong k = n;; --k) {
136 if (ref_is_prime64(k)) { TEST_CHECK_EQ(p, k); found = true; break; }
137 }
138 TEST_CHECK(found);
139 }
140 }
141
142 // 随机 64 位附近
143 u64 seed = 0x230bc3ae812873c0ull;
144 for (int i = 0; i < 60; ++i) {
145 ulong n = xorshift64(&seed) | 1;
146 if (n < 2) n = 2;
148 TEST_CHECK_MSG(next > n, "next_prime > n");
149 TEST_CHECK_MSG(ref_is_prime64(next), "next_prime is prime");
150 if (next > n + 1) {
151 for (ulong k = n + 1; k < next; ++k) TEST_CHECK_MSG(!ref_is_prime64(k), "next_prime no gap prime");
152 }
154 TEST_CHECK_MSG(p > 0, "prev_prime nonzero for n >= 2");
155 if (p > 0) {
156 TEST_CHECK_MSG(ref_is_prime64(p), "prev_prime is prime");
157 TEST_CHECK_MSG(p <= n, "prev_prime <= n");
158 for (ulong k = p + 1; k <= n; ++k) TEST_CHECK_MSG(!ref_is_prime64(k), "prev_prime no gap prime");
159 }
160 }
161}
#define k
ulong lmmp_prev_prime_ulong_(ulong n)
小于等于n的上一个素数
#define TEST_CHECK(cond)
定义 test.h:37

引用了 k, lmmp_next_prime_ulong_(), lmmp_prev_prime_ulong_(), n, ref_is_prime64(), TEST_CASE, TEST_CHECK, TEST_CHECK_EQ , 以及 TEST_CHECK_MSG.

函数调用图:

◆ test_prime_uint()

void test_prime_uint ( void )

在文件 test_prime_uint.c 第 199 行定义.

199 {
200 TEST_RUN("numth/prime", is_prime_uint_ulong_notrial);
201 TEST_RUN("numth/prime", is_prime_u32_tiers);
202 TEST_RUN("numth/prime", next_prev_prime);
203 TEST_RUN("numth/prime", mulmod_powmod);
204}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_prime_uint() , 以及 TEST_RUN.

被这些函数引用 main() , 以及 test_prime_uint().

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