4 ms·

Applying the unary "negate" operation isn't particularly useful test. For reference (and note the apostrophe locations): * sign-magnitude is slightly easier f

by o11c 3y ago

Applying the unary "negate" operation isn't particularly useful test. For reference (and note the apostrophe locations): * sign-magnitude is slightly easier for multiplication/division but makes addition/subtraction marginally harder. It's widely used in bigint libraries, and IEEE binary floats use a variant of it (unlike IEEE decimal floats, which are not at all sane). * two's complement is optimal for addition/subtraction, but has a weird "most negative" value. Fixed-width multiplication and division have a couple warts but . * ones' complement is not particularly useful compared to the above two choices, though I suppose it's marginally easier to sort than sign-magnitude * offset-binary is useful for naive sorting, but casting to/from unsigned is not a nop. For two's complement at least, to avoid the UB you can just cast to/from unsigned around most operations. Division has to be done with some kind of branches, however. I rather wish we had an integer `NaN` instead of the most-negative value. Also, there are several useful overflow behaviors: trap, wrap, saturate, unspecified, and undefined. "unspecified" is particularly useful if you're sometimes transpiling to a JS-like language that doesn't actually support integers.

tialaramex 3y ago
I don't think an integer NaN would be a good idea. People's intuition around the existing float NaNs is not good. I want to make user defined types like BalancedI32 (32bit signed integer but the magnitude of MAX and MIN are the same) possible in Rust. Today the stdlib is allowed to make NonZeroI32 which as its name suggests lacks zero but you can't make such types yourself except via wrapping these NonZero types with xor or similar. (In nightly Rust you can just break the rules and do the same thing the stdlib does, but there's no obligation to keep that working and it will never be stabilized) Because of the Guaranteed Niche Optimisation this means Option<BalancedI32> would have identical size to i32. So you get the same practicality as a normal signed integer with a sentinel value, but the same programming ergonomics as an expensive high level type.
- lifthrasiir 3y ago
  > People's intuition around the existing float NaNs is not good. I think that, if NaN was defined to be an unconditional trap but can be deferred for efficiency, then it could have worked much better. NaN surprises people because it was exposed in the first place, while it should really have been hidden behind the scene (because the presence of NaN means you are already wrong somewhere, and you are expected to be notified about that fact). In terms of Rust, say, every f32 operation could have returned `Result<f32, FloatError>` (mostly likely to be aliased though) that has the exactly same layout as the current f32. The current split between qNaN and sNaN (among others) is unnecessarily complex with little benefit.
- anonymoushn 3y ago
  Has Rust seriously committed to never stabilizing the ability for users to create types like the builtin string type? Wow.
  - tialaramex 3y ago
    Huh? I think you might have skimmed what I wrote a bit too fast and didn't end up comprehending most of it. Some Rust types have niches, bit patterns which the type doesn't use. For example booleans take up a whole byte, but only need two bit patterns, leaving 254 unused. Today there is no stable way to conjure into existence a type with a new niche of your choosing. The example I gave was BalancedI32, a type which is exactly like i32 except that it doesn't use the most negative value. The most negative value of integers in a two's complement system is a weird outlier, so in many ways this is nicer to work with, but the niche also allows such a type to take advantage of the Guaranteed Niche Optimisation. Rust's String type is basically just a Vec<u8> with extra promises about the bytes (they're guaranteed to be a UTF-8 string) and there's nothing special about it, you can make your own and several people have. You can even use an existing niche to do clever things, as CompactString does.
    - anonymoushn 3y ago
      I agree I've misunderstood things. I thought that the general class of "some bytes that are guaranteed to only contain certain bit patterns" was addressed by a single feature, but actually there's a single feature that addresses this for only primitives and types similar to primitives in some sense. The builtin string type is doing some unrelated thing where it has a thing and it assumes that the thing will contain only a strict subset of the possible bit patterns of the thing or you get nasal demons, and user code is free to do that, but doing that is unrelated to niche optimizations. Thanks.
nayuki 3y ago
I don't know about other bigint libraries, but java.math.BigInteger uses two's complement, not sign-magnitude. This class is designed to imitate machine-size two's complement integers. The most negative value is a wart in two's complement, but negative zero is a wart in sign-magnitude and ones' complement. The advantage of ones' complement compared to sign-magnitude is that the former needs minimal circuitry to implement subtraction. Namely, it just needs to invert every bit and then feed it into the adder. You only need to avoid undefined behavior in two's complement in C and C++. UB is not a property of two's complement, but a particular language's design choices. I can assure you that there is no UB in two's complement in Java or x86 assembly. Note that offset-binary is used in IEEE 754 floating-point exponents.
- account42 3y ago
  > You only need to avoid undefined behavior in two's complement in C and C++. UB is not a property of two's complement, but a particular language's design choices. I can assure you that there is no UB in two's complement in Java or x86 assembly. The entire point of making unsigned arithmetic UB in C was to support different bit representations of negative numbers depending on the HW. I think the GP's point was that if you want two's complement wraparound behavior in languages where you are not allowed to wrap around signed integers you can get the same result with unsigned arithmetic.
