Just what!? Standart rand() in C++ or undeniable proof of the existence of magic!

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Until recently, I knew that rand() in C++ works awfully with random_shuffle and it was not credible, but continued to use it for most tasks.. But recently I wrote some code and I cannot explain the result. Maybe you can?

I advise you to read to the end, it is really very interesting!

At each step, this code generates a random value from 0 to 1. As soon as 11 (for example) identical values equal 1 were received in a row, index number of current value is added to the vector. This operation is repeated a number of times and each time it starts from the beginning.

Let's output vector values and look at the last 15 of them for convenience.

Code here:

CODE

#include <bits/stdc++.h>
using namespace std;

int main() {
    srand(time(0));
    vector<int> v;
    for(int i = 0; i < 100; ++ i) {
        int it = 0, tec = 0;
        while(true) {
            ++ it;
            if(tec == 11) {
                v.push_back(it);
                break;
            }
            if(rand() % 2) ++ tec;
            else tec = 0;
        }
    }
    for(int i = v.size() - 15; i < v.size(); ++ i)
        cout << v[i] << endl;
}

OUTPUT1

OUTPUT2

OUTPUT3

OUTPUT4

At first glance it seems that the values are random. But let's try to sort the vector.

Code here:

CODE

#include <bits/stdc++.h>
using namespace std;

int main() {
    srand(time(0));
    vector<int> v;
    for(int i = 0; i < 100; ++ i) {
        int it = 0, tec = 0;
        while(true) {
            ++ it;
            if(tec == 11) {
                v.push_back(it);
                break;
            }
            if(rand() % 2) ++ tec;
            else tec = 0;
        }
    }
    sort(v.begin(), v.end());
    for(int i = v.size() - 15; i < v.size(); ++ i)
        cout << v[i] << endl;
}

OUTPUT1

OUTPUT2

OUTPUT3

OUTPUT4

It should be noted that the output is different each time, but the individual values are the same. Moreover, these individual values are repeated three to four times.

Using of mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); instead of rand() gives a random output array.
If we add a line that will not affect the answer in any way, but will affect the time difference between the rand() calls we also get random values in the output array. In doing so, we have to use random delay. If the delay is fixed, we will not get random values.

CODE1, rnd(), normal random values

#include <bits/stdc++.h>
using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int main() {
    srand(time(0));
    vector<int> v;
    for(int i = 0; i < 100; ++ i) {
        int it = 0, tec = 0;
        while(true) {
            ++ it;
            if(tec == 11) {
                v.push_back(it);
                break;
            }
            if(rnd() % 2) ++ tec;
            else tec = 0;
        }
    }
    sort(v.begin(), v.end());
    for(int i = v.size() - 15; i < v.size(); ++ i)
        cout << v[i] << endl;
}

CODE2, random delay between calls rand(), normal random values

#include <bits/stdc++.h>
using namespace std;

int main() {
    srand(time(0));
    vector<int> v;
    for(int i = 0; i < 100; ++ i) {
        int it = 0, tec = 0;
        while(true) {
            //
            int u = 1;
            for(int j = 0; j < rand() % 10; ++ j) u *= 3;
            //
            ++ it;
            if(tec == 11) {
                v.push_back(it);
                break;
            }
            if(rand() % 2) ++ tec;
            else tec = 0;
        }
    }
    sort(v.begin(), v.end());
    for(int i = v.size() - 15; i < v.size(); ++ i)
        cout << v[i] << endl;
}

With a fixed delay, we also get magic values, even if the delay is large.

CODE3, fixed delay between calls rand(), magic values

#include <bits/stdc++.h>
using namespace std;

int main() {
    srand(time(0));
    vector<int> v;
    for(int i = 0; i < 100; ++ i) {
        int it = 0, tec = 0;
        while(true) {
            //
            int u = 1;
            for(int j = 0; j < 10; ++ j) u *= 3;
            //
            ++ it;
            if(tec == 11) {
                v.push_back(it);
                break;
            }
            if(rand() % 2) ++ tec;
            else tec = 0;
        }
    }
    sort(v.begin(), v.end());
    for(int i = v.size() - 15; i < v.size(); ++ i)
        cout << v[i] << endl;
}

Now let's instead of an empty loop in the third code call rand().

CODE

#include <bits/stdc++.h>
using namespace std;

