Warp wrote:
>   Let me as you the reverse question: Why should we *not* offer large
> seeds? Why limit the usability of the RNGs for no good reason?

It disturbs the syntax of the seed() call that exists even more. So it's 
mostly a matter that you already addressed: the syntax is ugly.

However, consider your longseed() example. Why not pass the random number 
stream to the longseed() routine.  seed() would still be used to seed and 
create a random number generator, but now you can reseed the generator with 
longseed().  Given that someone might want to do this with the current PRNG, 
it could just be called "reseed()".

Conflating "create a PRNG stream" with "set the seed" seems to be at the 
crux of the syntactic-ugliness problem.  Just a thought to stew upon.

-- 
   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:
> Warp wrote:
> >   Let me as you the reverse question: Why should we *not* offer large
> > seeds? Why limit the usability of the RNGs for no good reason?

> It disturbs the syntax of the seed() call that exists even more. So it's 
> mostly a matter that you already addressed: the syntax is ugly.

  But it's not like you would notice if you don't care about the extra
long seeds. If you are content with the 32-bit seeds, you can use seed()
in the exact same way as now. The long seeds would just be an extra which
doesn't disturb the currently existing syntax.

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
....
> #declare S1 = seed(1234); // Use the current RNG
> #declare S2 = seed(1234, 1); // Identical to the above.
> #declare S3 = seed(1234, 2); // Use second RNG algorithm.
....
From an end user point of view, this is good. Can it be optionaly expanded
again?
#declare S4 = seed (1234, 2, array[4] { 1, 2, 3, 4 } )
to cover any additional requirements.

Stephen S

Post a reply to this message

Sounds like an excellent way of making povray more powerful without breaking the
old syntax.

I also think your philosophy is purely correct about erring on the side of
giving it more power. Giving povray a military-grade RNG may prevent some jerk,
five years from now, from complaining that it doesn't have such a quality RNG.

I sometimes wonder if there were a debate about giving us powerful tools like
the trace() function.  I could imagine someone saying, "povray is a raytracer,
not a modeler", so why would you give it functions that are properly handled in
the modeling software?

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Warp wrote:
>>>   Let me as you the reverse question: Why should we *not* offer large
>>> seeds? Why limit the usability of the RNGs for no good reason?
> 
>> It disturbs the syntax of the seed() call that exists even more. So it's 
>> mostly a matter that you already addressed: the syntax is ugly.
> 
>   But it's not like you would notice if you don't care about the extra
> long seeds. If you are content with the 32-bit seeds, you can use seed()
> in the exact same way as now. The long seeds would just be an extra which
> doesn't disturb the currently existing syntax.

Certainly. You asked what was wrong. It's not a big problem. It's just 
slightly ugly, because you're trying to take a function that currently takes 
one seed-number, and turn it into a function that takes an optional PRNG 
identifier and a variable number of seed numbers. That's hard to do, 
syntactically, without making things ugly (such as by passing a single value 
that's actually a collection of values).

I'm just saying, perhaps having a different function would make it less 
ugly, as well as leaving open the possibility of being able to save and 
recall the PRNG's state. As Mr Berger pointed out, being able to dump out 
the state and reload it would be good too.  Whether you can do the 
dump/reload with the same function that sets the seed is another question, 
tho. I would imagine some PRNGs (RC4 leaps to mind) might take a state that 
needs to be in a specific form.

As an aside, how about allowing a string as a seed, perhaps with hex 
digit-pairs if POV doesn't support 0-255 in strings?

seed(23)
seed("18D8237")

That would seem to allow for the maximum number of bytes in a seed without a 
problem. If you made the state dump/reload also provide/require a similar 
string, you could easily write it to a file, ship it to macros, etc.

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

Warp nous illumina en ce 2009-05-19 13:11 -->
>   I have discussed with the team about the idea of adding alternative,
> higher-quality random number generators to POV-Ray 3.7. The current generator
> would be kept for backwards compatibility, but alternatives would be offered.
> 
>   The only thing which is a bit open is the exact syntax for this. So far
> this is the best idea:
> 
>   Enhance seed() so that it will take an optional second parameter, which
> would specify the RNG algorithm used. It would default to the current RNG.
> The rand() function would remain unchanged (internally it smartly selects
> the proper RNG from the type of seed given to it). In other words, you would
> be able to do, for example, like this:
> 
> #declare S1 = seed(1234); // Use the current RNG
> #declare S2 = seed(1234, 1); // Identical to the above.
> #declare S3 = seed(1234, 2); // Use second RNG algorithm.
> 
>   Additional algorithms might be added in the future. As mentioned, rand()
> would be unchanged, so its usage would be the same:
> 
> #declare RandomValue1 = rand(S1);
> #declare RandomValue2 = rand(S3);
> 
>   The current RNG uses a 32-bit seed, so a single parameter to seed() is
> enough to get all possible streams. However, higher-quality random number
> generators usually support much longer seeds, so it would be possible to
> choose among a vastly larger amount of RNG streams. Thus it would be very
> nice if larger seeds could be specified.
> 
>   The problem here is one of syntax. How to do this? Here are the ideas
> so far:
> 
> 1) Simply don't support seeds larger than 32-bit. This would work, but would
>    be a bit of a bummer because the capabilities of higher-quality RNGs
>    wouldn't be fully utilized.
> 
>    Alternatively, since seed() actually takes a (64-bit) float rather than
>    a 32-bit integer, the seed range could be somewhat enlarged by taking
>    the entire float range into account. This would allow using seeds of
>    about 52 bits. (But it's still a long shot from the thousands of bits
>    supported by higher-quality RNGs.)
> 
> 2) Make it possible to give either a regular float (as now), or an array
>    of floats as the first parameter of seed(). This way larger seeds can
>    be specified as an array.
> 
>    While a bit cumbersome, it's not as bad as it may sound at first, because
>    it's possible to do eg. this:
> 
>      #declare S = seed(array[4] { 1, 2, 3, 4 }, 2);
> 
>    It would still be nicer if something less cumbersome could be used,
>    though...
> 
> 3) Use an alternative function for long seeds. For example:
> 
>      #declare S = longseed(2, 1, 2, 3, 4);
> 
>    (where the first parameter specifies the RNG type used.)
> 
>    One small cosmetic problem with this is, however, that it's a bit
>    inconsistent with the seed() function. seed() takes the RNG type as
>    the second parameter, while longseed() would take it as the first
>    parameter. This can be a bit confusing.
> 
> 4) Create an entirely new syntax for specifying a group of values. This,
>    however, would be laborious and should preferably be avoided.
> 
> 
>   Opinions and additional ideas will be appreciated.
> 
An option could be to do something similar to the noise generators. You can 
select witch one to use in the global_settings section, with a default one.

