Warp <war### [at] tagpovrayorg> 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