"Warp" <war### [at] tagpovrayorg> schreef in bericht 
news:4a12e846@news.povray.org...
>
> #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.
>
Maybe this is a simple solution:

#declare S1 = seed(1234);                   // Use the current RNG
#declare S1 = seed(1 * 1234);             // Use the current RNG
#declare S2 = seed(2 * 1234 * 4567); // Use second RNG algorithm
#declare S3 = seed(3 * 2^32 * 7890); // Use third RNG algorithm with big 
numbers

or if you want floats:

#declare S4 = seed(4 * 2^45 / 3^4);    //Use fourth float RNG algorithm

The parser can detect the difference easy, I think.

What about it?

Jaap Frank

Post a reply to this message

"Jaap Frank" <jjf### [at] casemanl> wrote:
> Maybe this is a simple solution:
>
> #declare S1 = seed(1234);                   // Use the current RNG
> #declare S1 = seed(1 * 1234);             // Use the current RNG
> #declare S2 = seed(2 * 1234 * 4567); // Use second RNG algorithm
> #declare S3 = seed(3 * 2^32 * 7890); // Use third RNG algorithm with big
> numbers
>
> or if you want floats:
>
> #declare S4 = seed(4 * 2^45 / 3^4);    //Use fourth float RNG algorithm
>
> The parser can detect the difference easy, I think.

With the current parser framework, this is far from easy. Let alone that it's
far from consistent either: Why should seed(2 * 1234 * 4567) give any different
result than seed(1 * 11271356)?

Post a reply to this message

Phoenex nous illumina en ce 2009-05-23 08:45 -->
> 
> What about this algorithm
> 
> Xn+1 = SXn - INT(SXn)
> 
> See
> 
> http://www.number.com.pt/index.html
> 
> 
> Phoenix
> 
> 
The test speed is totaly bogus!
You compare 2 algorythms speed with the followng:
They were not performed under the same OS
They were not compiled under the same compiler, let alone the same parameters.
and, worst of all, on different processors, one of witch is "Unknown"!

So, those results are totaly meaningless.

Also, the range of numbers generated should include zero.

Next, the quality values.
Totaly non random/chosen values CAN come very close to most of those values, and 
exactly at those in many cases. It's possible to have 
non-random/non-pseudorandom streams that will match the results shown.

Post a reply to this message

To Alain:

You are right. Do not compare algorithms without having all the parameters well
defined and with equality.
However, I think you should read previous messages, at least from the message
51.




Question: In previous speed tests? It was used ISAAC? Or ISSAC64?
It seems to me that was used to ISSAC.
Also, KISS is different from KISS64.
I would like to see the tests of speed compared only with the the algorithms:

KISS64
ALVO ( (int) Like the original idea )
ISSAC64

and other algorithms that work with 64 bit floating point.

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> cllpka
>
> I mean * p-values of * 0 *  zero and * 1 * one.
>
>
> Many people, say to get a good PRNG algorithm, several conditions are necessary:
>
> Must have a very large, which according to some, the more better.
> Must pass in a large number of mathematical/statistical tests.
> Should be easily portable and implementation.
>
> In my humble opinion, a * good * algorithm should have a period on the needs.

Yes, but your needs might not match the needs of other users. If all you need is
a trillion random numbers, where you are going to do the SAME EXACT operation on
each of those trillion numbers, then all you need is a period on the order of
trillions (e.g., a trillion squared). If you only need a thousand, then a
period of a million will probably suffice.

On the other hand, if you need ordered n-tuples (the simplest example relevant
to POV-Ray would be ordered triples as position or direction vectors), then
you'll need something on the order of a trillion to the n-th power, e.g., a
trillion to the 2*n power. Scientific applications routinely involve large n,
where even the best RNG's available are theoretically deficient, but we use
what we have because that's all we have. For POV-Ray, an example n might be 81,
where we're talking about sampling 81 pixels for anti-aliasing in a 9x9 grid.
Another example would be focal blur. Currently the jitter algorithm is pretty
weak, so visual artifacts can be trivially generated on purpose (above what we
would expect from a random sampling), and unfortunately, occasionally by
accident.

If you only need a thousand n-tuples (a very low number), you might think that a
period of a million is sufficient. But if n is 3, a million is already quite
insufficient.

So be careful when you say that a period is based on the needs: you might
convince yourself that a "really long" period is long enough, when in fact
it's very insufficient. Longer periods, if they can be attained at very little
additional cost (e.g., just a few extra bytes of storage, but no extra
computational time), should always be favored.

Post a reply to this message

