Larry Hudson wrote:
> 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 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)

Jérôme M. Berger wrote:
>  > 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)

"Jérôme M. Berger" <jeb### [at] freefr> wrote:
>         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

"Jérôme M. Berger" <jeb### [at] freefr> wrote:
> 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

Warp wrote:
> "J�r�me M. Berger" <jeb### [at] freefr> wrote:
>>         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 i
t for
> your platform. It might make a big difference, especially with this typ
e
> of code.
	It doesn't change anything here. Remember that the gcc shipped with 
most 32-bits linux distros is configured to generate code for the 
original Pentium! In this case, forcing the compiler to optimize for 
your machine is usually a big win. On 64-bits platforms however, 
there is not that much difference between the first generation 
Athlon64 and the current generation.

>   (Also -lm is probably not needed. At least I don't need it here.)
> 
	I originally didn't put it, but I added it because it was needed 
for the C version. Now that the code is compiled as C++, you're 
right it's not needed any more.

>>  > ./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=nat
ive)
> 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...
> 
	So it seems...

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


-- 
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:
> "J�r�me M. Berger" <jeb### [at] freefr> wrote:
>> So here are the timings with no optimization (-O0):
> 
>   I think comparing speed of unoptimized code is rather absurd and
> useless. :)
> 
	In a way, that's true. However, it's not as useless as you imply. 
For example, in hindsight it is now obvious to me that the compiler 
removed the floating point division from Kiss64 (dbl), which 
explains why it was as fast as the integer version. So I've attached 
a new version of the benchmark that's specifically designed to foil 
these kind of optimizations that wouldn't happen in real life. And 
here are the timings (with -O3):

Empty loop:       3387ms	(was     0ms)
Kiss64 (int):     7348ms	(was  6623ms)
Kiss64 (dbl):    16045ms	(was  5003ms)
Alvo (floor):    22209ms	(was 21539ms)
Alvo (cast):     16258ms	(was 14608ms)
Alvo (tmp+cast): 15054ms	(was 14664ms)
Isaac:           10701ms	(was 10540ms)

	Notice how all tests except Isaac now take longer. I believe that 
the reason why Isaac isn't affected is because it calls a function 
that's in another file, which prevented gcc from optimizing as 
aggressively.

	This just goes to show that designing benchmarks is not as easy as 
it appears...

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

Post a reply to this message

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

Jérôme M. Berger wrote:
> Empty loop:       3387ms    (was     0ms)
> Kiss64 (int):     7348ms    (was  6623ms)
> Kiss64 (dbl):    16045ms    (was  5003ms)
> Alvo (floor):    22209ms    (was 21539ms)
> Alvo (cast):     16258ms    (was 14608ms)
> Alvo (tmp+cast): 15054ms    (was 14664ms)
> Isaac:           10701ms    (was 10540ms)
> 

	I just ran the tests on another computer with a Core2 duo and the 
results are rather interesting:

	With the same binary as above:
Empty loop:       2173ms
Kiss64 (int):     7541ms
Kiss64 (dbl):    15844ms
Alvo (floor):    24778ms
Alvo (cast):      8469ms
Alvo (tmp+cast):  8473ms
Isaac:            7810ms

	Notice how the last three are much faster?

	Recompiled with g++ 4.4 and -O3:
Empty loop:       1154ms
Kiss64 (int):     5944ms
Kiss64 (dbl):    12590ms
Alvo (floor):    22433ms
Alvo (cast):      7636ms
Alvo (tmp+cast):  8076ms
Isaac:            6428ms

	Slight improvement (10-20%) all around.

	Recompiled with g++ 4.4 and -O3 -ftree-vectorize:
Empty loop:       1085ms
Kiss64 (int):     5504ms
Kiss64 (dbl):    11663ms
Alvo (floor):    22039ms
Alvo (cast):      7730ms
Alvo (tmp+cast):  7730ms
Isaac:            5918ms

	Again, slight improvement all around except for Alvo. I'm not sure 
why Kiss64 gets improved though...

	And here is the system info:
 > uname -a
