[math-fun] Unusual ways to count thru all w-bit numbers
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)
If this is C++, then the x == 0 test is technically unsound. In the C++ standard, the value of an integer post addition overflow is technically undefined, and the compiler has the right to optimize away your test. -----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Warren D Smith Sent: Tuesday, April 07, 2015 4:16 PM To: math-fun@mailman.xmission.com Subject: [math-fun] Unusual ways to count thru all w-bit numbers 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
What sort of application is envisaged for such counters, and why would "unidirectional" algorithms be unsuitable? WFL On 4/7/15, David Wilson <davidwwilson@comcast.net> wrote:
If this is C++, then the x == 0 test is technically unsound. In the C++ standard, the value of an integer post addition overflow is technically undefined, and the compiler has the right to optimize away your test.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Warren D Smith Sent: Tuesday, April 07, 2015 4:16 PM To: math-fun@mailman.xmission.com Subject: [math-fun] Unusual ways to count thru all w-bit numbers
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Quoting Fred Lunnon <fred.lunnon@gmail.com>:
What sort of application is envisaged for such counters, and why would "unidirectional" algorithms be unsuitable? WFL
My cipher HPC processes "arbitrarily long" arrays. It makes three passes over the array, in three different orderings. The algorithm requires that the indexing can also run backwards relatively cheaply, so simple schemes are best. The first pass indexing is ordinary counting from I=0 to 2^K-1. The second pass uses the ordering I' = 5I + 1 (mod 2^K). The third pass uses a finite field of size 2^K, and the indexing order I' = xI (mod x^K + ... + 1). The modulus is the smallest mod2 polynomial of degree K for which x is a primitive root, going through all 2^K-1 non-zero values. The present program needs all the data to be in memory at once. I'd like to be able to process the data somewhat sequentially, to do files bigger than memory. The first ordering is trivial, and I've worked out a scheme for the second ordering, but the third ordering has resisted my efforts. A giant sort is the best-so-far-- not especially appetizing. Rich
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
participants (5)
-
David Wilson -
Fred Lunnon -
Mike Stay -
rcs＠xmission.com -
Warren D Smith