Random Boolean Generation

Question

I am currently using the Eller algorithm in C ++, and a small detail bothers me about the randomness of the maze.

So far, I have used the following code to generate random bool:

bool randomBool()
{
    return 0 + (rand() % (1 - 0 + 1)) == 1;
}

// In main.cpp

time_t seconds;
time(&seconds);
srand((unsigned int) seconds);

But after debugging, I often see repetitive trueor false, sometimes up to 30 times in a row.

Is this algorithm really random or is there some better method in C ++?

Answer 1

STL ++ 11 , rand(). , 0 1:

#include <iostream>
#include <random>

int main(int argc, char *argv[]) {
    auto gen = std::bind(std::uniform_int_distribution<>(0,1),std::default_random_engine());
    const unsigned int N = 100;
    unsigned int numTrue = 0;
    unsigned int numFalse = 0;
    for (int i = 0; i < 100; ++i) {
        bool b = gen();
        if (b) ++ numTrue;
        else ++numFalse;
    }
    std::cout << numTrue << " TRUE, " << numFalse << " FALSE" << std::endl;
}

++. , - 50/50 "" "" , 0 1 , z true, false.

, ,

, 30 "true" "false" . rand() , , , , . , . 30 , - . . , , ; . , (, randomBool() ), , .

, , , 30 "" "" ( ). , , "" , , , . - , , , .

, ( 30) . , IID ( ) 50% , . , . L 1 2 ^ L; 2 2 ^ L 1 2 ^ (L-1). :

#include <iostream>
#include <random>
#include <map>

bool randomBool() {
    static auto gen = std::bind(std::uniform_int_distribution<>(0,1),std::default_random_engine());
    return gen();
}

int main(int argc, char *argv[]) {

    const unsigned int N = 1e8;
    std::map<unsigned int,unsigned int> histogram;
    bool current = randomBool();
    unsigned int currentLength = 1;
    for (int i = 0; i < N; ++i) {
        bool b = randomBool();
        if (b == current) {
            ++currentLength;
        } else {
            auto it = histogram.find(currentLength);
            if (it != histogram.end())
                it->second += 1;
            else
                histogram.insert(std::make_pair(currentLength,1));
            currentLength = 1;
        }
        current = b;
    }

    for (auto pair : histogram) 
        std::cout << "STREAK LENGTH " << pair.first << " OCCURS " << pair.second << " TIMES" << std::endl;
}

:

STREAK LENGTH 1 OCCURS 25011106 TIMES
STREAK LENGTH 2 OCCURS 12503578 TIMES
STREAK LENGTH 3 OCCURS 6249056 TIMES
STREAK LENGTH 4 OCCURS 3125508 TIMES
STREAK LENGTH 5 OCCURS 1560812 TIMES
STREAK LENGTH 6 OCCURS 781206 TIMES
STREAK LENGTH 7 OCCURS 390143 TIMES
STREAK LENGTH 8 OCCURS 194748 TIMES
STREAK LENGTH 9 OCCURS 97816 TIMES
STREAK LENGTH 10 OCCURS 48685 TIMES
STREAK LENGTH 11 OCCURS 24327 TIMES
STREAK LENGTH 12 OCCURS 12176 TIMES
STREAK LENGTH 13 OCCURS 6149 TIMES
STREAK LENGTH 14 OCCURS 3028 TIMES
STREAK LENGTH 15 OCCURS 1489 TIMES
STREAK LENGTH 16 OCCURS 811 TIMES
STREAK LENGTH 17 OCCURS 383 TIMES
STREAK LENGTH 18 OCCURS 193 TIMES
STREAK LENGTH 19 OCCURS 104 TIMES
STREAK LENGTH 20 OCCURS 43 TIMES
STREAK LENGTH 21 OCCURS 20 TIMES
STREAK LENGTH 22 OCCURS 14 TIMES
STREAK LENGTH 23 OCCURS 4 TIMES
STREAK LENGTH 24 OCCURS 3 TIMES

L N, L, . , , .

- 24 [: 23]. 24 1 2 ^ (24-1), 1 8 . 1e8 1e8/24 ~ 4,3 , , [ , ). 30, , 1 537 30 , 24.

Answer 2

, rand() , , RAND_MAX (.. , ). RAND_MAX , .

Answer 3

bool randomBool() {
    return 0 + (rand() % (1 - 0 + 1)) == 1;
}

, , rand() . , .

- , rand(), :

bool randomBool() {
   return rand() > (RAND_MAX / 2);
}

Answer 4

. rand(), LCG. bool - MSB. 1/2.

#include <cmath>
#include <cstdlib>

inline bool random_bool()
{
   static const int shift = static_cast<int>(std::log2(RAND_MAX));
   return (rand() >> shift) & 1;
}

Answer 5

++ 11, ( ) ( 0,5 ):

#include <random>
template <typename Prob>
bool binomial_trial(const Prob p = 0.5) {
    static auto dev = std::random_device();
    static auto gen = std::mt19937{dev()};
    static auto dist = std::uniform_real_distribution<Prob>(0,1);
    return (dist(gen) < p);
}