It should be possible to add something like:
random_gemerator 2

The generator 1 would be the number 1, the actualy proposed one number 2, and 
there is room to add some other generators.

I also like the idea of been able to use a float as the seed. Providing a float, 
like 1.0 would automaticaly sellect the new generator.

Post a reply to this message

>  I have discussed with the team about the idea of adding alternative,
> higher-quality random number generators to POV-Ray 3.7. The current 
> generator
> would be kept for backwards compatibility, but alternatives would be 
> offered.
>
>  The only thing which is a bit open is the exact syntax for this. So far
> this is the best idea:
>
>  Enhance seed() so that it will take an optional second parameter, which
> would specify the RNG algorithm used. It would default to the current RNG.
> The rand() function would remain unchanged (internally it smartly selects
> the proper RNG from the type of seed given to it). In other words, you 
> would
> be able to do, for example, like this:
>
> #declare S1 = seed(1234); // Use the current RNG
> #declare S2 = seed(1234, 1); // Identical to the above.
> #declare S3 = seed(1234, 2); // Use second RNG algorithm.
>
>  Additional algorithms might be added in the future. As mentioned, rand()
> would be unchanged, so its usage would be the same:
>
> #declare RandomValue1 = rand(S1);
> #declare RandomValue2 = rand(S3);
>
>  The current RNG uses a 32-bit seed, so a single parameter to seed() is
> enough to get all possible streams. However, higher-quality random number
> generators usually support much longer seeds, so it would be possible to
> choose among a vastly larger amount of RNG streams. Thus it would be very
> nice if larger seeds could be specified.
>
>  The problem here is one of syntax. How to do this? Here are the ideas
> so far:
>
> 1) Simply don't support seeds larger than 32-bit. This would work, but 
> would
>   be a bit of a bummer because the capabilities of higher-quality RNGs
>   wouldn't be fully utilized.
>
>   Alternatively, since seed() actually takes a (64-bit) float rather than
>   a 32-bit integer, the seed range could be somewhat enlarged by taking
>   the entire float range into account. This would allow using seeds of
>   about 52 bits. (But it's still a long shot from the thousands of bits
>   supported by higher-quality RNGs.)
>
> 2) Make it possible to give either a regular float (as now), or an array
>   of floats as the first parameter of seed(). This way larger seeds can
>   be specified as an array.
>
>   While a bit cumbersome, it's not as bad as it may sound at first, 
> because
>   it's possible to do eg. this:
>
>     #declare S = seed(array[4] { 1, 2, 3, 4 }, 2);
>
>   It would still be nicer if something less cumbersome could be used,
>   though...
>
> 3) Use an alternative function for long seeds. For example:
>
>     #declare S = longseed(2, 1, 2, 3, 4);
>
>   (where the first parameter specifies the RNG type used.)
>
>   One small cosmetic problem with this is, however, that it's a bit
>   inconsistent with the seed() function. seed() takes the RNG type as
>   the second parameter, while longseed() would take it as the first
>   parameter. This can be a bit confusing.
>
> 4) Create an entirely new syntax for specifying a group of values. This,
>   however, would be laborious and should preferably be avoided.
>
>
>  Opinions and additional ideas will be appreciated.

IMO, there's no real need for access to larger seeds...
for example mersenne twister (MT19937) is seeded from
a single 32 bit value, even though it generates 624 values for
the internal state. There's more call for access to the RNG
state, but I can't see a way to keep compatability with 3.6 syntax.
So, for now...
RNG_Identifier = seed( Float | Float_Identifier [,Float | Float_Identifier])

I'd like to see a reworking of the syntax for this in 4.0,
in general I think it's bad to have numbered parameters as
was done for media scattering models. I prefer more descriptive
wording. I also think that using optional parameters between ()
as if they were between {} looks ugly.

Ultimately for 4.0 I'd like to see all the command-line, and
ini file options moved into SDL, so that command-line, and
ini file options are always considered to over-ride settings
in SDL. Then separate the scope of such commands into
sections... animiation{}, environment{},scene{},post_process{}.

Seed is probably one of the commands that would belong in
the environment section, along with camera, photons, and radiosity.
It's part of the starting state of the renderer.

RNG_Identifier = random_number_generator {
   [type POV36 | mersenne_twister]
   seed Float | Float_Identifier
};

It's a bit more verbose, but it's more amenable to be
extended in the future.

Post a reply to this message

>  Enhance seed() so that it will take an optional second parameter

I don't think that's a good way to do it. The problem is that the second 
parameter is confusing to people who don't already know the function. Even 
if the parameter is passed as a named constant, like RNG_SUCHANDSUCH (which 
in POV-Ray would probably require #including a file with a name you'll 
forget), this isn't the sort of thing that's useful as a parameter, because 
you're never going to want to change it dynamically. I think it would be 
simpler and clearer to use a separate function for different random number 
generators, like rand_suchandsuch( seed ).

