Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Portable random number generator

Reply
Thread Tools

Portable random number generator

 
 
lawrence.jones@siemens.com
Guest
Posts: n/a
 
      11-18-2010
In comp.lang.c.moderated James Kanze <(E-Mail Removed)> wrote:
>
> If you have 64 bit arithmetic, something like:
>
> int32_t seed;
>
> int random()
> {
> seed = (48271LL * seed) % 2147483647LL;
> return seed;
> }
>
> works reasonably well (but as you say, better algorithms exist).


If your definition of "reasonably well" includes always returning 0.
--
Larry Jones

I think we need to change the rules. -- Calvin
--
comp.lang.c.moderated - moderation address: http://www.velocityreviews.com/forums/(E-Mail Removed) -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
 
Reply With Quote
 
 
 
 
lawrence.jones@siemens.com
Guest
Posts: n/a
 
      11-18-2010
In comp.lang.c.moderated James Kanze <(E-Mail Removed)> wrote:
>
> I'm sorry, but it fails just about every known test. To begin
> with, the results alternate between even and odd.


No it doesn't. The code again from the C standard is:

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}

Note the "/65536" in the return line that yields the high-order 15 bits
of the result, not the low-order. You're thinking of the brain-damaged
variant that originated at Berkeley (and apparently lives on in glibc)
that increases the range to 31 bits by eliminating the division and
increasing the modulus. That *does* fail just about every known test
and is infamously bad. Please don't tar the version in the Standard
with the same brush.
--
Larry Jones

Monopoly is more fun when you make your own Chance cards. -- Calvin
--
comp.lang.c.moderated - moderation address: (E-Mail Removed) -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
 
Reply With Quote
 
 
 
 
William Hughes
Guest
Posts: n/a
 
      11-18-2010
On Nov 17, 3:38*pm, James Kanze <(E-Mail Removed)> wrote:
> On Nov 16, 2:25 am, (E-Mail Removed) wrote:
>
> > In comp.lang.c.moderated James Kanze <(E-Mail Removed)> wrote:
> > > The "example" random generator in the C standard is particularly
> > > bad.

> > [...]
> > > And in fact, as it is (now) known to be a very poor generator,
> > > none of the implementations I know use it.

> > No, it's not. *It's a perfectly good 15-bit linear congruential
> > generator. *Certainly there are other forms of generators that are
> > "better" by some measures, but as LCGs go, it's a decent one. *A number
> > of implementations use it verbatim.

>
> I'm sorry, but it fails just about every known test. *To begin
> with, the results alternate between even and odd.


No they don't.


- William Hughes
--
comp.lang.c.moderated - moderation address: (E-Mail Removed) -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      11-18-2010
On Nov 17, 7:37 pm, Malcolm McLean <(E-Mail Removed)>
wrote:
> On Nov 15, 6:56 pm, James Kanze <(E-Mail Removed)> wrote:


> > On Nov 12, 11:05 pm, Malcolm McLean <(E-Mail Removed)>
> > wrote:


> > > On Nov 10, 6:12 am, Gus Gassmann <(E-Mail Removed)>
> > > wrote:
> > > > So now I am looking
> > > > for a random number generator with the following properties:
> > > > 1. Portability.
> > > > 2. Random starting points.
> > > > 3. Replicability on demand.
> > > Just use the K and R function
> > > static unsigned long random_seed = 123456;
> > > void simplesrand(unsigned long seed)
> > > {
> > > random_seed = seed;
> > > }
> > > int simplerand()
> > > {
> > > random_seed = random_seed * 1103515245 +12345;
> > > return (unsigned int)(random_seed / 65536) % 32768;
> > > }


> > Have you actually tried this one? And done any statistical
> > analysis on the results?


> Here are 100 results, created by taking modulus 100 to generate 2
> digit integers


[...]

> as you can see,


No, I can't see. Pseudo-)randomness isn't superficially
visible. What results do you get from a Chi-Square test, for
example?

> they are perfectly OK for many uses, eg random walks for space
> invaders, or generating random queries to test a database
> function.


They are perfectly OK is you don't care about randomness.

--
James Kanze
--
comp.lang.c.moderated - moderation address: (E-Mail Removed) -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
 
Reply With Quote
 
Nobody
Guest
Posts: n/a
 
      11-19-2010
On Wed, 17 Nov 2010 13:38:07 -0600, James Kanze wrote:

