I've played around with some "animations" where I am really testing out a
parameter space (fractals: camera position; hetero_mf's: parmeters).

I set up a #declare RRR=seed(frame_number);

Then I go using a whole bunch of rand(RRR)'s.  I can then set up a hundred
or thousand frame animation, go to sleep, and come back and use the
interesting images as the basis for further exploration. 

Problem is, a couple times when I was printing out the random values, I
noticed that every nth one were decreasing monotonically.  I don't remember
if it were the 7th or 17th one (hence a stupid bug report).

Q: is this expected behavior or already known?
Q: is anyone interested in taking the time to research this for me?


I've worked around it with some crazy formulas like:
#declare
RRR=seed(1200*abs(sin(frame_number/11.11))+550*abs(cos(frame_number/13.333)));

Post a reply to this message

Greg M. Johnson wrote:
> I've played around with some "animations" where I am really testing
> out a parameter space (fractals: camera position; hetero_mf's:
> parmeters).
>
> I set up a #declare RRR=seed(frame_number);

> Problem is, a couple times when I was printing out the random values,
> I noticed that every nth one were decreasing monotonically.

Every nth what? This must be every nth random stream, not every nth value 
within the same random stream.

The random streams are not random from each other. Only the numbers within a 
random stream are random from each other.

> Q: is this expected behavior or already known?

Yes.

When you use #declare RRR=seed(frame_number); then each stream will relate 
to the other streams in a predictable non-random manner.

Rune
-- 
http://runevision.com

Post a reply to this message

Greg M. Johnson wrote:
> I've worked around it with some crazy formulas like:
> #declare
> RRR=seed(1200*abs(sin(frame_number/11.11))+550*abs(cos(frame_number/13.333)));

I use

#declare rsA=seed(Frame);
#declare rsB=seed(floor(12345*rand(rsA)));

And use rsB as the primary seed for things.

Regards,
John

Post a reply to this message

John VanSickle <evi### [at] hotmailcom> wrote:
> #declare rsA=seed(Frame);
> #declare rsB=seed(floor(12345*rand(rsA)));

> And use rsB as the primary seed for things.

  Knowing how the random number generator used by povray works (it's pretty
simple, actually), I'm quite convinced that method doesn't actually add
any more "randomness" than simply using rsA as the seed. It simply
produces different results, that's all.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

> John VanSickle <evi### [at] hotmailcom> wrote:
>> #declare rsA=seed(Frame);
>> #declare rsB=seed(floor(12345*rand(rsA)));
> 
>> And use rsB as the primary seed for things.
> 
>   Knowing how the random number generator used by povray works (it's
>   pretty
> simple, actually), I'm quite convinced that method doesn't actually add
> any more "randomness" than simply using rsA as the seed. It simply
> produces different results, that's all.
> 

If the phenomenon I observed is valid, then it could be helpful to have an
less-predictable value by setting the seed based on something that varies
wildly as a function of frame_number: I was using cos & sin.

Post a reply to this message

"Greg M. Johnson" <pte### [at] thecommononethatstartswithYcom> wrote in 
message news:46f0778a@news.povray.org...
> Warp wrote:
>
>> John VanSickle <evi### [at] hotmailcom> wrote:
>>> #declare rsA=seed(Frame);
>>> #declare rsB=seed(floor(12345*rand(rsA)));
>>
>>> And use rsB as the primary seed for things.
>>
>>   Knowing how the random number generator used by povray works (it's
>>   pretty
>> simple, actually), I'm quite convinced that method doesn't actually add
>> any more "randomness" than simply using rsA as the seed. It simply
>> produces different results, that's all.
>>
>
> If the phenomenon I observed is valid, then it could be helpful to have an
> less-predictable value by setting the seed based on something that varies
> wildly as a function of frame_number: I was using cos & sin.

I would probably guess that you don't necessarily need increased randomness 
(or unpredicitability), just that the mode and value-step in the frame/seed 
sequence does shift to a harder pattern for the eye/brain to see.  Which 
John's trick might do without actually increasing "randomness".  In the 
absence of knowledge of the algorithm, experiment.  :-)

Brian

Post a reply to this message

Greg M. Johnson <pte### [at] thecommononethatstartswithycom> wrote:
> If the phenomenon I observed is valid, then it could be helpful to have an
> less-predictable value by setting the seed based on something that varies
> wildly as a function of frame_number: I was using cos & sin.

  What do you mean by "less predictable"?

  From any value returned by the random number generator it's possible