Linux rover 2.6.29-ARCH #1 SMP PREEMPT Sat May 9 14:09:36 CEST 2009 
x86_64 Intel(R) Core(TM)2 Duo CPU T5670 @ 1.80GHz GenuineIntel GNU/Linux

  > gcc --version
gcc (GCC) 4.4.0
Copyright (C) 2009 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.

		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)

"Jérôme M. Berger" <jeb### [at] freefr> wrote:
>         I just ran the tests on another computer with a Core2 duo and the 
> results are rather interesting:

>         With the same binary as above:
> Empty loop:       2173ms
> Kiss64 (int):     7541ms
> Kiss64 (dbl):    15844ms
> Alvo (floor):    24778ms
> Alvo (cast):      8469ms
> Alvo (tmp+cast):  8473ms
> Isaac:            7810ms

  One thing I can't understand: Why are the results *significantly* faster
in my Pentium4 (eg. the Isaac RNG seems to be 10 times faster, which is
a HUGE difference in speed), even though a Core2 duo should be faster
than a Pentium4? Something does not compute here.

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> http://warp.povusers.org/IsaacRand.zip

Just out of curiosity: Is that the same RNG that lives in MCPov?

I think I read something about you having supplied some RNG know-how or even
code to the montecarlo renderer.

Post a reply to this message

clipka <nomail@nomail> wrote:
> Warp <war### [at] tagpovrayorg> wrote:
> > http://warp.povusers.org/IsaacRand.zip

> Just out of curiosity: Is that the same RNG that lives in MCPov?

> I think I read something about you having supplied some RNG know-how or even
> code to the montecarlo renderer.

  Yes, I think the author used it when I suggested that he could use
something of higher quality than std::rand().

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> "Jérôme M. Berger" <jeb### [at] freefr> wrote:
> >         I just ran the tests on another computer with a Core2 duo and the
> > results are rather interesting:
>
> >         With the same binary as above:
> > Empty loop:       2173ms
> > Kiss64 (int):     7541ms
> > Kiss64 (dbl):    15844ms
> > Alvo (floor):    24778ms
> > Alvo (cast):      8469ms
> > Alvo (tmp+cast):  8473ms
> > Isaac:            7810ms
>
>   One thing I can't understand: Why are the results *significantly* faster
> in my Pentium4 (eg. the Isaac RNG seems to be 10 times faster, which is
> a HUGE difference in speed), even though a Core2 duo should be faster
> than a Pentium4? Something does not compute here.

What's the processor clock of your P4?
What's the typical processor clock of a modern multi-core CPU?

My Windows machine is an old, darn slow 3.4 GHz P4.
My Linux machine is a new, speedy 2.3 GHz AMD Phenom X4.

The modern Multi-Core CPUs win mainly due to...

- optimizations regarding caches, pipelining etc.
- providing multiple cores to run programs on

With a PRNG test suite, however, none of these bring any advantage. There are no
difficult-to-predict branch instructions; virtually no additional data to fetch
into the caches; no parallel threads to distribute the workload; all the CPU
has to do is to braindeadly execute one single thread of pure arithmetic
instructions.

I'm not too much surprised that in this case the bottleneck is sheer GHz power -
the only thing that hasn't been improved at all since the P4 (to the contrary!).

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
>   Yes, I think the author used it when I suggested that he could use
> something of higher quality than std::rand().

So one can say that it has been well-proven by now in a POV-Ray context (albeit
not as a SDL element).

Post a reply to this message

clipka <nomail@nomail> wrote:
> What's the processor clock of your P4?

  3.4 GHz.

> What's the typical processor clock of a modern multi-core CPU?

  Certainly not 340 MHz.

> The modern Multi-Core CPUs win mainly due to...

> - optimizations regarding caches, pipelining etc.
> - providing multiple cores to run programs on

> With a PRNG test suite, however, none of these bring any advantage. There are no
> difficult-to-predict branch instructions; virtually no additional data to fetch
> into the caches; no parallel threads to distribute the workload; all the CPU
> has to do is to braindeadly execute one single thread of pure arithmetic
> instructions.

  That doesn't really explain an entire order of magnitude of difference in