>> (Although, admittedly, not all LCG's are equally poor. Some
>> are way poorer than others, if the literals are chosen
>> inappropriately. However, even the best LCG's are rather poor
>> compared to more robust RNG's.)

>
> In fact, the one above is one of the worst ones.


AFAIK, it's about as good as you can get from a 32-bit LCG.

The coefficients produce a maximally periodic sequence. However, you need
to trade off the number of bits returned against the periodicity of those
bits. The lower bits all have short periods, so should really be discarded.

Using 64 bits is an improvement, but if portability is desired, you can't
assume the existence of a 64-bit integer type, so you either live with 32
bits or implement multi-word arithmetic.

FWIW, I normally use RC4 if I want something better than an LCG and I have
to implement it myself.

 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      11-23-2010
(E-Mail Removed) writes:
> In comp.lang.c.moderated James Kanze <(E-Mail Removed)> wrote:
>>
>> I'm sorry, but it fails just about every known test. To begin
>> with, the results alternate between even and odd.

>
> No it doesn't. The code again from the C standard is:
>
> static unsigned long int next = 1;
>
> int rand(void) // RAND_MAX assumed to be 32767
> {
> next = next * 1103515245 + 12345;
> return (unsigned int)(next/65536) % 32768;
> }
>
> Note the "/65536" in the return line that yields the high-order 15 bits
> of the result, not the low-order. You're thinking of the brain-damaged
> variant that originated at Berkeley (and apparently lives on in glibc)
> that increases the range to 31 bits by eliminating the division and
> increasing the modulus. That *does* fail just about every known test
> and is infamously bad. Please don't tar the version in the Standard
> with the same brush.


Yes, glibc still has a PRNG whose results alternate odd and even,
but that algorithm isn't the one that's use by default. You can
force its use by calling the non-standard initstate() function with
a sufficiently small state buffer.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
--
comp.lang.c.moderated - moderation address: (E-Mail Removed) -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      11-23-2010
On Nov 18, 10:21 pm, (E-Mail Removed) wrote:
> In comp.lang.c.moderated James Kanze <(E-Mail Removed)> wrote:


> > If you have 64 bit arithmetic, something like:


> > int32_t seed;


> > int random()
> > {
> > seed = (48271LL * seed) % 2147483647LL;
> > return seed;
> > }


> > works reasonably well (but as you say, better algorithms exist).


> If your definition of "reasonably well" includes always returning 0.


OK. Works reasonable well if seeded. (And you should probably
subtract 1 from the returned value.) I did say "something like"
(since I didn't have the exact code at hand, just the critical
constants).

--
James Kanze
--
comp.lang.c.moderated - moderation address: (E-Mail Removed) -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      11-23-2010
On Nov 19, 12:22*am, James Kanze <(E-Mail Removed)> wrote:
>
> > as you can see,

>
> No, I can't see. *Pseudo-)randomness isn't superficially
> visible. *What results do you get from a Chi-Square test, for
> example?
>
> > they are perfectly OK for many uses, eg random walks for space
> > invaders, or generating random queries to test a database
> > function.

>
> They are perfectly OK is you don't care about randomness.
>

Which is generally the case. Only rarely do you need to pass
sophisticated or even not-so sophisticated statistical tests for
randomness. As long as no integers are avoided and the results look
random to a superficial glance, it's probably good enough.
--
comp.lang.c.moderated - moderation address: (E-Mail Removed) -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
 
Reply With Quote
 
Nobody
Guest
Posts: n/a
 
      11-23-2010
On Tue, 23 Nov 2010 15:50:19 -0600, Keith Thompson wrote:

>> Note the "/65536" in the return line that yields the high-order 15 bits
>> of the result, not the low-order. You're thinking of the brain-damaged
>> variant that originated at Berkeley (and apparently lives on in glibc)
>> that increases the range to 31 bits by eliminating the division and
>> increasing the modulus. That *does* fail just about every known test
>> and is infamously bad. Please don't tar the version in the Standard
>> with the same brush.

>
> Yes, glibc still has a PRNG whose results alternate odd and even, but that
> algorithm isn't the one that's use by default. You can force its use by
> calling the non-standard initstate() function with a sufficiently small
> state buffer.


Note that the only real advantage of discarding the bottom bits is to
prevent naive users from shooting themselves in the foot. If you return
the entire 32-bit state, the user can discard bits as appropriate (i.e.
they can choose to retain some of the shorter-period lower bits in order
to obtain a longer overall period).

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Portable random number generator Gus Gassmann C++ 43 11-23-2010 09:51 PM
Portable random number generator Gus Gassmann C Programming 2 11-17-2010 07:36 PM
Portable random number generator Gus Gassmann C++ 2 11-17-2010 07:36 PM
Math.random() and Math.round(Math.random()) and Math.floor(Math.random()*2) VK Javascript 15 05-02-2010 03:43 PM
random.random(), random not defined!? globalrev Python 4 04-20-2008 08:12 AM



Advertisments