«

In comp.lang.c.moderated James Kanze <> 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: -- 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.

In comp.lang.c.moderated James Kanze <> 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: -- 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.

On Nov 17, 3:38*pm, James Kanze <james.ka...@gmail.com> wrote:
> On Nov 16, 2:25 am, lawrence.jo...@siemens.com wrote:
>
> > In comp.lang.c.moderated James Kanze <james.ka...@gmail.com> 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: -- 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.

On Nov 17, 7:37 pm, Malcolm McLean <malcolm.mcle...@btinternet.com>
wrote:
> On Nov 15, 6:56 pm, James Kanze <james.ka...@gmail.com> wrote:

> > On Nov 12, 11:05 pm, Malcolm McLean <malcolm.mcle...@btinternet.com>
> > wrote:

> > > On Nov 10, 6:12 am, Gus Gassmann <horand.gassm...@googlemail.com>
> > > 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: -- 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.

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.

writes:
> In comp.lang.c.moderated James Kanze <> 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) kst- <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: -- 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.

On Nov 18, 10:21 pm, lawrence.jo...@siemens.com wrote:
> In comp.lang.c.moderated James Kanze <james.ka...@gmail.com> 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: -- 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.

On Nov 19, 12:22*am, James Kanze <james.ka...@gmail.com> 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: -- 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.

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).