"clipka" <nomail@nomail> schreef in bericht 
news:web.4a1aff2538187d7ecdd6a80f0@news.povray.org...
> "Jaap Frank" <jjf### [at] casemanl> wrote:
>> Maybe this is a simple solution:
>>
>> #declare S1 = seed(1234);                   // Use the current RNG
>> #declare S1 = seed(1 * 1234);             // Use the current RNG
>> #declare S2 = seed(2 * 1234 * 4567); // Use second RNG algorithm
>> #declare S3 = seed(3 * 2^32 * 7890); // Use third RNG algorithm with big
>> numbers
>>
>> or if you want floats:
>>
>> #declare S4 = seed(4 * 2^45 / 3^4);    //Use fourth float RNG algorithm
>>
>> The parser can detect the difference easy, I think.
>
> With the current parser framework, this is far from easy. Let alone that 
> it's
> far from consistent either: Why should seed(2 * 1234 * 4567) give any 
> different
> result than seed(1 * 11271356)?

What I meant was that with this system you can choose your RNG with the 
first number and you can at the same time fabricate very large numbers. 
Bigger then 2^32 if needed and then Warp can use all the possibilities he 
want. But if this is difficult to detect for the parser, then it's not a 
good way.
Of coarse there is no difference in 2*1234*4567 and 1*11271356, but with 
this system you choose your RNG at the same time.

Jaap Frank

Post a reply to this message

To Jay Fox

With a speed of 5 seconds to generate random 1000000000 numbers is needed more
than 1 year and six months to sweep sequentially (0.0000000000000001 to
0.9999999999999999) a period of 2^53 or about 10^16 with a computer to work
without stopping.

How?

5 sec * (1E16) / 1E9 / 3600 / 24 / 365 = 1.585489599 years

It is a long time working.

Another example:

If each number occupying one micrometer then the whole period is 10^16
micrometers or 10000000 km, a long distance.

However, as the generation of numbers is not sequential, it is natural
that after a generation over a year never runs some numbers and other will be
repeated.
Precisely what happens in the real world random.

So I still say that the importance of the size of the period is a question of
need in each case.

If this is the case with POVRay, then I fully agree with you, because I do not
know the POVRay and do not know which their needs.

If the POVRay works with integers, then it is better in fact a good random
number generator with integers.
The numbers generated by PRNGAlvo need to be converted in integers, and as such
it takes time to be consumed at work.

The algorithm PRNGAlvo was put in this discussion, always with an attitude of
helping, and to receive critics about it.

Post a reply to this message

Phoenex wrote:

> 
> Question: In previous speed tests? It was used ISAAC? Or ISSAC64?
> It seems to me that was used to ISSAC.
> Also, KISS is different from KISS64.
> I would like to see the tests of speed compared only with the the algor
ithms:
> 
> KISS64
	That's the one I used.

> ALVO ( (int) Like the original idea )
	Since we've seen that the results vary widely from platform to 
platform, I believe that it is interesting to look at several 
implementations. Note that the mathematical formula you gave in your 
first post corresponds with the "floor" implementation. I have no 
idea what exactly the TurboBasic "INT" function does and what's the 
closest C equivalent.

> ISSAC64
	No idea. I took Warp's implementation as is, so I don't know if 
it's ISAAC or ISSAC64.

		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)

"Phoenex" <rib### [at] sapopt> wrote:
> To Jay Fox
>
> With a speed of 5 seconds to generate random 1000000000 numbers is needed more
> than 1 year and six months to sweep sequentially (0.0000000000000001 to
> 0.9999999999999999) a period of 2^53 or about 10^16 with a computer to work
> without stopping.
>
> How?
>
> 5 sec * (1E16) / 1E9 / 3600 / 24 / 365 = 1.585489599 years
>
> It is a long time working.
>
> Another example:
>
> If each number occupying one micrometer then the whole period is 10^16
> micrometers or 10000000 km, a long distance.
>
> However, as the generation of numbers is not sequential, it is natural
> that after a generation over a year never runs some numbers and other will be
> repeated.
> Precisely what happens in the real world random.
>
> So I still say that the importance of the size of the period is a question of
> need in each case.
>
> If this is the case with POVRay, then I fully agree with you, because I do not
> know the POVRay and do not know which their needs.
>
> If the POVRay works with integers, then it is better in fact a good random
> number generator with integers.
> The numbers generated by PRNGAlvo need to be converted in integers, and as such
> it takes time to be consumed at work.
>
> The algorithm PRNGAlvo was put in this discussion, always with an attitude of
> helping, and to receive critics about it.