to predict the next values. POV-Ray's RNG uses a very simple algorithm.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

> Greg M. Johnson <pte### [at] thecommononethatstartswithycom> wrote:
>> If the phenomenon I observed is valid, then it could be helpful to have
>> an less-predictable value by setting the seed based on something that
>> varies wildly as a function of frame_number: I was using cos & sin.
> 
>   What do you mean by "less predictable"?
> 
>   From any value returned by the random number generator it's possible
> to predict the next values. POV-Ray's RNG uses a very simple algorithm.
> 


Okay.  To restate, say I do this:

#declare RRR=seed(frame_number);
#declare a01=rand(RRR);
#declare a02=rand(RRR);
#declare a03=rand(RRR);
#declare a04=rand(RRR);
#declare a05=rand(RRR);
#declare a06=rand(RRR);
#declare a07=rand(RRR);
#declare a08=rand(RRR);
#declare a09=rand(RRR);
#declare a10=rand(RRR);
...
#declare an=rand(RRR);


Then for some n, n<20, if I then go plot out the values of an as a function
of frame_number when rendered, one of those values would be a straight
line. One but surely not all. 

That's not exactly predictable but it's entirely non random.

Post a reply to this message

Greg M. Johnson wrote:
> Okay.  To restate, say I do this:
>
> #declare RRR=seed(frame_number);
> #declare a01=rand(RRR);
> #declare a02=rand(RRR);
> #declare a03=rand(RRR);
> #declare a04=rand(RRR);
> #declare a05=rand(RRR);
> #declare a06=rand(RRR);
> #declare a07=rand(RRR);
> #declare a08=rand(RRR);
> #declare a09=rand(RRR);
> #declare a10=rand(RRR);
> ...
> #declare an=rand(RRR);
>
>
> Then for some n, n<20, if I then go plot out the values of an [in one 
> curve for each n]
> as a function of frame_number when rendered, one of those values
> [one of those *curves* not values - a value can't be a line] would be a 
> straight line.
> One but surely not all.

After trying to make sense of this sentence I think I understand what you 
mean and I'd say it's correct.

> That's not exactly predictable but it's entirely non random.

I think that Warp just meant something along the lines that no sequence 
generated by a computer is *really* non-predictable. I don't see how that's 
relevant for this discussion though.

I think the conclusion is that what you have found is not a bug, and you can 
get the behavior you want either by using workarounds with sin and cos as 
you have done, or by writing a large number of random numbers to a file 
(using a single random stream) and then reading the first of these numbers 
in your first frame, the second in the second and so on. Then you can 
multiply the numbers in this random sequence and use them as new seeds.

Rune
-- 
http://runevision.com

Post a reply to this message

Greg M. Johnson <pte### [at] thecommononethatstartswithycom> wrote:
> Then for some n, n<20, if I then go plot out the values of an as a function
> of frame_number when rendered, one of those values would be a straight
> line. One but surely not all. 

  Sorry, I didn't understand that.

-- 
                                                          - Warp

Post a reply to this message

Rune <new### [at] runevisioncom> wrote:
> I think that Warp just meant something along the lines that no sequence 
> generated by a computer is *really* non-predictable.

  No, what I meant was that POV-Ray uses a RNG such that you can predict
its entire outcome from the very first value it returns, even if you don't
know the original seed. That way it's very predictable.

  There exist other RNGs where this is not so. For example you can't
deduce the outcome of the Mersenne Twister with only the first result it
returns (you need to read several hundreds of values before you can
predict accurately the rest). With the Blum Blum Shub RNG it's even
more difficult.

> I don't see how that's 
> relevant for this discussion though.

  It isn't. I was just nitpicking about predictability.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

> Greg M. Johnson <pte### [at] thecommononethatstartswithycom> wrote:
>> Then for some n, n<20, if I then go plot out the values of an as a
>> function of frame_number when rendered, one of those values would be a
>> straight line. One but surely not all.
> 
>   Sorry, I didn't understand that.
> 


I was trying to understand the response of a hetero_mf or similar function,
one that has a bunch of parameters.  (And I was trying to find one that
just plain looked cool as an isosurface.)   So I set the computer running
with a couple hundred frames, where the parameters that go into the
function were determined by use of povray's rand function.  I also had the
image print out all the parms on the image as a text object.

In looking back at the set, I first noticed that the images didn't seem to
have varied as much as I might have liked.  Then as I studied the
parameters that showed up on the screen all (as expected) were bouncing all
around all over the place.  One (maybe the 3rd or 5th) was monotonically
decreasing from frame to frame by a constant value.

In other words, if one were to plot the values of each of the half-dozen,
rand()-derived, parameters as a function of frame_number,  all jumped
around unpredictably (to the human eye).  One parameter would have been a
straight line. In other words, someone could predict the next frame by
subtraction, even if they didn't know how povray computed the rand().

The nth use of rand() in a frame was anything but random if the seed were 
simply the frame_number.  I apologize I forget which n it was.

Post a reply to this message

Warp wrote:
> Rune <new### [at] runevisioncom> wrote:
> 
>>I think that Warp just meant something along the lines that no sequence 
>>generated by a computer is *really* non-predictable.
> 
> 
>   No, what I meant was that POV-Ray uses a RNG such that you can predict
> its entire outcome from the very first value it returns, even if you don't
> know the original seed. That way it's very predictable.
> 
>   There exist other RNGs where this is not so. For example you can't
> deduce the outcome of the Mersenne Twister with only the first result it
> returns (you need to read several hundreds of values before you can
> predict accurately the rest). With the Blum Blum Shub RNG it's even
> more difficult.

I wrote a C++ class that generates pseudo-random numbers using an array 
of 24 shorts.  I extract from the positions indexed by the first eight 
prime numbers (2, 3, 5, 7, 11, 13, 17 and 19), pair them up and take the 
maximum value from each pair, then pair up the remaining four values and 
take the minimum from each pair, add them and the values in positions 22 
and 23, shift values in positions 0 through 21 to the next higher 
position, put the sum into position 0 and return the low byte of the sum 
as the return value.  I also increment position 23 by 24109 (which is 
floor(65536/e), although I suspect that any odd value would work).

To initialize I fill the shift register with the seed value, and then 
generate byte values until every value from 0 to 255 has been generated 
at least once.

I haven't tested to see if there is any unusual patterns from the 
results, but I suppose I could go do that.

I originally wrote this to use to randomly generate game worlds, and I 
wanted to make very sure that the chance of two game worlds being the 
same was exceptionally small.  There are 2^384 possible states for the 
generator, and I'm not aware of any short loops in it.

Regards,
John

Post a reply to this message

Perhaps you could post a small piece of SDL demonstrating the effect?

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>  Perhaps you could post a small piece of SDL demonstrating the effect?

Here:

#declare SeedNr = 0;
#while (SeedNr<50)
   #declare Seed = seed(SeedNr);
   #declare RandNr = 0;
   #while (RandNr<10)
      #declare Rand = rand(Seed);
      sphere {0, 0.1 translate <SeedNr/5-5,Rand-RandNr*2+10,25>}
      #declare RandNr = RandNr+1;
   #end
   #declare SeedNr = SeedNr+1;
#end
background {rgb 1}

As can easily be seen, any sequence generated from the n'th random number 
from seeds 1...m is be completely linear.

And as previously stated, this is a feature, not a bug. I've been told 
earlier when I asked myself.

Rune
-- 
http://runevision.com

Post a reply to this message

Rune <new### [at] runevisioncom> wrote:
> And as previously stated, this is a feature, not a bug. I've been told 
> earlier when I asked myself.

  POV-Ray uses a very simple linear congruential generator. More precisely:

randValue = randValue * 1812433253 + 12345

(which is then scaled to the range 0.0 - 1.0)

  You have encountered one of the disadvantages of such a linear congruential
generator, as described here:

http://en.wikipedia.org/wiki/Linear_congruential_generator#Advantages_and_disadvantages_of_LCGs

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

> 1812433253

Fascinating.  Makes me want to make up my own from now on.

Is something like newrand()=  mod (1000* sin( (0.5+0.5*newrand())*pi ) , 1)

less "predictable?  Can you think of something better?

Post a reply to this message

Greg M. Johnson <pte### [at] thecommononethatstartswithycom> wrote:
> Can you think of something better? 

  Yes, the Mersenne twister.

-- 
                                                          - Warp

Post a reply to this message

Greg M. Johnson wrote:
> Warp wrote:
> 
>> 1812433253
> 
> Fascinating.  Makes me want to make up my own from now on.
> 
> Is something like newrand()=  mod (1000* sin( (0.5+0.5*newrand())*pi ) , 1)
> 
> less "predictable?  Can you think of something better? 
yes.
weakpoints are that it takes longer to compute than a standard random 
number generator but more importantly, is does not have a flat 
distribution. It is not as bad as I expected (see attached greg1.png) 
but not good enough. I think it is because if your number is close to 1, 
the next will also be. And you can get there by accident, so that is 
probably why there is that peak close to 1. Removing the pi from your 
equation helps a lot. I don't feel like doing a more complete analysis now.

Post a reply to this message

Attachments:
Download 'greg1.png' (4 KB) Download 'greg2.png' (5 KB)

Preview of image 'greg1.png'

Preview of image 'greg2.png'

Warp wrote:

>> Can you think of something better? 
> 
>   Yes, the Mersenne twister.

Results decorrelated to over 12 dimensions... ;-)



