4 ms·

When I have built true absolute value operations--which has actually been pretty rare as I don't think you usually want "integers" for most computer work and ar

by saurik 5y ago

When I have built true absolute value operations--which has actually been pretty rare as I don't think you usually want "integers" for most computer work and are better off thinking in terms of finite fields instead of numbers whenever possible--I add a check that the result is actually non-negative (which is the kind of sanity check one would also want to write to verify you don't lose precision, saturate, or overflow in other "I am using these as numbers instead of a finite field" cases); or, if I am working with a number I know to be negative, sometimes I go with "the additive inverse wasn't the number itself", as in this code: https://github.com/OrchidTechnologies/orchid/blob/be5cc32a1649e699509bdd0514067d36cadc6dcd/lot-ethereum/lottery1.sol#L137 https://github.com/OrchidTechnologies/orchid/blob/be5cc32a16...

dataflow 5y ago
Bear in mind the absolute value is a red herring, the problems is negating a signed number, which is extremely common, and hardly anyone guards against that.
- saurik 5y ago
  Well, nor do most people guard against absolute value failing, even inside their implementation: most people are simply wrong... that said, I also think matter-of-factly "negating" a signed number--rather than asking for the additive inverse of a field element (in which case -128 is the correct answer for -128 as when you later go to add it to another number it will have the correct behavior even if it doesn't look like it makes sense if you pretend it is a number)--is also usually a mistake ;P.
Hermitian909 5y ago
> finite fields instead of numbers whenever possible A nitpick: 32 or 64 bit integers are not finite fields. One of the finite field axioms is that any non-zero number must have a multiplicative inverse, which 2 does not have. They are, however, commutative rings.
- Sniffnoy 5y ago
  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.
    - 5y ago
throwaway81523 5y ago
> I don't think you usually want "integers" for most computer work and are better off thinking in terms of finite fields instead of numbers whenever possible I think it is the other way around, and that's why high level languages (under some definition of HLL) tend to have arbitrary precision integers. Python, Ruby, Lisp, and now Javascript (bigint) all have them. Finite fields are almost never used except in some special applications like cryptography or error correcting codes. Multiplication in the field with 2**32 elements doesn't look anything like integer multiplication. Normal computer arithmetic is not finite field arithmetic. We really should be using trap-on-overflow in C most of the time. Making that difficult on RISC-V seems to me like a poor design decision.
- saurik 5y ago
  Yeah... I absolutely appreciate my belief is controversial "at best" ;P, but I stand by it, and even (personally) consider this one of the defining characteristics of someone who truly "understands" and thinks fluently and natively in the mental model of practical computation vs. someone who would prefer to translate from their real-world experience into the inherently-finite world of machines. That said, I certainly agree that if you are working with an actual unbounded numerical value you should be using a data structure that at least attempts to simulate an unbounded numerical value; but, what people always insist on instead is to continue using their fixed integer types which they want to magically have compatible semantics with unbounded integers... a fiction they insist the compilers and even CPUs join them in crafting, with things like the "trap-on-overflow" feature you are advocating for :/. The result of this is that, rather than accepting types like "uint64" are finite fields that should have perfectly regular overflow, and inverse semantics that under no circumstances, should be "messed with" by the environment, and that they should be using "BigInt" for any actual numbers that occasionally come up, people keep ruining the finite field types by trying and, in the end, failing to add a bunch of weird optimizations and overflow trap semantics to their operation... mitigations that only cause further errors later: these types should have the most brutal possible interpretation of finite field math, and anyone who wants an actual number--maybe to represent a physical or monetary quantity should be forced to not consider them an option. Meanwhile, languages should do anything and everything possible to not pessimize the syntax of types like BigInt by providing a short name for a good implementation of the type along with operator overloading that prevents anyone from ever considering the usage of a type like C's "int" to represent a number merely because it is easier or looks better or feels natural: you fix this issue, and "trap on overflow"--a ridiculous semantic that makes software look like it works until you push it a bit, and in a way that fails to be fungible with (and accepting the same solutions as) running out of memory--becomes a feature that has no legitimate usage.

by saurik 5y ago

dataflow 5y ago

Bear in mind the absolute value is a red herring, the problems is negating a signed number, which is extremely common, and hardly anyone guards against that.

saurik 5y ago
Well, nor do most people guard against absolute value failing, even inside their implementation: most people are simply wrong... that said, I also think matter-of-factly "negating" a signed number--rather than asking for the additive inverse of a field element (in which case -128 is the correct answer for -128 as when you later go to add it to another number it will have the correct behavior even if it doesn't look like it makes sense if you pretend it is a number)--is also usually a mistake ;P.

Hermitian909 5y ago

> finite fields instead of numbers whenever possible A nitpick: 32 or 64 bit integers are not finite fields. One of the finite field axioms is that any non-zero number must have a multiplicative inverse, which 2 does not have. They are, however, commutative rings.

Sniffnoy 5y ago
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.
  - 5y ago

throwaway81523 5y ago

> I don't think you usually want "integers" for most computer work and are better off thinking in terms of finite fields instead of numbers whenever possible I think it is the other way around, and that's why high level languages (under some definition of HLL) tend to have arbitrary precision integers. Python, Ruby, Lisp, and now Javascript (bigint) all have them. Finite fields are almost never used except in some special applications like cryptography or error correcting codes. Multiplication in the field with 2**32 elements doesn't look anything like integer multiplication. Normal computer arithmetic is not finite field arithmetic. We really should be using trap-on-overflow in C most of the time. Making that difficult on RISC-V seems to me like a poor design decision.

saurik 5y ago
Yeah... I absolutely appreciate my belief is controversial "at best" ;P, but I stand by it, and even (personally) consider this one of the defining characteristics of someone who truly "understands" and thinks fluently and natively in the mental model of practical computation vs. someone who would prefer to translate from their real-world experience into the inherently-finite world of machines. That said, I certainly agree that if you are working with an actual unbounded numerical value you should be using a data structure that at least attempts to simulate an unbounded numerical value; but, what people always insist on instead is to continue using their fixed integer types which they want to magically have compatible semantics with unbounded integers... a fiction they insist the compilers and even CPUs join them in crafting, with things like the "trap-on-overflow" feature you are advocating for :/. The result of this is that, rather than accepting types like "uint64" are finite fields that should have perfectly regular overflow, and inverse semantics that under no circumstances, should be "messed with" by the environment, and that they should be using "BigInt" for any actual numbers that occasionally come up, people keep ruining the finite field types by trying and, in the end, failing to add a bunch of weird optimizations and overflow trap semantics to their operation... mitigations that only cause further errors later: these types should have the most brutal possible interpretation of finite field math, and anyone who wants an actual number--maybe to represent a physical or monetary quantity should be forced to not consider them an option. Meanwhile, languages should do anything and everything possible to not pessimize the syntax of types like BigInt by providing a short name for a good implementation of the type along with operator overloading that prevents anyone from ever considering the usage of a type like C's "int" to represent a number merely because it is easier or looks better or feels natural: you fix this issue, and "trap on overflow"--a ridiculous semantic that makes software look like it works until you push it a bit, and in a way that fails to be fungible with (and accepting the same solutions as) running out of memory--becomes a feature that has no legitimate usage.