=?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