OOC, are the coeficients for POV-Ray's generator from a book or where 
they just chosen arbitrarily?

-- 
http://blog.orphi.me.uk/

Post a reply to this message

andrel wrote:

> Greg M. Johnson wrote:
>> Warp wrote:
>> 
>>> 1812433253
>> 
>> Fascinating.  Makes me want to make up my own from now on.
>> 
>> Is something like newrand()=  mod (1000* sin( (0.5+0.5*newrand())*pi ) ,
>> 1)
>> 
>> less "predictable?  Can you think of something better?
> yes.
> weakpoints are that it takes longer to compute than a standard random
> number generator but more importantly, is does not have a flat
> distribution. It is not as bad as I expected (see attached greg1.png)
> but not good enough. I think it is because if your number is close to 1,
> the next will also be. And you can get there by accident, so that is
> probably why there is that peak close to 1. Removing the pi from your
> equation helps a lot. I don't feel like doing a more complete analysis
> now.


Wow, thanks!
And thanks for the pointer to the Mersenne

Post a reply to this message

Orchid XP v3 <voi### [at] devnull> wrote:
> OOC, are the coeficients for POV-Ray's generator from a book or where 
> they just chosen arbitrarily?

  Unlikely to be arbitrary because, IIRC, the period is 2^32. (In other
words, it goes through the entire range of 32-bit values before repeating.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v3 <voi### [at] devnull> wrote:
>> OOC, are the coeficients for POV-Ray's generator from a book or where 
>> they just chosen arbitrarily?
> 
>   Unlikely to be arbitrary because, IIRC, the period is 2^32. (In other
> words, it goes through the entire range of 32-bit values before repeating.)

Right. There's some kind of algorithm for picking LCG coefficients such 
that they have this property. (I have no idea what the algorithm is.)

So even though you get uniformly distrubuted numbers in 0 .. 1, POV-Ray 
is actually generating integers and converting them? Presumably that 
means no two random numbers can differ by less than 2^-32?

-- 
http://blog.orphi.me.uk/

Post a reply to this message

Orchid XP v3 <voi### [at] devnull> wrote:
> So even though you get uniformly distrubuted numbers in 0 .. 1, POV-Ray 
> is actually generating integers and converting them? Presumably that 
> means no two random numbers can differ by less than 2^-32?

  That's correct.

  There are also other side-effects. For example, you can have two
random seeds, each one creating random numbers independently of each
other, and suddenly one of them may start giving the exact same values
the other one gave when it started.
  This is because every seed is just going through the exact same
sequence of numbers, simply starting at different places. Advance
one seed enough and it will eventually reach the starting point of
the other seed.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v3 <voi### [at] devnull> wrote:
>> So even though you get uniformly distrubuted numbers in 0 .. 1,
>> POV-Ray is actually generating integers and converting them?
>> Presumably that means no two random numbers can differ by less than
>> 2^-32?
>
>  That's correct.
>
>  There are also other side-effects. For example, you can have two
> random seeds, each one creating random numbers independently of each
> other, and suddenly one of them may start giving the exact same values
> the other one gave when it started.
>  This is because every seed is just going through the exact same
> sequence of numbers, simply starting at different places. Advance
> one seed enough and it will eventually reach the starting point of
> the other seed.

And I presume it's a bad idea to choose different LCG coefficients for each 
seed?

Rune
-- 
http://runevision.com

Post a reply to this message

Rune <new### [at] runevisioncom> wrote:
> And I presume it's a bad idea to choose different LCG coefficients for each 
> seed?

  Not really, if each one has the same quality. POV-Ray just doesn't do
that.

-- 
                                                          - Warp

Post a reply to this message