Klimov and Shamir have a few papers on what they call "T-functions" and describe cheap ones with maximal period. "In particular, we show that for any n the mapping x → x + (x² ∨ C) (mod 2ⁿ) is a permutation with a single cycle of length 2ⁿ iff both the least significant bit and the third least significant bit in the constant C are 1." http://www.wisdom.weizmann.ac.il/~ask/ On Tue, Apr 7, 2015 at 1:15 PM, Warren D Smith <warren.wds@gmail.com> wrote:
Usual way (w=machine word length in bits, all operations modulo 2^w): x=0; do{ x+=1; }until(x==0);
Some other ways: x=0; do{ x+=C; }until(x==0); /*C is any odd residue modulo 2^w*/
x=0; do{ x*=A; x+=B; }until(x==0); /*B is any odd residue modulo 2^w, and A=1(mod 4)*/
The above ways all feature "unidirectional information flow" from the right toward the left end of x, regarded as binary.
If w=16 then this works: x=0; do{ x = 59276 - (x XOR (x>>1)); }until(x==0); For most w, it seems like there exist A with 0<A<w and B with 0<B<2^w such that x=0; do{ x = B - (x XOR (x>>A)); }until(x==0); works, but suitable values of A and B are not necessarily easy to find. [x>>A means x shifted rightward A bits. Also can be written floor(x/(2^A)).] Note this method has information flowing in *both* directions.
If w=16 this also works: x=0; do{ x*=3; x = 7080 + (x XOR (x>>1)); }until(x==0); and so does this: x=0; do{ x = 39027 + (x XOR (x>>1)); }until(x==0); and so does this: x=0; do{ x*=5; x = 60985 + (x XOR (x>>1)); }until(x==0); and so does this: x=0; do{ x*=5; x = 31241 + (x XOR (x>>3)); }until(x==0); and so does this: x=0; do{ x*=11415; x = 39110 + (x XOR (x>>8)); }until(x==0); etc, etc.
Almost certainly there are plenty of 32-bit counters of the above ilk, but I have not found any.
If w=64, then this counts thru all 2^64-1 *nonzero* w-bit numbers: x=1; do{ x = x XOR (x>>9); x = x XOR (x<<7); }until(x==1); But there are no 32- and 16-bit counters of this type (for nonzero words).
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com