How do you guys limit rand() results to a range?

Discussion in 'C Programming' started by DFS, Jun 1, 2014.

  1. [...]

    Are you saying that, given two streams of "randomish" numbers,
    one from a roulette wheel and one from some quantum source, it's
    possible to tell which is which just by examining the numbers?
    Is that correct? If so, I find it surprising. Can you summarize the
    difference in a way that a non-statistician is likely to understand?
     
    Keith Thompson, Jun 5, 2014
    1. Advertisements

  2. Nor would I. Given my ad-hoc definition, deterministic systems cannot
    generate "really random" numbers, though they can generate sequences
    that meet statistical tests for randomness. The digits of pi are
    (probably) an example.
     
    Keith Thompson, Jun 5, 2014
    1. Advertisements

  3. Same thing. The concept I'm trying to describe is a mathematical
    abstraction.
    I don't know. It may be that "really random" numbers are not physically
    possible; I lack sufficient knowledge of math and/or physics to say one
    way or the other.
     
    Keith Thompson, Jun 5, 2014
  4. One inefficient approach I've heard of: Generate two numbers x and y.
    If x < y, return 0. If x > y, return 1. (If x == y, try again.)
     
    Keith Thompson, Jun 5, 2014
  5. DFS

    Martin Shobe Guest

    I've heard that there is a difference in how the events are counted. I
    don't know enough about quantum mechanics to know for certain if this is
    correct, but here's how I understand the situation.

    In the classical case, each event has its own identity. This means that
    it matters which event produced which result. For example, if you flip
    two identical, fair coins, there are four equally probable outcomes:

    HH
    HT
    TH
    TT

    In the quantum case, the events don't have an identity. This means that
    it doesn't matter which event produced the result. If the two coins
    followed the quantum rules, there would only be three equally probable
    outcomes:

    HH
    HT
    TT

    Martin Shobe
     
    Martin Shobe, Jun 5, 2014
  6. DFS

    James Kuyper Guest

    On 06/05/2014 12:07 PM, Martin Shobe wrote:
    ....
    I'm fairly certain that's not correct, as you've stated it, though it
    might be a garbled version of a true statement. Can you locate a more
    authoritative explanation of the issue you're talking about?
     
    James Kuyper, Jun 5, 2014
  7. DFS

    Martin Shobe Guest

    After some quick research, I suspect it's a garbled version of the
    difference between Bose-Einstein statistics and Maxwell-Boltzmann
    statistics.

    Martin Shobe
     
    Martin Shobe, Jun 5, 2014
  8. Hmm. Seems to me that a roulette wheel might have some bias,
    as the little bins aren't all exactly the same. It would take a
    large number of rolls to detect that, though.

    For a quantum randomness source, one would likely use a debias
    algorithm on the bits coming out. The quantum source itself might
    be nice and random, but you have to convert the randomness to
    some other form to get it out, somewhat equivalent to the ball
    falling into the bin on the routlette wheel. (One possibility
    is a polarization detector for photons, which isn't quite perfect.)

    As mentioned in:

    https://en.wikipedia.org/wiki/Hardware_random_number_generator

    that algorithm (like so many) traces back to von Neumann.

    You take the bits two at a time, if the two are the same, throw
    out (ignore) the pair. If they are 01 or 10, output a 0 or 1,
    respectively, in the outgoing bit stream.

    But you could also use a debias algorithm on the routlette wheel.
    That would probably confuse gamblers, though. Seems to me that
    the main problem is that the bit generation rate of the roulette
    wheel is pretty low.

    -- glen
     
    glen herrmannsfeldt, Jun 5, 2014
  9. Well, there are three-state cases in QM, but you would normally
    know about them. That complicates bit extraction, just as it
    would getting bits from a roulette wheel.

    But consider the coin-flip case. Say you build a coin-flip bit
    generator. A box with a coin, flip device, and which side is up
    sensor. It is running fine, but the bits aren't coming out fast
    enough, so you speed it up. At some point, it will turn out that
    the coin isn't flipping enough between bit reads, and correlation
    starts to appear.

    A similar problem appears in quantum systems if you try to
    extract bits too fast. As noted, the exact effects are different
    for bosons and fermions.

    In the case of coupled two-state systems, the states aren't the
    ones indicated, but

    HH
    TT
    (HT+TH)/sqrt(2)
    (HT-TH)/sqrt(2)

    See, for example: https://en.wikipedia.org/wiki/Kaon#Mixing

    and especially the paragraph on regeneration.

    -- glen
     
    glen herrmannsfeldt, Jun 5, 2014
  10. What I am saying is that, for sufficiently large N, you don't care.

    The question left is, how large must N be, and how do we find a
    system with that large an N?

    It isn't so hard to make really large N PRNGs, but they get slower
    as N gets larger.

    So, one hopes to find a quantum system with a really large N, but
    that is also fast at the same time.

    -- glen
     
    glen herrmannsfeldt, Jun 5, 2014
  11. I'm sure that's true.

    (It's also a different point than the one I was making, which was
    abstract rather than practical.)
     
    Keith Thompson, Jun 5, 2014
  12. DFS

    Stefan Ram Guest

    This is true, but the arxiv article I have mentioned is
    about more subtle differences. However, I cannot explain
    it better than the arxiv article itself.

    http://arxiv.org/abs/1004.1521
     
    Stefan Ram, Jun 5, 2014
  13. DFS

    Stefan Ram Guest

    Ok, I now have actually looked at it again! I see that over
    the years I had lost some memory of the contents of that
    paper and hope that I have not misrepresented its contents
    here before.

    The article describes a comparison of statistical properties
    of quantum random values with pseudo-random (non-quantum)
    values and finds that the Borel normality test was able to
    distinguish between the quantum and non-quantum (pseudo-random)
    numbers: the quantum sources were /less/ normal! It seems
    that there is not yet an explanation for this. (A sequence is
    Borel normal if every binary string appears in the sequence
    with the right probability of 2^(-n) for a string of length n.)

    Before this article, it was know that quantum randomness
    cannot be computed, but this measurement showed differences
    that were detectable by analyzing the outputs (not the sources).
     
    Stefan Ram, Jun 5, 2014
  14. "DFS" wrote in message news:lmfiti$dqm$...
    A long time ago, I had to get a range from 0...9

    So, IIRC, I did some crazy hack like:
    _________________________________________
    #include <stdlib.h>
    #include <stdint.h>
    #include <stdio.h>
    #include <assert.h>


    unsigned
    rand_generate(
    unsigned const nmax,
    unsigned const nds
    ){
    unsigned r = 0;
    unsigned i = 0;
    unsigned ds = 0;

    int denom = 1;
    unsigned const pow = 10;

    // hack, and potential infinite loop! ;^/
    // find a non-zero random number...
    while (! (r = (unsigned)rand() + nds));

    for (i = 0; i < nmax && r > 0; ++i)
    {
    unsigned n = r / denom;
    unsigned m = n / pow * pow;
    unsigned d = n - m;
    ds += d;

    printf("%u", d);

    r = r - d * denom;

    denom *= pow;
    }

    return ds;
    }


    int
    main(void)
    {
    unsigned i = 0;
    unsigned nds = 0;
    unsigned const imax = 113;

    srand(74);

    for (i = 0; i < imax; ++i)
    {
    nds = rand_generate(10, nds);
    }

    return 0;
    }
    _________________________________________


    This generates a sequence of digits where each
    digit is 0...9.

    lol!

    ;^)
     
    Chris M. Thomasson, Jun 6, 2014
  15. DFS

    DFS Guest


    ha!

    I ran it 3x. It spit out the same set of numbers each time:

    471371441210092359788123968142812184305707186212696807660766600741796518517104183152211929905651609000124162460704934537682346850821676420697715568000994776507284982399312165110415264434169198821448611078785597205543392112344186259905591693732028121484809243503997223530895166900899213546766802358427495144992159311664158081816648249141071851532971182368592456215209414841065235518915403860889415051777874643527817110139655971122121806212303727100296782579742403581121715528632759741168069545561048331423104543944511308042236669471311252886712411298032197945013916353275181493902383547742078129646926216929338771527872135181672385018062766411066939581725372671485128032729861562129681395823417953712767461161853730178163434460714815420951789082527183588465331919216517216353902160869769338762960187268107218298145639185761931872254452431701385032480574265320834696431521953928583821728091326113415108194198499266029217555515249571285364129793001620924106492346668264466121866747064164013155437021333
    7153310348111770904127537067114468902677729750735081889859901518074927458331

    471371441210092359788123968142812184305707186212696807660766600741796518517104183152211929905651609000124162460704934537682346850821676420697715568000994776507284982399312165110415264434169198821448611078785597205543392112344186259905591693732028121484809243503997223530895166900899213546766802358427495144992159311664158081816648249141071851532971182368592456215209414841065235518915403860889415051777874643527817110139655971122121806212303727100296782579742403581121715528632759741168069545561048331423104543944511308042236669471311252886712411298032197945013916353275181493902383547742078129646926216929338771527872135181672385018062766411066939581725372671485128032729861562129681395823417953712767461161853730178163434460714815420951789082527183588465331919216517216353902160869769338762960187268107218298145639185761931872254452431701385032480574265320834696431521953928583821728091326113415108194198499266029217555515249571285364129793001620924106492346668264466121866747064164013155437021333
    7153310348111770904127537067114468902677729750735081889859901518074927458331

    471371441210092359788123968142812184305707186212696807660766600741796518517104183152211929905651609000124162460704934537682346850821676420697715568000994776507284982399312165110415264434169198821448611078785597205543392112344186259905591693732028121484809243503997223530895166900899213546766802358427495144992159311664158081816648249141071851532971182368592456215209414841065235518915403860889415051777874643527817110139655971122121806212303727100296782579742403581121715528632759741168069545561048331423104543944511308042236669471311252886712411298032197945013916353275181493902383547742078129646926216929338771527872135181672385018062766411066939581725372671485128032729861562129681395823417953712767461161853730178163434460714815420951789082527183588465331919216517216353902160869769338762960187268107218298145639185761931872254452431701385032480574265320834696431521953928583821728091326113415108194198499266029217555515249571285364129793001620924106492346668264466121866747064164013155437021333
    7153310348111770904127537067114468902677729750735081889859901518074927458331
     
    DFS, Jun 6, 2014
  16. "DFS" wrote in message news:lmr04v$olu$...
    Try changing the seed for the random number generator
    to a unique number per run? The posted hack code is hard
    coded to `srand(74)'.

    ;^)
     
    Chris M. Thomasson, Jun 6, 2014
  17. DFS

    Richard Bos Guest

    Well, yeah. Consider the above line.

    Richard
     
    Richard Bos, Jun 6, 2014
  18. DFS

    DFS Guest


    duh! I seeded it with time(NULL) and got different results each time
    (unless I ran it again right away and the seed hadn't had time to change).
     
    DFS, Jun 6, 2014
  19. DFS

    James Kuyper Guest

    On 06/05/2014 06:54 PM, Stefan Ram wrote:
    ....
    If that's what they measured, then I'm far less surprised by that result
    than I was by your original statement of it. I'm so unsurprised, that
    the fact that they consider it unexplained confuses me. Possibly I'm
    missing something that makes that result less obvious than it seems to be.

    Quantum randomness is always necessarily derived ultimately from
    measurements of a quantum process. It's extremely difficult to ensure an
    exactly even distribution when measuring something, even if the thing
    you're trying to measure does, in fact, have an exactly uniform
    distribution. Even the tiniest contamination of your measurement will
    introduce some uneveness. It's far easier to ensure an absolutely even
    distribution when generating pseudo-random numbers.

    I doubt that it would be difficult to pick an arbitrary possible value
    for the Borel normality test, and design a deliberately defective
    pseudo-random number generator that would, on average, produce that value.
     
    James Kuyper, Jun 6, 2014
  20. I note all the smileys and LOLs and so on, but what is the point of
    posting this? Joke code is rarely funny to anyone but the author, and
    there's a chance (slight, I grant you) that someone might use it!
     
    Ben Bacarisse, Jun 6, 2014
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.