simple PRNG?

Discussion in 'C Programming' started by copx, Mar 21, 2008.

  1. copx

    copx Guest

    Can anyone point me to a simple, fast RRNG function to generate random ints
    within a specified range? It is important that each value within the range
    has the same probability (uniform distribution).
    I do not want to use the unreliable rand() function, but I do not want to
    bloat my code with something as complex as MT either. I am just looking for
    a short code snippet that I can copy without worrying about licensing.
    The function should work on limited platforms (no floating-point math
    please, one that works even on platforms where int is only 16 bit would be
    perfect).
    I did search this group and the web but I could not find anything which
    meets the requirements.
     
    copx, Mar 21, 2008
    #1
    1. Advertising

  2. copx

    Morris Dovey Guest

    copx wrote:
    >
    > Can anyone point me to a simple, fast RRNG function to generate random ints
    > within a specified range? It is important that each value within the range
    > has the same probability (uniform distribution).
    > I do not want to use the unreliable rand() function, but I do not want to
    > bloat my code with something as complex as MT either. I am just looking for
    > a short code snippet that I can copy without worrying about licensing.
    > The function should work on limited platforms (no floating-point math
    > please, one that works even on platforms where int is only 16 bit would be
    > perfect).
    > I did search this group and the web but I could not find anything which
    > meets the requirements.


    How simple, how fast, and how short do you require?

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto/
     
    Morris Dovey, Mar 21, 2008
    #2
    1. Advertising

  3. copx

    copx Guest

    "Morris Dovey" <> schrieb im Newsbeitrag
    news:...
    > copx wrote:
    >>
    >> Can anyone point me to a simple, fast RRNG function to generate random
    >> ints
    >> within a specified range? It is important that each value within the
    >> range
    >> has the same probability (uniform distribution).
    >> I do not want to use the unreliable rand() function, but I do not want to
    >> bloat my code with something as complex as MT either. I am just looking
    >> for
    >> a short code snippet that I can copy without worrying about licensing.
    >> The function should work on limited platforms (no floating-point math
    >> please, one that works even on platforms where int is only 16 bit would
    >> be
    >> perfect).
    >> I did search this group and the web but I could not find anything which
    >> meets the requirements.

    >
    > How simple, how fast, and how short do you require?


    Not more than a page of code would be nice (with "simple" I meant little
    code, not necessary easy to understand code). Fast means that the algorithm
    should be able to generate hundreds of random numbers per second on a 80386
    level machine at least. Of course, 10,000 numbers per second on a 8086 are
    even better! ;)
     
    copx, Mar 21, 2008
    #3
  4. copx said:

    >
    > "Morris Dovey" <> schrieb im Newsbeitrag
    > news:...
    >> copx wrote:
    >>>
    >>> Can anyone point me to a simple, fast RRNG function to generate random
    >>> ints
    >>> within a specified range? It is important that each value within the
    >>> range
    >>> has the same probability (uniform distribution).
    >>> I do not want to use the unreliable rand() function, but I do not want
    >>> to bloat my code with something as complex as MT either. I am just
    >>> looking for
    >>> a short code snippet that I can copy without worrying about licensing.
    >>> The function should work on limited platforms (no floating-point math
    >>> please, one that works even on platforms where int is only 16 bit would
    >>> be
    >>> perfect).
    >>> I did search this group and the web but I could not find anything which
    >>> meets the requirements.

    >>
    >> How simple, how fast, and how short do you require?

    >
    > Not more than a page of code would be nice (with "simple" I meant little
    > code, not necessary easy to understand code). Fast means that the
    > algorithm should be able to generate hundreds of random numbers per
    > second on a 80386 level machine at least. Of course, 10,000 numbers per
    > second on a 8086 are even better! ;)


    /* PRNG requirements:
    * simple
    * fast
    * uniform distribution within specified range
    * mustn't call rand()
    * no licensing issues
    * works on limited platforms (no floating-point)
    * works on platforms with 16-bit ints
    * no more than one page of code
    */

    /* prng() - returns a random number in the specified range 0 to 0 */
    int prng(void)
    {
    return 0;
    }

    Requirements specifications can be a bitch to write, can't they? But
    seriously, this is the kind of thing you either do yourself, or pay
    someone to do for you. Yes, someone here might know of a free solution
    that meets all your requirements, but you'd be silly to count on it.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Mar 21, 2008
    #4
  5. copx

    copx Guest

    "Richard Heathfield" <> schrieb im Newsbeitrag
    news:...
    [snip]
    > /* PRNG requirements:
    > * simple
    > * fast
    > * uniform distribution within specified range
    > * mustn't call rand()
    > * no licensing issues
    > * works on limited platforms (no floating-point)
    > * works on platforms with 16-bit ints
    > * no more than one page of code
    > */
    >
    > /* prng() - returns a random number in the specified range 0 to 0 */
    > int prng(void)
    > {
    > return 0;
    > }
    >
    > Requirements specifications can be a bitch to write, can't they?


    Muhuhuha, you are so funny!
    Constructive contributions have become too boring, eh?

    > But seriously, this is the kind of thing you either do yourself, or pay
    > someone to do for you.


    Paying someone for about 20 lines of code?

    > Yes, someone here might know of a free solution
    > that meets all your requirements, but you'd be silly to count on it.


    There are many free PRNGs available on the web, including high quality ones
    who live up to all kinds of requirements (like MT), so I think it is
    perfectly reasonable to assume that one of them might meet my requirements.
    I did not expect that someone would write such a thing from scratch for me,
    just that someone might knew where to find it.

    copx
     
    copx, Mar 21, 2008
    #5
  6. copx

    Morris Dovey Guest

    copx wrote:
    >
    > "Morris Dovey" <> schrieb im Newsbeitrag
    > news:...
    > > copx wrote:


    > >> a short code snippet that I can copy without worrying about licensing.
    > >> The function should work on limited platforms (no floating-point math
    > >> please, one that works even on platforms where int is only 16 bit would
    > >> be perfect).
    > >> I did search this group and the web but I could not find anything which
    > >> meets the requirements.

    > >
    > > How simple, how fast, and how short do you require?

    >
    > Not more than a page of code would be nice (with "simple" I meant little
    > code, not necessary easy to understand code). Fast means that the algorithm
    > should be able to generate hundreds of random numbers per second on a 80386
    > level machine at least. Of course, 10,000 numbers per second on a 8086 are
    > even better! ;)


    Ok. Priorities are 16-bit, small, fast, uniform distribution,
    free, and random (in that order):

    unsigned simple_fast_uniform_free_16(void)
    { static unsigned x;
    return x = 0x0FFFFu & ++x;
    }

    is restricted to 16-bit integer values, meets speed requirement
    for 8086, and distribution is perfectly uniform. It's free and
    there is no licensing to worry about.

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto/
     
    Morris Dovey, Mar 21, 2008
    #6
  7. copx said:

    >
    > "Richard Heathfield" <> schrieb im Newsbeitrag
    > news:...


    <snip>

    >> But seriously, this is the kind of thing you either do yourself, or pay
    >> someone to do for you.

    >
    > Paying someone for about 20 lines of code?


    How do you know it's only 20 lines of code? And what makes you think that
    short==simple? Just because an algorithm doesn't take much code to
    express, that doesn't mean it is trivial to think it up and implement it
    correctly. E=mc^2 is simple enough to express, but it took quite a lot of
    mathematics to establish that it was correct.

    <snip>

    > I did not expect that someone would write such a thing from
    > scratch for me, just that someone might knew where to find it.


    Fair enough - but you might get better results by asking in an algorithms
    group.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Mar 21, 2008
    #7
  8. copx

    jacob navia Guest

    copx wrote:
    > "Richard Heathfield" <> schrieb im Newsbeitrag


    [snip nonsense answer]

    >
    > Muhuhuha, you are so funny!
    > Constructive contributions have become too boring, eh?
    >


    The prefered sport of "regulars" here is to laugh at
    people. Do not bother. Not everybody is like that.


    >> But seriously, this is the kind of thing you either do yourself, or pay
    >> someone to do for you.

    >
    > Paying someone for about 20 lines of code?
    >
    >> Yes, someone here might know of a free solution
    >> that meets all your requirements, but you'd be silly to count on it.

    >
    > There are many free PRNGs available on the web, including high quality ones
    > who live up to all kinds of requirements (like MT), so I think it is
    > perfectly reasonable to assume that one of them might meet my requirements.
    > I did not expect that someone would write such a thing from scratch for me,
    > just that someone might knew where to find it.
    >
    > copx
    >
    >


    The lcc-win compiler system uses this:
    /*
    * Pseudo-random number generator. The result is uniform on
    * [0, 2^31 - 1].
    */
    static unsigned long _randseed = 1;

    unsigned long EXPORT random(void)
    {
    register long x, hi, lo, t;

    /*
    * Compute x[n + 1] = (7^5 * x[n]) mod (2^31 - 1).
    * From "Random number generators: good ones are hard to find",
    * Park and Miller, Communications of the ACM, vol. 31, no. 10,
    * October 1988, p. 1195.
    */
    x = _randseed;
    hi = x / 127773;
    lo = x % 127773;
    t = 16807 * lo - 2836 * hi;
    if (t <= 0)
    t += 0x7fffffff;
    _randseed = t;
    return (t);
    }

    void EXPORT srandom(unsigned long seed)
    {
    _randseed=seed;
    }

    This needs 32 bit maths as you see. I think it could be ported to 16
    bits by making the result mod 2^16 -1

    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Mar 21, 2008
    #8
  9. In article <fs00ia$nrl$>, jacob navia <> wrote:

    >The lcc-win compiler system uses this:


    > /*
    > * Compute x[n + 1] = (7^5 * x[n]) mod (2^31 - 1).
    > * From "Random number generators: good ones are hard to find",
    > * Park and Miller, Communications of the ACM, vol. 31, no. 10,
    > * October 1988, p. 1195.
    > */


    The original poster requested,

    >>I am just looking for
    >>a short code snippet that I can copy without worrying about licensing.


    The lcc-win32 page says,
    http://www.cs.virginia.edu/~lcc-win32/

    License:

    This software is not freeware, it is copyrighted by Jacob Navia. It's
    free for non-commercial use, if you use it professionally you have to
    have to buy a licence.


    By posting that routine in response to the original poster's question,
    are you releasing that routine from your license? If not, then
    it does not meet the original poster's requirements.

    It is presently March 2008, which is less than 20 years since
    the October 1988 publication date of the cited article. Do you
    certify that there is no patent upon the algorithm, and are you
    prepared to indemnify the original poster if it turns out that
    there is a remaining patent upon it?
    --
    "The study of error is not only in the highest degree
    prophylatic, but it serves as a stimulating introduction to the
    study of truth." -- Walter Lipmann
     
    Walter Roberson, Mar 21, 2008
    #9
  10. jacob navia said:

    <snip>

    > The lcc-win compiler system uses this:


    Let us not forget that the lcc-win compiler system does not conform to
    ISO/IEC 9899:1999, which you have said this very morning is "standard C".
    So you're advocating a non-conforming compiler system.

    <snip>

    > This needs 32 bit maths as you see. I think it could be ported to 16
    > bits by making the result mod 2^16 -1


    Yes, it can. Unfortunately, this gives the result 32767 on every call. Time
    to break out your debugger, perhaps.

    Put your own house in order before complaining about other people.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Mar 21, 2008
    #10
  11. copx

    MisterE Guest


    > Not more than a page of code would be nice (with "simple" I meant little
    > code, not necessary easy to understand code). Fast means that the
    > algorithm should be able to generate hundreds of random numbers per second
    > on a 80386 level machine at least. Of course, 10,000 numbers per second on
    > a 8086 are even better! ;)


    Why one page of code? MT and ciphers like AES could easily make 10,000
    numbers per second even on 386.
     
    MisterE, Mar 21, 2008
    #11
  12. copx

    Richard Bos Guest

    "copx" <> wrote:

    > "Richard Heathfield" <> schrieb im Newsbeitrag
    > > Yes, someone here might know of a free solution
    > > that meets all your requirements, but you'd be silly to count on it.

    >
    > There are many free PRNGs available on the web, including high quality ones
    > who live up to all kinds of requirements (like MT), so I think it is
    > perfectly reasonable to assume that one of them might meet my requirements.


    And you've looked at those before you came here? If not, why not? If so,
    why, if they're so good, ask us instead?

    > I did not expect that someone would write such a thing from scratch for me,
    > just that someone might knew where to find it.


    You could probably do worse than searching this newsgroup for posts by
    George Marsaglia.

    Richard
     
    Richard Bos, Mar 21, 2008
    #12
  13. copx

    Noob Guest

    copx wrote:

    > Can anyone point me to a simple, fast RRNG function


    Did you mean PRNG?

    > to generate random ints within a specified range?
    > It is important that each value within the range
    > has the same probability (uniform distribution).
    > I do not want to use the unreliable rand() function, but I do not want to
    > bloat my code with something as complex as MT either. I am just looking for
    > a short code snippet that I can copy without worrying about licensing.
    > The function should work on limited platforms (no floating-point math
    > please, one that works even on platforms where int is only 16 bit would be
    > perfect).
    > I did search this group and the web but I could not find anything which
    > meets the requirements.


    Did you look into linear congruential generators?

    http://en.wikipedia.org/wiki/Linear_congruential_generator

    They have several drawbacks, but they are very simple to program.
     
    Noob, Mar 21, 2008
    #13
  14. copx

    jacob navia Guest

    Walter Roberson wrote:
    > In article <fs00ia$nrl$>, jacob navia <> wrote:
    >
    >> The lcc-win compiler system uses this:

    >
    >> /*
    >> * Compute x[n + 1] = (7^5 * x[n]) mod (2^31 - 1).
    >> * From "Random number generators: good ones are hard to find",
    >> * Park and Miller, Communications of the ACM, vol. 31, no. 10,
    >> * October 1988, p. 1195.
    >> */

    >
    > The original poster requested,
    >
    >>> I am just looking for
    >>> a short code snippet that I can copy without worrying about licensing.

    >
    > The lcc-win32 page says,
    > http://www.cs.virginia.edu/~lcc-win32/
    >
    > License:
    >
    > This software is not freeware, it is copyrighted by Jacob Navia. It's
    > free for non-commercial use, if you use it professionally you have to
    > have to buy a licence.
    >
    >
    > By posting that routine in response to the original poster's question,
    > are you releasing that routine from your license? If not, then
    > it does not meet the original poster's requirements.
    >
    > It is presently March 2008, which is less than 20 years since
    > the October 1988 publication date of the cited article. Do you
    > certify that there is no patent upon the algorithm, and are you
    > prepared to indemnify the original poster if it turns out that
    > there is a remaining patent upon it?


    1) I have no license for this, it is not my algorithm as stated
    in the comment. How could I license that?
    2) Your only objective is here to try to denigrate my work. Go
    ahead.
    3) You can't patent an algorithm, as far as I know. So, your
    suggestion is moot.

    It would be better for everybody if all people around that need
    to laugh at others, take advantage of people asking valid
    questions here to scorn them would just disappear.

    This is of course not going to happen, and you will go on posting
    this kind of useless posts, with the only objective of confusing
    people.




    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Mar 21, 2008
    #14
  15. copx

    jacob navia Guest

    Richard Heathfield wrote:
    > jacob navia said:
    >
    > <snip>
    >
    >> The lcc-win compiler system uses this:

    >
    > Let us not forget that the lcc-win compiler system does not conform to
    > ISO/IEC 9899:1999, which you have said this very morning is "standard C".
    > So you're advocating a non-conforming compiler system.
    >
    > <snip>
    >
    >> This needs 32 bit maths as you see. I think it could be ported to 16
    >> bits by making the result mod 2^16 -1

    >
    > Yes, it can. Unfortunately, this gives the result 32767 on every call.


    I said "ported". Not just copied



    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Mar 21, 2008
    #15
  16. copx

    Ian Collins Guest

    Richard Heathfield wrote:
    > jacob navia said:
    >
    > <snip>
    >
    >> It would be better for everybody if all people around that need
    >> to laugh at others, take advantage of people asking valid
    >> questions here to scorn them would just disappear.

    >
    > How about people who hurl insults and swear at those who disagree with
    > them?
    >

    Come on now girls, can you take it outside?

    --
    Ian Collins.
     
    Ian Collins, Mar 21, 2008
    #16
  17. jacob navia said:

    <snip>

    > It would be better for everybody if all people around that need
    > to laugh at others, take advantage of people asking valid
    > questions here to scorn them would just disappear.


    How about people who hurl insults and swear at those who disagree with
    them?

    >
    > This is of course not going to happen, and you will go on posting
    > this kind of useless posts, with the only objective of confusing
    > people.


    You think your suggestion of modifying code to return 32767 on every call
    was *useful*?

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Mar 21, 2008
    #17
  18. jacob navia said:

    > Richard Heathfield wrote:
    >> jacob navia said:
    >>

    <snip>
    >>
    >>> This needs 32 bit maths as you see. I think it could be ported to 16
    >>> bits by making the result mod 2^16 -1

    >>
    >> Yes, it can. Unfortunately, this gives the result 32767 on every call.

    >
    > I said "ported". Not just copied


    Show us.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Mar 21, 2008
    #18
  19. Ian Collins said:

    > Richard Heathfield wrote:
    >> jacob navia said:
    >>
    >> <snip>
    >>
    >>> It would be better for everybody if all people around that need
    >>> to laugh at others, take advantage of people asking valid
    >>> questions here to scorn them would just disappear.

    >>
    >> How about people who hurl insults and swear at those who disagree with
    >> them?
    >>

    > Come on now girls, can you take it outside?


    Quite so.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Mar 21, 2008
    #19
  20. In article <fs0230$1iv$>,
    Walter Roberson <-cnrc.gc.ca> wrote:

    >By posting that routine in response to the original poster's question,
    >are you releasing that routine from your license?


    Of course he is. Why else would he post it to Usenet?

    A short code fragment implementing a published algorithm is not
    copyrightable anyway.

    >It is presently March 2008, which is less than 20 years since
    >the October 1988 publication date of the cited article. Do you
    >certify that there is no patent upon the algorithm, and are you
    >prepared to indemnify the original poster if it turns out that
    >there is a remaining patent upon it?


    Of course he isn't.

    Do you have any reason to suppose that the algorithm is patented? Do
    you even think it's possible to patent such an algorithm in most of
    the world? Presumably you would never post any code at all, because
    it might be patented somewhere.

    In short, your post is mean-minded FUD, a most unworthy response
    to someone who is trying to help.

    -- Richard
    --
    :wq
     
    Richard Tobin, Mar 21, 2008
    #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. Jean-Michel Besnard

    init and set state of PRNG with VC++

    Jean-Michel Besnard, Jul 27, 2004, in forum: C++
    Replies:
    0
    Views:
    630
    Jean-Michel Besnard
    Jul 27, 2004
  2. John Schutkeker

    PRNG Algorithm for RAN()

    John Schutkeker, Jul 4, 2003, in forum: C Programming
    Replies:
    4
    Views:
    2,036
    John Schutkeker
    Jul 6, 2003
  3. Francois Grieu

    Re: C code for pure float PRNG

    Francois Grieu, Feb 5, 2004, in forum: C Programming
    Replies:
    0
    Views:
    668
    Francois Grieu
    Feb 5, 2004
  4. Good binary PRNG

    , May 15, 2006, in forum: C Programming
    Replies:
    31
    Views:
    1,016
    CBFalconer
    May 19, 2006
  5. Protoman

    PRNG writing

    Protoman, Sep 13, 2005, in forum: C++
    Replies:
    7
    Views:
    785
    Dave Rahardja
    Sep 14, 2005
Loading...

Share This Page