Better random algorithm?

问题:

I'm making a game in C++ and it involves filling tiles with random booleans (either yes or no) whether it is yes or no is decided by rand() % 1. It doesn't feel very random.

I'm using srand with ctime at startup, but it seems like the same patterns are coming up.

Are there any algorithms that will create very random numbers? Or any suggestions on how I could improve rand()?

回答1:

True randomness often doesn't seem very random. Do expect to see odd runs.

But at least one immediate thing you can do to help is to avoid using just the lowest-order bit. To quote Numerical Recipes in C:

If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));

and never by anything resembling

j = 1 + (rand() % 10);

(which uses lower-order bits).

Also, you might consider using a different RNG with better properties instead. The Xorshift algorithm is a nice alternative. It's speedy and compact at just a few lines of C, and should be good enough statistically for nearly any game.

回答2:

The low order bits are not very random.
By using %2 you are only checking the bottom bit of the random number.

Assuming you are not needing crypto strength randomness.
Then the following should be OK.

bool  tile = rand() > (RAND_MAX / 2);

回答3:

The easiest thing you can do, short of writing another PRNG or using a library, would be to just use all bits that a single call to rand() gives you. Most random number generators can be broken down to a stream of bits which has certain randomness and statistical properties. Individual bits, spaced evenly on that stream, need not have the same properties. Essentially you're throwing away between 14 and 31 bits of pseudo-randomness here.

You can just cache the number generated by a call to rand() and use each bit of it (depending on the number of bits rand() gives you, of course, which will depend on RAND_MAX). So if your RAND_MAX is 32768 you can use the lowest-order 15 bits of that number in sequence. Especially if RAND_MAX is that small you are not dealing with the low-order bits of the generator, so taking bits from the high end doesn't gain you much. For example the Microsoft CRT generates random numbers with the equation

x_{n + 1} = x_n · 214013 + 2531011

and then shifts away the lowest-order 16 bits of that result and restricts it to 15 bits. So no low-order bits from the generator there. This largely holds true for generators where RAND_MAX is as high as 2³¹ but you can't count on that sometimes (so maybe restrict yourself to 16 or 24 bits there, taken from the high-order end).

So, generally, just cache the result of a call to rand() and use the bits of that number in sequence for your application, instead of rand() % 2.

回答4:

Many pseudo-random number generators suffer from cyclical lower bits, especially linear congruential algorithms, which are typically the most common implementations. Some people suggest shifting out the least significant bits to solve this.

回答5:

Boost Random Number Library

回答6:

I have used the Mersenne Twister random number generator successfully for many years. Its source code is available from the maths department of Hiroshima Uni here. (Direct link so you don't have to read Japanese!)

What is great about this algorithm is that:

1. Its 'randomness' is very good
2. Its state vector is a vector of unsigned ints and an index, so it is very easy to save its state, reload its state, and resume a pseudo-random process from where it left off.

I'd recommend giving it a look for your game.

回答7:

The perfect way of Yes or No as random is toggling those. You may not need random function.

回答8:

The lowest bits of standard random number generators aren't very random, this is a well known problem.

I'd look into the boost random number library.

回答9:

C++11 has the following way of implementing the Mersenne tittie twister algorothm. From cppreference.com:

#include <random>
#include <iostream>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 6);

    for (int n=0; n<10; ++n)
        std::cout << dis(gen) << ' ';
    std::cout << '\n';
}

This produces random numbers suitable for simulations without the disadvantages of many other random number generators. It is not suitable for cryptography; but cryptographic random number generators are more computationally intensive.

There is also the Well equidistributed long-period linear algorithm; with many example implementations.

回答10:

A quick thing that might make your numbers feel a bit more random would be to re-seed the generator each time the condition if(rand() % 50==0) is true.

回答11:

Knuth suggests a Random number generation by subtractive method. Its is believed to be quite randome. For a sample implementation in the Scheme language see here

回答12:

People say lower-order bits are not random. So try something from the middle. This will get you the 28th bit:

(rand() >> 13) % 2

回答13:

With random numbers to get good results you really need to have a generator that combines several generators's results. Just discarding the bottom bit is a pretty silly answer.

multiply with carry is simple to implement and has good results on its own and if you have several of them and combine the results you will get extremely good results. It also doesn't require much memory and is very fast.

回答14:

Also if you reseed too fast then you will get the exact same number. Personally I use a class that updates the seed only when the time has changed.