> 1) Simply don't support seeds larger than 32-bit. This would work, but 
> would
>   be a bit of a bummer because the capabilities of higher-quality RNGs
>   wouldn't be fully utilized.

I would go with this, because it's easy for the user. In my life, I will 
never see more than 2^32 images, so that many different random number 
streams aren't necessary. The biggest advantages of other RNGs are the 
randomness of their behavior over multiple calls, not the number of 
different streams.

Keep in mind that, in practice, when you are writing a scene and need to 
come up with a seed you just type in a "random" number. If it gives bad 
results, you type in another one. Maybe instead you'll do something that's 
calculated, like frame_number, or the time of day, or something like that, 
but even in these cases, when are you going to run out of values?

At the very least, the simplicity of seed(345) should be available so users 
don't have to learn more than they already do to use a conceptually simple 
feature.

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

Post a reply to this message

>  But it's not like you would notice if you don't care about the extra
> long seeds. If you are content with the 32-bit seeds, you can use seed()
> in the exact same way as now. The long seeds would just be an extra which
> doesn't disturb the currently existing syntax.

As long as that is the case, I would go with whatever syntax is most useful 
for people who will be generating their scenes programatically, because 
they're the most likely to want to use that feature.

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

Post a reply to this message

Alain <ele### [at] netscapenet> wrote:

> An option could be to do something similar to the noise generators. You can
> select witch one to use in the global_settings section, with a default one.
>
> It should be possible to add something like:
> random_gemerator 2
>
> The generator 1 would be the number 1, the actualy proposed one number 2, and
> there is room to add some other generators.
>

I like this idea as well--very simple. Although, I don't see how the more
complex random generators that Warp has mentioned would be able to be
incorporated in such a scheme, IF we continue to use just seed() with a single
value (as we do now.) I.e., how would seed(23) provide or access all the
multiple variables that have been discussed?

I tend to agree that just about any syntax for more complex seeding(s) would be
OK. Those of us that need a more complex random generator will learn it's
usage; those who just need a 'good' generator will stick with seed(23). I think
it boils down to who needs what: Scientists/cryptographers/experimenters will
likely welcome more complex seed algorithms; the typical POV 'artisan' (like
me) just needs a (better) random-number generator, simply an improvement over
what we have now, with the same easy-to-use syntax.

KW

Post a reply to this message

=?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeb### [at] freefr> wrote:
>  There is a very common use case that you have forgotten: to be able
> to save the state of the random generator so that you can pick up
> from the same point later (in a subsequent animation frame for
> example). This requires two things:
> - A function that returns the current state of the generator;
> - The ability to initialize the generator with this state.
>
>  In that case, the seed may take the whole range of values supported
> by the algorithm.

Obviously it's not so common in the POV-Ray world :P

Anyway, if there would be intention to implement such a thing in POV-Ray SDL,
there would be no need for a "user-friendly" notation. So e.g. a base64-encoded
string of the raw state data would do as fine as any other notation.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> As an aside, how about allowing a string as a seed, perhaps with hex
> digit-pairs if POV doesn't support 0-255 in strings?

Being on it, methinks the string handling in POV needs reworking anyway... one
more for the POV-Ray "bug"tracker

Post a reply to this message

Jérôme M. Berger wrote:
>     In that case, the seed may take the whole range of values supported
 
> by the algorithm.

In many PRNGs, the seed and the state are distinct structures. Sometimes,
 
for example, the internal state maintains a certain pattern, and the 
algorithm stops working if you put arbitrary data into the state.

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

Slime wrote:
> simpler and clearer to use a separate function for different random number 
> generators, like rand_suchandsuch( seed ).

The advantage of changing the seeding rather than the rand() call is there's 
usually a very small number of seed()s, one for each stream.  If you find 
your trees aren't being placed properly, you can change the seed() for the 
tree placement and leave the seed for the leaf placement alone. And you 
don't need to track down every call to rand() and figure out which it is.

Putting it in the defaults is a good idea, but then it prevents using 
multiple different PRNGs in the same scene.

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

Alain <ele### [at] netscapenet> wrote:
> I also like the idea of been able to use a float as the seed. Providing a float,
> like 1.0 would automaticaly sellect the new generator.

Unfortunately, that's a no-go: POV-Ray's parser framework isn't designed to tell
the difference between 1 and 1.0.

Post a reply to this message

"Tim Attwood" <tim### [at] anti-spamcomcastnet> wrote:
> Seed is probably one of the commands that would belong in
> the environment section, along with camera, photons, and radiosity.
> It's part of the starting state of the renderer.

Not if it's used in some huge macro. In that case, it's part of the starting
state of the macro.


> RNG_Identifier = random_number_generator {
>    [type POV36 | mersenne_twister]
>    seed Float | Float_Identifier
> };
>
> It's a bit more verbose, but it's more amenable to be
> extended in the future.

I'd actually favor something like:

My_Random_Stream = Pov36_Rng(4711);
My_Random_Number = My_Random_Stream.getNext();

Other_Random_Stream = Mersenne_Twister_Rng(...);
Other_Random_Number = Other_Random_Stream.getNext();

i.e. sort of defining the different RNGs as different, independent objects
(which just "happen" to use the same method identifier to get the next value).

But that's "future music" as we'd say in German.

Post a reply to this message

"clipka" <nomail@nomail> wrote in message 
news:web.4a141b4b38187d7ef708085d0@news.povray.org...
> "Tim Attwood" <tim### [at] anti-spamcomcastnet> wrote:
>> Seed is probably one of the commands that would belong in
>> the environment section, along with camera, photons, and radiosity.
>> It's part of the starting state of the renderer.
>
> Not if it's used in some huge macro. In that case, it's part of the 
> starting
> state of the macro.

