如何快速生成大量(伪)随机比特?每个比特必须是独立的,并且以等概率为零或一。显然,我可以对其进行某些变化。
randbit=rand()%2;
但我觉得应该有更快的方法,每次调用随机数生成器时生成几个随机位数。理想情况下,我想获得一个整数或字符,其中每个二进制位都是随机且独立的,但也可以使用其他解决方案。
这个应用程序不涉及密码学,因此强大的随机性并不是主要因素,而速度和正确的分布是很重要的。
将随机数转换为二进制
为什么不获取一个数字(大小适当以获得所需的足够位数)然后将其转换为二进制。你实际上会从一个随机数中获得位,这意味着它们也是随机的。
0和1的概率也是50%,因为取所有介于0和某个2^n限制之间的数字,并计算零和一的数量相等> 这意味着零和一的概率是相同的。
关于速度
这可能非常快,因为只获取一个随机数与其中的位数相比更快。现在完全取决于您的二进制转换。
for ( i = 0; i < sizeof( randomNumber ) * 8; ++i ) { std::cout << ( randomNumber & 1U ); randimNumber >>= 1U; }
,假设randomNumber是一个无符号整数。 - mxmlnkn如你所说,只需生成随机整数。
那么你就有了32位随机比特,每个比特都是等概率的1或0。
通过循环获取这些比特:
for (int i = 0; i < 32; i++)
{
randomBit = (randomNum >> i) & 1
...
// Do your thing
}
重复此步骤直到获得正确的比特数。
这是我用Java编码的一个非常快速的算法,基于George Marsaglia的XORShift算法:一次获取64位!
/**
* State for random number generation
*/
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE);
/**
* Gets a long random value
* @return Random long value based on static state
*/
public static final long nextLong() {
long a=state;
state = xorShift64(a);
return a;
}
/**
* XORShift algorithm - credit to George Marsaglia!
* @param a Initial state
* @return new state
*/
public static final long xorShift64(long a) {
a ^= (a << 21);
a ^= (a >>> 35);
a ^= (a << 4);
return a;
}
请注意使用 [ThreadStatic] 属性,此对象会自动处理新线程,无需锁定。这是确保高性能随机、SMP无锁的唯一方法。
http://blogs.msdn.com/pfxteam/archive/2009/02/19/9434171.aspx
#include <iostream>
#include <bitset>
#include <random>
int main()
{
const size_t nrOfBits = 256;
std::bitset<nrOfBits> randomBits;
std::default_random_engine generator;
std::uniform_real_distribution<float> distribution(0.0,1.0);
float randNum;
for(size_t i = 0; i < nrOfBits; i++)
{
randNum = distribution(generator);
if(randNum < 0.5) {
randNum = 0;
} else {
randNum = 1;
}
randomBits.set(i, randNum);
}
std::cout << "randomBits =\n" << randomBits << std::endl;
return 0;
}
在我的测试中,这需要4.5886e-05秒,使用256位。
std :: bernoulli_distribution bdist(0.5); for(size_t i = 0; i <nrOfBits; i ++)randomBits.set(i,bdist(generator));
- mxmlnknunsigned int numbers[] =
{
0xABCDEF34, ...
};
然后将数组编译到您的程序中,逐个数字进行处理。
这样每次调用都可以获得32位(在32位处理器上),生成时间最短,因为所有数字都提前生成,分布由您控制。当然,缺点是这些数字根本不是随机的,这取决于您使用PRNG的目的是否重要。
bool coinToss()
{
return rand()&1;
}
由于将%2替换为&1是等效的,因此这实际上是一种更快的生成比特的方法。
((int)rand*rand)%2
这样的东西怎么样? - C4d