LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
mprand.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_MPRAND_H
24
#define LMMP_MPRAND_H
25
26
/*
27
本头文件提供的随机数发生器均为非密码学安全的伪随机数生成器,仅用于生成随机数序列。
28
输入种子类型为unsigned时,意味着无需输入高熵的随机数,我们会通过一些额外的信息(生成序列的长度)
29
通过一些简单的算法来生成高熵的新种子(依然可以保证可重用和可复现性)。对于种子类型为
30
其他类型,我们会直接使用输入的种子,我们仍然会在发生器中进行一些处理,以保证最低限度的随机性。
31
32
LMMP 主要实现了两个随机数引擎:PCG-XSL-RR-128/64 和 xoshiro256++。
33
其中,后者通常为LMMP默认的随机数引擎,生成速度较前者快,大约有1.5倍性能差距。
34
可以参考以下文章了解PCG:<https://www.pcg-random.org/paper.html>
35
36
PCG网站<https://www.pcg-random.org>中也有PCG和xoshiro256++及其他随机生成器的比较。
37
38
PCG-XSL-RR-128/64 生成的随机数序列通常拥有比xoshiro256++更好的统计性能,当然两者的统计性能
39
在大部分场景下都足够的好。在生成较短bit长度的随机数时,所有的发生器平均耗时都会因为初始化的开销而提高。
40
41
LMMP 实现的强随机数生成器,通常用于多次大量生成较长的随机大整数序列,比如用于多次生成
42
1000个limb长度的随机大整数。其随机状态为一个长度为 k 的limb数组,初始状态由种子决定,每个limb代表一个64bit状态,
43
初始状态会由种子和limb的位置通过复杂的hash算法确定,因此初始状态几乎完全不同,用以保证同一个大整数中的各个limb之
44
间几乎没有相关性。
45
46
在生成单个随机大整数时,强随机生成器的总生成速度会显著慢于PCG-XSL-RR-128/64和xoshiro256++,与cpp标准库的
47
梅森旋转法大致相当。这是由于初始化随机状态的巨大开销导致的。在多次生成固定长度的随机大整数序列时,强随机生成
48
器的生成速度则比pcg-xsl-rr-128/64略慢,但仍然快于梅森旋转算法(Mersenne Twister)。
49
*/
50
51
#include "
lmmp.h
"
52
53
#ifdef __cplusplus
54
extern
"C"
{
55
#endif
56
57
/**
58
* @brief 初始化全局随机数生成器
59
* @param seed 种子
60
* @param seed_type 随机数发生器类型(0:pcg64_128,1:xoshiro256++)
61
* @warning seed_type 必须在0到1之间,如果不是,则使用 seed_type%2 作为seed_type,
62
* 如果全局种子已经初始化,则会更新全局种子,或更新发生器类型
63
* @note 由于使用int类型作为种子,我们将会维护一个全局种子随机序列,丰富种子的随机性。
64
*/
65
LMMP_API
void
lmmp_global_rng_init_
(
unsigned
seed,
unsigned
seed_type);
66
67
/**
68
* @brief 生成随机大整数(0 - B^n-1 均匀分布)
69
* @param dst 随机数存储位置
70
* @param n dst的 limb 长度
71
* @param seed 种子(建议使用有效位数较多的随机数,以保证随机数质量)
72
* @param seed_type 随机数发生器类型(0:pcg64_128,1:xoshiro256++)
73
* @warning seed_type 必须在0到1之间,如果不是,则使用 seed_type%2 作为seed_type
74
* @return 随机数的 limb 长度(这是由于可能存在生成随机数为0的情况(虽然几乎不可能),
75
* 所以返回值可能小于n,但不会大于n)
76
*/
77
LMMP_API
mp_size_t
lmmp_seed_random_
(
mp_ptr
dst,
mp_size_t
n
,
mp_limb_t
seed,
unsigned
seed_type);
78
79
/**
80
* @brief 生成随机大整数(0 - B^n-1 均匀分布)
81
* @param dst 随机数存储位置
82
* @param n dst的 limb 长度
83
* @warning 如果dst==NULL或n==0,则返回0,无其他操作。种子由 lmmp_global_rng_init() 设置,发生器类型由
84
* lmmp_global_rng_init() 设置,如果没有进行全局初始化,则使用默认种子(默认等价设置全局种子为0,
85
* 并不代表全局种子为0)和默认发生器类型(默认为xoshiro256++),即未设置全局种子,行为等价于
86
* 执行了 lmmp_global_rng_init_(0, 1)
87
* @note 每调用一次此函数,种子将会进行一次更新,以确保多次调用时的种子不同,但是只要每次调用的方式
88
* 和顺序相同,在同一个进程中,每次生成的随机数序列相同。
89
* @return 随机数的 limb 长度(由于可能存在生成随机数为0的情况,所以返回值可能小于n,但不会大于n)
90
*/
91
LMMP_API
mp_size_t
lmmp_random_
(
mp_ptr
dst,
mp_size_t
n
);
92
93
/**
94
* @brief 强随机数生成器结构体
95
* @note 内部状态为一个长度为 k 的limb数组,初始状态由种子决定,每生成一次,内部状态将会更新,
96
* 内部状态的每个维度都是一个64位无符号整数,且可以认为是独立的。故通常情况下,此生成器得到的
97
* 随机数拥有极好的k-维均匀性。对于每个独立的limb,为了提高生成速度,我们使用pcg64-le随机数发生器
98
* 虽然各个limb间算法相同,但初始化状态几乎完全不同。
99
*/
100
typedef
struct
lmmp_strong_rng_t
lmmp_strong_rng_t
;
101
102
/**
103
* @brief 创建k维度强随机数生成器
104
* @param k 随机数长度(单位:limb)
105
* @param seed 种子
106
* @warning k>0
107
* @note 请注意,此操作是一个开销很大的操作,且会分配内存,在仅生成一次的情况下,甚至初始化时间会慢于生成
108
* 一个随机数的时间。
109
* @return 强随机数生成器指针
110
*/
111
LMMP_API
lmmp_strong_rng_t
*
lmmp_strong_rng_init_
(
mp_size_t
k
,
unsigned
seed
);
112
113
/**
114
* @brief 将rng内部状态拓展至k维度
115
* @param rng 强随机数生成器指针
116
* @param k 随机数长度(单位:limb)
117
* @warning rng!=NULL, k>0
118
* @note 若k<=rng->stream.k,则不进行任何操作。否则,将rng内部状态拓展至k维度。
119
*/
120
LMMP_API
void
lmmp_strong_rng_extern_
(
lmmp_strong_rng_t
* rng,
mp_size_t
k
);
121
122
/**
123
* @brief 销毁强随机数生成器
124
* @param rng 强随机数生成器指针
125
*/
126
LMMP_API
void
lmmp_strong_rng_free_
(
lmmp_strong_rng_t
* rng);
127
128
/**
129
* @brief 生成n维度强随机数(0 - B^n-1 均匀分布)
130
* @param dst 随机数存储位置(长度为k个limb)
131
* @param n dst的 limb 长度(n<=k)
132
* @param rng 强随机数生成器指针,每生成一次,内部状态将会更新
133
* @warning rng!=NULL, dst!=NULL, 0<n<=k,
134
* @note rng为强随机数生成器指针,每调用一次此函数,内部状态将会更新,以进行重复生成长度相同的随机大整数序列
135
* 此方法生成的随机数序列具有极好的k-维均匀性,单个随机大整数间的各个limb都是几乎完全独立的序列。
136
* @return 随机数的 limb 长度(由于可能存在生成随机数为0的情况,所以返回值可能小于n,但不会大于n)
137
*/
138
LMMP_API
mp_size_t
lmmp_strong_random_
(
mp_ptr
dst,
mp_size_t
n
,
lmmp_strong_rng_t
* rng);
139
140
#ifdef __cplusplus
141
}
142
#endif
143
144
#endif
// LMMP_MPRAND_H
k
#define k
lmmp.h
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
LMMP_API
#define LMMP_API
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
lmmp.h:77
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmp_strong_rng_t::seed
mp_limb_t seed
定义
mprand.c:95
lmmp_strong_rng_t
定义
mprand.c:94
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_strong_rng_init_
lmmp_strong_rng_t * lmmp_strong_rng_init_(mp_size_t k, unsigned seed)
创建k维度强随机数生成器
定义
mprand.c:99
lmmp_strong_rng_free_
void lmmp_strong_rng_free_(lmmp_strong_rng_t *rng)
销毁强随机数生成器
定义
mprand.c:127
lmmp_strong_random_
mp_size_t lmmp_strong_random_(mp_ptr dst, mp_size_t n, lmmp_strong_rng_t *rng)
生成n维度强随机数(0 - B^n-1 均匀分布)
lmmp_global_rng_init_
void lmmp_global_rng_init_(unsigned seed, unsigned seed_type)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
mprand.c:38
lmmp_strong_rng_extern_
void lmmp_strong_rng_extern_(lmmp_strong_rng_t *rng, mp_size_t k)
将rng内部状态拓展至k维度
定义
mprand.c:113
lmmp_random_
mp_size_t lmmp_random_(mp_ptr dst, mp_size_t n)
生成随机大整数(0 - B^n-1 均匀分布)
n
#define n
include
lmmp
mprand.h
生成于
, 为 LMMP使用
1.18.0