Jay Fox

Thank you for your work.

This is what I need.

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

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

BIRTHDAY SPACINGS TEST
THE overlapping 20-tuples Bitstream TEST

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

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

Can you will continue to do more analysis?

Question: Are you a mathematician?

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

This have a very big period.

Post a reply to this message

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

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

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

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

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

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

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

Post a reply to this message

http://gamesbyemail.com/News/DiceOMatic

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

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

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

Post a reply to this message

Dr. Jay

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

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

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

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

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

and the internal calculations of a huge pressision

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

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

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


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

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

Great George Marsaglia.

Post a reply to this message

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.

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


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)