speed. This is especially so because the Pentium4 line is notoriously crappy
at things like bit shifting (because they removed the fast shift barrel from
the P4 line for whatever reason, and reintroduced it later in the Core line,
AFAIK).

  If a Core2 Duo runs simple integer operations at 1/10th the speed of
my Pentium4, I really don't want a Core2 Duo.

  However, I still suspect there's something else going on here.

> I'm not too much surprised that in this case the bottleneck is sheer GHz power -
> the only thing that hasn't been improved at all since the P4 (to the contrary!).

  I would find it rather disappointing if processors had gone 10 years
backwards in integer speed (and in fact floating point speed as well,
because the floating point tests were also significantly faster in my
computer).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> clipka <nomail@nomail> wrote:
>> What's the processor clock of your P4?
> 
>   3.4 GHz.
> 
	The Core2 I used for these tests runs at 1.8GHz. So we already have 
a factor of two here.

	What version of gcc are you using? If it's more recent than 4.2.3, 
it might be optimizing some computations away. You should retry with 
the latest source code I posted (at 11am French time), which is the 
one I used on the Core2. I'll try the old code on the Core2 later 
this evening when it's cooler (currently at 27°C and rising, I don't
 
want to start my laptop in these conditions...)

		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)

"J?r?me M. Berger" <jeb### [at] freefr> wrote:
> You should retry with 
> the latest source code I posted (at 11am French time), which is the 
> one I used on the Core2.

  I was indeed using the wrong version of your program. I took the correct
version and now the timings are much more like what I would expect.

  To recapitulate, your timings with the Core 2 Duo were:

Empty loop:       2173ms
Kiss64 (int):     7541ms
Kiss64 (dbl):    15844ms
Alvo (floor):    24778ms
Alvo (cast):      8469ms
Alvo (tmp+cast):  8473ms
Isaac:            7810ms

  With my P4, using gcc 4.3.1, the timings are:

Empty loop:       1221ms
Kiss64 (int):    32455ms
Kiss64 (dbl):    65092ms
Alvo (floor):    21088ms
Alvo (cast):     17937ms
Alvo (tmp+cast): 17939ms
Isaac:            6785ms

  The Kiss64 results are very significantly slower (both by a factor of
about 4). With the integer version that's not a big surprise because
long longs are necessarily a bit slow on a 32-bit system. The slowness
of the floating point version is a bit more surprising, though.

  Tha Alvo versions are slower only by a factor of about 2, except for
the floor version, which is actually faster on my system. Curious. Maybe
floor() can be done faster on a P4 than on a Core 2.

  The P4 still beats the Core 2 on the Isaac test (although not by much),
which might not be all that surprising given the raw clockrate difference.
This might also explain the significant difference in the empty loop test.

-- 
                                                          - Warp

Post a reply to this message

To Warp

Try to use the MOD function to do an algorithm like Alvo and giving the same
random numbers.
I dont think x = sx MOD 1.0 is the same as x = sx - INT(sx)
Thats one of many explanations why x = sx - INT(sx) algorithm is not an LCG.



To clipka

It is true that I have not spent much time in analysis of the seed mechanism,
even as other mathematical important analysis.
That is why I say on the page, that this algorithm should be subject to further
analysis by specialists.
However, I made 3 tests with your "s" that follow. Also with the Diehard test
the results are quit good with no p-values.


File generated with 2^24 bytes size
Test results by the ENT program with:

s=20000.1

Entropy = 7.999990 bits per byte.
Optimum compression would reduce the size
of this 16777216 byte file by 0 percent.
Chi square distribution for 16777216 samples is 234.59, and randomly
would exceed this value 81.57 percent of the times.
Arithmetic mean value of data bytes is 127.5264 (127.5 = random).
Monte Carlo value for Pi is 3.139572892 (error 0.06 percent).
Serial correlation coefficient is 0.000327 (totally uncorrelated = 0.0).

s=20000.0001

