6 ms·

I wouldn't call that a nitpick; I'd call referring to these a serious misuse of terminology! Finite fields are altogether quite different. There are finite fi

I wouldn't call that a nitpick; I'd call referring to these a serious misuse of terminology! Finite fields are altogether quite different. There are finite fields of of order 2^k for each k, but they work quite differently from the integers modulo 2^k. I think the best short term for describing how machine integers work is to just say "modular arithmetic".

Hermitian909 5y ago
> I'd call referring to these a serious misuse of terminology! Finite fields are altogether quite different. Sure, but also the important part of OP's argument seems to be that numbers be treated as members of the appropriate algebraic structure. Simply subbing in the correct terminology should fix the issue. > I think the best short term for describing how machine integers work is to just say "modular arithmetic". For addition this is correct, I don't believe it's correct for multiplication because of the negative integers. That is, the ring described by signed n-bit signed integers under multiplication and addition is not isomorphic to (Z_{2^n}, +, *).
- Sniffnoy 5y ago
  > For addition this is correct, I don't believe it's correct for multiplication because of the negative integers. That is, the ring described by signed n-bit signed integers under multiplication and addition is not isomorphic to (Z_{2^n}, +, *). No, it is. It is in fact just Z modulo 2^n, just with the choice of representatives being { -2^(n-1), ..., 2^(n-1)-1 } instead of { 0, ..., 2^n-1 }. This is pretty easy to check... do you have an example to the contrary?
jart 5y ago
I'm not even sure if we can call it modular. For example the % operator is defined as remainder rather than modulus if you're dealing with negative numbers. That's why -7 % 3 == -1 in C and -7 % 3 == 2 in Python.
- Sniffnoy 5y ago
  I'm not sure how this is relevant? For addition, multiplication, and subtraction, it is indeed modular arithmetic. For anything involving division it's altogether different, but, I took that as being outside what's being discussed, as nobody would mistake that for a finite field.
  - jart 5y ago
    Your the one who chose to pull out the math terminology. Euclidean remainder isn't modulus. That's not even undefined behavior. For example, I could prove abs() isn't an abs() function by pointing out the abs(INT_MIN)<0 contradiction under two's complement arithmetic, if not for the fact that ANSI X3.159-1988 § 4.10.6.1 conveniently and explicitly un-defines that away. All it takes is one example of defined behavior that contradicts your mental model, to prove your mental model is wrong. So it's safer to assume that C is just C.
    - Sniffnoy 5y ago
      OK, sorry, but I'm not following what you're saying here. (Also, this comment seems needlessly hostile?) You seem to be making a bunch of assumptions that you haven't made explicit. I suspect we're simply talking about different things and therefore not actually disagreeing. So, to try to be absolutely explicit about what I was saying: I was not saying anything about the C programming language. I was talking about the more general notion of fixed-length integers; more specifically, ones that are either unsigned or two's-complement. Obviously, that is frequently applicable to the C programming language, but they are not identical, as, e.g., technically C doesn't require two's-complement for signed integers (and what I said would be false for other sorts of signed integers such as one's-complement). So I'm not talking about C, and the C standard is not relevant to what I was saying. I am not saying anything about the % operator, in C or any other programming language. I am talking about modular arithmetic, where you fix a modulus m -- which in this case is 2^k, where k is the length of the integers in question -- and you form a ring by taking congruence classes modulo m, and you add and multiply congruence classes by picking representatives, applying the appropriate operation, and then taking the congruence class of the result. The particular choice of representatives is irrelevant. As I already said, I am only talking about addition, negation/subtraction, and multiplication (and the constants 0 and 1, if you want to be really nitpicky). Other operations are not relevant to what I'm talking about. Now obviously, to represent congruence classes in a computer, you need to pick representatives; and so the modulo operator % (which, again, is not relevant to my point, but I think I need to address this anyway) returns a number rather than some sort of notional congruence class object, because, well, what else is it going to do. So, it returns a representative of the congruence class rather than the congruence class itself, because there's no way for it to do the latter. As you point out, in C (as of C99 anyway), as well as several other programming languages, the % operator, when evaluating n % m, returns a representative from { -|m|+1, ..., 0 } if n is negative, instead of { 0, ..., |m|-1 } like might be expected. This is a quirk of the % operator, for sure, but it doesn't have anything to do with what I'm talking about. Also note that the ways that programming languages handle negative n or negative m vary quite a bit; some do what C does, some use the sign of m rather than n, and some always return a nonnegative result. The distinction you are drawing between "modulus" and "Euclidean remainder" is, at least in mathematics, not a standard one; as such, if you want to make use of it, you are going to have to explain what you are talking about, rather than just assuming I know it. (I mean, to be clear, there is a distinction between the two, but it's not the one you seem to be drawing. Rather it's that Euclidean remainder is a number rather than a congruence class; is only defined in Euclidean domains; and isn't actually required to be unique. But that's tangential, we're just talking about integers, I'm going to assume you mean the obvious thing by "Euclidean remainder".) In math, at least, the result of modding out is a usually a congruence class, rather than a specific representative, unless you specify otherwise or the context makes it's clear that that really is what you mean (e.g. using "mod" as an operator). When "mod" is used as an operator, and n is negative, I'd assume that the author intended { 0, ..., |m|-1 } as their set of representatives, rather than mimicking C's % operator, unless they specified otherwise. As best I can tell, you seem to be using "modulus", as opposed to "Euclidean remainder", to indicate the specific behavior of C's % operator. I would suggest that this terminology is not as standard as you seem to think it is and will confuse people; this is both not how it is used in mathematics, and not how it is used in lots of other programming languages. If you are trying to refer to that particular behavior, you should use a more unambiguous description. But -- I say this again -- none of this is really on the point I was making. The point I was making was this: Addition, subtraction, and multiplication on fixed-width unsigned integers of length k, with all overflow ignored, consists exactly of operating on the numbers in Z/(2^k), and then taking the representative that can be expressed in k bits unsigned. Moreover, the same is true for fixed-with two's-complement integers of length k; you operate in Z/(2^k), and then take the representative that can be expressed in k bits 2's-complement. That is to say, you're just doing modular arithmetic. The numbers add, subtract, and multiply exactly like their corresponding congruence classes in Z/(2^k). That's all I'm claiming. Again, none of this is about the particular behavior of any C operators. Now that I have utterly belabored this point, is there anything, on that main point, that you disagree with?
