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).

The green dots below represent my best attempt so far to create something worthy
of the title "random function".   It requires one first to set an "aseed" value
between 0 and 1, but this aseed *may* increase monotonically, like #declare
aseed=(frame_number+0.1)/(final_frame+0.1);

#macro randoo()
#declare aseed=pi/(aseed)+pi/(1+aseed);
#declare aseed=aseed*10000-int(10000*aseed);
(aseed)
#end


And here is the complete (mess!) of code that generated my image:

#include"transforms.inc"

#macro Reorient(Axis1,Axis2)//john vansickle
                #local vX1=vnormalize(Axis1);
                #local vX2=vnormalize(Axis2);
                #local vY=vnormalize(vcross(vX1,vX2));
                #local vZ1=vnormalize(vcross(vX1,vY));
                #local vZ2=vnormalize(vcross(vX2,vY));
                matrix < vX1.x, vY.x,vZ1.x, vX1.y,vY.y,vZ1.y, vX1.z,vY.z, vZ1.z,
0,0,0 >
                matrix < vX2.x,vX2.y,vX2.z,  vY.x,vY.y, vY.z, vZ2.x,vZ2.y,vZ2.z,
0,0,0 >
              #end

#declare iwih=image_width/image_height;

#declare camang=45;

#declare camloke=-100*z;
#declare azee=0.5*iwih/tan(camang/2*pi/180);

#declare camlook_at=0;
#declare seedirn= camlook_at-camloke+0.000001;
#declare cameratransform=transform{ Reorient (z,seedirn*<1,0,1.001>)
Reorient(seedirn*<1,0,1.001>,seedirn) translate camloke}

camera {
  direction z*azee
  up y
  right     x*image_width/image_height
  transform{cameratransform}
 }

#declare RRR=seed(frame_number);   //standard way of declaring a seed
#declare aseed=0.335;//mod((frame_number+1)/100,1);

#macro randoo()                     //a new, truly random number generator.
#declare aseed=pi/(aseed)+pi/(1+aseed);
#declare aseed=aseed*10000-int(10000*aseed);
(aseed)
#end

#declare a=randoo();
#declare nmax=3980;
#declare oldway_oldend=rand(RRR);
#declare newway_oldend=randoo();//rand(aseed2);


#declare n=0;
#while(n<nmax)

#declare RRR=seed(n);
#declare aseed=mod((n+1)/nmax,1);


#declare oldway_newend =rand(RRR);
#declare newway_newend=randoo();

sphere{<iwih*(n+1)/nmax-iwih/2,0.5*(oldway_newend),azee>
,0.005
 pigment{red 1}finish{ambient rgb 1}
 transform{cameratransform}
 }

sphere{<iwih*(n+1)/nmax-iwih/2,0.5*(newway_newend)-0.5,azee>
,0.005
 pigment{green 0.5}finish{ambient rgb 1}
 transform{cameratransform}
 }

#declare oldway_oldend=oldway_newend;
#declare newway_oldend=newway_newend;

#declare n=n+1;
#end

box{<-iwih/2,-0.5,azee+1>,<iwih/2,0.5,azee+0.051> pigment{rgb 1}finish{ambient
rgb 1}
 transform{cameratransform}}

Post a reply to this message

Attachments:
Download 'zrandtest11.png' (137 KB)

Preview of image 'zrandtest11.png'

gregjohn 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).
> 
> The green dots below represent my best attempt so far to create something worthy
> of the title "random function".   It requires one first to set an "aseed" value
> between 0 and 1, but this aseed *may* increase monotonically, like #declare
> aseed=(frame_number+0.1)/(final_frame+0.1);

  The reason why you get regular patterns is because POV-Ray uses a
simple linear congruential generator as its RNG, which has this precise
flaw. LCGs are very poor-quality RNGs.

  You can try shuffling the results of the LGC around by adding
additional "garbage" to the result, but the quality of the results will
not increase. The only thing you will achieve is that in a particular
case where the original values presented regular patterns, it will stop
doing that. However, in a different case it will most probably show the
regular patterns again (because the quality of the randomness has not
increased).

  One solution would be if a new, higher-quality RNG was added to
POV-Ray internally. Perhaps it could be used with a different keyword
(such as seed2() and rand2()).

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).
>
> The green dots below represent my best attempt so far to create something worthy
> of the title "random function".   It requires one first to set an "aseed" value
> between 0 and 1, but this aseed *may* increase monotonically, like #declare
> aseed=(frame_number+0.1)/(final_frame+0.1);