Entropy = 7.999989 bits per byte.
Optimum compression would reduce the size
of this 16777216 byte file by 0 percent.
Chi square distribution for 16777216 samples is 246.93, and randomly
would exceed this value 62.98 percent of the times.
Arithmetic mean value of data bytes is 127.5292 (127.5 = random).
Monte Carlo value for Pi is 3.140549932 (error 0.03 percent).
Serial correlation coefficient is 0.000338 (totally uncorrelated = 0.0).

s=20000.005
Entropy = 7.999989 bits per byte.
Optimum compression would reduce the size
of this 16777216 byte file by 0 percent.
Chi square distribution for 16777216 samples is 244.83, and randomly
would exceed this value 66.53 percent of the times.
Arithmetic mean value of data bytes is 127.4936 (127.5 = random).
Monte Carlo value for Pi is 3.141781602 (error 0.01 percent).
Serial correlation coefficient is -0.000335 (totally uncorrelated = 0.0).

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> Try to use the MOD function to do an algorithm like Alvo and giving the same
> random numbers.
> I dont think x = sx MOD 1.0 is the same as x = sx - INT(sx)
> Thats one of many explanations why x = sx - INT(sx) algorithm is not an LCG.

Mathematically speaking, the "MOD 1.0" operation - when applied to floats - is
*exactly* what the fraction operation does.

However, there is indeed a significant difference between an LCG and your
algorithm, in that an LCG operates in the integer domain, and thus its values
can never "grow fractional digits".

To do exactly the same as your algorithm does, an LCG would have to use a
fractional s. I'm not sure whether that still fits the bill of an LCG, but at
any rate it's no longer a *classic* LCG.

> However, I made 3 tests with your "s" that follow. Also with the Diehard test
> the results are quit good with no p-values.

Um... may I ask what precisely you mean by "no p-values"?

If I'm not totally mistaken the Diehard test *gives* you p-values, no matter
what. They're the output of the test suite, and their actual values require
some degree of interpretation.

Also note that test suites don't tell you whether your numbers are really as
good as random. They just examine your random number stream for *some* types of
patterns.

Post a reply to this message

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.
Must pass certain tests, and I think the ENT and Diehard enough.
Should in fact be easy portability and implementation.
It should also be readily understanding and above all fast.

However, I still think that the resulting random numbers, shall, after
comparison, have same characteristics as the numbers generated by real sources,
such as atmospheric noise or atomic radiation and outher.

I think the PRNGAlvo, satisfies these small principles.

Even as the mechanism of seed, there are several ways to solve the problem.
I am studying the subject, later I will say some thing about it.


I would, if possible, that the people than use Linux  operating system, can make
some tests with the TESTU01
that can find at:

http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

I think that is an excellent set of tests, although I do not known it, since I
work on Windows environment, and sloth have not yet installed.

Thanks

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> I think the PRNGAlvo, satisfies these small principles.

That may well be; however, given the lack of detailed analysis that would
substantially support this claim, and the availability of other, much better
tested and tried PRNGs with similar performance, I see absolutely no reason to
adopt PRNGAlvo as *the* new standard sophisticated RNG for POV-Ray.

I do see why you might be eager to have it established for this purpose, but I
guess others (like me) can't be blamed to currently regard PRNGAlvo as nothing
more than a private toy of yours - which may have good potential, but hasn't
proven that yet. To the contrary: Although my findings may turn out to be
insignificant in the end, but for now they do give rise to doubt about the
algorithm's quality.

The question isn't "would PRNGAlvo be good enough for POV-Ray" - the question
is, "would PRNGAlvo be significantly better for POV-Ray to prefer it over much
better analyzed, tested and tried algorithms". And to that question, I'd
clearly vote "no".

Post a reply to this message

clipka <nomail@nomail> wrote:
> Mathematically speaking, the "MOD 1.0" operation - when applied to floats - is
> *exactly* what the fraction operation does.

> However, there is indeed a significant difference between an LCG and your
> algorithm, in that an LCG operates in the integer domain, and thus its values
> can never "grow fractional digits".

  That would make a difference if floats with unlimited precision were
used. However, since regular floats are used, only a fixed amount of bits
are dedicated to the actual value (in the case of double-precision floating
point numbers, 53 bits). Thus it sounds pretty much like a LCG to me.

-- 
                                                          - Warp

