[boost] [random] [tr1] xor_combine min/max

Subject: [boost] [random] [tr1] xor_combine min/max
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2011-02-10 12:36:38

AMDG

Currently these are implemented as
std::min(_rng1.min(), _rng2.min()) and
std::max(_rng1.max(), _rng2.max()).
This is obviously wrong, although it
happens to work for taus88 which is
the only use of xor_combine right now.

I looked at boost/tr1/random.hpp and
it has a more complex implementation.
Unfortunately, I don't think it's
completely right either as computes
min/max(x ^ y) where
(_rng1.min() << s1) <= x <= (_rng1.max() << s1) and
(_rng2.min() << s2) <= y <= (_rng2.max() << s2)

Alas, when a random value is shifted left,
the low order bits are always zero, so
this algorithm may overestimate the bounds.

Also, when the shift causes either
base engine to lose bits, the algorithm
forces the max to std::numeric_limits::max.
This is clearly wrong if _rng1.min/max =
[0x80000000, 0x800000FF], s1 = 1, since this
ends up being equivalent to [0, 0xFF].

So, I have a couple of options
a) Require the base ranges to be something
    sane like [0, 2^k-1].  The advantage
    of this is that it's easy, and it's
    automatically guaranteed that the
    combined engine is equidistributed
    if the base engines are.
b) Somehow make it work.  It would be
    nice if it were fully general, but
    working out the bit-twiddling for
    this will be a pain and the code
    will probably end up unintelligible.
    I'd rather not do this unless it's
    really needed.  Are there any algorithms
    that need to xor numbers from non
    power-of-two ranges?  For example,
    is xoring the outputs of two LCG's
    ever useful?

Thoughts?

In Christ,
Steven Watanabe