Sure, but a normal macro that isn't redefined multiple times
would belong in the environment section too... any subroutine
that can be compiled once would go there. With some
4.0 macro syntax to make it clear that is what is going on hopefully.

>> RNG_Identifier = random_number_generator {
>>    [type POV36 | mersenne_twister]
>>    seed Float | Float_Identifier
>> };
>>
>> It's a bit more verbose, but it's more amenable to be
>> extended in the future.
>
> I'd actually favor something like:
>
> My_Random_Stream = Pov36_Rng(4711);
> My_Random_Number = My_Random_Stream.getNext();
>
> Other_Random_Stream = Mersenne_Twister_Rng(...);
> Other_Random_Number = Other_Random_Stream.getNext();
>
> i.e. sort of defining the different RNGs as different, independent objects
> (which just "happen" to use the same method identifier to get the next 
> value).
>
> But that's "future music" as we'd say in German.

That would be hard on the parser, every RNG command would be
at the top level, if they're inside a common constructor then at the top
level there's just the check for the constructor.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> As an aside, how about allowing a string as a seed, perhaps with hex 
> digit-pairs if POV doesn't support 0-255 in strings?

  You could only specify integer literals like that. You couldn't do
something like this, which isn't even rare:

#declare S = seed(1234 + frame_number);

with a long seed.

-- 
                                                          - Warp

Post a reply to this message

StephenS <nomail@nomail> wrote:
> #declare S4 = seed (1234, 2, array[4] { 1, 2, 3, 4 } )

  If the extra seed values are given as additional parameters, there's no
need for an array, as they could be given as direct parameters, ie:

#declare S4 = seed (1234, 2, 1, 2, 3, 4 );

  That could work, although it's still a small cosmetic problem that the
seed is specified as the 1st, 3rd, 4th, etc. parameters, so there's an odd
discontinuity there...

-- 
                                                          - Warp

Post a reply to this message

Kenneth <kdw### [at] earthlinknet> wrote:
> I like this idea as well--very simple. Although, I don't see how the more
> complex random generators that Warp has mentioned would be able to be
> incorporated in such a scheme, IF we continue to use just seed() with a single
> value (as we do now.) I.e., how would seed(23) provide or access all the
> multiple variables that have been discussed?

  seed() can be changed so that it can take any amount of parameters.

  If the current RNG is being used, it would just take the first parameter
and ignore the rest. If RNGs with support for larger seeds are used, they
would take as many parameters as given (up to the maximum amount supported
by the RNG).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   You could only specify integer literals like that. You couldn't do
> something like this, which isn't even rare:

Good point. Probably still the easiest format if you want to dump internal 
state and then reload it later.

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

Tim Attwood <tim### [at] anti-spamcomcastnet> wrote:
> IMO, there's no real need for access to larger seeds...

  There are RNGs and applications for them where larger seeds are needed.

  Someone mentioned encryption, where the seed acts as the encryption key.
Sure, you could always argue "nobody will ever need encryption in POV-Ray".
You could make the same argument about half of POV-Ray's features.

  I'm pretty sure there are things like stochastic simulations where seeds
larger than 2^32 could be useful.

  As I mentioned in another post, it makes little sense to me to stop the
user from accessing the features of the RNG simply because someone can't
think of good uses for them. And I really think that going the old route
of "2^32 random number streams ought to be enough for anybody" is not smart
in the long run.

> for example mersenne twister (MT19937) is seeded from
> a single 32 bit value

  If that's true, then IMO that lessens the usefulness of MT.

  The RNG I'm considering supports very large seeds (up to something like
8192-bit seeds if so configured) and has very high quality and speed.

-- 
                                                          - Warp

Post a reply to this message

Slime <fak### [at] emailaddress> wrote:
> > 1) Simply don't support seeds larger than 32-bit. This would work, but 
> > would
> >   be a bit of a bummer because the capabilities of higher-quality RNGs
> >   wouldn't be fully utilized.

> I would go with this, because it's easy for the user.

  I'm not sure if you got the idea, but the addition of new RNGs with
larger seeds would *not* change the current usage of RNGs in any way.
You could still use the current RNG in the *exact* same way as currently.

  If you don't care about which RNG is used or how large the seeds are,
then you can simply ignore the extra stuff and use seed() and rand()
exactly like now.

  I really don't see how limiting the seeding is "easy for the user".

> In my life, I will 
> never see more than 2^32 images, so that many different random number 
> streams aren't necessary.

  How many of the features supported by POV-Ray have you ever used in your
life? Would you like those features you haven't used to be removed because
you have never used them?

  Does it bother you that POV-Ray supports more features than what you use?
If not, then why would it bother you if POV-Ray supported long seeds,
especially if you don't even have to know how they are specified and you
can still use seed() and rand() like currently?

  Can you agree that *some* people might find useful uses for longer seeds
even if you don't, exactly in the same way as some people find useful uses
for other POV-Ray features that you have never used?

-- 
                                                          - Warp

Post a reply to this message

>  If you don't care about which RNG is used or how large the seeds are,
> then you can simply ignore the extra stuff and use seed() and rand()
> exactly like now.
>
>  I really don't see how limiting the seeding is "easy for the user".


That's fine then. It's just the simple syntax which is easy.

>  Can you agree that *some* people might find useful uses for longer seeds
> even if you don't, exactly in the same way as some people find useful uses
> for other POV-Ray features that you have never used?

I can agree that they might. However, I can't imagine a situation where it 
would be useful, so the point to consider is whether it's worth the time to 
implement the feature (and fix any bugs it may have afterwards). At least we 
should come up with an imaginary case where someone might benefit from this 
functionality.

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

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Slime <fak### [at] emailaddress> wrote:

