Re: rand() pattern in texture?

From: Carlos Moreno (moreno_at_mochima_dot_com_at_xx.xxx)
Date: 10/14/04 

Date: Thu, 14 Oct 2004 08:47:56 -0400

Phil Carmody wrote:

>>>This is an urban legend -- it's false, period! (from what I've
>>>read, I think there was, at some point in history, a buggy
>>>implementation of rand() somewhere, and that one had less
>>>uncertainty in the LSbits than in the MSbits).
>
> No, what you've read has been incorrect. There were _many_
> PRNGs which were _designed_ to be crap (usually LC ones),
> and were implemented correctly.

I meant implementation of the LC concept, as opposed to the
programming implementation of a given algorithm. The
implementation of a LC includes the choice of the multiplier
and the modulo -- and that's most likely what was "wrong".

> If you think about it, even briefly, you'll see that the low
> order n bits of any LC PRNG _must_ have period <= 2^n, if you
> think about it.

This is completely false.

Here's a linear congruential generator:

Xn = (Xn-1 * 11 + 8) mod 17

Here's the sequence it produces when seeded with 1
(actually, here's part of the sequence it produces when
seeded with anything):

1 2 13 15 3 7 0 8 11 10 16 14 9 5 12 4 1 2 13 15

> I'm sure that Carlos can work out therefore
> what the period for the lowest single bit must be.

I'm sure you're suggesting that the period of the single
lowest bit MUST be 2 or 1... Well, doesn't look like a
period of 2 to me. The single lowest bit of the above is:

1 0 1 1 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 1 ......

Looks to me like the period of the single lowest bit is 17,
as is the period of the generator itself.

But I think we have a winner!! I think we've just found the
origin of the urban lagend, which I now must concede, may not
be 100% urban legend: Your argument is true IF the modulo
is a power of 2 -- which I think is almost always the case,
for efficiency reasons.

OR, perhaps this is precisely what the "buggy implementations"
used to do, and perhaps nowadays they realized that it's better
to use a prime number as the modulo -- or perhaps they did what
you suggest below: never show the lower numbers; show only
the bits starting at bit 16 or bit 32 -- if that is the case,
then it is still true that the lower bits are "less random"
(i.e., have a shorter period), even if it is not too obvious
(a period of 2^32 instead of 2^64, or 2^16 instead of 2^48,
etc.).

But notice that this is not a property of LCG's per se; it
is a property of a particular class of implementations of
LCG -- those that use a power of 2 as the module.

> I have reason to believe, from reading various empirically-
> oriented papers, that Microsoft C, IBM fortran, Microsoft
> Visual Basic, and others also have weak generators, or at
> least did up until 2002.

I've been contesting your arguments so far, but as far as
the bottom line of the argument goes, I am with you -- I've
always thought to myself "why, oh why, do they use crappy
PRNG as the standard random number generator for most
compilers/languages?" -- whenever you use a built-in facility
of a language/compiler, you tend to think that it is a good
implementation; if you need to take a square root, your
first thought wouldn't be to code your own square root
algorithm because you have reason to believe that the
built-in one is crap -- no, you tend to assume that it
would be extremely hard to do better than the built-in one,
since that one was coded by serious people, presumably with
a lot more experience than one has. This general argument
breaks down so loudly when it comes to rand()... Why can't
they use MT, or, if they want something simple (to guarantee
efficiency in the general case), something like a feedback
shift-register, or even a substitution-permutation network?

Ok, I'll stop here... I guess it is getting close to that
time at which we should let this thread die...

Cheers,

Carlos 

--

Relevant Pages

  • Re: rand() pattern in texture?
    ... > Phil Carmody wrote: ... > programming implementation of a given algorithm. ... > Looks to me like the period of the single lowest bit is 17, ... > as is the period of the generator itself. ...
    (sci.math)
  • Re: Agduria dungeon generation
    ... stage of the algorithm and rise appropriate error, ... A NTAE generator doesn't have to have any ... NTAE will happily accept all valid inputs and RNG states and produce ...
    (rec.games.roguelike.development)
  • Re: Math.random
    ... That's not the only possible algorithm; ... without much difficulty implement a long shift-register generator; ... doublevalue or null/undefined/false for auto reseeding, ... I think 0 to 364 would be better; it goes well with zero-based arrays, ...
    (comp.lang.javascript)
  • Re: real random
    ... Feel free to post such an algorithm, ... it as a generator of a stream of numbers, ... You need a genuine source of entropy, ... By suggesting Fortuna (which gathers genuine entropy as it goes), ...
    (comp.lang.c)
  • Re: Agduria dungeon generation
    ... Depends entirely on the pseudo random number generator, ... algorithm don't suddenly change that probability. ... TAE isn't even obviously less ... algorithms but do understand their NTAE algorithms, ...
    (rec.games.roguelike.development)