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