13 ms·

This all is suddenly less surprising for people who learned some modulo arithmetics in school (or university). That is, calculating with the remainders of divis

by vog 10y ago

This all is suddenly less surprising for people who learned some modulo arithmetics in school (or university). That is, calculating with the remainders of division. For example: - Calculating "modulo 60" means calculating time with a round clock in mind, considering only minutes and ignoring hours (and seconds). - Calculating with angles (in degrees) means just calculating "modulo 360". - "modulo 1000" means calculating with the last 3 decimal digits of an integer, ignoring the front digits. The fundamental result here is: No matter modulo which number you calculate: addition, negation, subtraction and multiplication work "out of the box". And you'll quickly notice that "two's complement" just means calculating modulo 2^n, where n=8,16,32,64 or 128. But this all really works for any m >= 2, not just m = 2^n. (One drawback though: division doesn't work here, it works only if m is prime, and even then it is slightly different from what you'd expect, although completely logical.) In short, the elegance comes from modulo arithmetics. It has nothing to do with "two" or "binary", it would e.g. work with 3-state logic machines the same way. EDIT: To those who downvoted this: Do you care to elaborate? The author did't mention modulo arithmetics with a single word, although it is an essential part to truly understand how and why two's complement works.

russdill 10y ago
You'd love finite fields.
- joatmon-snoo 10y ago
  And groups!
  - gizmo686 10y ago
    Don't forget about rings.
    - jmartinpetersen 10y ago
      I always found those ideal.
      - vog 10y ago
        But the base of all is still Gröbner.
