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)

>  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