saurik 5y ago
So, the reason I wanted to talk about this mathematical type--and then used the wrong term :(--is because of how +,* forms a ring... and so does ^,&. It isn't sufficient to say "modular arithmetic".
- Sniffnoy 5y ago
  I see, interesting. Yeah at that point you have more structure there. But yeah that's just like... two overlapping ring structures? Hm. <shrug>

Hermitian909 5y ago

> I'd call referring to these a serious misuse of terminology! Finite fields are altogether quite different. Sure, but also the important part of OP's argument seems to be that numbers be treated as members of the appropriate algebraic structure. Simply subbing in the correct terminology should fix the issue. > I think the best short term for describing how machine integers work is to just say "modular arithmetic". For addition this is correct, I don't believe it's correct for multiplication because of the negative integers. That is, the ring described by signed n-bit signed integers under multiplication and addition is not isomorphic to (Z_{2^n}, +, *).

Sniffnoy 5y ago
> For addition this is correct, I don't believe it's correct for multiplication because of the negative integers. That is, the ring described by signed n-bit signed integers under multiplication and addition is not isomorphic to (Z_{2^n}, +, *). No, it is. It is in fact just Z modulo 2^n, just with the choice of representatives being { -2^(n-1), ..., 2^(n-1)-1 } instead of { 0, ..., 2^n-1 }. This is pretty easy to check... do you have an example to the contrary?

jart 5y ago

I'm not even sure if we can call it modular. For example the % operator is defined as remainder rather than modulus if you're dealing with negative numbers. That's why -7 % 3 == -1 in C and -7 % 3 == 2 in Python.

Sniffnoy 5y ago
I'm not sure how this is relevant? For addition, multiplication, and subtraction, it is indeed modular arithmetic. For anything involving division it's altogether different, but, I took that as being outside what's being discussed, as nobody would mistake that for a finite field.
- jart 5y ago
  Your the one who chose to pull out the math terminology. Euclidean remainder isn't modulus. That's not even undefined behavior. For example, I could prove abs() isn't an abs() function by pointing out the abs(INT_MIN)<0 contradiction under two's complement arithmetic, if not for the fact that ANSI X3.159-1988 § 4.10.6.1 conveniently and explicitly un-defines that away. All it takes is one example of defined behavior that contradicts your mental model, to prove your mental model is wrong. So it's safer to assume that C is just C.
  - Sniffnoy 5y ago
    OK, sorry, but I'm not following what you're saying here. (Also, this comment seems needlessly hostile?) You seem to be making a bunch of assumptions that you haven't made explicit. I suspect we're simply talking about different things and therefore not actually disagreeing. So, to try to be absolutely explicit about what I was saying: I was not saying anything about the C programming language. I was talking about the more general notion of fixed-length integers; more specifically, ones that are either unsigned or two's-complement. Obviously, that is frequently applicable to the C programming language, but they are not identical, as, e.g., technically C doesn't require two's-complement for signed integers (and what I said would be false for other sorts of signed integers such as one's-complement). So I'm not talking about C, and the C standard is not relevant to what I was saying. I am not saying anything about the % operator, in C or any other programming language. I am talking about modular arithmetic, where you fix a modulus m -- which in this case is 2^k, where k is the length of the integers in question -- and you form a ring by taking congruence classes modulo m, and you add and multiply congruence classes by picking representatives, applying the appropriate operation, and then taking the congruence class of the result. The particular choice of representatives is irrelevant. As I already said, I am only talking about addition, negation/subtraction, and multiplication (and the constants 0 and 1, if you want to be really nitpicky). Other operations are not relevant to what I'm talking about. Now obviously, to represent congruence classes in a computer, you need to pick representatives; and so the modulo operator % (which, again, is not relevant to my point, but I think I need to address this anyway) returns a number rather than some sort of notional congruence class object, because, well, what else is it going to do. So, it returns a representative of the congruence class rather than the congruence class itself, because there's no way for it to do the latter. As you point out, in C (as of C99 anyway), as well as several other programming languages, the % operator, when evaluating n % m, returns a representative from { -|m|+1, ..., 0 } if n is negative, instead of { 0, ..., |m|-1 } like might be expected. This is a quirk of the % operator, for sure, but it doesn't have anything to do with what I'm talking about. Also note that the ways that programming languages handle negative n or negative m vary quite a bit; some do what C does, some use the sign of m rather than n, and some always return a nonnegative result. The distinction you are drawing between "modulus" and "Euclidean remainder" is, at least in mathematics, not a standard one; as such, if you want to make use of it, you are going to have to explain what you are talking about, rather than just assuming I know it. (I mean, to be clear, there is a distinction between the two, but it's not the one you seem to be drawing. Rather it's that Euclidean remainder is a number rather than a congruence class; is only defined in Euclidean domains; and isn't actually required to be unique. But that's tangential, we're just talking about integers, I'm going to assume you mean the obvious thing by "Euclidean remainder".) In math, at least, the result of modding out is a usually a congruence class, rather than a specific representative, unless you specify otherwise or the context makes it's clear that that really is what you mean (e.g. using "mod" as an operator). When "mod" is used as an operator, and n is negative, I'd assume that the author intended { 0, ..., |m|-1 } as their set of representatives, rather than mimicking C's % operator, unless they specified otherwise. As best I can tell, you seem to be using "modulus", as opposed to "Euclidean remainder", to indicate the specific behavior of C's % operator. I would suggest that this terminology is not as standard as you seem to think it is and will confuse people; this is both not how it is used in mathematics, and not how it is used in lots of other programming languages. If you are trying to refer to that particular behavior, you should use a more unambiguous description. But -- I say this again -- none of this is really on the point I was making. The point I was making was this: Addition, subtraction, and multiplication on fixed-width unsigned integers of length k, with all overflow ignored, consists exactly of operating on the numbers in Z/(2^k), and then taking the representative that can be expressed in k bits unsigned. Moreover, the same is true for fixed-with two's-complement integers of length k; you operate in Z/(2^k), and then take the representative that can be expressed in k bits 2's-complement. That is to say, you're just doing modular arithmetic. The numbers add, subtract, and multiply exactly like their corresponding congruence classes in Z/(2^k). That's all I'm claiming. Again, none of this is about the particular behavior of any C operators. Now that I have utterly belabored this point, is there anything, on that main point, that you disagree with?

saurik 5y ago

So, the reason I wanted to talk about this mathematical type--and then used the wrong term :(--is because of how +,* forms a ring... and so does ^,&. It isn't sufficient to say "modular arithmetic".

Sniffnoy 5y ago
I see, interesting. Yeah at that point you have more structure there. But yeah that's just like... two overlapping ring structures? Hm. <shrug>