- o11c 3y ago
  That's wrong, actually. It uses sign-magnitude internally, it just supports various bit-related operations as-if it were two's complement. https://github.com/openjdk/jdk/blob/28026434f74726d72857e781b8f1c3d12aba9125/src/java.base/share/classes/java/math/BigInteger.java#L173 https://github.com/openjdk/jdk/blob/28026434f74726d72857e781...
Sniffnoy 3y ago
IEEE decimal is definitely complicated and confusing, but it does seem to unambiguously be sign-magnitude? The confusing part is how the magnitude works, not how signedness works...
- o11c 3y ago
  The weird interleaving of the exponent with the mantissa - and the existence of noncanonical values - means you can't just through them into sign-magnitude integer comparison routines.
  - lifthrasiir 3y ago
    Isn't that interleaving is mainly used for making better use of bits? To me it is more like the limitation of exact power-of-two bit sizes, for example decimal40 (1 sign bit + 9 exponent bits + 30 mantissa bits) should have been not that bad. In comparison, decimal32 could have the following combinations: s e m 1 11 20 - 6 mantissa digits, exponent range too large (~10^+/-1000) 1 7 24 - 7 mantissa digits, exponent range too small (~10^+/-60) 1 7.6 23.3 - still 7 mantissa digits, but interleaving gives exponent range of ~10^+/-90 1 4 27 - 8 mantissa digits, exponent range too small to even contain binary32 1 1 30 - 9 mantissa digits but no usable exponent range I guess it is not the worst trade-off. Your point about non-canonical values is entirely valid though. I do know it is mostly due to the expensive normalization step, but that only sounds like a reason to always prefer DPD---there is little reason to define a decimal FP standard if it is not for hardwares nowadays.
  - Sniffnoy 3y ago
    Ah, I see. By "sign-magnitude" I just meant that the sign and the magnitude are stored independently, and I think that's the usual usage of the term; I wouldn't expect "a sign-magnitude format" to mean one where you can use sign-magnitude integer comparison.
anonymoushn 3y ago
A nit: a lot of uses of multiplication only care about a result type as wide as the input type. For these uses of multiplication, two's complement signed multiplication and reinterpreting the bits as unsigned then performing unsigned multiplication give the same result. When you start caring about i32 x i32 = i64 or i64 x i64 = i128 or bigint multiplies this stops being true because the bits you'd use to sign-extend the inputs can actually show up in the result.

by o11c 3y ago

tialaramex 3y ago

I don't think an integer NaN would be a good idea. People's intuition around the existing float NaNs is not good. I want to make user defined types like BalancedI32 (32bit signed integer but the magnitude of MAX and MIN are the same) possible in Rust. Today the stdlib is allowed to make NonZeroI32 which as its name suggests lacks zero but you can't make such types yourself except via wrapping these NonZero types with xor or similar. (In nightly Rust you can just break the rules and do the same thing the stdlib does, but there's no obligation to keep that working and it will never be stabilized) Because of the Guaranteed Niche Optimisation this means Option<BalancedI32> would have identical size to i32. So you get the same practicality as a normal signed integer with a sentinel value, but the same programming ergonomics as an expensive high level type.

