Xcode C++ help! A real random number generator

Discussion in 'Mac Programming' started by unknown.exe, Dec 13, 2007.

  1. unknown.exe macrumors member

    unknown.exe

    Joined:
    Sep 22, 2007
    Location:
    Somewhere on Earth
    #1
    Sup, I'm writing a C++ program that outputs the 4 components of DNA (A, G, T, and C) in a random order 1,000,000 times in order to replicate what the DNA for a single cell would look like. Here is my code:

    {
    //DNA
    DNA:
    int randnum;
    for(long double i = 1.0; i < 1000000.0; i++)
    {
    srand((unsigned)time(0));
    for(int index=0; index<1; index++)
    randnum = (rand()%1000)+1;
    if (randnum <=250)
    cout << "A";
    else if (randnum > 250 && randnum <= 500)
    cout << "C";
    else if (randnum > 500 && randnum <=750)
    cout << "T";
    else
    cout << "G";
    }
    }

    It compiles fine and everything, but the out put looks like this:

    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCCCCCCCC
    CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
    CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
    CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
    CCCCCCCCCCCCCCCCCCCCCCCCCGGGGGGGGGGGGGGGGGGGGGGGGGG
    GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
    GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
    GGGGGGGGGGGGGGGGGGGTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
    TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT..........................etc.

    Obviously the random number generator is very... uuuuhhh... un-random? Well, if any one knows of a very random number generator, or knows any way I can change my code to achieve this, please tell me!:apple:
     
  2. gnasher729 macrumors P6

    gnasher729

    Joined:
    Nov 25, 2005
  3. ChrisBrightwell macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #3
    Move the call to srand() outside your look. You only have to seed the RNG once.

    Here's your problem, though: That loop will execute several times sever millisecond. If you re-seed the RNG every time through the loop, you're going to get the same value several times during each individual millisecond.
     
  4. unknown.exe thread starter macrumors member

    unknown.exe

    Joined:
    Sep 22, 2007
    Location:
    Somewhere on Earth
    #4
    What do you mean by "outside your look"... you mean loop?
     
  5. unknown.exe thread starter macrumors member

    unknown.exe

    Joined:
    Sep 22, 2007
    Location:
    Somewhere on Earth
    #5
    Moving the srand() outside of the loop worked! Thanks a lot!
     
  6. ShosMeister macrumors newbie

    ShosMeister

    Joined:
    Dec 28, 2007
    #6
    If you do a search on the web, you will find a few online sources that will provide you true random numbers if you really need them. Some of them are free (just require you to create a login account) and others are pay. There are also a few that will show you how to create your own hardware random number generator.

    The key point in all the research that I've done is that true random numbers can not be produced without using some hardware input (i.e. video, sound, etc. as indicated in the online sources). Even PokerStars went to a hardware based random number system using everything they could get including the mouse activity of the users sitting at a given table!

    As you can tell (maybe) this is a topic that has been of great interest to me over the years since the first computer that I had used a true (read as non-algorithmic) random number generator - my Atari 800. What it did was use the lower 4 or 5 digits (have to get the books to be absolutely sure, but, this is close) of the clock frequency. It then sent that back to your program left shifted to be a number between 0 and 1.

    What I've tried to do over the years is duplicate this, but, it seems that most modern computers (using the languages available) do not have access to this data. So, I've created my own using the accessible timer with the highest resolution (like the nanoTime). If you take that and shift it appropriately, you can get some pretty impressive true random numbers. I ran that 10000 times and the built in rand functions 10000 times and compared the statistical results and they were relatively the same.

    One other thought that I had was to take a peek at network or hard drive activity and see if there was something I could use in that to capture a random number. Also, using a combination of my random number and then going into memory somewhere (based on the random number) and getting the data from that location (or maybe even a screen bit/byte).

    Just some thoughts in case you really do want/need true random numbers.
     
  7. Gelfin macrumors 68020

    Gelfin

    Joined:
    Sep 18, 2001
    Location:
    Denver, CO
    #7
    You are misusing rand by reseeding repeatedly it as ChrisBrightwell described, but it's a really poor example of a PRNG generally, and you would be well advised not to get into the habit of using it.

    There are two better alternatives available to you: If you are concerned about portability (say, to Windows), then look at the documentation for "random" instead of "rand." If you are sticking to the Mac (and certain other Unixes), then you might consider simply opening and reading bytes from /dev/random. The system maintains its own entropy pool for /dev/random, so you won't typically have to seed it, and it's random enough for anything short of serious cryptography.

    As an aside, unless you are merely looking to give the vague impression of DNAishness in print, a random assortment of a million bases is emphatically not what the DNA in a single cell would look like.

    The high resolution timer is readily available in Mac OS X. Include <mach/mach_time.h> and call mach_absolute_time() to get a 64-bit CPU clock value. Other platforms have similar means to accomplish the same thing.

    That said, think about this for a minute. If good randomness could be obtained this cheaply, why would anyone ever have invented algorithmic PRNGs? The distribution may appear similar for some kinds of analysis, but it is a far cry from random.
     
  8. ChrisA macrumors G4

    Joined:
    Jan 5, 2006
    Location:
    Redondo Beach, California
    #8
    Have you read Knuth Volume 2 "Seminumerical Algorithms" Knuth is pretty much the definitive source on this for most of us. One of the topics is the statistics of the generated numbers. Are they truely uniformly distributed over the range? Distribution is the usual problem of most ad-hoc techniques.
     
  9. kpua macrumors 6502

    Joined:
    Jul 25, 2006
    #9
    Also, rand() is not a good choice when modding the result. According to the man page for the more appropriate random() function, the lower bits of the rand() function go in a cyclic pattern that eliminates any good random results. random() makes sure that each bit of each successive number is randomized. Using /dev/random was also a good suggestion, but random() is generally more accessible, practical, and portable.
     
  10. Eraserhead macrumors G4

    Eraserhead

    Joined:
    Nov 3, 2005
    Location:
    UK
    #10
    According to man random, arc4random provides cyptographic strength random numbers (see man arc4random for details.)
     
  11. ShosMeister macrumors newbie

    ShosMeister

    Joined:
    Dec 28, 2007
    #11
    I've been wondering that for years and the only reason I can come up with is that as time went on, people realized there wasn't a need for anything other than pseudo random numbers. Also, a lot of people forget that the simplest solution is often the best.

    My personal feeling is that since the hardware has changed so fast over the last 15+ years, it has been impossible for programmers to keep up. They spend all of their time just trying to keep pace with the hardware and don't have very much time for real innovation as existed in the 1980's. Just my opinion.
     
  12. Gelfin macrumors 68020

    Gelfin

    Joined:
    Sep 18, 2001
    Location:
    Denver, CO
    #12
    It's a good just-so story, but it just doesn't wash. Your faith in the Atari 800 solution seems almost superstitious here. I'm trying to tell you it's misguided, and it isn't a good investment of your time trying to replicate a really poor solution.

    Algorithmic PRNGs that are sufficient for cryptography are computationally very expensive compared with masking out the high-order bits of a clock counter. What I previously asked rhetorically I now state affirmatively: No one would ever have created something so fantastically expensive when peeking at a clock counter would suffice. The problem is that peeking at a clock counter won't suffice if you're expecting anything more than the weakly semi-random behavior needed for games. That's all the Atari was shooting for.

    Wow. This must be what it feels like to be a doctor listening to an "alternative medicine" believer. Your notions of how the computer industry works are interesting to say the least.

    Look, I hate to disrespect a man's first computer, but there is no magic in the POKEY chip. The entire design lives on 14 hand-drawn schematic pages. Any patents on it have been lapsed for close to a decade. The transistors required could be added to any modern CPU at zero effective cost. And they would be if they did anything worth doing. The POKEY RNG suitable to its task in approximately the same way the POKEY sound generator is suitable to the task of reproducing sound. It was the cheapest way available in 1979 to get random-seeming behavior into game machines. It initializes into a well-defined state. It's counter based, so the more frequently you call it, the more predictable it becomes even to a casual observer, but a determined attacker can count clocks and know precisely the value you will get out of it at any given point in an operation.

    What you have there is not a "true" random number generator. What you have is a pseudorandom number generator so trivial you think it isn't the same sort of animal.

    In modern PRNGs, the algorithm is seeded with an arbitrary value. Frequently programmers use the current time as the seed, but this is not required. In the POKEY PRNG, the "seed" is a fixed value that is loaded into the register at the time the chip is initialized.

    POKEY's "algorithm" is (random = (seed+clocks_elapsed)&0xff). It seems to you like it isn't algorithmic because there is practically no algorithm there to examine and because it's implemented in hardware. By contrast, it is common for the most modern PRNGs to be based on strong cryptography to begin with. The seed you provide is used to derive a key that is used to encrypt an internal buffer. Random bytes are read from this encrypted buffer, and when all bytes in the buffer have been returned to consumers, you just encrypt the buffer again to get more. Thus the strength of the RNG is tied directly to the strength of your cryptographic algorithm.

    Bottom line, "real" random is the opposite of what computers do, and faking it convincingly is harder than it looks. The POKEY RNG is not a bit of romantic silicon frontier wisdom that we modern hidebound shlubs have forgotten. We could emulate POKEY quite easily; it just isn't a good idea.
     
  13. ShosMeister macrumors newbie

    ShosMeister

    Joined:
    Dec 28, 2007
    #13
    Sorry to get you so upset with all of this although I do disagree a bit. I don't think that we (as humans) always find the simplest solution. Often times, we find solutions that work, and work great, but, it doesn't always mean it's the best/simplest/easiest/most efficient. No matter though.

    You are correct if all you are going to do is look at the clock. It's pretty predictable. If I'm not mistaken, they did not look at the clock itself, but, the frequency which is constantly changing and a little less predictable - sorta. Again though, as you mentioned this is great for machines that run at 1.8mHz and are primarily game machines. That doesn't mean that the idea is foolish though and does not warrant investigation for modern systems. If it's something that provides equally random distribution as the available PRNG without the exact predictability of an algorithm, then again, why not.

    I am not a doctor (but I did stay at a Holiday Inn Express last night :)). Seriously, I do believe that the amount of innovation that existed in the 70's-80's was significantly more than it is today. Software engineers frequently designed and programmed things that the hardware engineers said it could not do - yet, it was done. Some of that innovation lead to things today like separate graphics cards which, at one time, were just software drivers. That's not to say there isn't still creativity and innovation, I just think it is less now due to the rapid advances in the hardware.

    Take as an example TV. Before it existed, someone had to create the idea. Now, not to say that the changes since then aren't fantastic (love my HD), but, to a certain extent, they are just improvements to the original idea. That doesn't mean that either the original or the changes are any less impressive, just different.

    No disrespect felt, but, there was a bit of magic there, otherwise, why did is help spawn the video games and such. It was a pretty unique idea to offer a separate graphics controller - not to say they were the first or only one, just made it more popular. And in 20 years we will be talking about our lame 32bit CPUs only running at 2GHz (roughly). Technology always changes and improves. That doesn't negate the impact of it. Where would we be if the first transistor circuit wasn't designed? Is that lame too? I think not.

    Again, not trying to raise your blood pressure and sorry if I did.
     

Share This Page