with a modulus of br ± bs ± 1. Multiply-with-carry PRNGs with a multiplier of a are equivalent to LCGs with a large prime modulus of abr−1 and a power-of-2 multiplier b. A permuted congruential generator begins with a power-of-2-modulus LCG and applies an output transformation to eliminate the short period problem in the low-order bits. Comparison with other PRNGs The other widely used primitive for obtaining long-period pseudorandom sequences is the linear-feedback shift register construction, which is based on arithmetic in GF(2)[x], the polynomial ring over GF(2). Rather than integer addition and multiplication, the basic operations are exclusive-or and carry-less multiplication, which is usually implemented as a sequence of logical shifts. These have the advantage that all of their bits are full-period; they do not suffer from the weakness in the low-order bits that plagues arithmetic modulo 2k. Examples of this family include xorshift generators and the Mersenne twister. The latter provides a very long period (219937−1) and variate uniformity, but it fails some statistical tests. Lagged Fibonacci generators also fall into this category; although they use arithmetic addition, their period is ensured by an LFSR among the least-significant bits. It is easy to detect the structure of a linear-feedback shift register with appropriate tests such as the linear complexity test implemented in the TestU01 suite; a boolean circulant matrix initialized from consecutive bits of an LFSR will never have rank greater than the degree of the polynomial. Adding a non-linear output mixing function (as in the xoshiro256** and permuted congruential generator constructions) can greatly improve the performance on statistical tests. Another structure for a PRNG is a very simple recurrence function combined with a powerful output mixing function. This includes counter mode block ciphers and non-cryptographic generators such as SplitMix64. A structure similar to LCGs, but not equivalent, is the multiple-recursive generator: Xn = (a1Xn−1 + a2Xn−2 + ··· + akXn−k) mod m for k ≥ 2. With a prime modulus, this can generate periods up to mk−1, so is a useful extension of the LCG structure to larger periods. A powerful technique for generating high-quality pseudorandom numbers is to combine two or more PRNGs of different structure; the sum of an LFSR and an LCG (as in the KISS or xorwow constructions) can do very well at some cost in speed. See also List of random number generators – other PRNGs including some with better statistical qualitites