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

["Jinchul Kim (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/IMPALA-5754?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Jinchul Kim resolved IMPALA-5754.
---------------------------------
       Resolution: Fixed
    Fix Version/s: Impala 2.12.0

> 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
>            Assignee: Jinchul Kim
>              Labels: newbie
>             Fix For: Impala 2.12.0
>
>
> {{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)