13
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – anon Jul 24 '12 at 19:53
  • $\begingroup$ 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. $\endgroup$ – Raymond Manzoni Jul 24 '12 at 19:54
  • $\begingroup$ @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$. $\endgroup$ – Thomas Russell Jul 24 '12 at 19:56
  • $\begingroup$ @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. $\endgroup$ – celtschk Jul 24 '12 at 20:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaz Sep 30 '12 at 17:43
17
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – tomasz Jul 24 '12 at 19:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Jul 24 '12 at 19:57
  • 1
    $\begingroup$ All the $2$s on this page made me misinterpret the word odd at first glance. Perhaps unusual, or just different? $\endgroup$ – Rahul Jul 24 '12 at 20:09
  • $\begingroup$ @Rahul: fair enough. $\endgroup$ – Qiaochu Yuan Jul 24 '12 at 20:10
  • $\begingroup$ 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. $\endgroup$ – celtschk Jul 24 '12 at 20:53
-1
$\begingroup$

Recursive Definition Not The Same Thing As The Limit

There is no paradox to be found. The limit of a summation doesn't add enough terms to create a paradox. In fact, to take the limit, you have to subtract the tail of the recursion off. This is what will be demonstrated, that the value of some object $A$ can be a finite value, when the limit of a sequence that it expands to is not finite.

$$ Limit[A] = A - Tail[A] $$

A sum of "all" powers of 2 is just a way to write -1; and you can never actually add the "last" term to cause the sum to become -1, so there is no contradiction. It's basic recursion, as found all over computer science. Focus on what a recursive definition actually says. We are defining an object $A$ with this property. $$ A = 1 + 2A $$ $$ (A = 1 + 2A) - 2A $$ $$ -A = 1 $$ $A$ is an object whose recursive definition says that it has an equal value to $-1$, though it may have other representations. This is no more strange than $0.999... = 1.000$ due to the trailing 9 triggering a carry and giving them both the same value. $$ A = -1 $$ Nothing particularly controversial happened there. But -1 is special because the sum of powers of 2 is always 1 less than the next power of 2. Just substitute equals for equals, and it stays consistent: $$ A = (1 + 2(1 + 2(1 + 2(1 + 2A)))) $$ $$ A = 1 + 2 + 4 + 8 + 16A $$ For every finite number of terms to expand, this recurrence is equal to $-1$ due to $A = -1$, $$ A = (1 - 2) = (1 + 2 - 4) = (1 + 2 + 4 - 8) = \cdots $$ So, very carefully, proceed without invoking a notion of infinity or twos complement computer representations. These are true for any finite $N$, $$ A = 1 + 2 + 4 + 8 + \cdots + (2^N)A $$ $$ -1 = 1 + 2 + 4 + 8 + \cdots + (2^N)(-1) $$ $$ -1 = 1 + 2 + 4 + 8 + \cdots + (-(2^N)) $$ Write a closed form for first $N$ in the recursive definition, $$ A = (2^N - 1) + (2^N)A $$ $$ A = (-1 + 2^N) + (2^N)A $$ That last term added in is the tail. $N$ can be as high or low as we like. $$ Tail[A] = (2^N)A $$ $A$, when defined recursively, solves for $-1$, regardless of what the limit of the sum is. So define the limit of the sequence as actually subtracting that tail off. Remember that the whole point of the integer $+\infty$ is that it isn't a number of iterations that you can perform. So no sum is in danger of yielding a result of -1. Remove the tail of the recursion off, because in a sum, we can add any number of terms, but there is no last term if you want the limit, rather than the value of $A$: $$ Limit[A] = \lim_{N \to \infty} (A - Tail[A]) $$ Now here is the crucial part, where people that don't believe in recursion will argue with the result. $A$ is just $-1$ by definition. $A$ has a finite value. But if we subtract $Tail[A]$, we are subtracting an arbitrarily large number. $$ Limit[A] = \lim_{N \to \infty} (-1 - (2^N)(A)) = \lim_{N \to \infty}(-1 + (2^N)) = -1 + \lim_{N \to \infty} 2^N = \infty $$

The really important idea here is that in general, the value of the recursively defined value is not necessarily the same as the limit of any indefinitely long sequence that you can expand it to.

$$ A \not= Limit[A] $$

Part of the problem is that the use of "$\cdots$" and "$\sum$" are not as specific as a recursive definition. There is no way to interpret recursion other than substituting equals for equals. This is why many computer languages only give you recursion as the way to define iterative constructs; because the computer cannot make "common sense" judgments, or iron out ambiguity for you.

Ambiguity Of Sum Notation With $\infty$

Currently, if somebody writes this down, I'm not sure which interpretation they mean. $$ \sum_{N}^{0 \cdots \infty}{2^N} $$

If they say that $L \to \infty$, then the intent is confusing: $$ A = \sum_{n}^{0 \cdots L}{2^n} $$ $$ \sum_{n}^{0 \cdots L}{2^n} = 1 + \sum_{n}^{1 \cdots L}{2^n} = 1 + 2\sum_{n}^{0 \cdots L}{2^n} $$ We said this, without meaning to say it: $$ A = 1 + 2A $$ If $L$ is finite, then that was false, because the summations expand to exactly $1 + L$ terms being added. If $L$ is infinite, the intent was generally not to define it recursively as $A = 1 + 2A$. But it's unsettling that we are not substituting true equals for equals (stronger than being equivalent values). If we ensure that the summations add the exact same number of terms so that they are exactly equal definitions: $$ \sum_{n}^{0 \cdots L+1}{2^n} = 1 + 2\sum_{n}^{0 \cdots L}{2^n} $$ The above statement cannot be solved for $-1$ because they don't add the exact same number of terms (that can be as many as we want). A computer is going to need to convert equal statements to statements that are exactly equal in every way before it can perform a substitution. Being imprecise with $\infty$ makes this hard to do without human intervention. $$ (\sum_{n}^{0 \cdots L}{2^n}) + 2^{L + 1} = 1 + 2\sum_{n}^{0 \cdots L}{2^n} $$ $$ A_2 + 2^{L + 1} = 1 + 2 A_2 $$ This doesn't cause $A_2$ to solve for -1 now. In fact, it subtracted the tail off of the recursion: $$ A_2 = 1 + 2 A_2 - 2^{L+1} $$ $$ -A_2 = 1 - 2^{L+1} $$ $$ A_2 = -1 + 2^{L+1} $$ If you try to sit down and write code to do these algebraic manipulations, problems like this are quite obvious; because the representation has to be converted to be exact before a substitution match can be made. Even exact same statements with different side-conditions are not exactly equal for substitution purposes. You must substitute equals for equals exactly (some equivalences are not as well defined enough to perform deterministicaly by a machine).

The correspondence with 2s complement isn't accidental.

Each bit represents an added in power of 2. Even in a finite representation, "all ones in high bits" means the same thing as "no zeroes in high bits (to the left)"; meaning that it doesn't necessarily rely on a notion of infinity to work.

$$ A = -1 = 1 + 2 + 4 + 8 + \cdots = 1 + 2A $$

This even works on the other side of the decimal point as well, where "all ones (to the right)" means the same thing as "no zeroes (to the right)" and triggers a ripple/carry just like in any finite machine representation. That is why simply negating the bits negates the number if you also represent the low bits (due to the ripple/carry).

Negate every bit above and below the decimal point for the number -1, gives you this: $$ A_3 = 1/2 + 1/4 + 1/8 + \cdots = 1 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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