[math-fun] The reverse of the bits of a negative integer?
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?
On Saturday 02 June 2012 19:32:24 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.
It seems to me that reversing should really be defined on non-negative dyadic rationals, as reflection in the decimal (binary) point. So the reverse of 1 is .1 = 1/2, the reverse of 2 = 10 is .01 = 1/4, etc. This way, trailing zeros don't introduce ambiguity. In that case, if n is negative then its reverse ends in an infinite string of 1s. So, e.g., the reverse of -1 = ...1111 is 0.111..., which of course equals 1. In general, reverse(-n) = reverse(~(n-1)) = ~reverse(n-1) = 1-reverse(n-1) when n is a non-negative integer. Here the first "~" means "flip all the bits before the binary point" and the second "~" means "flip all the bits after the binary point". Of course, once we allow this sort of thing reversing is no longer injective. But, aha, for the exact same reason it is also no longer well defined. Suppose we write 1 not as 1.0000... but as 0.1111..., and then -1 not as ...1111.0000... but as ...1110.1111...; then its reversal becomes ...1111.0111... = ...1111.1000... = -1/2. Which, not coincidentally, equals -reverse(1). In general, perhaps we "should" adopt the convention that a positive number ends with an infinite string of 0s, and a negative number ends with an infinite string of 1s; then negation is just bitwise complement, and reversal commutes with negation. -- g
The proper definition of bit-reversal depends on the application for which it is needed. In the case of Fast Fourier Transform, the index is an N-bit integer that may be regarded as a modulo 2^N pointer into the numeric array of length 2^N. It is automatically twos-complement. Here the proper bit reversal consists of reversing all N bits, including leading zeros. -- Gene
________________________________ From: Gareth McCaughan <gareth.mccaughan@pobox.com> To: math-fun@mailman.xmission.com Sent: Saturday, June 2, 2012 5:01 PM Subject: Re: [math-fun] The reverse of the bits of a negative integer?
On Saturday 02 June 2012 19:32:24 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.
It seems to me that reversing should really be defined on non-negative dyadic rationals, as reflection in the decimal (binary) point. So the reverse of 1 is .1 = 1/2, the reverse of 2 = 10 is .01 = 1/4, etc. This way, trailing zeros don't introduce ambiguity.
In that case, if n is negative then its reverse ends in an infinite string of 1s. So, e.g., the reverse of -1 = ...1111 is 0.111..., which of course equals 1. In general, reverse(-n) = reverse(~(n-1)) = ~reverse(n-1) = 1-reverse(n-1) when n is a non-negative integer. Here the first "~" means "flip all the bits before the binary point" and the second "~" means "flip all the bits after the binary point".
Of course, once we allow this sort of thing reversing is no longer injective.
But, aha, for the exact same reason it is also no longer well defined. Suppose we write 1 not as 1.0000... but as 0.1111..., and then -1 not as ...1111.0000... but as ...1110.1111...; then its reversal becomes ...1111.0111... = ...1111.1000... = -1/2. Which, not coincidentally, equals -reverse(1).
In general, perhaps we "should" adopt the convention that a positive number ends with an infinite string of 0s, and a negative number ends with an infinite string of 1s; then negation is just bitwise complement, and reversal commutes with negation.
-- g _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I agree with Gareth. After thinking about it some more, here's my final recommendation: We are considering finite bit sequences embedded in an infinite stream, both on the left (high order bits) and the right (low order bits below the "binary point"). In the case of "positive" integers, the bit stream is 0's far to the left (high order) and 0's below the binary point to the right (low order). One way to do reverse(n) would be to flip the number about the binary point, which would make the reverse of an integer not an integer. Furthermore, we have an ambiguity in the case of numbers with an odd number of bits in the finite portion -- e.g., "1" itself. We can't place the single "1" bit on top of the binary point, but must place it to one side or the other. Since we really don't want to deal either with this ambiguity or with fractional numbers, our only other choice is to keep the result as an integer, so the only answer that makes sense is to exactly preserve the number of "0" low-order bits. So in the case of positive integers, we are focused on that finite portion between the high order 1 bit (located at bit position integer_length(n)) and the low order 1 bit (located at bit position integer_length(n&-n)-1). We would like to reverse that finite bit string, while keeping the same number of low order 0 bits. Thus, for n>0, for odd n, we simply reverse the integer_length(n) bits, while for even n, we have reverse(n)=2*reverse(n/2). Now as Gareth (and HAKMEM item 154) rightly point out, a negative integer (-n) is really just the logical complement lognot(n). This means that such an "integer" has an infinite number of "1" bits ("sign bits") to the left, and an infinite number of "1" bits to the right of the binary point. But the bit sequence "0.111111111..." to the right of the binary point converges to the number "1.0", which is why we increment the bit-complement of the number in order to produce a "negative" integer (without an infinite fractional part). So now to reverse a negative number, we really want to complement the number, thus getting an infinite string of 0's to the left and to the right of the finite number, find the reverse of those bits (as above), and then complement again. But after this second complement, we need to eliminate that infinite string of 1's to the right of the binary point by incrementing the result by 1. We now know that reverse(0)=0, reverse(1)=0, reverse(2)=2, reverse(3)=3, reverse(4)=4, reverse(5)=5, reverse(6)=6, reverse(7)=7, reverse(8)=8, reverse(9)=9, reverse(10)=10, reverse(11)=13, reverse(12)=12, reverse(13)=11, reverse(14)=14, reverse(15)=15), reverse(16)=16, reverse(17)=17, reverse(18)=18, reverse(19)=25, reverse(20)=20, reverse(21)=21, reverse(22)=26, reverse(23)=29, reverse(24)=24, reverse(25)=19, reverse(26)=22, reverse(27)=27, reverse(28)=28, reverse(29)=23, reverse(30)=30, reverse(31)=31, reverse(32)=32, reverse(33)=33, reverse(34)=34, reverse(35)=49, etc. So the first number that isn't its own reverse is 11, whose reverse is 13, and vice versa. 11base10 = 10011base2, 13base10 = 11001base2. -11base10 = ...111101100.1111...base2, so complementing this gives us ...000010011.0000...base2, the reverse of which is ...000011001.0000...base2, and the complement of that is ...111100110.1111...base2. Now incrementing by 1 to clear the .1111...base2, we get ...111100111.0000...base2, which is -13base10. So, it appears that the correct property to preserve is reverse(-n)=-reverse(n), so we can push "-" down to the leaves, or pull "-" up to the top of any expression tree. We now get reverse(-0)=reverse(0)=-reverse(0)=0, reverse(-1)=-reverse(1)=-1, etc. So, we have successfully explained why the reverse of a negative integer -- e.g., -11 -- doesn't have an infinite number of 1's to the right of the decimal point; actually it _does_, but all these 1's have been cleared by recognizing that "0.111111...base2"="1.000000...base2", so we don't have to carry around an infinite number of 1 bits below the binary point. I now feel comfortable enough to propose that this definition of reverse should be utilized in any computer language implementing "bignums" and logical operations on such integers -- e.g., Common Lisp. At 05:01 PM 6/2/2012, Gareth McCaughan wrote:
On Saturday 02 June 2012 19:32:24 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.
It seems to me that reversing should really be defined on non-negative dyadic rationals, as reflection in the decimal (binary) point. So the reverse of 1 is .1 = 1/2, the reverse of 2 = 10 is .01 = 1/4, etc. This way, trailing zeros don't introduce ambiguity.
In that case, if n is negative then its reverse ends in an infinite string of 1s. So, e.g., the reverse of -1 = ...1111 is 0.111..., which of course equals 1. In general, reverse(-n) = reverse(~(n-1)) = ~reverse(n-1) = 1-reverse(n-1) when n is a non-negative integer. Here the first "~" means "flip all the bits before the binary point" and the second "~" means "flip all the bits after the binary point".
Of course, once we allow this sort of thing reversing is no longer injective.
But, aha, for the exact same reason it is also no longer well defined. Suppose we write 1 not as 1.0000... but as 0.1111..., and then -1 not as ...1111.0000... but as ...1110.1111...; then its reversal becomes ...1111.0111... = ...1111.1000... = -1/2. Which, not coincidentally, equals -reverse(1).
In general, perhaps we "should" adopt the convention that a positive number ends with an infinite string of 0s, and a negative number ends with an infinite string of 1s; then negation is just bitwise complement, and reversal commutes with negation.
-- g
="Henry Baker" <hbaker1@pipeline.com> I now feel comfortable enough to propose that this definition of reverse should be utilized in any computer language implementing "bignums" and logical operations on such integers -- e.g., Common Lisp.
Perhaps, but a more careful construction would foster greater comfort; extraordinary proposals demand extraordinary lucidity. For starters let's untangle numbers from symbol-sequences-sometimes-used-to-represent-numbers, here "numerals" for short. Reversal seems an intuitively natural concept for objects with internal structure like strings, lists or sequences, but to extend its application to point-like numbers requires clarity about the domain of numerals and their relationship to numbers. Positing that we understand numbers pretty well, let's look at this world of reversible objects. Define a numeral X as a mapping from the signed integers into an alphabet D of digits, X:N-->D. Numerals are actually compound objects with countably infinite internal structure. So for convenience we adopt notational conventions such as: compactly writing the successive D_n from left to right for increasing n using ellipses to indicate infinite implicit extensions omitting certain understood leading and trailing patterns entirely marking an origin "point" to the right of D_0 but all this can obscure the intrinsic infinite extent of numerals, as in ...00003.14159... (Note that numerals diverge from Lisp lists because, while (cdr nil)=nil and so we can think of the sequence of elements as infinitely extending to the right, there is no "anticdr" or "supercar" that returns a predecessor of the initial element; for uniformity CL would have to define (elt n L)=nil for negative n, and so on). Anyway, the reverse of a numeral is most naturally defined by reflecting the mapping's domain around n=0: if R = reverse(X) then R(n) = X(-n). Further, we conventionally map each numeral X into a number x by picking a "base" B whose "powers" are taken to generates a countable "basis" B^n and then interpreting digits in the numeral X as the coefficients of a formal "power series", giving x = X(B). With this, we naturally say that the reverse r of a number x is the value given by the reverse of its numeral, x --> X --> R --> r. However this natural interpretation has some interesting consequences. First, it inescapably conflicts with any hope of having the integers be closed under reversal (although the dyadic rationals are). In binary reverse(3) --> reverse("...00011.000...") --> "...0001.1000..." --> 3/2 Secondly, as discussed here, more than one numeral evaluates to the same number: eg both ...000.111... and ...001.000... evaluate to the number 1. So the reverse mapping, from numbers into numerals, is inherently multi-valued. To address this by convention we choose one member of this equivalence class of numerals to be the canonical "name" for the number. That's practical, but to avoid confusion we should carefully distinguish the canonical numeral string X* used as a name for x from the number x itself. Now consider numerals that evaluate to negative numbers. For B=2 we say that the canonical numeral for -1 is ...111.000.... Why does this work? Writing out the power series for the numeral ...111.000... we have ...1*2^2 + 1*2^1 + 1*2^0 + 0*2^-1 + 0*2^-2 + 0*2^-1 + ... Recognizing this as a simple formal geometric series with term ratio 2 we evaluate it by applying 1/(1-rho) for rho=2 --> 1/(1-2) = 1/(-1) = -1. That is, for two's complement numerals 1 + 2 + 4 + 8 +... = -1, and not infinity, as it would be for ordinary numbers. Thus expressing even the simplest negative integer as a binary numeral entails 2-adic arithmetic! Alas the elementary computer science curriculum evades 2-adics. But this view tells us how to evaluate other interesting infinite numerals, such as ...01010101.000... = 1/(1-4) = -1/3 which seems much cooler than the conventional canonical numeral for -1/3: ...111.10101010... which needs infinite non-zero extensions on both the left and right, instead of only on the left. Should we advocate canonizing these 2-adics instead? Anyhow I recommend that any proposed arithmetic extensions to computer languages that embrace an underlying two's complement model (heh, MMIX?) should clearly articulate this interplay between the numeral and the numerical domains, and not handwave the dyadic rationals into the shadows. Some math fun: Of course there are multiple numerals that evaluate to 0: ...000000.000000... ...111111.111111... ...010101.010101... So instead of "zero divisors" we might say numerals have "zero addvisors". Moreover these can be added to any numeral to get an equivalent numeral. Defined via numerals reverse(x) is an interesting function for real x, and also makes a dandy transform: reverse(f(reverse(x))). Along these lines f(x,y) = reverse(reverse(x)+reverse(y)) is like addition, except the carries propagate to the right, hence implements addition in base B=1/2. Reversing maps the parity test in the Collatz function into a vanilla magnitude comparison...
You're correct, Marc. I was a bit (!) presumptuous. Perhaps I should call it "bit_reverse(n)". BTW, bit_palindromep(n)=equal(n,bit_reverse(n)), i.e., fixpoints of (bit_reverse). I hadn't realized what a large fraction of the smaller numbers were actually bit_palindromes. Counting exercise: How many bit_palindromes of integer_length(n)=k are there? At 12:49 PM 6/3/2012, Marc LeBrun wrote:
="Henry Baker" <hbaker1@pipeline.com> I now feel comfortable enough to propose that this definition of reverse should be utilized in any computer language implementing "bignums" and logical operations on such integers -- e.g., Common Lisp.
Perhaps, but a more careful construction would foster greater comfort; extraordinary proposals demand extraordinary lucidity. For starters let's untangle numbers from symbol-sequences-sometimes-used-to-represent-numbers, here "numerals" for short. Reversal seems an intuitively natural concept for objects with internal structure like strings, lists or sequences, but to extend its application to point-like numbers requires clarity about the domain of numerals and their relationship to numbers.
Positing that we understand numbers pretty well, let's look at this world of reversible objects. Define a numeral X as a mapping from the signed integers into an alphabet D of digits, X:N-->D.
Numerals are actually compound objects with countably infinite internal structure. So for convenience we adopt notational conventions such as: compactly writing the successive D_n from left to right for increasing n using ellipses to indicate infinite implicit extensions omitting certain understood leading and trailing patterns entirely marking an origin "point" to the right of D_0 but all this can obscure the intrinsic infinite extent of numerals, as in ...00003.14159...
(Note that numerals diverge from Lisp lists because, while (cdr nil)=nil and so we can think of the sequence of elements as infinitely extending to the right, there is no "anticdr" or "supercar" that returns a predecessor of the initial element; for uniformity CL would have to define (elt n L)=nil for negative n, and so on).
Anyway, the reverse of a numeral is most naturally defined by reflecting the mapping's domain around n=0: if R = reverse(X) then R(n) = X(-n).
Further, we conventionally map each numeral X into a number x by picking a "base" B whose "powers" are taken to generates a countable "basis" B^n and then interpreting digits in the numeral X as the coefficients of a formal "power series", giving x = X(B).
With this, we naturally say that the reverse r of a number x is the value given by the reverse of its numeral, x --> X --> R --> r.
However this natural interpretation has some interesting consequences.
First, it inescapably conflicts with any hope of having the integers be closed under reversal (although the dyadic rationals are). In binary reverse(3) --> reverse("...00011.000...") --> "...0001.1000..." --> 3/2
Secondly, as discussed here, more than one numeral evaluates to the same number: eg both ...000.111... and ...001.000... evaluate to the number 1.
So the reverse mapping, from numbers into numerals, is inherently multi-valued. To address this by convention we choose one member of this equivalence class of numerals to be the canonical "name" for the number.
That's practical, but to avoid confusion we should carefully distinguish the canonical numeral string X* used as a name for x from the number x itself.
Now consider numerals that evaluate to negative numbers. For B=2 we say that the canonical numeral for -1 is ...111.000.... Why does this work?
Writing out the power series for the numeral ...111.000... we have ...1*2^2 + 1*2^1 + 1*2^0 + 0*2^-1 + 0*2^-2 + 0*2^-1 + ... Recognizing this as a simple formal geometric series with term ratio 2 we evaluate it by applying 1/(1-rho) for rho=2 --> 1/(1-2) = 1/(-1) = -1.
That is, for two's complement numerals 1 + 2 + 4 + 8 +... = -1, and not infinity, as it would be for ordinary numbers. Thus expressing even the simplest negative integer as a binary numeral entails 2-adic arithmetic!
Alas the elementary computer science curriculum evades 2-adics. But this view tells us how to evaluate other interesting infinite numerals, such as ...01010101.000... = 1/(1-4) = -1/3 which seems much cooler than the conventional canonical numeral for -1/3: ...111.10101010... which needs infinite non-zero extensions on both the left and right, instead of only on the left. Should we advocate canonizing these 2-adics instead?
Anyhow I recommend that any proposed arithmetic extensions to computer languages that embrace an underlying two's complement model (heh, MMIX?) should clearly articulate this interplay between the numeral and the numerical domains, and not handwave the dyadic rationals into the shadows.
Some math fun:
Of course there are multiple numerals that evaluate to 0: ...000000.000000... ...111111.111111... ...010101.010101... So instead of "zero divisors" we might say numerals have "zero addvisors". Moreover these can be added to any numeral to get an equivalent numeral.
Defined via numerals reverse(x) is an interesting function for real x, and also makes a dandy transform: reverse(f(reverse(x))). Along these lines f(x,y) = reverse(reverse(x)+reverse(y)) is like addition, except the carries propagate to the right, hence implements addition in base B=1/2.
Reversing maps the parity test in the Collatz function into a vanilla magnitude comparison...
participants (4)
-
Eugene Salamin -
Gareth McCaughan -
Henry Baker -
Marc LeBrun