> > In my life, I will
> > never see more than 2^32 images, so that many different random number
> > streams aren't necessary.
>
>   How many of the features supported by POV-Ray have you ever used in your
> life? Would you like those features you haven't used to be removed because
> you have never used them?
>
>   Does it bother you that POV-Ray supports more features than what you use?
> If not, then why would it bother you if POV-Ray supported long seeds,
> especially if you don't even have to know how they are specified and you
> can still use seed() and rand() like currently?
>
>   Can you agree that *some* people might find useful uses for longer seeds
> even if you don't, exactly in the same way as some people find useful uses
> for other POV-Ray features that you have never used?
>

Good argument, I have to say. (I'll probably never get around to using all the
features POV offers, unless I were to spend full-time with it--which isn't so
different than I what I do now!)

KW

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Tim Attwood <tim### [at] anti-spamcomcastnet> wrote:
> > for example mersenne twister (MT19937) is seeded from
> > a single 32 bit value
>
>   If that's true, then IMO that lessens the usefulness of MT.
>
>   The RNG I'm considering supports very large seeds (up to something like
> 8192-bit seeds if so configured) and has very high quality and speed.
>
> --
>                                                           - Warp

Actually, most common *implementations* of the Mersenne Twister use a single
32-bit value to seed the generator. In actuality, the "seed" of the Mersenne
Twister can be any 2^19937 bit value, except all 1 bits. In practice, we use a
single 32-bit value to "randomly" generate the seed, where the "random" part is
usually an LCG. Some specific implementations do allow seeding the with the full
range of valid seeds. The method of seeding is a separate issue from whether the
MT is a good RNG.

In practice, you're going to want a simple seeding system that uses a single
32-bit value, for people who just need data that "looks" as random as possible.
Then you will want a full-range seeding system (such that it places the RNG
anywhere in its period), for people who need data that IS as random as
possible.

For raytracing, I'll venture a guess that 99.9% or more of our users just need
data that LOOKS as random as possible. Very few people need data that truly IS
as random as possible. The distinction is subtle.

Consider shuffling a deck of cards. Each time we shuffle the deck, use a truly
random process to determine the shuffling, like thermal noise or radioactive
decay or whatever. This is basically what happens when you seed a high quality
RNG. Regardless of how you seed the RNG, as long as the seed is essentially
random, the output will be completely random for most practical purposes.

So, back to the card shuffling example: Do this 16 times, to get 2^4 (most
likely) different shufflings of the deck. (I'm using 2^4 to help exaggerate the
problem of insufficient seed space.)

Now consider each of these 16 shufflings as corresponding with a particular
"seed" in the range 0 to (2^4)-1. Each of these 2^4 shuffled decks appears
completely random, because they ARE completely random (remember, the thermal
noise or whatever?). Any one of these would be fine, if all we want is a
raytraced image of a poker game or whatever, one that LOOKS random.

However, there are only 16 possible shufflings out of 52!, or about 8*10^67. So
not every possible shuffling can be acheived from our initial seeds. Not even
close!

But in reality, every possible shuffling could appear from a truly random
process. So the 2^4 seeds are not sufficient to provide a poker hand that comes
from a proper random distribution. It LOOKS completely random, if all you want
is something that "looks" like a random shuffling of a deck. But, for example,
if none of those 16 shuffled decks contains a royal flush for some player, then
no matter how you seed the RNG, no one will EVER get a royal flush.

In other words, if I'm a poker player with money on the line, then I want a game
that guarantees that every possible shuffle of the deck is possible. With only
16 seeds, then the game can only guarantee that the deck will be one of 16
pre-determined random shufflings of the deck. Like I said, the distinction is
subtle, and I suppose some people won't think the distinction matters at all.

Post a reply to this message

clipka nous illumina en ce 2009-05-20 10:54 -->
> Alain <ele### [at] netscapenet> wrote:
>> I also like the idea of been able to use a float as the seed. Providing a float,
>> like 1.0 would automaticaly sellect the new generator.
> 
> Unfortunately, that's a no-go: POV-Ray's parser framework isn't designed to tell
> the difference between 1 and 1.0.
> 
> 
> 
Bummer!

Another possibility:
If the seed is an integer, use the current generator.

If the seed value is a float, use the improved generator. Here, a float would be 
deffined as any value that can't be represented as a 32 bits integer: to big or 
having a fractional part.

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
>   As I mentioned in another post, it makes little sense to me to stop the
> user from accessing the features of the RNG simply because someone can't
> think of good uses for them. And I really think that going the old route
> of "2^32 random number streams ought to be enough for anybody" is not smart
> in the long run.

Wasn't there *some* talk about a major rework of the SDL anyway?

So I'd say, never mind about "huge seeds" for now, and leave that up for a
next-generation SDL to take care of.

Post a reply to this message

clipka <nomail@nomail> wrote:
> Warp <war### [at] tagpovrayorg> wrote:
> >   As I mentioned in another post, it makes little sense to me to stop the
> > user from accessing the features of the RNG simply because someone can't
> > think of good uses for them. And I really think that going the old route
> > of "2^32 random number streams ought to be enough for anybody" is not smart
> > in the long run.

> Wasn't there *some* talk about a major rework of the SDL anyway?

> So I'd say, never mind about "huge seeds" for now, and leave that up for a
> next-generation SDL to take care of.

  No, I disagree with the idea that we should simply not support long seeds
for the simple reason that deciding on the handiest syntax is not immediately
obvious. I would certainly want access to the whole RNG even if doing so
would require writing a few more characters.

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
>   No, I disagree with the idea that we should simply not support long seeds
> for the simple reason that deciding on the handiest syntax is not immediately
> obvious. I would certainly want access to the whole RNG even if doing so
> would require writing a few more characters.

.... and me, I'd consider a higher-quality RNG too important to waste time on
special syntax whose sole *real* benefit would be the ability to turn POV-Ray
into a strong cryptographic application or a poker game engine.

