[random] uniform_int_distribution can produce out of range results - by Steven Watanabe

Status : 

  Fixed<br /><br />
		This item has been fixed in the current or upcoming version of this product.<br /><br />
		A more detailed explanation for the resolution of this particular item may have been provided in the comments section.


1
0
Sign in
to vote
ID 642557 Comments
Status Closed Workarounds
Type Bug Repros 0
Opened 2/10/2011 3:06:09 PM
Access Restriction Public

Description

It fails in some cases with long long, because the result is evaluated in floating point
arithmetic, which only has a 53 bit mantissa.  I tried to file this a while ago, but it failed
to go through and I forgot about it.
Sign in to post a comment.
Posted by Microsoft on 2/14/2011 at 7:43 PM
Hi Steven,

Thanks for reporting this bug. We've already fixed it, and the fix will be available in VC11. uniform_int_distribution has been completely rewritten to handle arbitrary ranges and arbitrary UniformRandomNumberGenerators using bitwise operations - the floating-point arithmetic has been completely eradicated. (This applies to shuffle() too.) Here's an example:

C:\Temp>type meow.cpp
#include <ios>
#include <iostream>
#include <map>
#include <ostream>
#include <random>
using namespace std;

template <typename URNG> void test() {
    URNG gen;

    const long long min = 0x1FFFFFFFFFFFFF1LL;
    const long long max = 0x1FFFFFFFFFFFFF8LL;

    uniform_int_distribution<long long> dist(min, max);

    map<long long, int> m;

    for (int i = 0; i <= 100000000; ++i) {
        if (i > 0 && i % 2000000 == 0) {
            cout << "*";
        }

        const long long val = dist(gen);

        if (val < min || val > max) {
            cout << "FAIL" << endl;
        }

        ++m[val];
    }

    cout << endl;

    for (auto i = m.cbegin(); i != m.cend(); ++i) {
        cout << "0x" << hex << uppercase << i->first << " was generated "
            << dec << i->second << " times." << endl;
    }
}

class Wacky {
public:
    Wacky() : mt(1729) { }

    typedef unsigned long result_type;

    static result_type min() {
        return 0;
    }

    static result_type max() {
        return 90000;
    }

    result_type operator()() {
        for (;;) {
            const result_type ret = mt() & 0x1FFFFUL;

            if (ret >= min() && ret <= max()) {
                return ret;
            }
        }
    }

private:
    mt19937 mt;
};

int main() {
    test<mt19937>();
    test<Wacky>();

    cout << "PASS" << endl;
}

C:\Temp>cl
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 17.00.40214 for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.

usage: cl [ option... ] filename... [ /link linkoption... ]

C:\Temp>cl /EHsc /nologo /W4 /MT /O2 /GL meow.cpp
meow.cpp
Generating code
Finished generating code

C:\Temp>meow
**************************************************
0x1FFFFFFFFFFFFF1 was generated 12494725 times.
0x1FFFFFFFFFFFFF2 was generated 12498602 times.
0x1FFFFFFFFFFFFF3 was generated 12508705 times.
0x1FFFFFFFFFFFFF4 was generated 12503544 times.
0x1FFFFFFFFFFFFF5 was generated 12496322 times.
0x1FFFFFFFFFFFFF6 was generated 12499830 times.
0x1FFFFFFFFFFFFF7 was generated 12498310 times.
0x1FFFFFFFFFFFFF8 was generated 12499963 times.
**************************************************
0x1FFFFFFFFFFFFF1 was generated 12504281 times.
0x1FFFFFFFFFFFFF2 was generated 12498365 times.
0x1FFFFFFFFFFFFF3 was generated 12502600 times.
0x1FFFFFFFFFFFFF4 was generated 12503016 times.
0x1FFFFFFFFFFFFF5 was generated 12506478 times.
0x1FFFFFFFFFFFFF6 was generated 12494497 times.
0x1FFFFFFFFFFFFF7 was generated 12496152 times.
0x1FFFFFFFFFFFFF8 was generated 12494612 times.
PASS

If you have any further questions, feel free to E-mail me at stl@microsoft.com .

Stephan T. Lavavej
Visual C++ Libraries Developer
Posted by Microsoft on 2/10/2011 at 11:46 PM
Thanks for your feedback. We are routing this issue to the appropriate group within the Visual Studio Product Team for triage and resolution. These specialized experts will follow-up with your issue.
Posted by Microsoft on 2/10/2011 at 3:14 PM
Thank you for your feedback, we are currently reviewing the issue you have submitted. If this issue is urgent, please contact support directly(http://support.microsoft.com)