There is a way of writing natural numbers in "base n" that uses the digits 1..n instead of 0..(n-1). The reverse of such an expansion will always have the same length. 0 1 1 2 2 3 11 4 12 5 21 6 22 7 111 8 112 9 121 A 122 B 211 C 212 D 221 E 222 On Sat, Jun 2, 2012 at 11:47 AM, Henry Baker <hbaker1@pipeline.com> wrote:

Perhaps we should count the low order zero bits, remove them, reverse the rest of the number as below, and then put them back, i.e.,

For even n>0, reverse(n)=2*reverse(n/2).

This works for polynomials over GF(2), as well.

For n<0, we can still define reverse(n)=reverse(n')', where n'=lognot(n).

At 11:32 AM 6/2/2012, Henry Baker wrote:

...

In Lisp, there are a number of operations on the bit representation of 2's complement arbitrary-precision integers.

One function missing is that of "reverse" -- probably because no one came up with a good suggestion about what it should mean.

If I have a bit _vector_ (finite ordered sequence of bits) in Lisp, the length is well-defined, so the reverse of this bit vector is also well-defined; Lisp therefore does define the reverse of a bit _vector_.  For all finite bit-vectors x, we have the nice properties that reverse(reverse(x))=x; for the zero-length bit-vector x, reverse(x)=x.

What now should be the definition for the reverse of the bits of an integer?

If the integer is non-negative, then the function "integer-length(n)" returns the number of bits necessary to hold the integer n; if we take integer-length(n) as the length of the appropriate bit-sequence, then we get a well-defined result.  In particular, for n>0, reverse(n) is always odd, because the high-order bit has become the low order bit; for n=0, where integer-length(0)=0, so we have a zero-length sequence which is an identity for reverse -- i.e., reverse(0)=0.

So at least for odd n, n>0, reverse(reverse(n))=n, which is comforting.

Unfortunately, for even n, this definition of reverse(n) loses all the information about the number of low order 0's in the number, and so reverse(reverse(n))/=n for all n.

In order to get reverse(reverse(n))=n for all n>=0, reverse(n) needs to be 1-1 -- i.e., an injection -- i.e., it doesn't lose any information.

If we consider the the bits of the bignum n>=0 to be a polynomial p(x) with coefficients in GF(2), then there _are_ no negative elements, and the above definition works when p(0)=1.  After all, we reverse the list of polynomial coefficients all the time -- e.g., reversing a polynomial inverts all the roots: r->1/r; this requires r/=0 <=> p(0)=1.  So this representation gains us no new insight.

But what should the reverse(n) for the 2's complement integer n<0 be?

I think we still need reverse(reverse(n))=n, so we obviously need to have reverse(x)<0 for some x's.  Since the positive integers are already accounted for, such x's must be <0.  So reverse(n)<0 for n<0.

It would be nice if integer-length(reverse(n)) is O(integer-length(n)).

If we consider n<0 as simply an infinite bit string, perhaps reverse(n)=reverse(n')', i.e., we first complement n = n' = lognot(n), compute reverse(n'), and then lognot again to produce reverse(n')'.

This definition gets us reverse(-1)=reverse((-1)')'=reverse(0)'=0'=-1.

But what other properties do we want reverse(x) to have/preserve?

I haven't looked at 2-adic numbers; perhaps there is an insight there?

Does anyone here have any thoughts?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://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