BTW, not only users, but also other parts of POV-Ray could benefit from a good
RNG. Subsurface scattering, for instance, currently suffers dearly from the
lack of a good random number source.

You can always wreck your brain on that super-duper-seeding syntax in a later
increment.

I'm not saying "never ever support it" - all I'm saying is "it's not nearly
important enough to waste time on it right now".

Post a reply to this message

As an alternative suggestion, how about treating PRNGs
syntactically more like an object, such as

#declare R = prng {type 1 seed 42}

It gives more flexibility to the syntax as the specified
attributes may now depend on the type of PRNG (possibly some
PRNGs could have additional settings such as number of bits
used or similar?).

Obviously, "seed(n)" should be treated as "prng{type 0 seed n}",
although it might print a warning about obsolete syntax.

The seed attribute would be convenient 32-bit seed, but some PRNGs may
support specifying specialized seed values via additional attributes 
long_seed or a different syntax for seed such as "seed {1,2,3,4}".
This syntax could probably be shared for most complex PRNGs.

There may also be additional type-specific attributes for
initializing the complete "state" of a PRNG (from messages in
this thread I infer the state may encompass more information
than even a long seed value?). However, to actually allow
persisting the state, it would be necessary to have a
function such as rand_state(R).

Post a reply to this message

>> >   As I mentioned in another post, it makes little sense to me to stop 
>> > the
>> > user from accessing the features of the RNG simply because someone 
>> > can't
>> > think of good uses for them. And I really think that going the old 
>> > route
>> > of "2^32 random number streams ought to be enough for anybody" is not 
>> > smart
>> > in the long run.
>
>> Wasn't there *some* talk about a major rework of the SDL anyway?
>
>> So I'd say, never mind about "huge seeds" for now, and leave that up for 
>> a
>> next-generation SDL to take care of.
>
>  No, I disagree with the idea that we should simply not support long seeds
> for the simple reason that deciding on the handiest syntax is not 
> immediately
> obvious. I would certainly want access to the whole RNG even if doing so
> would require writing a few more characters.

I'm just worried that extended syntax for some things might become
ugly and undocumented.

Something like...

PRNG_Id = prng {
   [type pov36 | mersenne_twister]
   seed Float | Float_Id | FloatArray | FloatArray_Id
}
wouldn't be too bad. It's just not 3.6 compatible.

For 3.7 to be 3.6 compatible, it makes sense to have it be

PRNG_Id = seed(Float | Float_Id [, Float | Float_Id [, Array | Array_Id]])

where the second number is an optional PRNG type,
and the first seed number is ignored if there is an array provided
to seed the state with.

Post a reply to this message

Tim Attwood wrote:
> For 3.7 to be 3.6 compatible, it makes sense to have it be

Or, you could just have two ways to create a PRNG stream. One with the old 
syntax, one with the new.

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

Warp wrote:
> StephenS <nomail@nomail> wrote:
>> #declare S4 = seed (1234, 2, array[4] { 1, 2, 3, 4 } )
> 
>   If the extra seed values are given as additional parameters, there's 
no
> need for an array, as they could be given as direct parameters, ie:
> 
> #declare S4 = seed (1234, 2, 1, 2, 3, 4 );
> 
>   That could work, although it's still a small cosmetic problem that th
e
> seed is specified as the 1st, 3rd, 4th, etc. parameters, so there's an 
odd
> discontinuity there...
> 
	Well, you could always say that if more than one parameter is 
given, then the first parameter identifies the algorithm and the 
other parameters make up the seed:

// Same as now:
#declare S1 = seed (1234);

// Equivalent to the above:
#declare S2 = seed (1, 1234);

// Use new algorithm number 2 with a longer seed:
#declare S3 = seed (2, 1234, 5678);

		Jerome
-- 
mailto:jeb### [at] freefr
http://jeberger.free.fr
Jabber: jeb### [at] jabberfr

Post a reply to this message

Attachments:
Download 'us-ascii' (1 KB)

Warp wrote:
>   The RNG I'm considering supports very large seeds (up to something li
ke
> 8192-bit seeds if so configured) and has very high quality and speed.
> 
	As a simple matter of curiosity, which RNG are you considering?

		Jerome
-- 
mailto:jeb### [at] freefr
http://jeberger.free.fr
Jabber: jeb### [at] jabberfr

Post a reply to this message

Attachments:
Download 'us-ascii' (1 KB)

Among other things, Warp saw fit to write:

> 3) Use an alternative function for long seeds. For example:
> 
>      #declare S = longseed(2, 1, 2, 3, 4);
> 
> [...]
> 
> 4) Create an entirely new syntax for specifying a group of values. This,
>    however, would be laborious and should preferably be avoided.

Somewhere between 3 and 4:

3.5) Create a sort of "concatenate numbers" function, that would allow
really large numbers, maybe with and arbitrary number of parameters. If the
function is named "numconcat":

seed(1234)   // current
seed(1234,1) // same as above
seed(1234,2) // new RNG with small seed
seed(numconcat(1234,5678,90),2) // new RNG with large seed

The function numconcat need not be a "real" concatenation, i.e., there's no
reason why numconcat(1234,5678,90)=1234567890, it should just create a
large number out of smaller ones.

Hmm... maybe that's what option 4 meant from the beginning, though.

-- 
light_source{9+9*x,1}camera{orthographic look_at(1-y)/4angle 30location
9/4-z*4}light_source{-9*z,1}union{box{.9-z.1+x clipped_by{plane{2+y-4*x
0}}}box{z-y-.1.1+z}box{-.1.1+x}box{.1z-.1}pigment{rgb<.8.2,1>}}//Jellby

Post a reply to this message

Tim Attwood <tim### [at] anti-spamcomcastnet> wrote:
> PRNG_Id = seed(Float | Float_Id [, Float | Float_Id [, Array | Array_Id]])

  Btw, just use "float expression" to indicate anything that evaluates to
