Open source random number generation algorithm in C++?

Question

I need to generate random numbers in the range 1 - 10000 continuously with out duplication. Any recommendations?

Description: we are building a new version for our application, which maintains records in Sqlite DB. in the last version of our application, we did not had unique key for each record. But now with new upgraded version, we need to support the import facility from the last version's DB. So what we do is, we read each and every record from the old DB and generate a random number for the unique key and store it in new DB. Here we many need to import up to 10000 records continuously.

Solution 1

If it really must be in the range of 1 to 10,0000 without repeats, but non-sequential then it would probably be best to first create a sequential array of 10000 elements, and then shuffle them.

However, I must agree with the comments on the original question. I see no value in making them non- sequential.

Alternately, in unique & non-sequential are important, then the 1 to 10,000 range become questionable. It would probably be best to just used a GUID.

Solution 2

Well, eventually you'll either have to stop generating them, or you're going to star duplicating them.

On a computer your options are pretty limited to Pseudo Random Number Generators (PRNGs), and given your constraint that they never repeat then a PRNG is your best option - real random data will occasionally duplicate a number.

In your case, I'd consider using a large PRNG (32 bit or larger) to shuffle your 10,000 numbers, and then send the numbers out in the shuffled order.

Once they're used up you can shuffle again - since the PRNG is so large you'll be able to go through the 10k numbers many times before duplicating a sequence.

Give us more information about what your doing and we may come up with a better answer.

-Adam

Solution 3

Mersenne Twister is the current best (though i could be a few weeks behind any really new discoveries). Source in just about every language is available somewhere out there, and MT is also provided in Boost here

Solution 4

TR1 has good random number support - if your compiler supports it.

Otherwise Boost

It's basically what became TR1.

As far as not getting duplicates - you want a shuffle. It can be pretty simple, but there are some pitfalls if you don't do it right. Jeff Atwood did a nice write up a while back:

http://www.codinghorror.com/blog/archives/001015.html

Solution 5

Boost probably does something that garantees no repeated numbers. But for a bit of fun here is my idea.

Note: I don't try and generate my rand in that direction lies madness.

#include <iostream>
#include <vector>
#include <algorithm>


class GaranteedNoRepeatRandom
{
    public:
        GaranteedNoRepeatRandom(int limit)
            :data(limit)
            ,index(0)
        {
            for(int loop=0;loop < limit;++loop)
            {   data[loop]  = loop;
            }
            // Note: random_shuffle optionally takes a third parameter
            // as the rand number generator.
            std::random_shuffle(&data[0],&data[0]+limit);
        }

        unsigned int rand()
        {
            unsigned int result = data[index];
            index   = (index+1) % data.size();

            // Add code to re-shuffle after index wraps around
            return result;
        }
    private:
        std::vector<unsigned int>               data;
        std::vector<unsigned int>::size_type    index;
};

int main()
{
    GaranteedNoRepeatRandom     gen(10000);

    for(int loop =0;loop < 10;++loop)
    {
        std::cout << gen.rand() << "\n";
    }
}

View more solutions

Comments

[Paul Nathan]

Mersenne Twister is considered a good compromise between Fast and Perfect PRNG, as far as I know.

[Roel]

It's only the 'best' for certain application, i.e. everything not crypto (like the OP's use case, or simulations).

[Eugene Bujak]

-1 for linking to torrent sites with pirated content

[Mateen Ulhaq]

For crypto, Blum Blum Shub's quite popular.