"Mark Wagner" <mar### [at] gtenet> wrote in message
news:pan### [at] gtenet...
> On Tue, 11 Feb 2003 12:03:28 -0500, Tom Melly quoth:
>
> > How many numbers are in the rand stream before it repeats itself, or is
> > this a meaningless question?
>
> 4.29 billion (2^32, to be exact).

Many thanks (so I shouldn't have given up at 500000 then? ;)

Post a reply to this message

"Warp" <war### [at] tagpovrayorg> wrote in message news:3e497ebc@news.povray.org...
> John VanSickle <evi### [at] hotmailcom> wrote:
> > #while(sA!=sB)
>
>   Are you completely sure that the same number will not appear twice
> in the stream without looping back to the beginning?
>   Naturally this might be so, but if the random number generator is made
> even with the slightest quality, the same number can repeat many times
> in the stream before it loops over.

Once I'd worked out what the code did, the same thought occured - is there
something in the way the stream is generated that makes that impossible? For
example, that a particular number is always followed by another fixed number?

Post a reply to this message

Tom Melly <tom### [at] tomandlucouk> wrote:
> Once I'd worked out what the code did, the same thought occured - is there
> something in the way the stream is generated that makes that impossible? For
> example, that a particular number is always followed by another fixed number?

  This depends a lot on how the random number generator is implemented.
There are (good) random number generators where the period is a lot larger
than the value range (eg. you get numbers between 0 and 2^64-1 from it, but
it gives you for example 2^256 numbers before starting over, which of course
means that the same number appears in the stream several times).
  As I don't have any idea what kind of algorithm pov's generator uses,
I can't say how it works there. Very simple generators start repeating
over immediately when the same number which has appeared before appears
again.

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Mark Wagner <mar### [at] gtenet> wrote:
>> How many numbers are in the rand stream before it repeats itself, or is
>> this a meaningless question?

> 4.29 billion (2^32, to be exact).

  Do you have any concrete proof or demonstration of this?

-- 
plane{-x+y,-1pigment{bozo color_map{[0rgb x][1rgb x+y]}turbulence 1}}
sphere{0,2pigment{rgbt 1}interior{media{emission 1density{spherical
density_map{[0rgb 0][.5rgb<1,.5>][1rgb 1]}turbulence.9}}}scale
<1,1,3>hollow}text{ttf"timrom""Warp".1,0translate<-1,-.1,2>}//  - Warp -

Post a reply to this message

Warp wrote:

> Tom Melly <tom### [at] tomandlucouk> wrote:
>> Once I'd worked out what the code did, the same thought occured - is
>> there something in the way the stream is generated that makes that
>> impossible? For example, that a particular number is always followed by
>> another fixed number?
> 
<snip>
>   As I don't have any idea what kind of algorithm pov's generator uses,
> I can't say how it works there. Very simple generators start repeating
> over immediately when the same number which has appeared before appears
> again.
> 

I found following in POV's express.cpp

static DBL stream_rand(int stream)
{
  next_rand[stream] = next_rand[stream] * 1812433253L + 12345L;

  return((DBL)(next_rand[stream] & 0xFFFFFFFFUL) / 0xFFFFFFFFUL);
}

An iterated random generator like this obiously cannot have a longer period 
than 2^sizeof(int).

- Micha

-- 
POV-Ray Objects Collection: http://objects.povworld.org

Post a reply to this message

>>>How many numbers are in the rand stream before it repeats itself
> 
>>4.29 billion (2^32, to be exact).
> 
>   Do you have any concrete proof or demonstration of this?

There is such proof. From the source (texture.cpp, don't know why there):

   static unsigned long int next_rand = 1;

   int POV_RAND()
   {
     next_rand = next_rand * 1812433253L + 12345L;

     return((int)(next_rand >> 16) & RNDMASK);
   }

I turned this into a program for testing the period as follows:

   #include <iostream.h>

   void main() {
     static unsigned long int next_rand = 1;
     static unsigned long int count = 0;
     do {
       next_rand = next_rand * 1812433253L + 12345L;
       count++;
     } while (next_rand!=1);
     cout << count;
   }

which returned 0. Now if you think this over, that means that it
is a full period generator.

-- 
max_trace_level 256media{absorption.02}camera{location<1,.3,1.7>}sphere{0
.8pigment{color.6}interior{media{emission<2,2,-2>absorption 2}}hollow}#macro
p(f,n)plane{n f-1finish{reflection<f,1f>}}#end p(1y)p(1z-x)p(-1,-z)p(1x-y)
// Mark Weyer

Post a reply to this message

> There is such proof. From the source (texture.cpp, don't know why there):

 From Micha Reiser's post I conclude that I might have looked in the
wrong place. The generator is the same, however.

-- 
max_trace_level 256media{absorption.02}camera{location<1,.3,1.7>}sphere{0
.8pigment{color.6}interior{media{emission<2,2,-2>absorption 2}}hollow}#macro
p(f,n)plane{n f-1finish{reflection<f,1f>}}#end p(1y)p(1z-x)p(-1,-z)p(1x-y)
// Mark Weyer

Post a reply to this message

Mark Weyer <wey### [at] informatikuni-freiburgde> wrote:
> which returned 0. Now if you think this over, that means that it
> is a full period generator.

  If this is so, then it means that there's actually just one single
fixed stream of pseudo-random numbers in POV-Ray, and with seed() you
just tell where to start taking numbers from this stream.
  (On implication of this is that if you have two streams generated
with different seed() values, they will both eventually start to give
the same numbers as the other.)

-- 
plane{-x+y,-1pigment{bozo color_map{[0rgb x][1rgb x+y]}turbulence 1}}
sphere{0,2pigment{rgbt 1}interior{media{emission 1density{spherical
density_map{[0rgb 0][.5rgb<1,.5>][1rgb 1]}turbulence.9}}}scale
<1,1,3>hollow}text{ttf"timrom""Warp".1,0translate<-1,-.1,2>}//  - Warp -

Post a reply to this message

"Warp" <war### [at] tagpovrayorg> wrote:
>   (On implication of this is that if you have two streams generated
> with different seed() values, they will both eventually start to give
> the same numbers as the other.)

AFAIK, preventing such behaviuor was never a desing goal of multiple RNG
streams in POV-Ray... They are there simply to protect scenes that rely on
RNG in placing/scattering objects etc.

On the other hand, the implication you point out may easily become of
importance for other scenes... IMHO one possible solution is to use the
RANDMAR generator I mentioned in my other post; it was specially designed to
provide users with ~32k independent streams.

Post a reply to this message

In article <3e4a67f6@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   If this is so, then it means that there's actually just one single
> fixed stream of pseudo-random numbers in POV-Ray, and with seed() you
> just tell where to start taking numbers from this stream.

Correct.


>   (On implication of this is that if you have two streams generated
> with different seed() values, they will both eventually start to give
> the same numbers as the other.)

Not correct. They will both repeat, and repeat the same sequence, but if 
they are initialized with different seeds, they will always have 
different numbers at any moment. Assuming you pull random numbers from 
each at an equal rate, anyway.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message