Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!wrdis01!gatech!bloom-beacon!dont-send-mail-to-path-lines
From: Alan@lcs.mit.EDU (Alan Bawden)
Newsgroups: comp.lang.scheme
Subject: Logical operations on integers.
Message-ID: <9104130412.AA14254@august>
Date: 13 Apr 91 04:12:55 GMT
References: <9104110124.AA11779@august>
Sender: alan@ai.mit.edu
Organization: The Internet
Lines: 59


   Date: Wed, 10 Apr 91 21:24:53 EDT
   From: Alan Bawden <Alan@lcs.mit.edu>

      Date: Mon, 8 Apr 91 23:02:43 PDT
      From: Scott Layson Burson <gyro@cymbal.reasoning.com>
      ...
      What would be the sensible semantics for unsigned integers given that
      they can be of arbitrary precision?  (It turns out that there is a
      surprisingly reasonable answer.)

   I'm not confident that there is a -unique- sensible semantics, but
   the 2-adic integers is certainly -one- sensible semantics.

Since comparing notes with Scott reveals that we had different notions in
mind, allow me to explain myself:

2's-complement arithmetic is normally defined over only those semi-infinite
bitstrings that are -eventually- always 0 or always 1.  The 2-adic numbers
are the set of -all- semi-infinite bitstrings with arithmetic defined in
exactly the same way.  So we have:

	3  =    [0]11	; "[]" indicates repetition
       -5  =   [1]011
       11  =  [0]1011

as usual, but we also have beasts like:

        X  =    [01]1

What is X?  Well, if you compute 3 * X, you will find:

       ( [11]0 )	; carry
	 [10]11		; 1 * X
       + [01]1		; 2 * X
       --------
	 [00]01		; sum = 3 * X = 1

so 3 * X = 1, and we are forced to conclude that X = 1/3.

In fact, all odd integers have inverses in the ring of 2-adic numbers, and
since the ring is closed under + and *, we can represent any rational p/q,
where q is odd.  Now you can see why (LOGIOR 2/3 3/5) = -7/15:

	2/3   =   [01]10  =  [0101]10
	3/5   =  [0011]1  =  [1001]11
       -7/15  =   [0111]  =  [1101]11

But the 2-adic numbers don't just include the semi-infinite bitstrings that
eventually fall into a repeating pattern (which are all rational), but all
kinds of other weird things -- for example sqrt(17) is a non-repeating
sequence whose low order bits are:

       ...100110011110100110010011011101001

I don't have any idea if you can say -which- root this is -- but you can,
of course, negate it to get the other one.  In fact, the 2-adic numbers
also contain many other algebraic numbers (including sqrt(-7)) as well as
having its own transcendentals.