lifthrasiir 3y ago
> People's intuition around the existing float NaNs is not good. I think that, if NaN was defined to be an unconditional trap but can be deferred for efficiency, then it could have worked much better. NaN surprises people because it was exposed in the first place, while it should really have been hidden behind the scene (because the presence of NaN means you are already wrong somewhere, and you are expected to be notified about that fact). In terms of Rust, say, every f32 operation could have returned `Result<f32, FloatError>` (mostly likely to be aliased though) that has the exactly same layout as the current f32. The current split between qNaN and sNaN (among others) is unnecessarily complex with little benefit.
anonymoushn 3y ago
Has Rust seriously committed to never stabilizing the ability for users to create types like the builtin string type? Wow.
- tialaramex 3y ago
  Huh? I think you might have skimmed what I wrote a bit too fast and didn't end up comprehending most of it. Some Rust types have niches, bit patterns which the type doesn't use. For example booleans take up a whole byte, but only need two bit patterns, leaving 254 unused. Today there is no stable way to conjure into existence a type with a new niche of your choosing. The example I gave was BalancedI32, a type which is exactly like i32 except that it doesn't use the most negative value. The most negative value of integers in a two's complement system is a weird outlier, so in many ways this is nicer to work with, but the niche also allows such a type to take advantage of the Guaranteed Niche Optimisation. Rust's String type is basically just a Vec<u8> with extra promises about the bytes (they're guaranteed to be a UTF-8 string) and there's nothing special about it, you can make your own and several people have. You can even use an existing niche to do clever things, as CompactString does.
  - anonymoushn 3y ago
    I agree I've misunderstood things. I thought that the general class of "some bytes that are guaranteed to only contain certain bit patterns" was addressed by a single feature, but actually there's a single feature that addresses this for only primitives and types similar to primitives in some sense. The builtin string type is doing some unrelated thing where it has a thing and it assumes that the thing will contain only a strict subset of the possible bit patterns of the thing or you get nasal demons, and user code is free to do that, but doing that is unrelated to niche optimizations. Thanks.

nayuki 3y ago

I don't know about other bigint libraries, but java.math.BigInteger uses two's complement, not sign-magnitude. This class is designed to imitate machine-size two's complement integers. The most negative value is a wart in two's complement, but negative zero is a wart in sign-magnitude and ones' complement. The advantage of ones' complement compared to sign-magnitude is that the former needs minimal circuitry to implement subtraction. Namely, it just needs to invert every bit and then feed it into the adder. You only need to avoid undefined behavior in two's complement in C and C++. UB is not a property of two's complement, but a particular language's design choices. I can assure you that there is no UB in two's complement in Java or x86 assembly. Note that offset-binary is used in IEEE 754 floating-point exponents.

account42 3y ago
> You only need to avoid undefined behavior in two's complement in C and C++. UB is not a property of two's complement, but a particular language's design choices. I can assure you that there is no UB in two's complement in Java or x86 assembly. The entire point of making unsigned arithmetic UB in C was to support different bit representations of negative numbers depending on the HW. I think the GP's point was that if you want two's complement wraparound behavior in languages where you are not allowed to wrap around signed integers you can get the same result with unsigned arithmetic.
o11c 3y ago
That's wrong, actually. It uses sign-magnitude internally, it just supports various bit-related operations as-if it were two's complement. https://github.com/openjdk/jdk/blob/28026434f74726d72857e781b8f1c3d12aba9125/src/java.base/share/classes/java/math/BigInteger.java#L173 https://github.com/openjdk/jdk/blob/28026434f74726d72857e781...

Sniffnoy 3y ago

IEEE decimal is definitely complicated and confusing, but it does seem to unambiguously be sign-magnitude? The confusing part is how the magnitude works, not how signedness works...

o11c 3y ago
The weird interleaving of the exponent with the mantissa - and the existence of noncanonical values - means you can't just through them into sign-magnitude integer comparison routines.
- lifthrasiir 3y ago
  Isn't that interleaving is mainly used for making better use of bits? To me it is more like the limitation of exact power-of-two bit sizes, for example decimal40 (1 sign bit + 9 exponent bits + 30 mantissa bits) should have been not that bad. In comparison, decimal32 could have the following combinations: s e m 1 11 20 - 6 mantissa digits, exponent range too large (~10^+/-1000) 1 7 24 - 7 mantissa digits, exponent range too small (~10^+/-60) 1 7.6 23.3 - still 7 mantissa digits, but interleaving gives exponent range of ~10^+/-90 1 4 27 - 8 mantissa digits, exponent range too small to even contain binary32 1 1 30 - 9 mantissa digits but no usable exponent range I guess it is not the worst trade-off. Your point about non-canonical values is entirely valid though. I do know it is mostly due to the expensive normalization step, but that only sounds like a reason to always prefer DPD---there is little reason to define a decimal FP standard if it is not for hardwares nowadays.
- Sniffnoy 3y ago
  Ah, I see. By "sign-magnitude" I just meant that the sign and the magnitude are stored independently, and I think that's the usual usage of the term; I wouldn't expect "a sign-magnitude format" to mean one where you can use sign-magnitude integer comparison.

anonymoushn 3y ago

A nit: a lot of uses of multiplication only care about a result type as wide as the input type. For these uses of multiplication, two's complement signed multiplication and reinterpreting the bits as unsigned then performing unsigned multiplication give the same result. When you start caring about i32 x i32 = i64 or i64 x i64 = i128 or bigint multiplies this stops being true because the bits you'd use to sign-extend the inputs can actually show up in the result.