float in a comprehensive way.

-- 
                                                          - Warp

Post a reply to this message

"Jérôme M. Berger" <jeb### [at] freefr> wrote:
> [-- text/plain, encoding quoted-printable, charset: UTF-8, 14 lines --]

> Warp wrote:
> >   The RNG I'm considering supports very large seeds (up to something like
> > 8192-bit seeds if so configured) and has very high quality and speed.
> > 
>         As a simple matter of curiosity, which RNG are you considering?

  The ISAAC RNG, of which I have some experience and have found to be of
very decent quality (should be rather cryptographically strong) and very
fast, and with a very large period. Also according to my experience it's
faster than Mersenne Twister without the need for special compiler options
(the MT can be made as fast, but only if you create a special SSE version
of it).

  (Of course speed is not really crucial here, but the quality should be
very good.)

-- 
                                                          - Warp

Post a reply to this message

Christian Froeschlin <chr### [at] chrfrde> wrote:
> #declare R = prng {type 1 seed 42}

  I'm not sure if with the POV-Ray parser that 'seed' keyword would cause
a clash with the seed() function. Some names can be used in different
contexts, but I'm not sure this is one of those cases.

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
>   (Of course speed is not really crucial here, but the quality should be
> very good.)

Given that there might be some good use for a more sophisticated RNG inside
POV-Ray's rendering engine possibly heading our way (thinking of SSLT here, or
maybe addition of some montecarlo elements), I guess speed *should* be
considered an issue.

So to hear that the RNG you have in mind *is* fairly fast, that's good news.

Post a reply to this message

What about this algorithm

Xn+1 = SXn - INT(SXn)

See

http://www.number.com.pt/index.html


Phoenix

Post a reply to this message

Warp wrote:
> "J�r�me M. Berger" <jeb### [at] freefr> wrote:
>> [-- text/plain, encoding quoted-printable, charset: UTF-8, 14 lines --]
> 
>> Warp wrote:
>>>   The RNG I'm considering supports very large seeds (up to something like
>>> 8192-bit seeds if so configured) and has very high quality and speed.
>>>
>>         As a simple matter of curiosity, which RNG are you considering?
> 
>   The ISAAC RNG, of which I have some experience and have found to be of
> very decent quality (should be rather cryptographically strong) and very
> fast, and with a very large period. Also according to my experience it's
> faster than Mersenne Twister without the need for special compiler options
> (the MT can be made as fast, but only if you create a special SSE version
> of it).
> 
>   (Of course speed is not really crucial here, but the quality should be
> very good.)
> 
	Thanks, that's very interesting to know.

		Jerome

PS: If anybody wants more information on ISAAC, Google gave me this 
page: http://burtleburtle.net/bob/rand/isaacafa.html
-- 
mailto:jeb### [at] freefr
http://jeberger.free.fr
Jabber: jeb### [at] jabberfr

Post a reply to this message

"Jérôme M. Berger" <jeb### [at] freefr> wrote:
> PS: If anybody wants more information on ISAAC, Google gave me this 
> page: http://burtleburtle.net/bob/rand/isaacafa.html

  My C++ version should be much easier to use, though:

http://warp.povusers.org/IsaacRand.zip

-- 
                                                          - Warp

Post a reply to this message

Phoenex wrote:
> 
> What about this algorithm
> 
> Xn+1 = SXn - INT(SXn)
> 
> See
> 
> http://www.number.com.pt/index.html
> 
	That's a basic LCG (same as the current POV algorithm) except that 
it's implemented in floating point. It will have the same 
shortcomings...

		Jerome
-- 
mailto:jeb### [at] freefr
http://jeberger.free.fr
Jabber: jeb### [at] jabberfr

Post a reply to this message

>  That's a basic LCG (same as the current POV algorithm) except that
> it's implemented in floating point. It will have the same
> shortcomings...


Jerôme,

This algorithm is not a basic LCG.
If you Check carefully the tests, you can not find weaknesses or shortcomings.
In addition it is very, but very fast.

Post a reply to this message

Phoenex <rib### [at] sapopt> wrote:
> This algorithm is not a basic LCG.
> If you Check carefully the tests, you can not find weaknesses or shortcomings.

  Unless someone explains in more detail how it's different from a basic
LCG, I can't see why it's different. It's doing the basic LCG formula:

seed = (seed*a + b) mod 1.0

with a value of 0.0 for b (which is interesting, but doesn't really
differentiate it much from a basic LCG).

  I wonder if the "quality" of this RNG is not simply caused by its
typical usage: The highest bits of the result are used, rather than
the lowest bits, which is a rather common mistake on integral LCGs.

> In addition it is very, but very fast.

  It might be pretty fast if you want to generate random floating point
numbers in the range [0.0, 1.0]. It beats integral RNGs in that with
them you have to perform a floating point division to scale them to the
[0.0, 1.0] range, which is slow.

  OTOH, it wouldn't be very fast to generate integer random numbers.

  The remaining question would be the quality of the randomness.

-- 
                                                          - Warp

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> What about this algorithm
>
> Xn+1 = SXn - INT(SXn)
>
> See
>
> http://www.number.com.pt/index.html

Interestingly simple formula; however, it seems to me that not very much
research has gone into it.

We can observe that the claim

  "Theoretically and mathematically speaking, this algorithm is non periodic"

