Kenneth wrote:
> In other words, as frame_number progresses linearly, then seed(frame_number)
> will start showing patterns quite quickly *from frame to frame.* Again, only IF
> one rand() value is called per frame (or so it seems.)

If you have a known number of random numbers being used in each frame, you 
can seed once at frame 0, then on each subsequent frame, generate 
frame_number time known_random_number_count random numbers, and then pick up 
the stream from there. Use a while loop in SDL to generate calls to rand(), 
in other words.

There's no good reason to believe the first number you generate after 
seeding the RNG looks especially random for different seeds. It's the 
consecutive numbers from the same seed that are pseudo-random.

-- 
   Darren New, San Diego CA, USA (PST)
   There's no CD like OCD, there's no CD I knoooow!

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:

>
> If you have a known number of random numbers being used in each frame, you
> can seed once at frame 0, then on each subsequent frame, generate
> frame_number time known_random_number_count random numbers, and then pick up
> the stream from there. Use a while loop in SDL to generate calls to rand(),
> in other words.

If I understand you correctly, that's the (good!) idea that Chris B. came up
with here (which was also linked-to earlier):
http://news.povray.org/povray.general/message/%3C497a49fd%241%40news.povray.org%3E/#%3C497a49fd%241%40news.povray.org%3


>
> There's no good reason to believe the first number you generate after
> seeding the RNG looks especially random for different seeds...
>

