threads + unique random numbers

[Sebastiano Barbieri]

My program starts n threads at the same time and at a certain point of the code a random number is generated. Correct me if I'm wrong if the system time in milliseconds is the same this causes the generated number to be the same for each thread. The problem I'm facing is that I'd like each thread to generate a different number, which doesn't happen if I'm starting them at exactly the same time. I was thinking about a time delay before starting the threads, but I don't like the idea too much. Any suggestions? Thanx in advance.

[Leslie Chaim]

How do you generate your random numbers?
Are you using the Random class?
at a certain point of the code a random number is generated
How about if you synchronize on a common (or static) Random instance?

[Stan James]

Have you tried this? Does it really happen? If so, there should be lots of ways to make each thread unique:
You might re-seed the randomizer with current time in millis right before you ask for a number. It's near impossible for all the threads to do this re-seed with the same time value.
Maybe you could hash thread id and use it in the seed or multiply it into the random number.
The main thread could pass a random number to each sub-thread, and the sub-thread could re-seed with that number.
or do all of the above!

[Jim Yingst]

Have you tried this? Does it really happen?
I have and yes it can, depending on how the random numbers were generated.
If so, there should be lots of ways to make each thread unique:
You might re-seed the randomizer with current time in millis right before you ask for a number. It's near impossible for all the threads to do this re-seed with the same time value.
Actually new Random() does this anyway, will appallingly bad results here. It's extremely easy to create threads that get the same value of System.currentTimeMillis(), on my system at least.

import java.util.*;
public class ThreadRandomTest {
    public static void main(String[] args) throws Exception {
        Thread[] threads = new Thread[1000];
        final Set set = new HashSet();
        for (int i = 0, max = threads.length; i < max; i++) {
            threads[ i ] = new Thread() {
                public void run() {
                    Random r = new Random(System.currentTimeMillis());
                    //Random r = new Random();
                    double x = r.nextDouble();
                    //double x = Math.random();
                    Thread.yield();
                    if (!set.add(new Double(x)))
                        System.out.println("Duplicate: " + x);
                }
            };
        }
        for (int i = 0, max = threads.length; i < max; i++)
            threads[ i ].start();
        for (int i = 0, max = threads.length; i < max; i++)
            threads[ i ].join();
        System.out.println(set.size() + " unique values");
    }
}

Note that Math.random() works great here. That's because it's already been written to do what Leslie suggests: create a single static Random instance and keep re-using it for each new value. I'd use Math.random() if a double is desired; otherwise implement Leslie's solution for maximum customizability, to take advantage of the methods like nextLong(), nextInt(), etc. Alternately you can adapt the results of Math.random() with minor mathmatical transformations, but it's a bit less efficient than using Random's methods, and especially if you want a long, using Math.random() will probably do a poorer job of giving you an even random distribution than Random.nextLong() will. Roundoff errors will probably cause results to glob around certain values.
Maybe you could hash thread id and use it in the seed or multiply it into the random number.
This could work - especially if thread contention (for the static random source) were an issue. I'd probably XOR the hash with the current time.
The main thread could pass a random number to each sub-thread, and the sub-thread could re-seed with that number.
Also viable, if each thread is going to generate a lot of different numbers of its own.
or do all of the above!
Urk. That could be some ugly code...
[ July 23, 2003: Message edited by: Jim Yingst ]

[David Weitzman]

The Random class isn't thread safe, but if you want to give each thread its own Random instance and have them all seeded differently, you could do something like this:
Random seedRandom = new Random();
For Each Thread
startThreadUsingRandomInstance(new Random(seedRandom.nextInt()));
End For
Each class has its own instance of Random to avoid concurrency issues when sharing one, but they're all seeded from one initial Random to insure that the seeds are distinct.
You could store the Random instances as ThreadLocals.
[ July 23, 2003: Message edited by: David Weitzman ]

[Jim Yingst]

I believe that's what Stan meant when he said "The main thread could pass a random number to each sub-thread, and the sub-thread could re-seed with that number."

[Sebastiano Barbieri]

Thanx a lot to all of you guys, you were a great help and gave me a lot of ideas about the topic. I used the reseeding option since truly every thread might generate multiple values. Works great! Thanx!
[ July 24, 2003: Message edited by: Sebastiano Barbieri ]

[Stan James]

Your threads coming up with identical time in millis surprised me. They must be doing something more quickly than I imagined. Maybe you just get them all started and they all ask for current time in one tick at your computer's time resolution.
A singleton (global) static rn generator might do the trick. Each thread would get the next number from the same generator and we could hope it wouldn't repeat itself often. But synchronizing on the get might be a bottle-neck.