So I was thinking today…
As everyone familiar with multi-threaded programming knows, it’s very difficult to predict which thread will get control of a shared resource after it becomes available. I wondered if it would be possible to produce nearly-random numbers as follows:[list=1]
[li]Start with an integer variable set to zero.[/li][li]Create 31 threads, each of which will flip one bit (I don’t want to mess with the sign bit).[/li][li]Have a mutex that protects this number. Each time a thread gets the mutex, it flips the bit it’s responsible for, releases the mutex, and then goes back to the beginning of its sequence again.[/li][li]Repeat this about 1000 times (maybe 961 (31[sup]2[/sup])) and spew the result out as a random number.[/li][/list=1]Obviously, this isn’t the fastest process in the world, so it should only be used for security–assuming it’s secure (i.e., nearly random).
So how 'bout it? Does it look like it would produce a nearly random sequence of numbers? The one advantage I can see straightaway of this over a standard generator is that you can’t reproduce a sequence of numbers just by giving the seed.
I’m away from my computer (or any computer that I could install Visual C++ on), so I can’t play around with this. Any thoughts?
I can’t really comment on your procedure, as I don’t do much parallel programming. My guess is that what you describe may be hard to predict, but is probably not any more random than just using a traditional generator with a randomized seed, and possibly a lot less (i.e. certain computers may consistently produce certain patterns in their thread distributions).
I do know of a recently-developed parallel random number generator package developed at NCSA (National Center for Supercomputing Applications, in Urbana, IL). It’s called SPRNG (here’s the original web site, and it looks like there’s a new one as well.) It’s pretty widely used in the scientific community, for parallel Monte Carlo codes. I don’t remember exactly, but the algorithm may take advantage of the randomness of multi-threaded programs. I think their algorithms are all public, though.
Nitpicky edit to my own post: replace that last “, though” with something like “, so check them out!” That though really doesn’t make any sense.
This isn’t the same as random. On one computer, the threads may be executed in order 0, 1, …, 30, while on another in order 30, 29, … , 0, but neither is random. Also, if an executed thread has its priority reduced, it may not execute again until all the threads have had a turn. If so, after N bitflips, there will mod(N,31) zeros or ones, and 31-mod(N,31) of the other, not a very random number.
I dunno…my experience (at least with win98) is that running the same multi-threaded program multiple times will produce different execution orders. Also, the number of ones isn’t quite as important as their distribution.
Bottom line is, I’m gonna have to try this once I get back to my own computer.
ultra - it would seem to me that you’re merely relying on the “randomness” of the OS’s thread scheduling algorithm to generate your random numbers. If it schedules threads in a “round-robin” manner, you’re definitely not going to get random numbers that way. On the other hand, if the OS schedules threads (of equal priority) “randomly”, where do you think it gets its random numbers?
I suppose you’ve got a point. Still, even if this is based on a standard pseudorandom number generator, it might be a little bit tougher to crack than your workaday rand() function. I’m not planning on encrypting any secrets with this method (or any other method, for that matter), just curious about it.
As has been said, the results of such a calculation would mainly depend on the amount of other work being done on the system and on the thread scheduler algorithm. Things like the number of threads started, the order of starting them, and thread priorities would also affect the result but probably not its randomness.
If there’s little running besides this multi-threaded generator, the results will very likely be decidedly non-random. Depending on the thread scheduler you may get “somewhat random” data on a system where the generator’s threads are frequently preempted by other activity. But if you can guarantee some kind of system activity it’s probably better to collect other hard-to-predict measurements based on such activity; keyboard, mouse or network packet timings, for example.
Why do you need to use a ‘workaday rand()’ generator? There are all kinds of pseudo-random number algorithms available on the net which do a fine job.
Your scheduler trick wouldn’t work at all. It’s a deterministic process.
What do you want to use this generator for? What’s acceptable for some uses is unacceptable for others.
I had no particular use for this in mind. I was just curious as to how it would compare against other random number generators. Consensus seems to be that it sucks, so I guess there’s not much left to say.