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

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




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

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

>     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