Post a reply to this message

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


To Warp and Jérôme

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:
> To Warp and Jérôme
> 
> 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.
To make the machines work whenever possible with símbols, as in mathematics.

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

Jay

Another thing.

When you say a billion you mean 1000000000 or 1000000000000 ?

Here in Europe we use the long scale. A billion is 10^12.

10^9 is a thousand million.

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> 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.
> To make the machines work whenever possible with símbols, as in mathematics.
>
> Again, I ask. This is mathematical non periodic algorithm?

I see what you're getting at. Actually, if we had unlimited numerical precision,
we wouldn't need a fancy RNG that performs "iterations" and all that pesky work.
We'd just pick a suitable irrational number, and use its expansion in a
suitable base (e.g., base 2^52), and call it a day.

Unfortunately, we don't have unlimited precision. We could use a fancy arbitrary
precision math library, and several good ones are available. The pseudo-random
numbers thus generated would far exceed the quality of most if not all RNG's
already in use today. Unfortunately, the speed would be incredibly slow, to the
point of making these hypothetical RNG's useless.

So, we settle for what can be reasonably calculated with 16-bit, 32-bit, or
64-bit integer math, typically over the field of integers (e.g., the LCG and
MWC generators), but occasionally over the field of polynomials mod 2
(typically written as F2 or GF2, etc.). Linear feedback shift registers fall in
this latter category, and the Mersenne Twister is probably the current favorite
in this category (though I don't particularly care for it).

I think LFSR generators would be far more common if chip-makers included a
multiplicative equivalent of the XOR operator. In fact, were it not for this
lack of xor-multiplication, LFSR's would be my favorite, as you could make a
LFSR equivalent of a MWC generator, with very little effort.

Unfortunately, to do so today would require performing one or two dozen xor
operations just to generate a single high-quality 32-bit random number! The
Mersenne Twister uses a shortcut, where they perform two xor operations to
produce one very random bit and 31 modestly random bits. They then resort to
"tempering" to try to increase the randomness of those 31 questionable bits.
But if we had an xor-multiply, we wouldn't need to resort to tempering.

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> I believe that now is the time of our architects / engineers begin a new
> approach in building processors for the future.
> To make the machines work whenever possible with símbols, as in mathematics.

Um... definitely not.

Even doing exact math with something as "simple" as Geometric Numbers (the
mathematical equivalent of drawing things with compass and straightline) is a
far from trivial thing.

To exactly represent such numbers (and they're really just very basic examples
of how complicated exact numerical representation can get), you'll potentially
need an arbitrary amount of storage *per number*. And to actually do
*computations* with them (or even just *compare* them)... uhm!

Post a reply to this message

Jay Fox wrote:
> "Phoenex" <rib### [at] sapopt> wrote:
>> The algorithm PRNGAlvo was put in this discussion, always with an atti
tude of
>> helping, and to receive critics about it.
> 
> Well, in the spirit of constructive analysis, I will say that Alvo is p
robably
> 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.
> 
	I beg to disagree. An LCG is called that because it uses a linear 
equation followed by a congruence. The Alvo algorithm fits that 
description.

	However, I will admit that for properly chosen seeds, Alvo is 
probably better than an integer LCG of the same size. This is mostly 
due to the rounding errors that occur with floating point and won't 
occur with integers. This raises an additional issue: that of 
repeatability. Depending on your platform and compiler, you will get 
different rounding errors and therefore different sequences. 
Depending on your application, this may be a showstopper. For 
example, with the exact same source code, I get different values:

 > gcc -O3 -mfpmath=sse -lm -o alvo alvo.c
 > ./alvo
0.149126
 > gcc -O3 -mfpmath=387 -lm -o alvo alvo.c
 > ./alvo
0.917551

	I've attached the code if someone wants to play with it. Note that 
in 387 mode (i.e *not* the default here contrary to what I thought), 
you can also play with the setRoundMode and setPrecision functions 
to get yet different results.

		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)

