Radewoosh's blog

Mindf**k of the day — rand() from c++ and Berlekamp–Massey algorithm
By Radewoosh, history, 6 years ago, In English

Once, during one training, my team and I noticed something strange. I'll write a little bit later what it was exactly. The point is that after the contest we decided to investigate how c++ rand() behaves on our machines (we use Linux). So, we used a Berlekamp–Massey algorithm on the results of rand() taken modulo 2.

The result is shocking — the length of the linear recurrence is only 527! No, the results aren't cyclic, just the recurrence is short.

"Cool, but who cares? Just some random fact which I wouldn't notice and it wouldn't have any impact on me." — wrong!

We discovered it while solving a task which required calculating the rank of a binary matrix. We wanted to check something, so we just generated big matrix using rand(), which turned out to be a bad decision. As only the first 527 columns were, let's say, independent, the rest were determined by first 527 ones, so the rank didn't exceed 527, and we lost much time just wondering what's happening.

Moreover, if the number of columns is even, the rank is only 496 (for matrices big enough of course). Guess what's the length of the recurrence if we look only at every second value of rand().

Yep, you're right — 496. One can notice that 527 - 496 = 31 and that 31 divides 527! Illuminati!

Here are some useful links: 1 2.

If anybody can explain precisely what's happening for even number of columns, it would be great. Also, if anybody knows how does rand() look inside and can say a few words about it, it also would be great.

  • Vote: I like it
  • +119
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Where's Blogwoosh??? xD

→ Reply
»
6 years ago, # |
  Vote: I like it +63 Vote: I do not like it

Have noone ever told you to never use rand()?

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Wow, rand() is getting worse ...

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +74 Vote: I do not like it

    rand() is not getting worse, Berlekamp-Massey is getting better!

    → Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Don't use rand(): a guide to random number generators in C++ by neal

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it -12 Vote: I do not like it

    This has nothing to do with the blog.

    EDIT: it does, my bad.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +40 Vote: I do not like it

      It does. The post contains the exact implementation of rand() that Codeforces uses, which is a linear congruential generator.

      The compiler Radewoosh is using has a better implementation of rand() than Codeforces, but it's most likely still a linear congruential generator, which means rand() % 2 has a relatively low period.

      Try mt19937 instead and see what you get.

      EDIT: this one might actually be a linear-feedback shift register rather than a linear congruential generator, but the point about rand() % 2 having low-quality randomness is still true.

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +200 Vote: I do not like it

Yep, you're right — 496. One can notice that 527 - 496 = 31 and that 31 divides 527! Illuminati!

Not just that, but 31 also divides 496! Now that cannot be a coincidence.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -31 Vote: I do not like it

Here is a possible simple fix for this problem using the standard library function random_shuffle(). 1

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Easier fix: use rand() % 1000007 % 2

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      Thanks for the constructive comment; an interesting and much simpler fix, indeed. The previous link includes a pefroamance comparison between both fixes.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The GLIBC random number generator: https://www.mathstat.dal.ca/~selinger/random/

→ Reply
»
6 years ago, # |
  Vote: I like it -18 Vote: I do not like it

I've learned to use a linear congruential generator, with the rand() as a seed. Seems to work pretty well.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The length of the linear recurrence of Xorshift64 is 64, I surprised. It seems to that calculating linear recurrence is weak points of some RNGs. At least it of mt19937 isn't short.

https://ideone.com/UxRMg8 (xorshift) https://ideone.com/8ueYut (mt19937) https://en.wikipedia.org/wiki/Xorshift (the code of xorshift64)

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

It's more likely to be a feature, but on my machine this code outputs only zeros (on Codeforces it doesn't): 

for (int i = 0; i < 100; i++) {
    srand(i);
    cout << rand() % 7 << " ";
}

And 0 is the only seed among all seeds from 0 to 100000, such that the first number generated by rand() isn't a multiple of 16807 = 75.
This caused me a lot of problems when I was stressing my solution once and wrote something like this:

srand(some number);
int n = rand() % 7 + 1;
→ Reply