"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