Jay Fox wrote:
> On the other hand, 1234.56789 has a period of 116,032,317, and 123.4567
89 has a
> period of 1,078,493,612. Finally, a value of s of 12.3456789 has a peri
od in
> excess of a hundred billion (i.e., my program is still running, having 
already
> produced over 110 billion iterates).
> 
	Note that due to rounding error, you might never get the first 
value back. I.e it is quite possible for the algorithm to go: 1, 2, 
3, 2, 3, 2, 3...

		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)

Jay Fox wrote:
> I think LFSR generators would be far more common if chip-makers include
d a
> multiplicative equivalent of the XOR operator. In fact, were it not for
 this
> lack of xor-multiplication, LFSR's would be my favorite, as you could m
ake a
> LFSR equivalent of a MWC generator, with very little effort.
> 
	Uh, what would this xor-multiplication do? If you see "xor" as a 
bitwise addition, then the bitwise multiplication is done with the 
"and" operator, which all modern CPUs have (and in fact this analogy 
is even better than the xor-addition since bitwise multiplication 
does not have trouble with carry and therefore never overflows).

		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)

>  However, I will admit that for properly chosen seeds, Alvo is
> probably better than an integer LCG of the same size. This is mostly
> due to the rounding errors that occur with floating point and won't
> occur with integers. This raises an additional issue: that of
> repeatability. Depending on your platform and compiler, you will get
> different rounding errors and therefore different sequences.
> Depending on your application, this may be a showstopper. For
> example, with the exact same source code, I get different values:
>
>  > gcc -O3 -mfpmath=sse -lm -o alvo alvo.c
>  > ./alvo
> 0.149126
>  > gcc -O3 -mfpmath=387 -lm -o alvo alvo.c
>  > ./alvo
> 0.917551
>

Berger is right .

It is very difficult to work with double-precision floating point.

I already knew this, by the many tests carried out.

Depending on the CPU, the compiler or platform, with the same seed
you can get quite different results.

This is why it is very difficult to heuristic analysis.

Only mathematically analysis can get good results.

Alvo prng, in addition to trying to be a good generator of chaos, it still
offers the crazy on the computers of today.

Post a reply to this message

=?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeb### [at] freefr> wrote:
> Jay Fox wrote:
> > On the other hand, 1234.56789 has a period of 116,032,317, and 123.4567
> 89 has a
> > period of 1,078,493,612. Finally, a value of s of 12.3456789 has a peri
> od in
> > excess of a hundred billion (i.e., my program is still running, having
> already
> > produced over 110 billion iterates).
> >
>  Note that due to rounding error, you might never get the first
> value back. I.e it is quite possible for the algorithm to go: 1, 2,
> 3, 2, 3, 2, 3...
>
Yeah, I took that into account. I calculated the first iterate, then checked if
the next iterate matched (sounds silly, but it was part of a loop).

Then I checked the third and fourth to see if they matched the second value.
Then the fifth through eighth to see if they matched the fourth. Then 9th-16th
to see if they matched the 8th. And so on. If there's a period, it's guaranteed
to be found.

For example, one particular s value went through over a six billion iterates
before settling into a period of about 15 million. Weird, huh?

Post a reply to this message

And what you think about this:

On my computer and my poor compilor, applying to Alvo prng:

s = 12346.4951171875
x(0) = 0.5697481036186218

I get
x(1) = 0.3921793401241302


Again but with a differente x(0)
s = 12346.4951171875
x(0) = 0.2149915546178818

I get the same
x(1) = 0.3921793401241302

I have 2 diferent roots x(0) for the same x(1)

Perhaps making the experience with another platform, the results are not the
same.

However you can find on any other system these values for x(0).
Just know the random number that is repeated after a certain period
and look past the numbers. That is what I did

Now I can say.

After all not always a PRNG implemented on different machines gives the same
results.
Is this not also a form of randomness?

Post a reply to this message

