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