="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...