Perhaps you missed my point. As I said, if all you need is one million random
numbers, with which you will perform the same set of operations, then a period
of a trillion is fine, or even a billion. So 2^52 is certainly overkill
(doesn't hurt, but doesn't necessarily help).

However, let's take sets of ordered triples, for example. Using only
single-precision accuracy (23 bits, assuming an equal-spaced lattice), there
are 2^(23*3) or 2^69 ordered triples in the unit cube. With a period of 2^52,
your generator cannot possibly produce every possible ordered triple in
single-precision, let alone produce every possible ordered triple at double
precision with approximately equal probability. For that, you would need a
period of at least 2^156, and more realistically, probably greater than 2^180.
And what if you need two ordered triples? For example, two random points in
space, or a random point and a random direction? Then we might demand a period
of at least 2^312.

Keep in mind, I understand that we'll never exhaust the total period of the RNG
by actually drawing that many values. That's not the point. The point is
whether, given a totally random seed value, an RNG can produce a particular
ordered triple. If a particular ordered triple can never be produced, no matter
how the RNG is seeded, then the RNG has a serious flaw. Maybe not for you, maybe
not for most people. But apparently enough people are concerned about the flaws
in LCG's that we're having this discussion. People care.

POV-Ray is all about ordered triples: positions or direction vectors in 3-D
space, color vectors (ignorning alpha), etc. POV-Ray's default RNG should have
a period of AT LEAST 2^156, if not 2^312. But why aim for the bare minimum? If
a period of 2^1000 or 2^10000 can be had for little or no additional
computational power, and a pittance in terms of storage space (system memory is
typically measured in GB, so why are we so concerned about a few KB?), then why
settle for something far, far, less?

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> The algorithm PRNGAlvo was put in this discussion, always with an attitude of
> helping, and to receive critics about it.

Well, in the spirit of constructive analysis, I will say that Alvo is probably
better than a 32-bit LCG.

Just to set the record straight, Phoenex is right: Alvo is NOT an LCG.
Technically, anyway, and depending on how strictly you define an LCG.

An LCG uses an integer multiplier, such as 123, while Alvo uses a fractional
multiplier, such as 123.001. This can slightly perturb the lattice structure
that an ordinary LCG would have. I plan to investigate this further, as this
seems highly dependent on the exact value of the fractional portion of s (for
some values, the pertubations to the lattice will be negligible, while for
others, they should be fairly significant).

All the problems of LCG's are still going to be present in an Alvo setup, as far
as values lying on hyperplanes and what not. In Alvo, they'll just lie on
slightly bumpy hyperplanes, rather than perfectly flat ones. With a good choice
of s, the bumpiness of the hyperplanes will make the lattice structure seem to
disappear, so in this sense, I will admit that Alvo has a big advantage over a
traditional LCG. Finding good s is key, and not just for hiding the lattice
structure.

Let's use single precision math and analyze a simple example. I'll set
s=123.4567, and x = 0.4.

The first few iterates are:
x_0 = 0.400000006
x_1 = 0.382682800
x_2 = 0.244758606
x_3 = 0.217090607
x_4 = 0.801290512
x_5 = 0.924682617
x_6 = 0.158264160

Now, I'll pick the 1000-th value, to give time for the periodicity to set in
(flush out all the non-periodic rounding errors, so only periodic ones remain):
x_{1000} = 0.015350342
x_{1001} = 0.895102620
x_{1002} = 0.506416321
....
x_{1202} = 0.526624680
x_{1203} = 0.015350342
x_{1204} = 0.895102620

And there you have it, a period of 203.

Maybe a different s would fair better?

s           period
----------  ------
101.0101    339
 97.01      57
103.123     894
111.0123    781
 98.7654    480
100.0001    454
 47.1234    1564
 47.01      1891
 29.03      2189
 29.62118   2411
 29.62129   7



With a careful choice of s, I can get periods a few thousand long. Get s
slightly off (see the last two examples), and the period can be horrible.
Either way, using a floating point number with 23 bits of precision, the period
is quite disappointing.

Extending to double precision should *hopefully* give us an extra 30-ish bits of
periodicity on average, assuming a good choice of s, so periods in the billions
might be expected, even a few trillion. This makes double-precision Alvo seem
promising as a replacement for a 32-bit LCG, if you can find a good value for s
(please don't pick one at random! Find one you can prove the period for, and
find one you can prove has a virtually undetectable lattice).

If the period is greater than 2^32, it will probably do at least as well on
Diehard-style tests as a 32-bit LCG, and probably a little better because the
lattice structure is uneven.

Post a reply to this message