wbhart 10y ago
I didn't downvote, but just a minor nitpick, it's modular arithmetic, not modulo arithmetics.
gizmo686 10y ago
I didn't downvote you. However, I am a math person and your post feels wrong for some reason. It isn't wrong, but it feels like it should be; and I am not entirely sure why. CPUs use modular arithmetic for both signed (two's complement) and unsigned values, so that cannot be the defining feature of twos complement. The insight with two's complement is that we can interperet the "upper" half of numbers as negative. As you say, this should be very familar to anyone who has worked with modular arithmatic. For those who have not, this just means that (in 3-bit twos complement/ integers mod 8). We interperate 7 = 8-1 = -1 and so on. As a result of this, operations on signed and unsigned integers are literally identical. Almost. CPUs differ from modular arithmetic in 1 way: multiplication. Specifically, CPUs do not do modular arithmetic for multiplication. However, the result of the multiplication of two n-bit numbers could be as big as 2n-bits. When CPUs do this multiplication, they store the result in two registers. If you only look at the bottom register, the result is equivalent to modular arithmatic. However, if you consider the top register, the result is not (this is why there is a MUL and IMUL instruction). Arguably, the same thing happens for addition. However, because there is at most 1 extra bit needed, it is not given its own register, but rather, the upper digit is stored in the carry flag. The other insight of two's complement is encoding. Under the construction I presented above, if given the 3-bit twos complement number 0b111, we would have to compute that: 0b111 > 0b011 0b111 = 0b1000 - 0b0001 The insight of two complement is a way performing this computation using primitive bitwise operations. Specifically: If the first bit is 0, we are done Otherwise, perform bitwise negation, add 1, and consider the result "negative". There is no obvious equivelent of this method for other bases.
- alipang 10y ago
  https://en.wikipedia.org/wiki/Method_of_complements https://en.wikipedia.org/wiki/Method_of_complements
- vog 10y ago
  > CPUs use modular arithmetic for both signed (two's complement) and unsigned values, so that cannot be the defining feature of twos complement I disgree, because this still fits nicely into modulo arithmetics. Signed versus unsigned just means that we choose a different set of representants for certain operations (such as). For unsigned, we use the smalles non-negative representant. For signed, we use the representant with the smallest absolute value (and prefer the negative one if there is a tie). Still, nothing with binary. Except for one single detail: The "tie" is solved in favour of the negative number, because that way, the first bit always denotes the sign. This little details is binary-specific, but that's it. > CPUs differ from modular arithmetic in 1 way: multiplication. Specifically, CPUs do not do modular arithmetic for multiplication. However, the result of the multiplication of two n-bit numbers could be as big as 2n-bits. When CPUs do this multiplication, they store the result in two registers. If you only look at the bottom register, the result is equivalent to modular arithmatic. Good point, but in most (non-assembly) code that I see, the result of a multiplication is stored in a same-size integer. So I'd argue this is used as much. I agree that this is still a difference, though. > The insight of two complement is a way performing this computation using primitive bitwise operations. I believe that negation is not what this is all about. To the contrary, the negation is more complicated for two's complement than for other representations. For example, in other representatios you just flip a single bit to negate a number. No, the point is that there no special cases for increment, decrement, addition, subtraction and multiplication (with the small difference discussed above). And there is not even a difference between signed versus unsigned arithmetics except for comparison (also discussed above). This is what works out perfectly well in modulo arithmetics, and has nothing to do with binary.
dahart 10y ago
I didn't downvote, but the article was comparing one's complement to two's complement. One's complement also requires arithmetic modulo 2^n, so nothing you've said is unique to two's complement or helps to explain why it works. With two's complement, you flip all the bits, and then add 1 to the result. The surprise is that you can shift the negative half of the circle by 1 and everything still works. And not only does it work, but it has advantages over not shifting. This can indeed be done in any base, but you always have the choice of two complements to use. In decimal you have 9's complement and 10's complement. So, you're right about it working similar in trinary, but the name 2's complement is in fact somewhat specific to binary. https://en.m.wikipedia.org/wiki/Method_of_complements https://en.m.wikipedia.org/wiki/Method_of_complements
- vog 10y ago
  > The surprise is that you can shift the negative half of the circle by 1 and everything still works But this, again, has has nothing to do with binary but all with modulo arithmetics. If you think in modulo arithmetics, this is still no "surprise". For example, if you calculate modulo 1000 you don't distinguish between 777 and (777 + 1000x) for any integer x. That is, the following numbers are treated the same: 777, 1777, 2777, ..., 4131321777, ... but also (777 - 1000 = -223): -223, -1223, -2223, ... These all represent the same number (modulo 1000). Modulo arithmetics tells you that for almost all operations it doesn't matter which representative you use (i.e. addition, subtraction, increment, decrement, etc.). The only difference between signed and unsigend is which representatives you use. "Unsigned" means: For each class, use the smallest non-negative representative: 0,1,2,...,999 "Signed" means: For each class, use the representative with the smallest absolute value (and use the negative one on tie): -500,-499,...,0,1,...,499 The only binary-specific thing here is how the tie is resolved in the signed case. We prefer -500 over 500 (both are equal modulo 1000), because in binary, that way the first bit always indicates the sign. But if you are fine with a slightly more complicated sign check, you could als well define the following, where addition, etc. still all work the same way: "Signed-2": For each class, use the representative with the smallest absolute value (and use the positive one on tie): -499,...,0,1,...,499,500
  - 10y ago
misterrobot 10y ago
"Division" i.e. multiplying by the multiplicative inverse doesn't require the modulus be prime; it just requires that the number you are finding the inverse of and the modulus are relatively prime.

by vog 10y ago

russdill 10y ago

You'd love finite fields.

joatmon-snoo 10y ago
And groups!
- gizmo686 10y ago
  Don't forget about rings.
  - jmartinpetersen 10y ago
    I always found those ideal.
    - vog 10y ago
      But the base of all is still Gröbner.

wbhart 10y ago

I didn't downvote, but just a minor nitpick, it's modular arithmetic, not modulo arithmetics.

gizmo686 10y ago

I didn't downvote you. However, I am a math person and your post feels wrong for some reason. It isn't wrong, but it feels like it should be; and I am not entirely sure why. CPUs use modular arithmetic for both signed (two's complement) and unsigned values, so that cannot be the defining feature of twos complement. The insight with two's complement is that we can interperet the "upper" half of numbers as negative. As you say, this should be very familar to anyone who has worked with modular arithmatic. For those who have not, this just means that (in 3-bit twos complement/ integers mod 8). We interperate 7 = 8-1 = -1 and so on. As a result of this, operations on signed and unsigned integers are literally identical. Almost. CPUs differ from modular arithmetic in 1 way: multiplication. Specifically, CPUs do not do modular arithmetic for multiplication. However, the result of the multiplication of two n-bit numbers could be as big as 2n-bits. When CPUs do this multiplication, they store the result in two registers. If you only look at the bottom register, the result is equivalent to modular arithmatic. However, if you consider the top register, the result is not (this is why there is a MUL and IMUL instruction). Arguably, the same thing happens for addition. However, because there is at most 1 extra bit needed, it is not given its own register, but rather, the upper digit is stored in the carry flag. The other insight of two's complement is encoding. Under the construction I presented above, if given the 3-bit twos complement number 0b111, we would have to compute that: 0b111 > 0b011 0b111 = 0b1000 - 0b0001 The insight of two complement is a way performing this computation using primitive bitwise operations. Specifically: If the first bit is 0, we are done Otherwise, perform bitwise negation, add 1, and consider the result "negative". There is no obvious equivelent of this method for other bases.

alipang 10y ago
https://en.wikipedia.org/wiki/Method_of_complements https://en.wikipedia.org/wiki/Method_of_complements
vog 10y ago
> CPUs use modular arithmetic for both signed (two's complement) and unsigned values, so that cannot be the defining feature of twos complement I disgree, because this still fits nicely into modulo arithmetics. Signed versus unsigned just means that we choose a different set of representants for certain operations (such as). For unsigned, we use the smalles non-negative representant. For signed, we use the representant with the smallest absolute value (and prefer the negative one if there is a tie). Still, nothing with binary. Except for one single detail: The "tie" is solved in favour of the negative number, because that way, the first bit always denotes the sign. This little details is binary-specific, but that's it. > CPUs differ from modular arithmetic in 1 way: multiplication. Specifically, CPUs do not do modular arithmetic for multiplication. However, the result of the multiplication of two n-bit numbers could be as big as 2n-bits. When CPUs do this multiplication, they store the result in two registers. If you only look at the bottom register, the result is equivalent to modular arithmatic. Good point, but in most (non-assembly) code that I see, the result of a multiplication is stored in a same-size integer. So I'd argue this is used as much. I agree that this is still a difference, though. > The insight of two complement is a way performing this computation using primitive bitwise operations. I believe that negation is not what this is all about. To the contrary, the negation is more complicated for two's complement than for other representations. For example, in other representatios you just flip a single bit to negate a number. No, the point is that there no special cases for increment, decrement, addition, subtraction and multiplication (with the small difference discussed above). And there is not even a difference between signed versus unsigned arithmetics except for comparison (also discussed above). This is what works out perfectly well in modulo arithmetics, and has nothing to do with binary.

dahart 10y ago

I didn't downvote, but the article was comparing one's complement to two's complement. One's complement also requires arithmetic modulo 2^n, so nothing you've said is unique to two's complement or helps to explain why it works. With two's complement, you flip all the bits, and then add 1 to the result. The surprise is that you can shift the negative half of the circle by 1 and everything still works. And not only does it work, but it has advantages over not shifting. This can indeed be done in any base, but you always have the choice of two complements to use. In decimal you have 9's complement and 10's complement. So, you're right about it working similar in trinary, but the name 2's complement is in fact somewhat specific to binary. https://en.m.wikipedia.org/wiki/Method_of_complements https://en.m.wikipedia.org/wiki/Method_of_complements

vog 10y ago
> The surprise is that you can shift the negative half of the circle by 1 and everything still works But this, again, has has nothing to do with binary but all with modulo arithmetics. If you think in modulo arithmetics, this is still no "surprise". For example, if you calculate modulo 1000 you don't distinguish between 777 and (777 + 1000x) for any integer x. That is, the following numbers are treated the same: 777, 1777, 2777, ..., 4131321777, ... but also (777 - 1000 = -223): -223, -1223, -2223, ... These all represent the same number (modulo 1000). Modulo arithmetics tells you that for almost all operations it doesn't matter which representative you use (i.e. addition, subtraction, increment, decrement, etc.). The only difference between signed and unsigend is which representatives you use. "Unsigned" means: For each class, use the smallest non-negative representative: 0,1,2,...,999 "Signed" means: For each class, use the representative with the smallest absolute value (and use the negative one on tie): -500,-499,...,0,1,...,499 The only binary-specific thing here is how the tie is resolved in the signed case. We prefer -500 over 500 (both are equal modulo 1000), because in binary, that way the first bit always indicates the sign. But if you are fine with a slightly more complicated sign check, you could als well define the following, where addition, etc. still all work the same way: "Signed-2": For each class, use the representative with the smallest absolute value (and use the positive one on tie): -499,...,0,1,...,499,500
- 10y ago

misterrobot 10y ago

"Division" i.e. multiplying by the multiplicative inverse doesn't require the modulus be prime; it just requires that the number you are finding the inverse of and the modulus are relatively prime.