is substantially invalid at least for some cases of S. The author himself (I
presume that's you?) explicitly concedes that cases giving S = INT(S) are
problematic. However, we find no reasoning why this is so, let alone why the
same problem does not apply to other conditions for S.

Furthermore, the author adds to the seed a "magic" value to generate the
parameter S governing the sequence of random numbers, without giving any
reasoning for his choice of this "magic" number.

There is also no mention of analysis on the influence of rounding on the
algorithm.

The author also claims that

  "The numbers are generated with double precision (64 bit - 8 Bytes), and
therefore a period of 2^53 bit"

However, the author fails to provide evidence that shorter periods can be ruled
out completely.

Analysis of the PRNG seems to have been limited to running a few standard test
suites, and even their reports seem poorly understood by the author.

If this is not the case, then the author has made a poor job at communicating
his findings about the algorithm's quality.


As a mater of fact, a few test runs reveal that the algorithm does in fact have
some more flaws regarding the choice of S; for instance, S = 20000.1 results in
a remarkable distribution pattern, with all (!) 0.1-width intervals from
[0.1;0.2[ to [0.5;0.6[ having a probability of >10%, and all (!) others a
probability of <10%, while the very same pattern is seen inverted with S =
20000.0001. With S = 20000.005, a similar pattern can be seen again, except
that the high-probability intervals are those from [0.2;0.3[ to [0.6;0.7[.

Given that such cases are rather easy to create, this suggests that the author
of the algorithm did not really invest too much time into analyzing the effect
of seeding on the quality of his PRNG - which in turn gives rise to the
assumption that other bad news are still hidden in that area.


Or, to make a long story short:

This algorithm looks like yet another poorly-researched home-brewn PRNG to me,
which may be good enough for some applications, but looks far from well enough
understood to make it *the* future high-quality PRNG for POV-Ray. Sorry pal.

For PRNGs, the same basic rule holds true as for cryptographic algorithms: Never
trust that ingenious system you just invented all on your own - you never know
what pitfalls it may have in stake that you haven't though of. Instead, rather
use a system that has been around a while, even if it has some known
limitations - chances are those are the only issues, so at least you know your
enemy.

Post a reply to this message

Phoenex wrote:
>>  That's a basic LCG (same as the current POV algorithm) except that
>> it's implemented in floating point. It will have the same
>> shortcomings...
> 
> 
> Jerôme,
> 
> This algorithm is not a basic LCG.

	Like Warp said, it uses exactly the same equation as an LCG, so 
that makes it an LCG.

> If you Check carefully the tests, you can not find weaknesses or shortcomings.
> In addition it is very, but very fast.
> 
	I just ran a quick test that shows that this algorithm is actually 
3 to 4 times *slower* than Kiss64. See attached source file. Test 
was run like this:

 > gcc -O3 -lm -o random random.c

 > ./random
Empty loop: 0ms
Kiss64 (int): 6622ms
Kiss64 (dbl): 5003ms
Alvo: 21021ms

 > gcc --version
gcc (GCC) 4.2.3 (4.2.3-6mnb1)
Copyright (C) 2007 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There 
is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR 
PURPOSE.

 > uname -a
Linux wraith 2.6.24.7-desktop-2mnb #1 SMP Thu Oct 30 14:31:33 EDT 
2008 x86_64 AMD Athlon(tm) 64 X2 Dual Core Processor 3800+ GNU/Linux


		Jerome
-- 
mailto:jeb### [at] freefr
http://jeberger.free.fr
Jabber: jeb### [at] jabberfr

Post a reply to this message

Attachments:
Download 'us-ascii' (2 KB)

Jérôme M. Berger wrote:
>     I just ran a quick test that shows that this algorithm is actually 3 
> to 4 times *slower* than Kiss64. See attached source file. Test was run 
> like this:
> 
>  > gcc -O3 -lm -o random random.c
> 
>  > ./random
> Empty loop: 0ms
> Kiss64 (int): 6622ms
> Kiss64 (dbl): 5003ms
> Alvo: 21021ms
> 
Interesting...  I played with your test example on my system and got 
rather different results.  My system is much older and slower -- 32-bit 
Athlon 2000+, old version of Linux & gcc.  (I won't bother going into 
the reasons why I still use Fedora 3, I do have and use newer versions 
of Linux.  But this is what I still use to read these newsgroups.)

Anyway, I had to reduce your loop count by a factor of 10 to get timings 
similar to yours, but I found the Alvo was _faster_ than the Kiss64.

Then I made a couple changes, first, instead of the call to floor() I 
used a simple type cast to int.  Second, since the original performs the 
same multiplication twice, I changed it to use a temporary variable instead.

The original relevant line:
     alvo_x = (alvo_s * alvo_x) - floor (alvo_s * alvo_x);

My first change:
     alvo_x = (alvo_s * alvo_x) - (int)(alvo_s * alvo_x);

My second change:  (Also adding "double alvo;" to the variable list)
     alvo = alvo_s * alvo_x;
     alvo_x = alvo - (int)alvo;

Here are the timings on my last run:
100000000 loops:
Empty loop: 255ms
Kiss64 (int): 4568ms
Kiss64 (dbl): 8980ms
Alvo: 3626ms
Alvo: 2646ms:   (int with 2 mults)
Alvo: 325ms:    (int with 1 mult)

Of course, this comparison is completely irrelevant to the discussion of 
RNG's for POV-Ray.  I certainly don't have enough knowledge of the 
subject to have an opinion about it.  It also has nothing to do with the 
quality of these RNGs, but I thought the differences we got for the 
relative timings for this specific test example was interesting.

      -=- Larry -=-

Post a reply to this message

Larry Hudson <org### [at] yahoocom> wrote:
> Interesting...  I played with your test example on my system and got 
> rather different results.  My system is much older and slower -- 32-bit 
> Athlon 2000+, old version of Linux & gcc.

  The fact that the test program uses the 'long long' type might have
a *lot* to do with that. Long longs are slow in 32-bit systems, for rather
obvious reasons (being (sort of) *emulated* 64-bit integers, after all).

  One thing I like about the ISAAC RANG is that it has a *huge* period,
yet it uses 32-bit operations and is very fast.

-- 
                                                          - Warp

Post a reply to this message