Using race conditions to generate a better random number?

Discussion in 'Mac Programming' started by GorillaPaws, Jun 3, 2010.

  1. GorillaPaws macrumors 6502a

    GorillaPaws

    Joined:
    Oct 26, 2003
    Location:
    Richmond, VA
    #1
    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.
     
  2. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #2
    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
     
  3. Sander macrumors 6502

    Joined:
    Apr 24, 2008
    #3
    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.
     
  4. Sander macrumors 6502

    Joined:
    Apr 24, 2008
    #4
    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.
     
  5. GorillaPaws thread starter macrumors 6502a

    GorillaPaws

    Joined:
    Oct 26, 2003
    Location:
    Richmond, VA
    #5
    Yes, I see the problem now. Thanks for helping me realize my own stupidity...
     
  6. Alkiera macrumors regular

    Joined:
    Mar 11, 2008
    #6
    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.
     
  7. Efrem macrumors regular

    Joined:
    Jul 30, 2009
    #7
    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.
     
  8. qtx43 macrumors 6502a

    Joined:
    Aug 4, 2007
    #8
    It's not stupid, it's just a random thought. Most things are obvious after somebody has already realized the answer.

    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.
     
  9. skunkworker macrumors regular

    Joined:
    Sep 9, 2007
    #9
    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.
     
  10. GorillaPaws thread starter macrumors 6502a

    GorillaPaws

    Joined:
    Oct 26, 2003
    Location:
    Richmond, VA
    #10
    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).
     
  11. Rhalliwell1 macrumors 6502a

    Joined:
    May 22, 2008
    #11
    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!
     
  12. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #12
    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
     
  13. Sydde macrumors 68020

    Sydde

    Joined:
    Aug 17, 2009
    #13
    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.
     
  14. Krevnik macrumors 68040

    Krevnik

    Joined:
    Sep 8, 2003
    #14
    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.
     
  15. skunkworker macrumors regular

    Joined:
    Sep 9, 2007
    #15
    Yeah they usually use a digital geiger counter hooked up to a radioactive source, then through some software to get the randomness.
     
  16. MorphingDragon macrumors 603

    MorphingDragon

    Joined:
    Mar 27, 2009
    Location:
    The World Inbetween
    #16
    Or Americium if you want measurable radiation.
     
  17. Sydde macrumors 68020

    Sydde

    Joined:
    Aug 17, 2009
    #17
    Kind of high on gamma, that. You really want something that requires a little less shielding. Gamma is a bit hard on electronics.
     
  18. MorphingDragon macrumors 603

    MorphingDragon

    Joined:
    Mar 27, 2009
    Location:
    The World Inbetween
    #18
    All radiation is a bit hard on electronics. Even an electric field.

    The insulation found in smoke detectors should be enough.
     

Share This Page