=?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeb### [at] freefr> wrote:
> Jay Fox wrote:
> > "Phoenex" <rib### [at] sapopt> wrote:
> >> The algorithm PRNGAlvo was put in this discussion, always with an atti
> tude of
> >> helping, and to receive critics about it.
> >
> > Well, in the spirit of constructive analysis, I will say that Alvo is p
> robably
> > 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.
> >
>  I beg to disagree. An LCG is called that because it uses a linear
> equation followed by a congruence. The Alvo algorithm fits that
> description.
>
Well, I tried to qualify that it depends on how strictly you define an LCG. In
an integer LCG (or a floating point LCG with an INTEGER multiplier and
sufficient 0-padding in the lower bits of the floating point number), there is
never a loss of information in the lower bits. The upper bits are intentionally
discarded, which is the "congruential" part of an LCG.

However, when the multiplier is not an integer, then unless you use
infinite-precision math (which is to say, never), you necessarily will have to
truncate lower bits. That's truncation, not modular congruence. So it's not an
LCG in the strictest sense. The truncation is non-linear. And it's not exactly
modular congruence either (e.g. 1.211 mod 1.0 != 0.21). Take your pick, but in
my book, it's not an LCG.

But yes, it's basically the same thing. Apple or orange, it's still a fruit.
It's not a carrot or a rack of lamb.

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> And what you think about this:
>
> On my computer and my poor compilor, applying to Alvo prng:
>
> s = 12346.4951171875
> x(0) = 0.5697481036186218
>
> I get
> x(1) = 0.3921793401241302
>
>
> Again but with a differente x(0)
> s = 12346.4951171875
> x(0) = 0.2149915546178818
>
> I get the same
> x(1) = 0.3921793401241302
>
> I have 2 diferent roots x(0) for the same x(1)
>
> Perhaps making the experience with another platform, the results are not the
> same.
Actually, results like that are to be expected.

For example, let's use s=2.5

If x_{0}=1.0, then x_{1}=0.5 (i.e., 2.5 mod 1.0 = 0.5)
If x_{0}=0.6, then x_{1}=0.5 (i.e., 1.5 mod 1.0 = 0.5)
If x_{0}=0.2, then x_{1}=0.5 (i.e., 0.5 mod 1.0 = 0.5)

This is idealized, of course, because with rounding errors, those three
different 0.5 values might not be exactly equal to each other.

Post a reply to this message

=?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeb### [at] freefr> wrote:
> Jay Fox wrote:
> > I think LFSR generators would be far more common if chip-makers include
> d a
> > multiplicative equivalent of the XOR operator. In fact, were it not for
>  this
> > lack of xor-multiplication, LFSR's would be my favorite, as you could m
> ake a
> > LFSR equivalent of a MWC generator, with very little effort.
> >
>  Uh, what would this xor-multiplication do? If you see "xor" as a
> bitwise addition, then the bitwise multiplication is done with the
> "and" operator, which all modern CPUs have (and in fact this analogy
> is even better than the xor-addition since bitwise multiplication
> does not have trouble with carry and therefore never overflows).
>
>   Jerome
> --
> mailto:jeb### [at] freefr
> http://jeberger.free.fr
> Jabber: jeb### [at] jabberfr

I think you misunderstood what I meant by multiplication. I'm not talking about
"multiplying" 32 pairs of bits, one at a time. I'm talking about multiplying a
pair of 32-bit strings (or 16- or 8-bit, as the case might be).

Mutliplication:

  10010110
x 10110011
----------

Can be rewritten as

         10010110  1
        10010110   1
              0    0
             0     0
     10010110      1
    10010110       1
          0        0
+ 10010110         1
-----------------

The plus-sign is ordinary addition WITH CARRY for the field of integers, or xor
(which is addition WITHOUT CARRY) for the field of polynomials mod 2.

