LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
rand_state.h
浏览该文件的文档.
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
#ifndef __LMMP_RAND_STATE_H__
24
#define __LMMP_RAND_STATE_H__
25
26
#include "
impl/longlong.h
"
27
#include "
lmmp/lmmp.h
"
28
29
typedef
struct
{
30
mp_limb_t
state
[2];
31
mp_limb_t
inc
[2];
// 必须为奇数
32
}
pcg64_128_state
;
33
34
typedef
struct
{
35
mp_limb_t
s
[4];
// 256位状态,必须初始化为非零值
36
}
xoshiro256pp_state
;
37
38
#define PCG128_DEFAULT_MULTIPLIER_HI 0x2360ED051FC65DA4ULL
39
#define PCG128_DEFAULT_MULTIPLIER_LO 0x4385DF649FCCF645ULL
40
41
#define LMMP_INLINE static inline
42
43
LMMP_INLINE
mp_limb_t
rotl
(
const
mp_limb_t
x,
int
k
) {
44
const
int
shift =
k
& 63;
45
return
(x << shift) | (x >> ((-shift) & 63));
46
}
47
48
/**
49
* @brief 种子生成器
50
* @param seed 低熵种子
51
* @return 高熵种子
52
*/
53
LMMP_INLINE
mp_limb_t
lmmp_seed_generator
(
mp_limb_t
seed) {
54
mp_limb_t
z = (seed += 0x9e3779b97f4a7c15);
55
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
56
z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
57
return
z ^ (z >> 31);
58
}
59
60
LMMP_INLINE
mp_limb_t
mix64
(
mp_limb_t
h) {
61
h ^= h >> 33;
62
h *= 0xc2b2ae3d27d4eb4fULL;
63
h ^= h >> 29;
64
h *= 0x165667b19e3779f9ULL;
65
h ^= h >> 32;
66
return
h;
67
}
68
69
LMMP_INLINE
void
pcg64_128_action
(
mp_limb_t
state[2],
const
mp_limb_t
inc[2]) {
70
// state = (state * PCG64_MULT + inc) mod 2^128
71
// state * M = s0*m0 + ((s0*m1 + s1*m0) mod 2^64) << 64 (mod 2^128)
72
// 交叉项 s0*m1 与 s1*m0 只有低 64 位落在 2^128 以内,高 64 位模掉
73
mp_limb_t
tmp
[2] = {0, 0};
74
_umul64to128_
(state[0],
PCG128_DEFAULT_MULTIPLIER_LO
,
tmp
,
tmp
+ 1);
75
tmp
[1] += state[1] *
PCG128_DEFAULT_MULTIPLIER_LO
;
76
tmp
[1] += state[0] *
PCG128_DEFAULT_MULTIPLIER_HI
;
77
state[0] =
tmp
[0] + inc[0];
78
mp_limb_t
c = state[0] < inc[0] ? 1 : 0;
79
state[1] =
tmp
[1] + inc[1] + c;
80
}
81
82
LMMP_INLINE
void
lmmp_pcg64_128_srandom
(
pcg64_128_state
* rng,
mp_limb_t
seed) {
83
lmmp_param_assert
(rng != NULL);
84
85
rng->
state
[0] =
lmmp_seed_generator
(seed);
86
rng->
state
[1] =
mix64
(seed);
87
rng->
inc
[0] =
mix64
(seed + 0x9e3779b97f4a7c15ULL);
88
rng->
inc
[0] |= 1ull;
89
rng->
inc
[1] =
lmmp_seed_generator
(seed * 11154045850622628491ULL);
90
}
91
92
// (PCG-XSL-RR-128/64)
93
LMMP_INLINE
mp_limb_t
lmmp_pcg64_128_random
(
pcg64_128_state
* rng) {
94
lmmp_param_assert
(rng != NULL);
95
mp_limb_t
oldstate[2] = {rng->
state
[0], rng->
state
[1]};
96
pcg64_128_action
(rng->
state
, rng->
inc
);
97
98
// XSL-RR
99
mp_limb_t
xsl = ((oldstate[1]) ^ oldstate[0]);
100
101
mp_byte_t
rot = (
mp_byte_t
)(oldstate[1] >> 58);
102
return
(xsl >> rot) | (xsl << ((-rot) & 63));
103
}
104
105
LMMP_INLINE
mp_limb_t
lmmp_xoshiro256pp_random
(
xoshiro256pp_state
* rng) {
106
lmmp_param_assert
(rng != NULL);
107
const
mp_limb_t
r =
rotl
(rng->
s
[0] + rng->
s
[3], 23) + rng->
s
[0];
108
const
mp_limb_t
t
= rng->
s
[1] << 17;
109
110
rng->
s
[2] ^= rng->
s
[0];
111
rng->
s
[3] ^= rng->
s
[1];
112
rng->
s
[1] ^= rng->
s
[2];
113
rng->
s
[0] ^= rng->
s
[3];
114
rng->
s
[2] ^=
t
;
115
rng->
s
[3] =
rotl
(rng->
s
[3], 45);
116
117
return
r;
118
}
119
120
LMMP_INLINE
void
lmmp_xoshiro256pp_srandom
(
xoshiro256pp_state
* rng,
mp_limb_t
seed) {
121
lmmp_param_assert
(rng != NULL);
122
123
const
mp_limb_t
C
= 0x9e3779b97f4a7c15ULL;
124
125
rng->
s
[0] =
mix64
(seed + 0 *
C
);
126
rng->
s
[1] =
mix64
(seed + 1 *
C
);
127
rng->
s
[2] =
mix64
(seed + 2 *
C
);
128
rng->
s
[3] =
mix64
(seed + 3 *
C
);
129
// 由于mix64为双射,故不可能为全零状态
130
}
131
132
#define PCG64_LE_MULTIPLIER 6364136223846793005ULL
133
#define PCG64_LE_INCREMENT 1442695040888963407ULL
134
135
typedef
struct
{
136
mp_size_t
k
;
137
mp_limb_t
*
restrict
state
;
138
}
pcg64_le_seq_t
;
139
140
LMMP_INLINE
void
pcg64_le_seq_init
(
pcg64_le_seq_t
* rng,
mp_size_t
i,
mp_limb_t
seed) {
141
lmmp_param_assert
(rng != NULL);
142
lmmp_param_assert
(rng->
k
> 0);
143
lmmp_param_assert
(rng->
state
!= NULL);
144
145
mp_limb_t
s
;
146
147
for
(; i < rng->
k
; i++) {
148
s
= seed + i * 11154045850622628491ULL;
149
rng->
state
[i] =
mix64
(
s
);
150
}
151
}
152
153
LMMP_INLINE
mp_limb_t
pcg64_le_action
(
mp_limb_t
*
restrict
state) {
154
mp_limb_t
old_state = *state;
155
*state = old_state *
PCG64_LE_MULTIPLIER
+
PCG64_LE_INCREMENT
;
156
157
// RXS-M-XS
158
mp_limb_t
x = old_state;
159
int
count = x >> 59;
160
x ^= x >> (5 + count);
161
x *= 12605985483714917081ULL;
162
x ^= x >> 43;
163
164
return
x;
165
}
166
167
LMMP_INLINE
void
pcg64_le_seq_next
(
mp_ptr
restrict
dst,
mp_size_t
n
,
pcg64_le_seq_t
* rng) {
168
lmmp_param_assert
(dst != NULL);
169
lmmp_param_assert
(rng != NULL);
170
lmmp_param_assert
(
n <= rng->
k
);
171
mp_size_t
i;
172
mp_limb_t
mixn =
lmmp_seed_generator
(
n
);
173
for
(i = 0; i + 3 <
n
; i += 4) {
174
dst[i + 0] =
pcg64_le_action
(&rng->
state
[i + 0]) ^ mixn;
175
dst[i + 1] =
pcg64_le_action
(&rng->
state
[i + 1]) ^ mixn;
176
dst[i + 2] =
pcg64_le_action
(&rng->
state
[i + 2]) ^ mixn;
177
dst[i + 3] =
pcg64_le_action
(&rng->
state
[i + 3]) ^ mixn;
178
}
179
for
(; i <
n
; i++) {
180
dst[i] =
pcg64_le_action
(&rng->
state
[i]) ^ mixn;
181
}
182
for
(; i < rng->
k
; i++) {
183
mp_limb_t
old_state = rng->
state
[i];
184
rng->
state
[i] = old_state *
PCG64_LE_MULTIPLIER
+
PCG64_LE_INCREMENT
;
185
}
186
}
187
188
/**
189
* @brief 依据全局状态获取单个随机limb(0 - B 均匀分布)
190
* @return 随机limb
191
* @note 每调用一次将会重置全局随机状态
192
*/
193
mp_limb_t
lmmp_randlimb_
(
void
);
194
195
#undef LMMP_INLINE
196
197
#endif
// __LMMP_RAND_STATE_H__
k
#define k
C
#define C
lmmp.h
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_byte_t
uint8_t mp_byte_t
定义
lmmp.h:91
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
LMMP_INLINE
#define LMMP_INLINE
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
lmmpn.h:30
longlong.h
_umul64to128_
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
定义
longlong.h:132
t
#define t
s
#define s
n
#define n
tmp
#define tmp
pcg64_le_seq_init
static void pcg64_le_seq_init(pcg64_le_seq_t *rng, mp_size_t i, mp_limb_t seed)
定义
rand_state.h:140
pcg64_le_seq_t::state
mp_limb_t *restrict state
定义
rand_state.h:137
lmmp_xoshiro256pp_random
static mp_limb_t lmmp_xoshiro256pp_random(xoshiro256pp_state *rng)
定义
rand_state.h:105
pcg64_128_state::state
mp_limb_t state[2]
定义
rand_state.h:30
pcg64_128_action
static void pcg64_128_action(mp_limb_t state[2], const mp_limb_t inc[2])
定义
rand_state.h:69
lmmp_xoshiro256pp_srandom
static void lmmp_xoshiro256pp_srandom(xoshiro256pp_state *rng, mp_limb_t seed)
定义
rand_state.h:120
pcg64_le_seq_t::k
mp_size_t k
定义
rand_state.h:136
lmmp_seed_generator
static mp_limb_t lmmp_seed_generator(mp_limb_t seed)
种子生成器
定义
rand_state.h:53
lmmp_randlimb_
mp_limb_t lmmp_randlimb_(void)
依据全局状态获取单个随机limb(0 - B 均匀分布)
定义
mprand.c:43
pcg64_128_state::inc
mp_limb_t inc[2]
定义
rand_state.h:31
PCG64_LE_INCREMENT
#define PCG64_LE_INCREMENT
定义
rand_state.h:133
PCG64_LE_MULTIPLIER
#define PCG64_LE_MULTIPLIER
定义
rand_state.h:132
pcg64_le_action
static mp_limb_t pcg64_le_action(mp_limb_t *restrict state)
定义
rand_state.h:153
lmmp_pcg64_128_srandom
static void lmmp_pcg64_128_srandom(pcg64_128_state *rng, mp_limb_t seed)
定义
rand_state.h:82
PCG128_DEFAULT_MULTIPLIER_HI
#define PCG128_DEFAULT_MULTIPLIER_HI
定义
rand_state.h:38
rotl
static mp_limb_t rotl(const mp_limb_t x, int k)
定义
rand_state.h:43
lmmp_pcg64_128_random
static mp_limb_t lmmp_pcg64_128_random(pcg64_128_state *rng)
定义
rand_state.h:93
pcg64_le_seq_next
static void pcg64_le_seq_next(mp_ptr restrict dst, mp_size_t n, pcg64_le_seq_t *rng)
定义
rand_state.h:167
xoshiro256pp_state::s
mp_limb_t s[4]
定义
rand_state.h:35
mix64
static mp_limb_t mix64(mp_limb_t h)
定义
rand_state.h:60
PCG128_DEFAULT_MULTIPLIER_LO
#define PCG128_DEFAULT_MULTIPLIER_LO
定义
rand_state.h:39
xoshiro256pp_state
定义
rand_state.h:34
pcg64_le_seq_t
定义
rand_state.h:135
pcg64_128_state
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
rand_state.h:29
restrict
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_powmod.c:35
src
lmmp
impl
rand_state.h
生成于
, 为 LMMP使用
1.18.0