How to generate distinct random numbers per distinct threads in .NET?

Question

Dear ladies and sirs.

I have to generate 19 bit random numbers. However, there is a constraint - two threads may not generate the same random number when running certain code.

The simplest solution is lock the entire code. However, I would like to know if there is a non locking solution. I thought, I can incorporate ManagedThreadId within the produced random numbers, but the ManagedThreadId documentation on the Internet mentions that it may span the whole Int32 range. Unmanaged thread id seems to be limited to 11 bits, still this leaves me with just 8 truly random bits.

Are there any other ways? Somehow to utilize the Thread Local Storage, may be?

Thanks.

EDIT

I wish to clear something. The random numbers may repeat, this is inevitable, eventually. What I wish to avoid is if a certain piece of code is simultaneously entered by two threads, then these threads may not use the same random number, guaranteed. Before or after that code is executed - fine, but not within the code itself. Again, I can use some locking scheme to prevent it, but I want to examine non locking schemes first.

EDIT 2

Reading the comments/answers to my question I have understood that I cannot avoid but to lock the particular code. However, for the sake of pure academic curiosity, I am still interested to know if anyone knows a good solution to my original question - generating 19 bits random numbers in multiple threads, where the numbers are guaranteed to be distinct between threads, given that the ManagedThreadId can be potentially very large, so large that simply aggregating it within the random number is bad - leaves no space for the actual random bits.

Answer 1

Well how many threads are you actually going to use? That's the limiting factor. If you only need (say) 8 threads then you can just lose 3 bits of information. You could create a "generator factory" which knows how many generators it's allowed to create, and throws an exception if you try to create too many.

Your requirement for distinct numbers isn't very clear though - even if you make sure that one thread never creates the same number that another thread has created, you still have to worry about whether you create a duplicate number on the same thread. Is that a problem for you or not?

Answer 2

Use thread-local storage to hold a reference to a System::Random object. Give each thread its own RNG (you can tell easily enough if you've not yet allocated one) and you can pull values from each one merrily for as long as you like. It's probably a good idea to wrap up the code to get a thread-specific random number in a method so that you only need to get it right once.

---

[Edit: Include example]

class example {
    [ThreadStatic]
    static Random threadLocalRandom;
    private int GimmeARandomNumber(int upperBound) {
        Random r = threadLocalRandom;
        if (r == null) {
            r = threadLocalRandom = new Random();
        }
        return r.Next(0, upperBound);
    }
}

Answer 3

If you really can never repeat a number between threads or in the same thread (that part isn't 100% clear), a regular random number generator will not work for you. A generator that creates a number between 1 and N has a 1-in-N chance of generating the previous number the next time it's asked for one.

If there's an reasonable upper limit on the total number of random numbers, call it N, for a particular run, you might consider creating an array from 1 to N. Sequentially populate that array with numbers from 1 to N, and then use a shuffling algorithm to sort the numbers. If you have M threads, you could then segment the shuffled array such that the first thread uses indices 0, M, 2M; the second thread uses indices 1, M+1, 2M+1, etc. ensuring you don't access past the end of the shuffled array.

This is a memory intensive solution for fairly large N, so may not be appropriate for your problem. If you are allowed to repeat the same random number on a given thread, just not between threads, Jon's solution is much more resource friendly.