>  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

Larry Hudson 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 timing
s 
> 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 th
e 
> same multiplication twice, I changed it to use a temporary variable 
> instead.
> 
	Funny, I did try it with a temp variable instead of two mults. It 
didn't change the timings so I assumed that my version of gcc was 
able to optimize it and kept the one closest to the algorithm.

	I hadn't tried with a cast instead of "floor" and it is indeed 
faster, though still not as fast as Kiss64.

	As for the reason why Kiss64 is faster on my computer, I suppose 
it's due to the fact that it is 64 bits and therefore able to do 
some operations in one instruction while 32 bit computers need 
several instructions to do the same thing.

> 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)
> 
	Interesting that on your computer the dbl version of Kiss64 should 
be so much slower than the int version while on mine the results are 
comparable.

	By simple curiosity, I've also added Warp's implementation of Isaac 
and here is the result (see attached code):

 > g++ -O3 -lm -o random random.cc IsaacRand.cc

 > ./random
Empty loop:          0ms
Kiss64 (int):     6623ms
Kiss64 (dbl):     5003ms
Alvo (floor):    21539ms
Alvo (cast):     14608ms
Alvo (tmp+cast): 14664ms
Isaac:           10540ms

		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)

>  > g++ -O3 -lm -o random random.cc IsaacRand.cc
> 
>  > ./random
> Empty loop:          0ms
> Kiss64 (int):     6623ms
> Kiss64 (dbl):     5003ms
> Alvo (floor):    21539ms
> Alvo (cast):     14608ms
> Alvo (tmp+cast): 14664ms
> Isaac:           10540ms
> 
	Upon reflection, those timing are ridiculous because there is no 
way to know what was optimized away by the compiler (like the empty 
loop: no matter how high I set LOOPS, that takes 0ms which is 
absurd). So here are the timings with no optimization (-O0):

Empty loop:       6324ms
Kiss64 (int):    13482ms
Kiss64 (dbl):    33679ms
Alvo (floor):    26223ms
Alvo (cast):     20113ms
Alvo (tmp+cast): 23512ms
Isaac:           33855ms

	Of course, this doesn't say anything about the quality of the 
random numbers generated.

		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)

>         By simple curiosity, I've also added Warp's implementation of Isaac 
> and here is the result (see attached code):

>  > g++ -O3 -lm -o random random.cc IsaacRand.cc

  I suggest adding -march=native in order for gcc to fully optimize it for
your platform. It might make a big difference, especially with this type
of code.
  (Also -lm is probably not needed. At least I don't need it here.)

>  > ./random
> Empty loop:          0ms
> Kiss64 (int):     6623ms
> Kiss64 (dbl):     5003ms
> Alvo (floor):    21539ms
> Alvo (cast):     14608ms
> Alvo (tmp+cast): 14664ms
> Isaac:           10540ms

  I tried running the program on my Pentium4 (with g++ -O3 -march=native)
and got the following results:

Empty loop:          0ms
Kiss64 (int):     2669ms
Kiss64 (dbl):     2643ms
Alvo (floor):     2098ms
Alvo (cast):      1767ms
Alvo (tmp+cast):  1766ms
Isaac:             690ms

  The speed seems to be pretty dependant on the CPU type being used...

  Out of curiosity, I also tried adding -mfpmath=sse to the compiler options,
and the results changed a bit:

Empty loop:          0ms
Kiss64 (int):     2687ms
Kiss64 (dbl):     2640ms
Alvo (floor):     2424ms
Alvo (cast):      1294ms
Alvo (tmp+cast):  1335ms
Isaac:             685ms

-- 
                                                          - Warp

Post a reply to this message

> So here are the timings with no optimization (-O0):

  I think comparing speed of unoptimized code is rather absurd and
useless. :)

-- 
                                                          - Warp

Post a reply to this message