Skip to main content
14 events
when toggle format what by license comment
Apr 5, 2023 at 15:33 comment added Ntwali B. @JohnL. I think your proof carries easily to two's complement (which is what Java and Python use): an integer $A$ in $\mathbb{Z}$ has two's complement representation $A = -A_{n-1} 2^{n-1} + \sum_{i=0}^{n-2} A_i2^{i}$. We use the procedure you have outlined above for the two parts of the formula above. The sum $\sum_{i=0}^{n-2} A_i2^{i} + \sum_{i=0}^{n-2} B_i2^{i}$ is already proved above. We do the procedure again for the sign part $-A_{n-1} 2^{n-1} -B_{n-1} 2^{n-1}$, keeping in mind that $-0 \equiv 0$ and $-1 \equiv 11$. And that's it. The formula holds for $A, B$ in $\mathbb{Z}$.
Apr 5, 2023 at 15:19 history edited John L. CC BY-SA 4.0
Fixed typos. Added two's complement with infinite length.
Apr 5, 2023 at 14:17 comment added Sneftel IMO an easy way to extend the proof to two's complement integers is to show that the result holds for (unsigned) addition modulo 2^n, then demonstrate the equivalence of that to two's complement. Two's complement arithmetic is really just carefully biased modular arithmetic.
Apr 5, 2023 at 6:05 comment added John L. It looks a proof wanted at the end of this answer is given in Hacker's Delight section 2-1 and 2-2 if we assume the specification of Java or Python can fit in.
Apr 5, 2023 at 5:36 history edited John L. CC BY-SA 4.0
Another modern interpretation.
Apr 5, 2023 at 4:45 comment added hobbs I'm not conversant enough in the relevant bits of math to enumerate the conditions exactly, but I think it's basically: any chain of operations involving only addition, subtraction, and, or, and xor is "safe" provided that the "true result" of that chain is in the representable range [even if the intermediate values are not], and other operations (like multiplication) are safe if they consume only safe values and don't overflow themselves.
Apr 5, 2023 at 4:37 comment added hobbs @JohnL. basically, the overflow behavior you were worried about is actually pretty benign, and gives you the same answer as infinite width under certain conditions, and we're staying within those conditions. One of the reasons why it's the dominant form of arithmetic on computers :)
Apr 4, 2023 at 23:40 vote accept Ntwali B.
Apr 4, 2023 at 23:40 comment added Ntwali B. To my shame, I should have written the expansion as you did and the proof would have been obvious, thank you for spelling it out! For it's worth, I took a different route after my last comment: prove that for $A = 1$ and $B = 0$ we have $A + B = 1$. Then assume Peano's axioms, that is $1 = successor(0)$ and so on for any $B$ in $\mathbb{N}$. It then becomes sufficient to show that $A + (B + 1) = (A + B) +1$, which is trivial. But I still like your proof better as it is very explicit and it is exactly what I was looking for.
Apr 4, 2023 at 22:40 comment added hobbs You can imagine negative numbers having an "infinity of ones off to the left" the same way positive numbers have zeroes, and use twos-complement without having to tie yourself to a particular word size. I think the HAKMEM group would have been comfortable with that idea; it's semi-jokingly implied in HAKMEM 154.
Apr 4, 2023 at 19:58 comment added John L. @NtwaliB. Is my updated answer clear enough?
Apr 4, 2023 at 19:55 history edited John L. CC BY-SA 4.0
More explanation.
Apr 4, 2023 at 18:59 comment added Ntwali B. Thank you for the clarification on the interpretation. I'm still not able to fully appreciate the entirety of the reservations you point when dealing with negative $A$ or $B$ but will comment here (or ask a separate question) after I've given it more thought. As for the proof, it makes sense that we consider $A, B$ in $\mathbb{B}$ as being enough. But it is taking me some time to convince myself that it is indeed enough :-). Will comment again with either additional clarification request or a thank you comment and accept the answer.
Apr 4, 2023 at 15:24 history answered John L. CC BY-SA 4.0