我不打算将其用于安全目的或统计分析.我需要创建一个简单的随机数生成器,用于我的计算机图形应用程序.我不想使用术语"随机数发生器",因为人们用非常严格的术语来思考它,但我想不出任何其他的词来形容它.
最重要的是,我需要能够在恒定时间内计算系列中的第n个项.
看来,我无法用rand_r或srand()实现这一点,因为这些需求是依赖于状态的,我可能需要以某种未知的顺序计算nth.
我看过线性反馈移位寄存器,但这些寄存器也依赖于状态.
到目前为止我有这个:
int rand =(n*prime 1 + seed)%prime 2
n =用于表示序列中术语的索引.例如:对于第一学期,n == 1
素数1和素数2是素数,其中素数1 >素数2
seed =某个数字,它允许一个人使用相同的函数根据种子产生不同的系列,但是给定种子的系列相同.
我不知道这是多么好或坏,因为我还没有充分利用它,但如果有更多经验的人可以指出这方面的问题,或者帮助我改进它,那将会很棒.
编辑 - 我不在乎它是否可预测.我只是想在我的计算机图形学中创建一些随机性.
我不久前偶然发现了这个问题，正在寻找同一问题的解决方案。最近，我想出了如何在低常数 O(log(n)) 时间内做到这一点。虽然这不太符合作者要求的 O(1)，但它可能足够快（使用 -O3 编译的示例运行，实现了 10 亿个任意索引随机数的性能，其中 n 在 1 到 2 之间变化^ 48，55.7 秒——略低于 1800 万个数字/秒）。
首先，解决方案背后的理论：
一种常见的 RNG 类型是线性同余生成器，基本上，它们的工作原理如下：
随机(n) = (m*随机(n-1) + b) mod p
其中 m 和 b 以及 p 是常数（有关如何选择它们的信息，请参阅有关 LCG 的参考资料）。由此，我们可以使用一些模运算来设计以下内容：
random(0) = seed mod p
random(1) = m*seed + b mod p
random(2) = m^2*seed + m*b + b mod p
...
random(n) = m^n*seed + b*Sum_{i = 0 to n - 1} m^i mod p
= m^n*seed + b*(m^n - 1)/(m - 1) mod p
计算上述内容可能是一个问题，因为数字很快就会超出数字限制。一般情况的解决方案是计算 m^n 以 p*(m - 1) 为模，但是，如果我们取 b = 0 （LCG 的子情况，有时称为乘法同余生成器），我们有一个更简单的方法解，并且只能以 p 为模进行计算。
下面，我使用 RANF 使用的常量参数（由 CRAY 开发），其中 p = 2^48 且 g = 44485709377909。p 是 2 的幂这一事实减少了所需的操作数量（如预期）：
#include <cassert>
#include <stdint.h>
#include <cstdlib>
class RANF{
// MCG constants and state data
static const uint64_t m = 44485709377909ULL;
static const uint64_t n = 0x0000010000000000ULL; // 2^48
static const uint64_t randMax = n - 1;
const uint64_t seed;
uint64_t state;
public:
// Constructors, which define the seed
RANF(uint64_t seed) : seed(seed), state(seed) {
assert(seed > 0 && "A seed of 0 breaks the LCG!");
}
// Gets the next random number in the sequence
inline uint64_t getNext(){
state *= m;
return state & randMax;
}
// Sets the MCG to a specific index
inline void setPosition(size_t index){
state = seed;
uint64_t mPower = m;
for (uint64_t b = 1; index; b <<= 1){
if (index & b){
state *= mPower;
index ^= b;
}
mPower *= mPower;
}
}
};
#include <cstdio>
void example(){
RANF R(1);
// Gets the number through random-access -- O(log(n))
R.setPosition(12345); // Goes to the nth random number
printf("fast nth number = %lu\n", R.getNext());
// Gets the number through standard, sequential access -- O(n)
R.setPosition(0);
for(size_t i = 0; i < 12345; i++) R.getNext();
printf("slow nth number = %lu\n", R.getNext());
}
虽然我认为作者现在已经继续前进，但希望这对其他人有用。
如果你真的关心运行时性能，使用查找表可以使上述速度提高大约 10 倍，但代价是编译时间和二进制大小（根据 OP 的要求，它也是 O(1) wrt 所需的随机索引）
在下面的版本中，我使用 c++14constexpr在编译时生成查找表，每秒获得 176M 任意索引随机数（这样做确实增加了大约 12 秒的额外编译时间，并且二进制文件增加了 1.5MB）大小——如果使用部分重新编译，增加的时间可能会减少）。
class RANF{
// MCG constants and state data
static const uint64_t m = 44485709377909ULL;
static const uint64_t n = 0x0000010000000000ULL; // 2^48
static const uint64_t randMax = n - 1;
const uint64_t seed;
uint64_t state;
// Lookup table
struct lookup_t{
uint64_t v[3][65536];
constexpr lookup_t() : v() {
uint64_t mi = RANF::m;
for (size_t i = 0; i < 3; i++){
v[i][0] = 1;
uint64_t val = mi;
for (uint16_t j = 0x0001; j; j++){
v[i][j] = val;
val *= mi;
}
mi = val;
}
}
};
friend struct lookup_t;
public:
// Constructors, which define the seed
RANF(uint64_t seed) : seed(seed), state(seed) {
assert(seed > 0 && "A seed of 0 breaks the LCG!");
}
// Gets the next random number in the sequence
inline uint64_t getNext(){
state *= m;
return state & randMax;
}
// Sets the MCG to a specific index
// Note: idx.u16 indices need to be adapted for big-endian machines!
inline void setPosition(size_t index){
static constexpr auto lookup = lookup_t();
union { uint16_t u16[4]; uint64_t u64; } idx;
idx.u64 = index;
state = seed * lookup.v[0][idx.u16[0]] * lookup.v[1][idx.u16[1]] * lookup.v[2][idx.u16[2]];
}
};
基本上，它的作用是将 、 等的计算拆分m^0xAAAABBBBCCCC mod p为(m^0xAAAA00000000 mod p)*(m^0xBBBB0000 mod p)*(m^CCCC mod p) mod p，然后为 0x0000-0xFFFF范围内可以填充AAAA、BBBB或的每个值预先计算表CCCC。