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