I think that one has to be familiar with the arcania of RNGs and such to fully
understand why that may be so. (I don't count myself in that category,
unfortunately--it's all *still* over my head.) I would imagine that the typical
POV user probably believes--at least in the early stages of using the
program--that each-and-every different seed value *does* generate a nicely
psuedo-random stream (which it appears to do, of course--in a static,
non-animated scene. I think! With the possible exception of pulling only ONE
rand() value per seed--which is itself kind of idiotic: Why set up a bunch of
different seeds in a static scene if you're only using one rand() call per
seed?!) The problem of 'patterns' really only seems to show its ugly self when
one gets into animation. Yet there's nothing currently in the POV documentation
that explains any of this.  Alas, most of us have to learn about this situation
the hard way.

KW

Post a reply to this message

Kenneth wrote:
> If I understand you correctly, that's the (good!) idea that Chris B. came up
> with here (which was also linked-to earlier):

Yes. It's a pretty obvious hack, if you're used to dealing with software 
architectures like POV's animation architecture.

> I would imagine that the typical
> POV user probably believes--at least in the early stages of using the
> program--that each-and-every different seed value *does* generate a nicely
> psuedo-random stream 

It does. The lack of randomness is between the seed and the first value, not 
between the first and second value.  Indeed, it would be interesting to see 
a similar plot if one called rand() exactly once after seeding it.

> The problem of 'patterns' really only seems to show its ugly self when
> one gets into animation. 

Only if you don't use enough random numbers in your scene. The formula for 
going from one random number to the next shows convincing randomness. The 
formula for going from the seed to the first random number does not.

> Yet there's nothing currently in the POV documentation
> that explains any of this.  

That would probably be a good thing to fix, yes.

-- 
   Darren New, San Diego CA, USA (PST)
   There's no CD like OCD, there's no CD I knoooow!

Post a reply to this message

Kenneth wrote:
> I would imagine that the typical
> POV user probably believes--at least in the early stages of using the
> program--that each-and-every different seed value *does* generate a nicely
> psuedo-random stream (which it appears to do, of course--in a static,
> non-animated scene.

  Each and every different seed value *does* generate a stream of
pseudo-random numbers with the exact same quality of randomness.

  In fact, POV-Ray has only one single stream of pseudo-random numbers.
This stream has 4294967296 (2^32) unique numbers in it. When you set up
a seed, you are simply setting up your starting point in this stream.
All random number streams will eventually start giving the same values
as all the other streams at some point, because they are all actually
just traversing the one and same stream, just at different starting points.

  (The reason for this is that POV-Ray uses a simple linear congruential
generator with a period of 2^32. If you want to know more, search it in
wikipedia.)

  The reason for seed(n)/rand() pairs, where n consists of consecutive
numbers, giving results of less quality, is that the consecutive values
of seed() are choosing the starting point for the RNG stream poorly
(this is just a consequence of the LCG algorithm).

  Basically when you do a seed(n), what you get next time you call
rand() is (n*a+b) mod 2^32, where a and b are some constants. You will
probably guess that if you calculate that with consecutive values of n,
the result will not be very random. Basically you are just getting
multiples of a (with an offset of b).

  A higher-quality RNG will probably give better results even when doing
this, but it's still not recommended even with them (if for nothing
else, because seeding high-quality RNGs is usually rather slow, even
though pulling values from them is very fast).

Post a reply to this message

"gregjohn" <pte### [at] yahoocom> wrote:
> The neatly ordered, predictable pattern of red dots in the top half of the image
> are generated with povray's rand() function.  They demonstrate what you get if
> you cause a monotonic increase in the seed value.  Once I had a project
> "ruined" by this predictable pattern because I was exploring some parameter
> space via use of the #declare RSEED=seed(frame_number).

I became aware of these issues as a co-op student when running some Monte Carlo
simulations for a U.S. Air Force contractor.  Not that I know anything about
it; I was working with a professional mathematician.

If you think POV's rand() is bad, take a look at the IBM 360's RANDU() function.
The parameters for this LCG were chosen with hardware optimization in mind. It
seems that no thought was given to the quality of the number stream; perhaps
the implementer was unaware of the mathematical issues.

A whole bunch of scientific studies from the early '70s were invalidated when
this bug was discovered.

What's more, quick look through Google showed that RANDU() was far from the
worst LCG out there.

LCGs are simple and fast, and that's probably why every built-in pseudorandom
number generator that I've seen is an LCG.  A high quality LCG is fine for
casual works, but if you're doing serious statistical or scientific work, you
best study up on non-LCG pseudorandom number generators and write your own.

I've attached some frames of a RANDU() animation.  (I'm not very good at
compression, so I can't post it to p.b.a.)  A simlar run of POV's rand() showed
no discernable visual pattern, but a pattern is in there, even with a stream
from a single seed() call.  (It was a suspicious regularity in some of my POV
runs that prompted me to do the test.)  All that means is that POV uses better
LCG parameters than IBM did.

Post a reply to this message

Attachments:
Download 'randu.jpg' (399 KB)

Preview of image 'randu.jpg'

Cousin Ricky wrote:
> All that means is that POV uses better
> LCG parameters than IBM did.

  I'm pretty certain that's not the case, and that the difference you
are seeing is caused by your choice of bits in the returned values,
rather than the quality of the LCG.

  LCGs have one big flaw: If you take the lowest bits, they tend to show
regular patterns. For example, doing something like this (in pseudocode):

    putpixel(rand() % 256, rand() % 256)

is *very* likely to produce visible regular patterns. That's because the
least-significant 8 bits of the values returned by the RNG are used
as-is to generate the locations of the pixels.

  A simple change to the above code like this:

    putpixel((rand() / 65536) % 256, (rand() / 65536) % 256)

is probably going to get rid of the regular pattern, because now it will
be using bits 16-23 rather than bits 0-7, and the higher bits in a LCG
usually don't present the same type of regularity as the lowest bits.

  The reason why in POV-Ray you rarely get the regular patterns is that
you are usually using the highest bits of the values returned by rand(),
rather than the lowest bits. That's because POV-Ray's rand() returns
seed/4294967296.0 (which effectively scales the 32-bit seed to the range
0.0 - 1.0). Since the value of rand() is then usually multiplied by
something to place objects (eg. rand()*256), you are effectively using
the highest bits of the value rather than the lowest bits, which is why
it's rarer to get the repeated patterns.

  The *quality* of POV-Ray's RNG is not any higher. It's just that you
are not encountering the flaws in the LCG so easily.

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Cousin Ricky wrote:
> > All that means is that POV uses better
> > LCG parameters than IBM did.
>
>   I'm pretty certain that's not the case, and that the difference you
> are seeing is caused by your choice of bits in the returned values,
> rather than the quality of the LCG.

Actually, the issue with the RANDU LCG was a quality issue, and had nothing to
do with regular patterns in the lower bits. That series of screenshots in the
randu.jpg shows the entire unit cube. There really are just 15 planes in that
cube:
http://en.wikipedia.org/wiki/RANDU

There may be a high degree of "randomness" in the upper 8 bits, but if you take
any three consecutive outputs from the randu generator, they will fall on one
of those 15 planes. The density of the lattice within any particular plane is
very high, but the spacing between the planes is orders of magnitude larger.

Imagine a random number generator that returned ordered triples in the unit
cube, such that x could be one of the 1000 values {0.000, 0.001, 0.002, ...,
0.999}, and y could be any of the same 1,000 values, but z could only be one of
the three values {0.1, 0.5, or 0.9}. You have a total of 3 million possible
combinations.

Would you consider that high quality? In effect, this was the flaw with randu.
This is IN ADDITION TO the "one big flaw" that you went on to describe!

>   LCGs have one big flaw: If you take the lowest bits, they tend to show
> regular patterns. For example, doing something like this (in pseudocode):
>
>     putpixel(rand() % 256, rand() % 256)
>
> is *very* likely to produce visible regular patterns. That's because the
> least-significant 8 bits of the values returned by the RNG are used
> as-is to generate the locations of the pixels.

As far as random number generators go, there are plenty of generators out there
that are simple, efficient, and far more effective than an LCG. One of the more
popular generators these days is the Mersenne Twister. It is, however, quite
complex and even a bit slow, compared to other generators that produce similar
quality random numbers (unless you need trillions of random numbers in a single
simulation).

A few variants I would recommend are the KISS generator (actually combines three
small but very fast generators), or a small period MWC or CMWC generator
("lag-4" with base 2^32 or (2^32)-1 is more than sufficient for most purposes,
though larger variants don't add complexity, so the sky's the limit). Google
"Marsaglia" for more info on MWC and CMWC generators.

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:

>   Each and every different seed value *does* generate a stream of
> pseudo-random numbers with the exact same quality of randomness.
>
>   In fact, POV-Ray has only one single stream of pseudo-random numbers.
> This stream has 4294967296 (2^32) unique numbers in it. When you set up
> a seed, you are simply setting up your starting point in this stream.
> All random number streams will eventually start giving the same values
> as all the other streams at some point, because they are all actually
> just traversing the one and same stream, just at different starting points.

Ah!  It *finally* clicks in my brain. Thanks for the excellent clarification.

IIRC, you mentioned something several ago (to me) that seed() chooses it
'starting point' in the stream in a very complex fashion...not just 'linearly'
in the stream.  IOW, the difference between seed(23) and seed(24) isn't just
jumping one value ahead in the 2^32 stream. Is my thinking correct?

KW

Post a reply to this message

"Kenneth" <kdw### [at] earthlinknet> wrote:
> IIRC, you mentioned something several ago (to me) that seed() chooses it
> 'starting point' in the stream in a very complex fashion...not just 'linearly'
> in the stream.  IOW, the difference between seed(23) and seed(24) isn't just
> jumping one value ahead in the 2^32 stream. Is my thinking correct?

Yes. In a first approach, think of seeding the RNG as fast-forwarding to the
position in the 2^32 stream at which that very number appears, so it would not
make a difference (except for speed) whether you would call seed(23), or
instead pull and discard numbers from the stream until the value you pull is 23
(which you discard as well).

Admittedly, this is a bit oversimplified: In real-life RNGs, that 23 is almost
always hidden from your view, and what you get when pulling from the stream is
actually some hash of it (in some primitive RNGs just to make it fit the
desired output range, while in high-quality RNGs it also serves to "distill"
all the "randomness" from a huge but relatively low-random "raw" value into a
small but relatively high-random number).

So to do the stunt of replacing seed() with a lot of dummy calls to rand() you'd
have to know what that 23 is hashed into. And with higher-quality RNGs various
"raw" values will result in identical output numbers, so from pulling a number
from the stream you still cannot tell where in the stream you currently are,
making that stunt impossible.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:

> If you have a known number of random numbers being used in each frame, you
> can seed once at frame 0, then on each subsequent frame, generate
> frame_number time known_random_number_count random numbers, and then pick up
> the stream from there. Use a while loop in SDL to generate calls to rand(),
> in other words.
>

It works, if the lack of pattern in this image were any indication:

Post a reply to this message

Attachments:
Download 'zrandtest12e.png' (39 KB)

Preview of image 'zrandtest12e.png'