Sidebar Sidebar
Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.

macOS Using race conditions to generate a better random number?

GorillaPaws

GorillaPaws

macrumors 6502a
Original poster
Oct 26, 2003
932
8
Richmond, VA
I just started learning about concurrency with MDN's recent release of their concurrency video course, and the discussion about race conditions got me thinking about how you could take advantage of it to improve the generation of random numbers.

Couldn't you spawn off several threads that all execute a custom rand() function (using different seeds) that all access the same memory? The result would be non-deterministic based on different processor loads and therefore a more-random random() function? Because this is such a simple solution I'm guessing someone has thought of it, and therefore it can't be as great as it seems.
 
I'll put it this way:
You're taking a pseudo-random number generator, getting the results of (say) 6 runs, then putting those 6 on a die and rolling it. Is this more random? Sure, a little. It doesn't get you much closer to real randomosity. You can combine results of many "rolls" of the pseudo-random number generator in interesting ways (XOR'ing a number of results together, etc.) but at the end of the day, you've pushed the randomitude up just a little. The most novel suggestions of getting "more random" random numbers I've seen are camera-on-a-fish-tank or camera-on-a-lava-lamp type approaches that you can't really replicate if you're distributing your app to others.

-Lee
 
Couldn't you just use the current processor load as a value to seed your random generator instead?

In your proposal, you would need to re-seed the threads every time rand() was used, because after the first "randomized" access, each of the threads would be working from the same previous value (which would defeat the purpose). The trick then becomes coming up with a random seed value, which gives kind of a chicken-and-egg problem.
 
As is often the case, lee1210 beat me to it. A "real" random device should be hardware (on Unixy systems, including Mac OS X, there's a /dev/random).

In a pinch, you could probably still use the camera and only use a couple of LSB's (or perhaps do the same thing with the mic input). If the camera or sound ADC is too good though, this will not be very random either.
 
I should hunt down the link for the guy who ran a gaming website where people complained about his random numbers... so he build a large machine that runs for an hour or so per day, which rolls physical dice, uses a digital camera to observe/read the results, and records them to a file from which he pulls numbers for the 'random' functions on his page.

It's fast, an hour run generates many thousands of results. It is, however, VERY noisy, and reportedly causes that part of the house to shake slightly. It's also hard to argue with it's randomness.
 
Before you go too far down this path in a real situation, you have to think about what the numbers are for. There aren't many situations where you want really random unrepeatable numbers. For checking out simulations, hashing functions and so on, you want a repeatable sequence so you can recreate problems and check that you've fixed them. The nice thing about pseudo-random number generators is that they create a repeatable sequence that has the statistical properties of a random one. (You can change the seed to get a new sequence, so you're not stuck with the same conditions all the time.)

In your case playing with this could be an interesting exercise, though.
 
GorillaPaws said:
Yes, I see the problem now. Thanks for helping me realize my own stupidity...
Click to expand...
It's not stupid, it's just a random thought. Most things are obvious after somebody has already realized the answer.

Alkiera said:
I should hunt down the link for the guy who ran a gaming website where people complained about his random numbers... so he build a large machine that runs for an hour or so per day, which rolls physical dice, uses a digital camera to observe/read the results, and records them to a file from which he pulls numbers for the 'random' functions on his page.

It's fast, an hour run generates many thousands of results. It is, however, VERY noisy, and reportedly causes that part of the house to shake slightly. It's also hard to argue with it's randomness.
Click to expand...
Was his name Rube Goldberg, by any chance? Instead of a camera, he should have flipped coins with magnets attached, which then selectively pushed/pulled a lever which either released a hook holding a toy sailboat or underwater float which, depending on the vagaries of the weather and currents, sailed into one of three channels or popped up into one of three tubes, respectively. That would've been much more straightforward way to get an even distribution of one to six.
 
Why not just go overkill and use a true random number generator? like one that samples radioactive decay and ends up with a number quite close to random.
 
skunkworker said:
Why not just go overkill and use a true random number generator?
Click to expand...

Because trying (and failing) to solve difficult/impossible problems helps you learn more about the nature of a thing. I have no specific interest in generating truly random numbers, but the thought experiment helped me better understand the problem of pseudo-random numbers, and also helped me realize that race conditions are probably a hard thing to use deliberately to benefit from their non-deterministic behavior (or that there are smarter alternative approaches for doing this).
 
skunkworker said:
Why not just go overkill and use a true random number generator? like one that samples radioactive decay and ends up with a number quite close to random.
Click to expand...

Does this exist? When i was reading through this thread i was thinking about using radioactive decay to generate a number and then you mentioned this! freaky huh!
 
Rhalliwell1 said:
Does this exist? When i was reading through this thread i was thinking about using radioactive decay to generate a number and then you mentioned this! freaky huh!
Click to expand...

I am not a physicist, so I don't know how alpha radiation would be random (using the microseconds between detection of an alpha particle?). However, I assume we have devices to detect alpha radiation that can be accessed digitally so this should be possible.

-Lee
 
The thing about thread dispatch is that it is not random. The kernel runs a thread for a few microseconds, then interrupts it, saves its context, and goes on to repeat with the next thread in a very strict rotation. The thing that leads to the indeterminacy of thread execution is not the dispatch but the fact that a stream of CPU instructions will have varying execution times for each one, so there is no reliable way to know where any given thread will be relative to any other. This is why we have locks and their derivatives. I can imagine the task of synchronizing two or four or eight CPUs so that none of them are trying to start the same thread must have been quite a challenge, at least for the first person who did it.
 
lee1210 said:
I am not a physicist, so I don't know how alpha radiation would be random (using the microseconds between detection of an alpha particle?). However, I assume we have devices to detect alpha radiation that can be accessed digitally so this should be possible.

-Lee
Click to expand...

Alpha or beta particles would be pretty useful for this type of device, especially since beta emitters tend to be more common in nature, and don't require you to get your hands on these rarer, heavier elements. With a sensitive enough device, you could even use Carbon-14 as a beta emitter.

But the general idea is correct. If you have a radioactive isotope, you have a half-life, sure, but that's it, it's a statement about the general decay rates of large quantities of the material. It's not a statement about specific decay rates at any point in time. So what you see in reality is random fluctuations around the average at any point in time. These fluctuations, being truly random, can be used as seeds to an algorithm that converts the fluctuation into a number in the desired range.
 
Yeah they usually use a digital geiger counter hooked up to a radioactive source, then through some software to get the randomness.
 
Krevnik said:
Alpha or beta particles would be pretty useful for this type of device, especially since beta emitters tend to be more common in nature, and don't require you to get your hands on these rarer, heavier elements. With a sensitive enough device, you could even use Carbon-14 as a beta emitter.

But the general idea is correct. If you have a radioactive isotope, you have a half-life, sure, but that's it, it's a statement about the general decay rates of large quantities of the material. It's not a statement about specific decay rates at any point in time. So what you see in reality is random fluctuations around the average at any point in time. These fluctuations, being truly random, can be used as seeds to an algorithm that converts the fluctuation into a number in the desired range.
Click to expand...

Or Americium if you want measurable radiation.
 
You must log in or register to reply here.
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.
Top Bottom
Back