[jira] [Created] (IMPALA-5754) rand() algorithm is very non-random

["Jim Apple (JIRA)" <ji...@apache.org>]

Jim Apple created IMPALA-5754:
---------------------------------

             Summary: rand() algorithm is very non-random
                 Key: IMPALA-5754
                 URL: https://issues.apache.org/jira/browse/IMPALA-5754
             Project: IMPALA
          Issue Type: Bug
          Components: Backend
            Reporter: Jim Apple


{{MathFunctions::Rand}} includes the line {{*seed = rand_r(seed);}}. I think this is incorrect use of {{rand_r}}, which sets its seed during the call, and so doesn't seed to set it in an assignment. This produces very unrandom output; the following program which simulates this typically loops after less than 20k distinct items, while a good PRNG would produce somewhere in the neighborhood of {{RAND_MAX/2}} items before looping.

{noformat}
#include <cstdlib>
#include <unordered_set>
#include <iostream>

using namespace std;

int main() {
  unsigned int seed;
  while(cin >> seed) {
    unordered_set<int> history;
    while (history.find(seed) == history.end()) {
      history.insert(seed);
      seed = rand_r(&seed);
      if (0 == (history.size() & (history.size() - 1))) {
        cout << history.size() << endl;
      }
    }
    cout << history.size() << endl;
  }
}
{noformat}

In any case, we should drop the use of {{rand_r}}; see IMPALA-4954.



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)