Open source random number generation algorithm in

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.

Answer 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.

Answer 2

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

Answer 3

mtrand is nice.

Answer 4

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

Answer 5

How random? Obviously there's rand(), there's also OS specific stuff (Windows has something in the CryptoAPI, for example). Are you writing something (not recommended), or just looking for a pre-existing function to use?

Answer 6

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";
    }
}