This was the problem I found with my stochastic rig - esp because I was seeding
each frame's RNG with frame_number. I wrote some (non-mathematically-robust)
functions to increase the quality of the random numbers I was using for a few
key parameters. They helped for my code, but I don't really know if they were
increasing the randomness, or just hiding the problems from my uses. I've seen
papers about how to create high-quality random numbers from poor-quality RNGs,
but I'm not mathematically adept enough to understand them...

In the end I found myself using halton sequences more and more - they are
decidedly non-random, but what I was really using the RNG for was to create low
discrepancy samples, and the halton sequence seemed better than a RNG for that
purpose.

A (ever-so slightly buggy) version of both a RNG massager, and a halton sequence
generator are both in my 35m Camera macros I posted a few months back.

Cheers,
Edouard.

Post a reply to this message

gregjohn 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).
> 
The key to using a RNG is that it should be seeded once and ONLY once, 
before the RNG is used the first time.  That starts up a sequence of 
random numbers.  Then each time the RNG is called it gives you the next 
(pseudo) random number in the sequence.  If you try to seed it each 
time, you're not using a random sequence, it depends on however your 
seqence of seeds is defined.

Now, this can be a problem in POV-Ray animations because each frame is 
essentially created from scratch.  There's no built-in way to continue 
the RNG sequence between frames.  One possible approach is to save a 
final random number to a file and use that as the seed for the next 
frame.  But in a single, non-amimated image, don't use more than one 
initial seed.

Of course, since POV-Ray allows multiple random streams, this means that 
each one should be only seeded once -- and generally a different seed 
for each.

      -=- Larry -=-

Post a reply to this message

Larry Hudson <org### [at] yahoocom> wrote:
> gregjohn 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).
> >
> The key to using a RNG is that it should be seeded once and ONLY once,
> before the RNG is used the first time.  That starts up a sequence of
> random numbers.  Then each time the RNG is called it gives you the next
> (pseudo) random number in the sequence.  If you try to seed it each
> time, you're not using a random sequence, it depends on however your
> seqence of seeds is defined.
>
> Now, this can be a problem in POV-Ray animations because each frame is
> essentially created from scratch.  There's no built-in way to continue
> the RNG sequence between frames.  One possible approach is to save a
> final random number to a file and use that as the seed for the next
> frame.  But in a single, non-amimated image, don't use more than one
> initial seed.
>
> Of course, since POV-Ray allows multiple random streams, this means that
> each one should be only seeded once -- and generally a different seed
> for each.
>
>       -=- Larry -=-

This sounds familiar ;)

The op may want to read this thread here:
http://news.povray.org/povray.general/thread/%3Cweb.497a1e5215dcf5ebf50167bc0%40news.povray.org%3E/?ttop=307384&toff=50
&mtop=300618

Of particular interest is this posting:
http://news.povray.org/povray.general/message/%3C497a49fd%241%40news.povray.org%3E/#%3C497a49fd%241%40news.povray.org%3
E
To make a long story short, one can use the frame number to iterate through the
stream, so that a "random" number is used for each frame.

That said, I would like to see a new, stronger rand function in a future
version.


-Reactor

Post a reply to this message

Larry Hudson wrote:
> The key to using a RNG is that it should be seeded once and ONLY once,
> before the RNG is used the first time.  That starts up a sequence of
> random numbers.  Then each time the RNG is called it gives you the next
> (pseudo) random number in the sequence.

  That won't help the regular patterns which appear in some situations
when using a LCG (which is a very poor-quality RNG). When or how often
you seed is not really the point.

> Now, this can be a problem in POV-Ray animations because each frame is
> essentially created from scratch.  There's no built-in way to continue
> the RNG sequence between frames.

  seed(frame_number) is a perfectly good way of using different random
streams at each frame. The quality of the randomness will neither
increase nor decrease by doing that. There will be no obvious pattern
caused by doing this.

  You are confusing "seed every time before calling rand()" with "seed
at the beginning of each frame" (using a value which varies at each
frame, eg. the frame number), which are completely different things. The
former is a bad idea, the latter is completely ok and won't result in
reduction of the quality of the randomness.

  Btw, I have suggested to the pov-team the implementation of
additional, higher-quality RNGs into povray, and they liked the idea. So
it may be possible that in a future beta we might have alternative,
better-quality RNGs (the current one will obviously be preserved for
backwards compatibility reasons; the new one can be used optionally). I
can't promise anything, though.

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
>
>   seed(frame_number) is a perfectly good way of using different random
> streams at each frame. The quality of the randomness will neither
> increase nor decrease by doing that. There will be no obvious pattern
> caused by doing this.
>