int main() {
    srand(time(0));
    vector<int> v;
    for(int i = 0; i < 100; ++ i) {
        int it = 0, tec = 0;
        while(true) {
            //
            rand();
            //
            ++ it;
            if(tec == 11) {
                v.push_back(it);
                break;
            }
            if(rand() % 2) ++ tec;
            else tec = 0;
        }
    }
    sort(v.begin(), v.end());
    for(int i = v.size() - 25; i < v.size(); ++ i)
        cout << v[i] << endl;
}

OUTPUT1

OUTPUT2

OUTPUT3

Values become repeated much more often..

CODE

#include <bits/stdc++.h>
using namespace std;
int main() {
    srand(time(0));
    vector<int> v;
    for(int i = 0; i < 100; ++ i) {
        int it = 0, tec = 0;
        while(true) {
            //
            for(int j = 0; j < 2; ++ j) rand();
            //
            ++ it;
            if(tec == 11) {
                v.push_back(it);
                break;
            }
            if(rand() % 2) ++ tec;
            else tec = 0;
        }
    }
    sort(v.begin(), v.end());
    for(int i = v.size() - 25; i < v.size(); ++ i)
        cout << v[i] << endl;
}

OUTPUT

If we call the method twice, the values are repeated more often.

I believe that this is not quite a trivial algorithm and the result is rather strange. If you have any idea how to explain this, please state your thoughts in the comments. Thanks for reading!

Комментарии (13)

Написать комментарий?

gfonn

6 лет назад, # |

My guess is: it's due to time(0). But I don't really know how or why :S

→ Ответить

seo

6 лет назад, # ^ |

← Rev. 2 →

Checked without using srand(time(0)); You should understand that every time the output array will be the same. But the question is whether we get groups of identical values in a sorted vector.

Result:

#include <bits/stdc++.h>
using namespace std;

int main() {
    //srand(time(0));
    vector<int> v;
    for(int i = 0; i < 100; ++ i) {
        int it = 0, tec = 0;
        while(true) {
            ++ it;
            if(tec == 11) {
                v.push_back(it);
                break;
            }
            if(rand() % 2) ++ tec;
            else tec = 0;
        }
    }
    sort(v.begin(), v.end());
    for(int i = v.size() - 15; i < v.size(); ++ i)
        cout << v[i] << endl;
}

OUTPUT, same every time

Therefore, srand(time(0)); does not affect the oddity of the result.

P.S. Using srand(time(nullptr)); instead of srand(time(0)); gives same result as using of srand(time(0));.

No, I mean, I know you need to seed the rand, but maybe there's a pattern on time(0) everytime you run it. I read that time(0) gets time in seconds since the Unix epoch, I thought it might depend on how codeforces or your computer get that value, but I think I'm wrong.

Tried to use srand(56164989), same result.

NVAL

+23

It isn't magic. It's small period of std::rand

So how I should write this code with rand() and without crutches to get a normal result?

+36

Don't use std::rand :)

mouse_wireless

Why std::rand? rand is part of the C standard library, is it not? std:: prefix is not needed.

Nevermind, apparently everything contained in libraries is part of the std namespace. But compilers are allowed to inject things in the global namespace as well.

Roberio

You also shouldn't really expect any differences between CODE and CODE3. You are simply doing a loop that doesn't change the state of the PRNG.

The topic has been updated. If we call the method a fixed number of times

//
rand();
//

//
for(int j = 0; j < 2; ++ j) rand();
//

//
for(int j = 0; j < 10; ++ j) rand();
//

the repeating becomes more frequent. But if we use

//
int u = 1;
for(int j = 0; j < rand() % 10; ++ j) u *= 3;
//

values become random.

Can you explain this in some way?

Auto comment: topic has been updated by seo (previous revision, new revision, compare).

CrafterKolyan

No magic at all here. That's just an implementation of rand() function.

The only fact you should know that it is Linear congruential generator with some parameters.

So what you are saying (11 times odd numbers in a row) are actually just some equations which need to be satisfied, so you have not many solutions. You can increase this number to 17 odd numbers in a row and will eventually find that on Windows it will fail to find any number (I've waited for five minutes and haven't found any number). That means that no value satisfies the system of equations.

Very interesting. Thanks for the reply. I understood how it works approximately, but for me it remains unclear how to explain it exactly.

Блог пользователя seo