> If my simplistic assumptions/understandings are correct, then it seems to 
> me
> that it all still begs the question of why there are repetitive patterns 
> when
> using seed(frame_number) in animations--albeit when calling only one 
> rand()
> value per seed. I don't mean to beat this poor old horse to death, but
> seed(frame number 23) and seed(frame number 24) should--as far as I 
> understand
> things--pick up the 2^32 stream at wildly differing locations (with 
> completely
> different 'blocks' of random values that rand() then picks out--even just 
> one
> rand() call.) If the 2^32 values in the stream are indeed pseudo-randomly
> created, then from where does a semi-repeating pattern arise?

I don't think POV-Ray's RNG does any hash with your initial value. I think 
clipka was referring to other RNGs.

LCGs, like the one POV-Ray uses, usually do a simple process with the seed 
along the lines of multiplying by a constant, adding a different constant, 
and then looping the result back around if it's too high. Every time you 
take a random number, it does this again with the previous one. When you 
always start with a similar number, this basic math doesn't provide enough 
randomness. However, you might find that you can get better results if you 
call rand() with the seed a few extra times before using it.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

"Slime" <fak### [at] emailaddress> wrote:
> ...When you
> always start with a similar number, this basic math doesn't provide enough
> randomness. However, you might find that you can get better results if you
> call rand() with the seed a few extra times before using it.
>

and Darren wrote (taken out of context)...
> 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 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.

So skipping the first (or first few) rand values sounds like a good recipe for
avoiding patterns, especially in animation using seed(frame_number) and pulling
only a few rand()s from the seed. Thanks to you both for the info; VERY
useful.

KW

Post a reply to this message

Kenneth wrote:
> If my simplistic assumptions/understandings are correct, then it seems to me
> that it all still begs the question of why there are repetitive patterns when
> using seed(frame_number) in animations

Think of it this way: each number resulting from seed(n) is related to the 
number from seed(n+1) in a fairly simple way. However, calling rand() three 
times gives you rand(rand(rand(seed(n)))). In other words, the seed starts 
you, but the rand() call uses the result of the previous rand() call as the 
next seed. *That* is where the more complex randomness comes from.

This only applies to the LCG type PRNG that POV uses, btw. This isn't true 
of all RNGs.  It *is* true of many cryptographic systems, but they have far 
more complex RNGs to start with, also.

-- 
   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" <kdw### [at] earthlinknet> wrote:
> Interesting! So as I understand it--again using seed(23) and seed(24) as
> examples--the '23' and the '24' are definitely not next to each other in the
> 2^32 stream, but are distributed *who knows where* (admittedly a simplified way
> of expressing the situation.) Correct so far?

Definitely so.

> Then (guessing further), the rand() calls from those two seeds 'start up' at the
> pseudo-random values following the pseudo-randomly-dispersed 23 and 24 in the
> stream? (I may be *grossly* oversimplifying here.)

You're not oversimplifying more than I did, so yes :)

> If my simplistic assumptions/understandings are correct, then it seems to me
> that it all still begs the question of why there are repetitive patterns when
> using seed(frame_number) in animations--albeit when calling only one rand()
> value per seed. I don't mean to beat this poor old horse to death, but
> seed(frame number 23) and seed(frame number 24) should--as far as I understand
> things--pick up the 2^32 stream at wildly differing locations (with completely
> different 'blocks' of random values that rand() then picks out--even just one
> rand() call.) If the 2^32 values in the stream are indeed pseudo-randomly
> created, then from where does a semi-repeating pattern arise?

I'm a bit puzzled about this one as well. I guess I'll have to look at the
actual code one of these days. It *may* be the case that the first rand()
actually does not yet pull the value *after* the "23", but the "23" itself -
somewhat garbled due to the hashing always performed, but still with a
recognizable correlation to the seed value.

It might be interesting to see how the "single-rand()-per-frame" thing works out
when you discard the first result of rand(), and use only the second result,
e.g.:

#declare R = seed(4711);
#declare dummy = rand(R);
#declare myValue = rand(R);

Post a reply to this message

"Slime" <fak### [at] emailaddress> wrote:
> I don't think POV-Ray's RNG does any hash with your initial value. I think
> clipka was referring to other RNGs.

If you're thinking along the lines of strong cryptographic hashes, then you're
right, that's probably not done in POV-Ray's RNG.

I was thinking of a more general definition of "hash", as basically *any* digest
of an input value other than equality.

Post a reply to this message

"clipka" <nomail@nomail> wrote:
> "Kenneth" <kdw### [at] earthlinknet> wrote:
> > If my simplistic assumptions/understandings are correct, then it seems to me
> > that it all still begs the question of why there are repetitive patterns when
> > using seed(frame_number) in animations--albeit when calling only one rand()
> > value per seed. I don't mean to beat this poor old horse to death, but
> > seed(frame number 23) and seed(frame number 24) should--as far as I understand
> > things--pick up the 2^32 stream at wildly differing locations (with completely
> > different 'blocks' of random values that rand() then picks out--even just one
> > rand() call.) If the 2^32 values in the stream are indeed pseudo-randomly
> > created, then from where does a semi-repeating pattern arise?
>
> I'm a bit puzzled about this one as well. I guess I'll have to look at the
> actual code one of these days. It *may* be the case that the first rand()
> actually does not yet pull the value *after* the "23", but the "23" itself -
> somewhat garbled due to the hashing always performed, but still with a
> recognizable correlation to the seed value.
>
> It might be interesting to see how the "single-rand()-per-frame" thing works out
> when you discard the first result of rand(), and use only the second result,
> e.g.:
>
> #declare R = seed(4711);
> #declare dummy = rand(R);
> #declare myValue = rand(R);