Unless I misunderstand what you're saying, I believe the exact opposite. I first
discovered the problem when using seed(frame_number) and saw a predictable,
linearly monotonous effect in rand().  I believe that's also exactly what I
showed in my red dot pattern.  The "n" is a placeholder for what you see across
multiple frame_number 's .

Post a reply to this message

gregjohn wrote:
> Warp <war### [at] tagpovrayorg> wrote:
>>   seed(frame_number) is a perfectly good way of using different random
>> streams at each frame. The quality of the randomness will neither
>> increase nor decrease by doing that. There will be no obvious pattern
>> caused by doing this.
>>
> 
> Unless I misunderstand what you're saying, I believe the exact opposite. I first
> discovered the problem when using seed(frame_number) and saw a predictable,
> linearly monotonous effect in rand().  I believe that's also exactly what I
> showed in my red dot pattern.  The "n" is a placeholder for what you see across
> multiple frame_number 's .

  If you are getting a regular pattern inside one single frame, it's
certainly *not* because you did a "seed(frame_number)" at the beginning
of your scene.

  "seed(frame_number)" is not any more likely to produce regular
patterns than "seed(0)" (or any other value for that matter) is.

  The only difference between doing a "seed(0)" and a
"seed(frame_number)" is that in the former case you will always get the
same sequence of numbers for the frame, while in the latter case you
will get a different sequence for each frame (which is what you usually
want). The quality of the sequence will be the same in either case.

  It has been suggested that to get a different sequence of random
numbers for each frame in an animation, some kind of "seed" value should
be saved to a file and then in the next frame read and used as parameter
for seed(). However, this does not produce anything that the simple
"seed(frame_number)" wouldn't. It will not increase the quality of the
randomness, nor reduce the likelihood of regular patterns appearing in
certain situations.

  There's one situation where doing a "seed(frame_number)" might produce
"more" regular patterns than something else, and that's if the next
frame somehow remembers what was created in the previous frame. The
simplest case is that each frame executes a "seed(frame_number)", then
calls rand() once (or to create one object), and then the location of
this object is somehow stored in a file and read in the next frame.

  In this case the effect will be the same as if you had called
seed+rand repeatedly in a loop (giving seed() the loop counter).

Post a reply to this message

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

>
>   If you are getting a regular pattern inside one single frame, it's
> certainly *not* because you did a "seed(frame_number)" at the beginning
> of your scene.
>
>   "seed(frame_number)" is not any more likely to produce regular
> patterns than "seed(0)" (or any other value for that matter) is.
>

I *think* you're correct in that, if there are *multiple* calls of rand() within
a single frame--using a single seed(frame_number)--then a pattern isn't
discernible. (I never actually did any definitive experiments to determine
that, though.) But of course it sounds logical.

However, if only ONE rand() value is called per frame, then a pattern is
definitely there as the animation progresses. So, extrapolating that to
multiple rand() calls per frame, there may (or may not) be patterns in *every*
rand() call--*from frame to frame.* Personally, I just don't know.

But as regards pulling just a single rand() per frame, I have to agree with
GregJohn.  Let me quote myself(!) from the above-mentioned newsgroup
post--about the core problem that prompted the post:

"...I *thought* that by simply throwing some multiplier value 'M'
at seed(M*clock) or seed(M*frame_number)--just one time in my POV scene, to use
for the entire animation--would give me 'obvious' random numbers from frame to
frame. Unfortunately, not so. There are, to my great surprise, clear
*almost*-repeating rand() patterns, no matter what seed values I use. And it
shows up quite quickly in animation--usually over 5 to 10 frames...."

"...It's especially obvious when using
strict integer multiples for M--3,6,9,12, for example. Actually, any multiple
of any integer. So simply using clock or frame_number to change the seed value
from frame to frame presents a problem, as they both count up linearly."

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.)

In reality, these patterns are not *exact* duplicates, of course. Depending on
how (and for what) a single rand() value is used in a scene, any resulting
pattern may not even be visually apparent.

KW

Post a reply to this message

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'

"clipka" <nomail@nomail> wrote:
> "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...
>
> 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...
>

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?

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.)

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?

This is all semi-informed guesswork, so *please* correct me where appropriate!
;-) I'm still trying mightily to get a clear--but simple!--picture of how seed
works, and what causes those patterns.

Ken W.

Post a reply to this message

> 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