The Mersenne Twister effectively gets away with performing two addition
operations, whereas a multiply-with-carry operation uses (as its name implies)
a multiplication (and an addition, but the addition is a consequence of the
carry property of the underlying field, so it's not quite the same thing).

In this sense, the MWC should be superior, because its single multiplication is
equivalent to a dozen or more additions. Indeed, the MT authors had to add
tempering (hashing, essentially) to increase the randomness of their generator.
The MT is really a one-bit RNG (a really, really, really good one-bit RNG), and
the other 31 bits are in various stages of "random mixing" (the more significant
bits are better-mixed, so as a floating point source, it suffices I suppose),
which is why the tempering was needed.

Had they had access to an xor-multiply operation (not sure what its technical
name would be, though surely it must have one), then they could matched the MWC
in terms of randomness, with two simple operations, rather than the five or six
they need currently.

Post a reply to this message

Jay Fox

My first conclusion was this Prng:

x = n (s + x) - Int (n (s + x))

With x and s with double precision and n integer = 1,2,3 ,....

What do you think about this algorithm?

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> Jay Fox
>
> My first conclusion was this Prng:
>
> x = n (s + x) - Int (n (s + x))
>
> With x and s with double precision and n integer = 1,2,3 ,....
>
> What do you think about this algorithm?

Phoenex,

I think we should move any further discussion of your RNG to a new thread, so
that we don't clutter this thread any further. I feel we've drifted quite a bit
off-topic, and this thread is really important. I assume no one would object to
moving this particular side discussion?

Phoenex, why don't you create a new thread and link to a couple of the relevant
posts in this thread. Once the new thread is created, just leave a quick reply
here with a link to the new thread, so anyone who's interested can follow
along. Then we can move there to continue to discuss your RNG (and any related
side discussions ;-p ).

Post a reply to this message

"Phoenex" <rib### [at] sapopt> wrote:
> After all not always a PRNG implemented on different machines gives the same
> results.
> Is this not also a form of randomness?

It's an absolute No-Go for a RNG to be used for POV-Ray's rand() function.

For instance, one of my current WIPs features some spheres with randomly
oriented grooves, which I let POV-Ray re-calculate every time; in these
grooves, I let POV-Ray scatter other tiny objects, which I let POV-Ray generate
as an #include file on-the-fly only when I deem it necessary, and just #include
the file as generated by a previous run instead.

For this to work, I absolutely need the RNG sequences to be reproducible from
run to run.

But not only that - I also need the sequences to be reproducible regardless of
the computer system POV-Ray runs on, because I usually design and quick-preview
my scenes on a 32-bit Windows XP machine, but do the more time-consuming test
renders and final renders on a 64-bit Linux machine. And to save time, I
positively want to avoid having to re-calculate the #include files. Let alone
that I may also want to try several RNG seeds to see which produces the nicest
orientation of grooves - and in that case I positively want the Linux machine
to produce exactly the same orientation as the Windows machine.

Post a reply to this message

Jay Fox wrote:
> =?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeberger@f
ree.fr> wrote:
>> Jay Fox wrote:
>>> I think LFSR generators would be far more common if chip-makers inclu
de
>> d a
>>> multiplicative equivalent of the XOR operator. In fact, were it not f
or
>>  this
>>> lack of xor-multiplication, LFSR's would be my favorite, as you could
 m
>> ake a
>>> LFSR equivalent of a MWC generator, with very little effort.
>>>
>>  Uh, what would this xor-multiplication do? If you see "xor" as a
>> bitwise addition, then the bitwise multiplication is done with the
>> "and" operator, which all modern CPUs have (and in fact this analogy
>> is even better than the xor-addition since bitwise multiplication
>> does not have trouble with carry and therefore never overflows).
>>
>>   Jerome
>> --
>> mailto:jeb### [at] freefr
>> http://jeberger.free.fr
>> Jabber: jeb### [at] jabberfr
> 
> I think you misunderstood what I meant by multiplication. I'm not talki
ng about
> "multiplying" 32 pairs of bits, one at a time. I'm talking about multip
lying a
> pair of 32-bit strings (or 16- or 8-bit, as the case might be).
> 
> Mutliplication:
> 
>   10010110
> x 10110011
> ----------
> 
> Can be rewritten as
> 
>          10010110  1
>         10010110   1
>               0    0
>              0     0
>      10010110      1
>     10010110       1
>           0        0
> + 10010110         1
> -----------------
> 
> The plus-sign is ordinary addition WITH CARRY for the field of integers
, or xor
> (which is addition WITHOUT CARRY) for the field of polynomials mod 2.
> 
	Okay, I see what you mean now. Although it seems that this kind of 
operation is pretty domain-specific which might explain why nobody 
has gotten around to integrating it into a general purpose processor...

		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)