Truly random?

Discussion in 'C Programming' started by Alvin, Dec 6, 2005.

  1. Alvin

    Alvin Guest

    Well, I'm developing a Tetris game in SDL, but when it comes to
    deciding the next block, I'm stuck. It's random, but when I try
    something like seeding the randomizer with the time, it won't update as
    fast as one block can fall, and the next to be determined. Generating
    different numbers in one spur can work, but people can play Tetris for
    hours (or even days), and so you can't predict how long. You could
    constantly be making more with the same system as making, say 5 random
    numbers out of a seed, but that would prove system intensive if the
    game already uses a lot of memory (not that Tetris does, but I'm sure
    there's a better way).
    Alvin, Dec 6, 2005
    #1
    1. Advertising

  2. "Alvin" <> writes:
    > Well, I'm developing a Tetris game in SDL, but when it comes to
    > deciding the next block, I'm stuck. It's random, but when I try
    > something like seeding the randomizer with the time, it won't update as
    > fast as one block can fall, and the next to be determined.


    You only need to seed the PRNG once, at the start of the game.

    DES
    --
    Dag-Erling Smørgrav -
    =?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=, Dec 6, 2005
    #2
    1. Advertising

  3. Alvin

    Randy Howard Guest

    Alvin wrote
    (in article
    <>):

    > Well, I'm developing a Tetris game in SDL, but when it comes to
    > deciding the next block, I'm stuck. It's random, but when I try
    > something like seeding the randomizer with the time, it won't update as
    > fast as one block can fall, and the next to be determined.


    It sounds like you are trying to seed on every random call. You
    only need to seed it once, or perhaps once per game worst case,
    not every time. That would slow things down quite a bit, and
    not achieve much at all.



    --
    Randy Howard (2reply remove FOOBAR)
    "The power of accurate observation is called cynicism by those
    who have not got it." - George Bernard Shaw
    Randy Howard, Dec 6, 2005
    #3
  4. If, as your subject line suggests, you want truly random numbers,
    forget a PRNG like rand() or random(). The PR part stands for
    PSEUDO-RANDOM. Computers aren't very good at generating truly
    random numbers unless they are broken or they have specific hardware
    for the purpose. Some attempts at truly random number generation
    time keystrokes, or listen to thermal noise or radioactive decay,
    or time events from outside the computer (like network traffic).

    If you need truly random numbers for cryptography, a PRNG won't
    do. The difference can get you killed.

    >Well, I'm developing a Tetris game in SDL, but when it comes to
    >deciding the next block, I'm stuck. It's random, but when I try
    >something like seeding the randomizer with the time, it won't update as
    >fast as one block can fall, and the next to be determined. Generating


    Don't seed the PSEUDO random number generator more than once. Since
    the time() call gives a time granularity of seconds on most (POSIX)
    systems, and presumably blocks update faster than that, you'll get
    sucky non-random numbers.

    >different numbers in one spur can work, but people can play Tetris for
    >hours (or even days), and so you can't predict how long. You could
    >constantly be making more with the same system as making, say 5 random
    >numbers out of a seed, but that would prove system intensive if the
    >game already uses a lot of memory (not that Tetris does, but I'm sure
    >there's a better way).


    Seed once. Period. If calling rand() or random() alone slows down
    the display too much, perhaps you need a faster CPU. But I doubt it.
    All the graphics probably takes a lot more work than just generating
    a pseudo-random number.

    Gordon L. Burditt
    Gordon Burditt, Dec 6, 2005
    #4
  5. "Alvin" <> wrote in message
    news:...
    > Well, I'm developing a Tetris game in SDL, but when it comes to
    > deciding the next block, I'm stuck. It's random, but when I try
    > something like seeding the randomizer with the time, it won't update as
    > fast as one block can fall, and the next to be determined. Generating
    > different numbers in one spur can work, but people can play Tetris for
    > hours (or even days), and so you can't predict how long. You could
    > constantly be making more with the same system as making, say 5 random
    > numbers out of a seed, but that would prove system intensive if the
    > game already uses a lot of memory (not that Tetris does, but I'm sure
    > there's a better way).
    >


    The ideal solution (which, however, requires an internet connection) is to
    connect to www.random.org and download some random bytes...

    They are truly random, since they come from *sampling backgound noise in the
    atmosphere* (how cool is that?!).

    This would also be a cool selling argument!

    </funmaking>
    <serious>
    Check Randy Howard's answer :eek:)

    -Mogens
    Mogens Heller Jensen, Dec 6, 2005
    #5
  6. Alvin

    Alvin Guest

    Well, it works like a charm for large numbers, but for small numbers
    (say, 0 to 7), it often repeats them 3 or so times before changing. I
    guess I could determine on how big the number is, so if it's > 100 and
    < 200, select an right sided L block or something. Thanks very much,
    though.
    Alvin, Dec 6, 2005
    #6
  7. Alvin

    Randy Howard Guest

    Gordon Burditt wrote
    (in article <>):

    > If, as your subject line suggests, you want truly random numbers,
    > forget a PRNG like rand() or random(). The PR part stands for
    > PSEUDO-RANDOM. Computers aren't very good at generating truly
    > random numbers unless they are broken or they have specific hardware
    > for the purpose. Some attempts at truly random number generation
    > time keystrokes, or listen to thermal noise or radioactive decay,
    > or time events from outside the computer (like network traffic).
    >
    > If you need truly random numbers for cryptography, a PRNG won't
    > do. The difference can get you killed.


    He said he's writing a Tetris game. I find it highly unlikely
    he needs crypto random numbers for that.

    --
    Randy Howard (2reply remove FOOBAR)
    "The power of accurate observation is called cynicism by those
    who have not got it." - George Bernard Shaw
    Randy Howard, Dec 6, 2005
    #7
  8. Alvin

    Randy Howard Guest

    Alvin wrote
    (in article
    <>):

    > Well, it works like a charm for large numbers, but for small numbers
    > (say, 0 to 7), it often repeats them 3 or so times before changing.


    Random does not mean "no repeats", especially in such a narrow
    range. People often think that the output from a random number
    generator should be evenly disributed. Bzzt.

    If you are still reseeding it over and over, that will skew your
    results. Fix that first.

    If you think the random implementation on your platform is
    flawed (after seeding it properly), then check out the Mersenne
    Twister PRNG. It's probably overkill for a video game, but it
    might make you feel better anyway.



    --
    Randy Howard (2reply remove FOOBAR)
    "The power of accurate observation is called cynicism by those
    who have not got it." - George Bernard Shaw
    Randy Howard, Dec 6, 2005
    #8
  9. >> If, as your subject line suggests, you want truly random numbers,
    >> forget a PRNG like rand() or random(). The PR part stands for
    >> PSEUDO-RANDOM. Computers aren't very good at generating truly
    >> random numbers unless they are broken or they have specific hardware
    >> for the purpose. Some attempts at truly random number generation
    >> time keystrokes, or listen to thermal noise or radioactive decay,
    >> or time events from outside the computer (like network traffic).
    >>
    >> If you need truly random numbers for cryptography, a PRNG won't
    >> do. The difference can get you killed.

    >
    >He said he's writing a Tetris game. I find it highly unlikely
    >he needs crypto random numbers for that.


    True, but he asked for truly random numbers. Perhaps he's betting
    large amounts on the outcome (anyone for Tetris machines next to
    the video poker machines and the slots?), enough to make organized
    efforts to cheat worth the time and trouble. If you're building
    gambling machines which will take bets of real money, you *DO* need
    crypto-quality random numbers or you're going to go broke.

    Gordon L. Burditt
    Gordon Burditt, Dec 6, 2005
    #9
  10. Alvin

    Randy Howard Guest

    Gordon Burditt wrote
    (in article <>):

    >> He said he's writing a Tetris game. I find it highly unlikely
    >> he needs crypto random numbers for that.

    >
    > True, but he asked for truly random numbers. Perhaps he's betting


    I'd rather bet on the outcome of the Rose Bowl...

    > large amounts on the outcome (anyone for Tetris machines next to
    > the video poker machines and the slots?), enough to make organized
    > efforts to cheat worth the time and trouble.


    Ok, but I don't see a market for "Tetris Gambling". Maybe there
    is, prove me wrong. :)


    --
    Randy Howard (2reply remove FOOBAR)
    "The power of accurate observation is called cynicism by those
    who have not got it." - George Bernard Shaw
    Randy Howard, Dec 6, 2005
    #10
  11. In article <>,
    Gordon Burditt <> wrote:
    >True, but he asked for truly random numbers. Perhaps he's betting
    >large amounts on the outcome (anyone for Tetris machines next to
    >the video poker machines and the slots?), enough to make organized
    >efforts to cheat worth the time and trouble. If you're building
    >gambling machines which will take bets of real money, you *DO* need
    >crypto-quality random numbers or you're going to go broke.


    [OT]

    My recollection is somewhat vague, as I just skimmed the material
    some time ago, but if I recall what I have read correctly, the
    professional casinos in places like Los Vegas do -not- use
    crypto-quality random numbers, at least for some kinds of machines
    such as slot machines. I seem to recall reading that they use a PRNG
    but with algorithm parameters modified by a central computer.

    The PNRG use has partly to do with managable auditing -- recording each
    individual truly random number would take too much storage. The
    ability to modify the parameters is used to adjust the payout rate
    based upon the payin rate -- essentially once the intake has reached a
    trigger value, the central computer adjusts the payout probabilities
    upwards to make it more likely that someone will win a large prize. For
    one thing, a slot machine that shows exactly the same losing line of
    symbol 100 times in a row might be truly random, but it won't be
    -perceived- to be random...

    PNRG are losing propositions in gambling to the extent that someone
    can effectively analyze the past history to predict the future outcomes.
    A simple linear congruence PNRG is very risky in that respect, but
    there are PRNG with large internal states, and if those states are
    reseeded at intervals shorter than would be needed to extract useful
    state information, then PRNG can become practical.
    --
    "It is important to remember that when it comes to law, computers
    never make copies, only human beings make copies. Computers are given
    commands, not permission. Only people can be given permission."
    -- Brad Templeton
    Walter Roberson, Dec 6, 2005
    #11
  12. In article <>,
    Alvin <> wrote:
    >Well, it works like a charm for large numbers, but for small numbers
    >(say, 0 to 7), it often repeats them 3 or so times before changing. I
    >guess I could determine on how big the number is, so if it's > 100 and
    >< 200, select an right sided L block or something. Thanks very much,
    >though.


    (Obviously, what follows is off-topic, not portable, and blah, blah, blah,
    but anyway...)

    Long ago and far away, using a compiler/development environment that need
    not be mentioned here, I discovered that the higher order bits seemed to
    be more random than the lower ordered ones. So, that the usual method (get
    the number between, say, 0 and 32767, then divide it by the top of your
    range, to get a random number between 0 and your range) tended to give less
    good random results. So, I would take the result of random and bit shift
    it left 5 (<< 5) to get the lower ordered bits more random. Seems to work.
    Kenny McCormack, Dec 6, 2005
    #12
  13. Alvin

    Guest

    Kenny McCormack wrote:
    > In article <>,
    > Alvin <> wrote:
    > >Well, it works like a charm for large numbers, but for small numbers
    > >(say, 0 to 7), it often repeats them 3 or so times before changing. I
    > >guess I could determine on how big the number is, so if it's > 100 and
    > >< 200, select an right sided L block or something. Thanks very much,
    > >though.

    >
    > (Obviously, what follows is off-topic, not portable, and blah, blah, blah,
    > but anyway...)
    >
    > Long ago and far away, using a compiler/development environment that need
    > not be mentioned here, I discovered that the higher order bits seemed to
    > be more random than the lower ordered ones. So, that the usual method (get
    > the number between, say, 0 and 32767, then divide it by the top of your
    > range, to get a random number between 0 and your range) tended to give less
    > good random results. So, I would take the result of random and bit shift
    > it left 5 (<< 5) to get the lower ordered bits more random. Seems to work.


    Gee, I got a new asshole reamed for suggesting that very thing
    a couple months ago despite it being in the FAQ.

    Better sit on your helmet.
    , Dec 6, 2005
    #13
  14. Alvin

    Michael Mair Guest

    Kenny McCormack wrote:
    > In article <>,
    > Alvin <> wrote:
    >
    >>Well, it works like a charm for large numbers, but for small numbers
    >>(say, 0 to 7), it often repeats them 3 or so times before changing. I
    >>guess I could determine on how big the number is, so if it's > 100 and
    >>< 200, select an right sided L block or something. Thanks very much,
    >>though.

    >
    >
    > (Obviously, what follows is off-topic, not portable, and blah, blah, blah,
    > but anyway...)
    >
    > Long ago and far away, using a compiler/development environment that need
    > not be mentioned here, I discovered that the higher order bits seemed to
    > be more random than the lower ordered ones. So, that the usual method (get
    > the number between, say, 0 and 32767, then divide it by the top of your


    You probably are talking about talking the remainder modulo the top
    of the range. "Divide" was the other thingy, the one which worked
    better than plain modulo.

    > range, to get a random number between 0 and your range) tended to give less
    > good random results. So, I would take the result of random and bit shift
    > it left 5 (<< 5) to get the lower ordered bits more random. Seems to work.


    You probably mean the other left. The one most people call "right".
    rand() << 5 certainly will give you five quite unrandom lower bits.

    -Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, Dec 6, 2005
    #14
  15. Alvin

    Jordan Abel Guest

    On 2005-12-06, Kenny McCormack <> wrote:
    > In article <>,
    > Alvin <> wrote:
    >>Well, it works like a charm for large numbers, but for small numbers
    >>(say, 0 to 7), it often repeats them 3 or so times before changing. I
    >>guess I could determine on how big the number is, so if it's > 100 and
    >>< 200, select an right sided L block or something. Thanks very much,
    >>though.

    >
    > (Obviously, what follows is off-topic, not portable, and blah, blah, blah,
    > but anyway...)
    >
    > Long ago and far away, using a compiler/development environment that
    > need not be mentioned here, I discovered that the higher order bits
    > seemed to be more random than the lower ordered ones. So, that the
    > usual method (get the number between, say, 0 and 32767, then divide it
    > by the top of your range, to get a random number between 0 and your
    > range) tended to give less good random results. So, I would take the
    > result of random and bit shift it left 5 (<< 5) to get the lower
    > ordered bits more random. Seems to work.


    I assume you mean to the right.

    And it is marginally on-topic, because the code of a PRNG with IIRC
    characteristics like those you describe appears in the text of the C
    standard.
    Jordan Abel, Dec 6, 2005
    #15
  16. Alvin

    Simon Biber Guest

    Walter Roberson wrote:
    > PNRG are losing propositions in gambling to the extent that someone
    > can effectively analyze the past history to predict the future outcomes.
    > A simple linear congruence PNRG is very risky in that respect, but
    > there are PRNG with large internal states, and if those states are
    > reseeded at intervals shorter than would be needed to extract useful
    > state information, then PRNG can become practical.


    Given a PRNG of the form

    #include <stdint.h>

    uint32_t foo(void)
    {
    static uint32_t s = /* unknown */;
    const uint32_t n = /* unknown */;
    const uint32_t m = /* unknown */;

    s = s * n + m;
    return s;
    }

    How many calls would it take to guess what the values of s, n and m were?

    --
    Simon.
    Simon Biber, Dec 6, 2005
    #16
  17. Simon Biber said:

    > Given a PRNG of the form
    >
    > #include <stdint.h>
    >
    > uint32_t foo(void)
    > {
    > static uint32_t s = /* unknown */;
    > const uint32_t n = /* unknown */;
    > const uint32_t m = /* unknown */;
    >
    > s = s * n + m;
    > return s;
    > }
    >
    > How many calls would it take to guess what the values of s, n and m were?


    None.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
    Richard Heathfield, Dec 7, 2005
    #17
  18. In article <43962341$0$18203$>,
    Simon Biber <> wrote:
    >Given a PRNG of the form


    >#include <stdint.h>


    >uint32_t foo(void)
    >{
    > static uint32_t s = /* unknown */;
    > const uint32_t n = /* unknown */;
    > const uint32_t m = /* unknown */;
    >
    > s = s * n + m;
    > return s;
    >}


    >How many calls would it take to guess what the values of s, n and m were?


    As few as 3.

    If you have 3 consequative values (x,y,z) that do not involve integer
    overflow, then

    s = (x*(y+z)-(x^2+y^2))/(z-y)
    n = (z-y)/(y-x)
    m = (y^2-x*z)/(y-x)

    --
    I was very young in those days, but I was also rather dim.
    -- Christopher Priest
    Walter Roberson, Dec 7, 2005
    #18
  19. Alvin

    Simon Biber Guest

    Walter Roberson wrote:
    > In article <43962341$0$18203$>,
    > Simon Biber <> wrote:
    >
    >>Given a PRNG of the form

    >
    >
    >>#include <stdint.h>

    >
    >
    >>uint32_t foo(void)
    >>{
    >> static uint32_t s = /* unknown */;
    >> const uint32_t n = /* unknown */;
    >> const uint32_t m = /* unknown */;
    >>
    >> s = s * n + m;
    >> return s;
    >>}

    >
    >
    >>How many calls would it take to guess what the values of s, n and m were?

    >
    >
    > As few as 3.
    >
    > If you have 3 consequative values (x,y,z) that do not involve integer
    > overflow, then


    However, as is always the case for PRNGs, n can easily be chosen large
    enough that there will always be integer overflow within three
    consecutive values. It wouldn't produce anything resembling random
    output if there wasn't integer overflow.

    > s = (x*(y+z)-(x^2+y^2))/(z-y)
    > n = (z-y)/(y-x)
    > m = (y^2-x*z)/(y-x)


    Thanks for the formulas; they can be got by just typing

    Solve[{x == s * n + m, y == x * n + m, z == y * n + m}, {s, n, m}]

    into Mathematica. Unfortunately it doesn't work so well with

    Solve[{x == Mod[s * n + m, 2^32],
    y == Mod[x * n + m, 2^32],
    z == Mod[y * n + m, 2^32]}, {s, n, m}]

    --
    Simon.
    Simon Biber, Dec 7, 2005
    #19
  20. Alvin

    Thad Smith Guest

    Simon Biber wrote:

    > Given a PRNG of the form
    >
    > #include <stdint.h>
    >
    > uint32_t foo(void)
    > {
    > static uint32_t s = /* unknown */;
    > const uint32_t n = /* unknown */;
    > const uint32_t m = /* unknown */;
    >
    > s = s * n + m;
    > return s;
    > }
    >
    > How many calls would it take to guess what the values of s, n and m were?


    Three calls plus a few seconds of compute time via brute force. There
    may be a faster way.

    Of course, if I can only see something like s/100000000, rather than s,
    it will take many more samples.

    --
    Thad
    Thad Smith, Dec 7, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Kettenbach

    Truly Sign out a user

    Chris Kettenbach, Oct 14, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    379
    Ken Cox [Microsoft MVP]
    Oct 15, 2005
  2. Harald Hein
    Replies:
    9
    Views:
    420
    Andrew Thompson
    Aug 17, 2003
  3. Ian Pilcher

    A truly uninstantiable class?

    Ian Pilcher, Oct 13, 2005, in forum: Java
    Replies:
    19
    Views:
    1,769
    Ross Bamford
    Oct 16, 2005
  4. globalrev
    Replies:
    4
    Views:
    753
    Gabriel Genellina
    Apr 20, 2008
  5. VK
    Replies:
    15
    Views:
    1,154
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page