An open source random number generation algorithm in C ++?

Question

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

Description: we are creating a new version for our application that supports writing to Sqlite DB. In the latest version of our application, we did not have a unique key for each record. But now with the new updated version we need to support the import mechanism from the latest version of DB. So, what we do, we read each record from the old database and generate a random number for the unique key and save it in the new database. Here we need to import up to 10,000 records continuously.

Answer 1

Well, in the end, you will either have to stop generating them, or you are going to duplicate them.

On a computer, your parameters are pretty limited by pseudo random number generators (PRNGs) and given your restriction that they never repeat, then PRNG is your best option - real random data will sometimes duplicate a number.

In your case, I would prefer to use a large PRNG (32 bits or more) to shuffle your 10,000 numbers, and then send the numbers in shuffled order.

Once they are used up, you can shuffle again - since the PRNG is so large, you can go through 10,000 numbers many times before duplicating the sequence.

Give us more information on what you are doing, and we can come up with a better answer.

-Adam

Answer 2

Mersenne Twister is the best at the moment (although I could be behind some really new discoveries in a few weeks). A source in almost every language is available somewhere there, and MT is also provided in Boost here.

Answer 3

If it really should be in the range of 1 to 10,0000 without repetitions, but not sequential, then it would probably be better to create a sequential array of 10,000 elements first and then shuffle them.

However, I have to agree with the comments on the first question. I do not see any value, making them inconsistent.

Alternatively, in unique and inconsistent cases important, the range from 1 to 10,000 becomes doubtful. It would probably be best to use a GUID.

Answer 4

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

Otherwise boost

It basically became TR1.

If you do not get duplicates, you want to shuffle . It can be quite simple, but there are some pitfalls if you are not doing it right. Jeff Atwood made a nice note a while ago:

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

Answer 5

Boost probably does something that does not guarantee duplicate numbers. But for a bit of fun here is my idea.

Note: I am not trying to generate my rand in this direction, this is crazy.

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

Answer 6

Boost.Random is a good choice and works great for me. However, if you do not need many random number generators and distributions, you can look for another library so as not to install the entire Boost package.

Answer 7

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

Answer 8

mtrand is nice.

Answer 9

Can one cast doubt on the whole idea of ​​using a random number as a unique key for writing a database? I am not familiar with sqlite, but it's worth finding out if it supports some sort of unique identifier for the column inside. For example, SQL Server has “identity” columns, and Oracle has “sequences”, both of which serve the same purpose.

Answer 10

Generate large random numbers. Let's say 128 bits. The coefficients of two such numbers, the same in the set 10,000, are ridiculously small (of order n ^ 2/2 ^ b, where n = the number of numbers needed and b = the number of bits used). Given a sufficient number of bits, the chances will be less than the likelihood that your drum will be damaged by a cosmic ray, so your algorithm will fail anyway. Be careful that the space in which you draw random numbers really has the number of bits you are looking for. It is easy to mistakenly generate 128-bit numbers from a pool of 32 bits (i.e. there are only 2 ^ 32 possibilities, even if you generate numbers from 1 to 2 ^ 128). The boost random number generators can do this right for you. BTW: if you do not like 128 bits, then use 256 bits or more until you feel comfortable that there is no practical chance of hashing. If you need to do this only once, just use the shuffle method already mentioned in the previous answer. This will have the advantage of generating an ideal hash.

Answer 11

Although you may have a requirement to generate a sequence of values ​​that are not repeated, you cannot call the result “random”. True randomness is less associated with the lack of repetition than with the distribution of values ​​in a sequence.

Answer 12

Random number generation is too important to be left to chance. - Robert R. Coveu, Oak Ridge National Laboratory.

Answer 13

Numerical recipes in C contain an entire chapter on random number generation. There are several implementation options. From simple and direct to complex with good statistical properties.

Answer 14

http://random.org/ if you need really random numbers