Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Probably everyone has once come across the following "theorem" with corresponding "proof": $$\sum_{n=0}^\infty 2^n = -1$$ Proof: $\sum_{n=0}^\infty q^n = 1/(1-q)$. Insert $q=2$ to get the result.

Of course the "proof" neglects the condition on $q$ for this formula, and the sum really diverges. However I now noticed an interesting fact:

If you use two's complement to represent negative numbers on computers, $-1$ is represented by all bits set. Also, sign extending to a larger number of bits (that is, getting the same number in two's complement representation on more bits) works by copying the left-most bit (also known as sign bit) into the additional bits on the left.

Now imagine that formally you sign-extend the number $-1$ to infinitely many bits. What you get is an infinite-to-the-left string of $1$s. Which, using the normal base-2 formula $n = \sum_k b_k 2^k$ (where $b_k$ is the bit k positions from the right, i.e. $b_0$ is the rightmost bit), that infinite string of $1$s translates into exactly the sum above! So in some sense we have an independent re-derivation of that equation.

Now my question is: Is there something deeper behind this? Somehow I cannot imagine it is just coincidential.

share|improve this question
2  
What does "sign-extend" mean? The reason the formula works out soundly is because the geometric series formula works out in the formal power series ring and in particular the $2$-adics. –  anon Jul 24 '12 at 19:53
    
see this and these p-adic link1 link 2. $-1$ is for all digits equal to $p-1$, $-2$ for all the digits at $p-2$ and so on. –  Raymond Manzoni Jul 24 '12 at 19:54
    
@anon I believe he means if you take some binary string, say $1001_{2}=-7$ using two's-complement in 4-bits, and then 'sign-extend' it to 8 bits, we'd have $11111001_{2}=-7$. –  Shaktal Jul 24 '12 at 19:56
    
@anon: I said what "sign extending to a larger number of bits" means in the parenthesis directly following that phrase (starting with "that is"), and described the mechanism how to do it afterwards in the same sentence. –  celtschk Jul 24 '12 at 20:35
    
Incidentally, infinite two's complement integers are found in Common Lisp, Ruby, and I have recently implemented them in a language called TXR. A negative value is taken to be infinitely padded with 1's, as if sign-extended out to infinity. Of course, the underlying bignums are stored in sign-magnitude, so this is just a charade perpetrated by the carefully implemented semantics of the bit operations. –  Kaz Sep 30 '12 at 17:43
add comment

1 Answer 1

up vote 13 down vote accepted

Yes. What you are doing is known as working in the $2$-adic numbers.

The $2$-adic numbers are equipped with a curious notion of distance given by the $2$-adic metric. In this metric, two numbers are close together if their difference is divisible by a large power of $2$. In particular, large powers of $2$ are very small. So relative to the $2$-adic metric the geometric series you wrote down really does converge, and the value it converges to really is $-1$.

share|improve this answer
    
But does it actually have anything to do with two's complement? I think that's what the question is about, not just the convergence. –  tomasz Jul 24 '12 at 19:55
1  
Yes. Large powers of $2$ get close to $0$ so the two's complement of a number, for sufficiently large powers of $2$, approximates the negative of that number $2$-adically. –  Qiaochu Yuan Jul 24 '12 at 19:57
1  
All the $2$s on this page made me misinterpret the word odd at first glance. Perhaps unusual, or just different? –  Rahul Jul 24 '12 at 20:09
    
@Rahul: fair enough. –  Qiaochu Yuan Jul 24 '12 at 20:10
    
That's quite interesting. So two's complement arithmetic is basically 2-adic arithmetic with the left-most bit representing an infinity of equal bits. Indeed, I've now seen that the linked Wikipedia page contains a link to a page for exactly the sum I started with. –  celtschk Jul 24 '12 at 20:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.