A simple way to understand the problem is to use a simple example. An LCG works
by logic like this:
R[0] = seed
R[i] = mod(A * R[i-1] + C, Base)
rand()[i] = R[i]/Base

So rand[i], with i>0, will be the random sequence.

In a typical example, A might be 69069, C might be an odd number like 1234567,
and Base might be 2^32.

A simple example might be A=21, C=3, and Base = 100.

If we start with a seed of 1, then the first few rand's will be 0.24, 0.07,
0.50, 0.53, 0.16, 0.39, 0.22, 0.65, etc. Looks pretty random, and for practical
purposes, where you need fewer than, say a dozen random numbers, it works fine.

However, if we only look at the first random value, using consecutive seeds, we
get the following pattern:

seed(1); rand() = 0.24
seed(2); rand() = 0.45
seed(3); rand() = 0.66
seed(4); rand() = 0.87
seed(5); rand() = 0.08
seed(6); rand() = 0.29

Notice that each is exactly 0.21 larger than the one before (mod 100). A very
regular pattern.

But what if we take the second rand() value for each seed?

seed(1); rand(); rand() = 0.07
seed(2); rand(); rand() = 0.48
seed(3); rand(); rand() = 0.89
seed(4); rand(); rand() = 0.30
seed(5); rand(); rand() = 0.71
seed(6); rand(); rand() = 0.12

Again, there is a regular pattern: each is 0.41 larger than the one before (mod
100).

Sorry folks, but no free lunch. Multiple rand() streams with consecutive seeds
will show a very regular pattern. The pattern continues, regardless of how far
we go into the stream.

As a practical example, if we grabbed the first three rand() values and made
them into vector, and we used the frame number as the seed, then the vector
will follow a well-defined lattice pattern, i.e., it will change by the same
amount from frame to frame, mod 1.0 on each axis to stay in the unit cube.

An LCG is only useful as an RNG if we pick one and only one seed. Therefore,
from frame to frame, we need to seed with the last rand() value from the
previous frame. Unless, of course, we use a different RNG.

Post a reply to this message

"Jay Fox" <jay### [at] gmailcom> wrote:
> Sorry folks, but no free lunch. Multiple rand() streams with consecutive seeds
> will show a very regular pattern. The pattern continues, regardless of how far
> we go into the stream.
>
> As a practical example, if we grabbed the first three rand() values and made
> them into vector, and we used the frame number as the seed, then the vector
> will follow a well-defined lattice pattern, i.e., it will change by the same
> amount from frame to frame, mod 1.0 on each axis to stay in the unit cube.
>
> An LCG is only useful as an RNG if we pick one and only one seed. Therefore,
> from frame to frame, we need to seed with the last rand() value from the
> previous frame. Unless, of course, we use a different RNG.

After thinking about it, I realized the situation isn't so bad after all.

Yes, taking consecutive seeds will display a very regular pattern. But this is
due to insufficient seeding, not insufficient "randomness" of the RNG.

The solution, of course, is to use better seeding. The answer so far has been to
use the last rand() value from the previous frame.

But a simpler approach would accomplish nearly the same result: use a non-linear
function of the frame number.

A simple example would be to use a polynomial of degree at least 2. For example,
if k is the frame number, then seed(k*k) or seed(k*k*k) would work very nicely.
Give it a try and see what you think. Even using the first rand() value, this
approach should provide good randomness.

Another simple approach would be to use k as the seed, but throw away the first
k random numbers, or the first k*k. Or mix and match these two approaches as
needed. For example, seed with seed(k*k*k), and throw away the first k rand()
values.

Post a reply to this message

"Jay Fox" <jay### [at] gmailcom> wrote:
> Sorry folks, but no free lunch.

That's the story of existence, isn't it?

Post a reply to this message

Kenneth wrote:
> If my simplistic assumptions/understandings are correct, then it seems to me
> that it all still begs the question of why there are repetitive patterns when
> using seed(frame_number) in animations--albeit when calling only one rand()
> value per seed. I don't mean to beat this poor old horse to death, but
> seed(frame number 23) and seed(frame number 24) should--as far as I understand
> things--pick up the 2^32 stream at wildly differing locations

  They do choose a starting point at "wildly different locations".
That's not the issue. The issue is that there's a discernible pattern
between seed(23), seed(24) and seed(25). They all jump around the stream
rather "wildly", but by the same amount. Basically seed(24) has the same
"difference" to seed(23), as seed(25) has to seed(24). That's where the
regular patterns are so easily jumping out.

  This is due to how a linear congruential generator works. As
mentioned, the next value in the stream is chosen with the formula:

n = n * a + b; // (modulo 2^32, as 32-bit integers are used)

where a and b are some constants (and the initial value of n is the seed
you specified).

  So if you calculate that with consecutive values of n (which is what
you are doing with seed(frame_number)), what you are getting is
consecutive multiples of a, with an offset of b (modulo 2^32).

  One thing you could try to avoid the regularity is to call rand() a
random number of times at each frame. This might mask the regularity
between consecutive seeds. For example like this:

#declare S = seed(frame_number);
#declare Ind = 0;
#declare IndMax = int(rand(S)*10);
#while(Ind < IndMax)
  #declare DummyValue = rand(S);
  #declare Ind = Ind+1;
#end

  Since you are choosing the amount of loops with the same RNG, the
overall quality of the randomness is not increasing, but this trick
might mask the regular patterns, so they won't become discernible so easily.

Post a reply to this message