"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

Jay Fox

Thank you for your work.

This is what I need.

I did some accounts, with Microsoft Calculator and with the Excel2003 and the
results were very different.

However you are right. With s = 123.4567 and with x = 0.4 the test failed to
Diehard

BIRTHDAY SPACINGS TEST
THE overlapping 20-tuples Bitstream TEST

I had the perception that.
The seed has to be special. Why? I do not know.
If you see my page is not by chance that I do
s = seed + 12345.67890123456 0 <= seed <= 99999

I have the feeling that the whole part of "s" should have 4 to 5 digits.
Again thank you for your cooperation in such analysis.

Can you will continue to do more analysis?

Question: Are you a mathematician?

BTW see http://en.wikipedia.org/wiki/Multiply-with-carry

This have a very big period.

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> Jay Fox
>
> Thank you for your work.
>
> This is what I need.
>
> I did some accounts, with Microsoft Calculator and with the Excel2003 and the
> results were very different.
>
> However you are right. With s = 123.4567 and with x = 0.4 the test failed to
> Diehard
>
> BIRTHDAY SPACINGS TEST
> THE overlapping 20-tuples Bitstream TEST
>
> I had the perception that.
> The seed has to be special. Why? I do not know.
> If you see my page is not by chance that I do
> s = seed + 12345.67890123456 0 <= seed <= 99999
>
> I have the feeling that the whole part of "s" should have 4 to 5 digits.
> Again thank you for your cooperation in such analysis.
>
> Can you will continue to do more analysis?
I'm having fun with it so far.

As far as s goes, the more entropy it contains, the better the randomness of the
output. Also, the larger the value of s is, the better the randomness. However,
larger values of s seem to reduce the period. The default seed of
12345.67890123456 has a period of 31,752,133. Changing s to 12345.6789
increases the period to about 79,639,459.

On the other hand, 1234.56789 has a period of 116,032,317, and 123.456789 has a
period of 1,078,493,612. Finally, a value of s of 12.3456789 has a period in
excess of a hundred billion (i.e., my program is still running, having already
produced over 110 billion iterates).

I assume that this is because the larger values of s cause greater truncation of
the lower bits of s*x, which causes information loss. The lost information was
vital to achieving a longer period.

Based on these heuristics, my guess is that good values of s will be in the low
three-digit range. This should provide reasonable randomness (as good or better
than a 32-bit LCG) with a reasonable period (longer than 2^32). That might be
better than a 32-bit LCG, but it will be inferior to a 64-bit LCG or a 32-bit
lag-1 MWC generator.

> Question: Are you a mathematician?
In my spare time, I suppose. My degree is in computer science, with the
equivalent of a minor in mathematics and physics. I hope to pursue a masters in
statistics in the near future.

>
> BTW see http://en.wikipedia.org/wiki/Multiply-with-carry
>
> This have a very big period.
The MWC (and CMWC, complementary MWC) generators are currently my favorite. They
are by far the simplest to understand of all the long-period generators, and
with careful planning, they can be just as effective as anything else out
there, at least for non-cryptographic purposes. I hope that at least one
long-period MWC or CMWC gets considered in POV-Ray.

Post a reply to this message

http://gamesbyemail.com/News/DiceOMatic

Note, it only produces random integers in the range 1..6, and it can only
produce about 1.5 million random numbers a day, which is roughly 20 per second,
or 50 million nanoseconds per random number. So it's not particularly fast, or
uh, useful for that matter, but wouldn't it be fun...?

With proper modification to use 10-sided or 12-sided dice, and running 9 in
parallel (eight 12-sided, one 10-sided), we can generate 32-bit numbers, only
needing to discard about 0.113% of the results.

Or not. It... it was just an idea...

Post a reply to this message

Dr. Jay

Thanks again for your work.
You know, I will try to beat the MWC from PRNGAlvo.
I'm kidding.

When I say on my page that this algorithm is not mathematically regular people
contest.
But I still think so. but see.
When we talk about 3.141592 ........, we write PI.
                                                __
When we talk about 1.414213.......... we write V 2    (sqrt(2))
etc..

Of course, the machines still can not work with symbols and are limited to their
ability of physical memory.

Imagine that the random numbers generated by a PRNG with double precision are:

1 - aerwwew = 0.4674858488345345345 ......
2 - bgdnmdu = 1 / 3
3 - cfsrehhd = Pi
....
....
n - xrwmkfifhf = 0.4663728223339 .....

and the internal calculations of a huge pressision

1/3 is diferente from 0.33333333333333333333 and more rigorous
Pi is different from 3.1415926535897932384626433832795.... and more rigorous
and so on.

This is the spirit of this algorithm. And that is why I say that is a nos
periodic algorithm, mathematically speaking.

I believe that now is the time of our architects / engineers begin a new
approach in building processors for the future.


Again, I ask. This is mathematical non periodic algorithm?

I agree with you for MWC to be the choice for the POVRay
I think it should be easy to implement.

Great George Marsaglia.

Post a reply to this message