Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Almost Always Unsigned

graphitemaster.github.io

Post reply on HN
Print view View original

91–100 of 103 posts

Re: Almost Always Unsigned

#91

Post by amavect »

derdi wrote: post #82
amavect wrote: post #63

Earlier quoted context omitted.

I believe the main issue lies in most programming languages lacking theorem proving capabilities to prove the safety of integer operations. The safety conditions for unsigned arithmetic: Ensure y+x ≤ INT_MAX. If x ≤ UINT_MAX-y, then x+y evaluates correctly: ∀x∀y(x ≤ UINT_MAX-y → ∃z(z = y+x)) Ensure y-x ≤ INT_MAX. If x≤y, then y-x evaluates correctly: ∀x∀y(x≤y → ∃z(z = y-x)) The safety conditions for signed arithmetic…

What do you mean by notation like: Ensure y+x ≤ INT_MAX. Is this supposed to be a precondition? Why would I want this precondition when using unsigned arithmetic?

I included that to try to explain the symbol soup that correctly encodes the preconditions (the ∀ lines). I intended that to mean "I need to make sure that y+x doesn't overflow", even that unsigned arithmetic cannot express that precondition in that way, as you point out. From there, derive y ≤ INT_MAX-x as the actual precondition for unsigned addition. I forgot that "ensure" actually means something in some programming languages, sorry for the confusion.

More simply put, unsigned addition needs to check that y+x doesn't overflow, while signed addition needs to check that y+x doesn't overflow and doesn't underflow. So, unsigned arithmetic has a simpler precondition that would win a technical debate on whether to use signed or unsigned arithmetic, but since most programming languages lack theorem proving, signed arithmetic wins on the small integer assumption.

Re: Almost Always Unsigned

#92

Post by empw »

flohofwoe wrote: post #88
safercplusplus wrote: post #83

Earlier quoted context omitted.

But are we necessarily limited to native integer types? At least with C++, the type system is powerful enough to support integer replacement types (eg. [0][1]) that don't inherit these issues. (Where, for example, the subtraction of an unsigned from another unsigned returns a value of signed integer type.) Another advantage being the ability to customize the overflow/underflow handling policy per declaration (rather…

I would rather do away with signed vs unsigned integer types completely, and instead have sign-agnostic integers like down on the assembly level (the world has settled on two's-complement anyway). Signed-vs-unsigned only matters in one situation: when extending a narrow integer type to a wider integer type (e.g. "sign-extension"), and this could be an explicit operation. Beyond that, the decision whether a number is…

Wait till this guy learns about multiplication and division

Re: Almost Always Unsigned

#93

Post by [deleted] »

empw wrote: post #92
flohofwoe wrote: post #88

Earlier quoted context omitted.

I would rather do away with signed vs unsigned integer types completely, and instead have sign-agnostic integers like down on the assembly level (the world has settled on two's-complement anyway). Signed-vs-unsigned only matters in one situation: when extending a narrow integer type to a wider integer type (e.g. "sign-extension"), and this could be an explicit operation. Beyond that, the decision whether a number is…

Wait till this guy learns about multiplication and division

[deleted]

Re: Almost Always Unsigned

#94

Post by flohofwoe »

empw wrote: post #92
flohofwoe wrote: post #88

Earlier quoted context omitted.

I would rather do away with signed vs unsigned integer types completely, and instead have sign-agnostic integers like down on the assembly level (the world has settled on two's-complement anyway). Signed-vs-unsigned only matters in one situation: when extending a narrow integer type to a wider integer type (e.g. "sign-extension"), and this could be an explicit operation. Beyond that, the decision whether a number is…

Wait till this guy learns about multiplication and division

Yeah ok got me, but AFAIK at least multiplication is sign-agnostic when the result is clamped to the width of the inputs (e.g. the result of multiplying two 64-bit values being clamped to 64-bits). Not sure about division though.

But in any case: with 'sign-agnostic' integer types high level languages would simply need separate signed vs unsigned mul/div operators. Not a big thing when modern languages already have different operators for wraparound vs overflow-checked arithmetic (for instance + vs +% in Zig).

Re: Almost Always Unsigned

#95

Post by Nevermark »

derdi wrote: post #81
Nevermark wrote: post #77

using int64 = int64_t; using nat64 = uint64_t; There are no unsigned integers. Naturals, folks, naturals have no sign. Or, if you must, the positive integers: using pos64 = uint64_t;

Naturals have no 64-bit limit.

You understood the notation.

So "nat64" cleared up two notation deficiencies: correct base type, and explicit declaration of modularity.

A plain natural (unbounded/big) would be "nat" or "natural".

Re: Almost Always Unsigned

#96

Post by kazinator »

amavect wrote: post #91
derdi wrote: post #82

Earlier quoted context omitted.

What do you mean by notation like: Ensure y+x ≤ INT_MAX. Is this supposed to be a precondition? Why would I want this precondition when using unsigned arithmetic?

I included that to try to explain the symbol soup that correctly encodes the preconditions (the ∀ lines). I intended that to mean "I need to make sure that y+x doesn't overflow", even that unsigned arithmetic cannot express that precondition in that way, as you point out. From there, derive y ≤ INT_MAX-x as the actual precondition for unsigned addition. I forgot that "ensure" actually means something in some programm…

In two's complement, calculating the overflow for addition is nearly exactly as complex as calculating carry for unsigned arithmetic.

Various versions of the Motorola 68000 programmer's manuals have a table which succinctly shows the Boolean formulas for calculating the flags for various operations.

In the following document it is Table 3-18. Integer Unit Condition Code Computations:

https://www.nxp.com/docs/en/reference-manual/M68000PRM.pdf

The ADD operation is in the second row of the table. See how in the right column, the calculation of C (carry out of highest bit) and V (overflow) have about the same complexity. V has only two "not" inversions compared to C's three, but otherwise both have six operands reduced via five "and" or "or" operations. C is a sum of two three-term products, V is a sum of three two-term products.

These calculations assume that we perform the addition as unsigned, and so we then have access to all three operands: the S, D, and R (source, destination and result). (That terminology is specific to the MC68K whose instruction set doesn't support the result going to a third operand which is not one of the two input operands.)

All the difficulties come from the higher level language semantics that don't provide a way to safely perform an overflowing operation and then detect overflow from a calculation applied to the two inputs and result.

I.e. some assembly-language-like "higher level" languages make things worse than assembly language, for the sake of abstraction and portability.

Re: Almost Always Unsigned

#97

Post by gwerbin »

flohofwoe wrote: post #76
delta_p_delta_x wrote: post #56

I have a better solution: address the root cause of unsafe semantics by not using raw indexed for-loops, unless one absolutely needs an index, in which case one should generate it with std::views::enumerate. To reverse it, use std::views::enumerate | std::views::reverse. Ditto for languages with similar semantics. I almost never write a raw for-i loop any more, especially since 99% of the time I want to enumerate thr…

Loop counters really are not the problem. The problem is that even when using unsigned integers you often want to do 'signed math' on them (e.g. adding a negative amount, or you could have an expression made entirely of unsigned integers (like ((x - y) + z) where an intermediate result may become negative even when the end result is positive - and in languages with overflow check that may result in a panic). A better…

Inductive number types seem pretty appealing here. A type like "Nat = Zero | Succ Nat" is 100% always correct by construction and can be safely transformed into raw integers (and operations thereon) by the compiler. And it is also precisely the correct number type for array indices.

If you can open your mind to dependent types, then Fin is even better, which also avoids overflow by construction. But then again dependent types are a whole different beast when it comes to compilers and language capabilities and so on.

Re: Almost Always Unsigned

#98

Post by gumby »

tialaramex wrote: post #19
gumby wrote: post #10

Earlier quoted context omitted.

> for instance C and C++ leave signed integer wrap undefined Not in C++29, and I think the big 3 compilers (gcc, clang, MS) will have squashed this long before that version is officially approved.

> Not in C++29 C++ 29 doesn't yet exist. It'll be finalised in (as its name suggests) 2029. Are you referring to some proposal you think has been accepted? Or is this one of those "I have concepts of a proposal?" ideas where you confused wishful thinking with reality ?

The "list of undefined behaviour" annex has been written and was discussed at the last meeting. As I said, some of what's in it are already being implemented by the big compilers (though TBF to your comment not yet in any released versions as far as I know).

But this case will be one of the early ones.

Re: Almost Always Unsigned

#99

Post by orlp »

shaggie76 wrote: post #61

While I'm a fan of unsigned (size_t mostly) there have been a few times when the tax for converting them to float was shockingly high: https://godbolt.org/z/96T4jTshc 1-2 instructions for signed vs 11 including a branch for unsigned. (in times like these I found casting to signed first preferable)

That's a GCC skill issue. You can do it in five branchless instructions for unsigned by splitting the unsigned up in two 32-bit halves, converting those to floats simply by inserting their values as mantissa into constants 2^52 and 2^(52 + 32). This conversion is exact.

Then to finish the conversion you subtract 2^52 and 2^(52 + 32) respectively from the halves and add them together.

    vmovq       xmm0, rdi
    vpunpckldq  xmm0, xmm0, xmmword ptr [rip + .CONST1]
    vsubpd      xmm0, xmm0, xmmword ptr [rip + .CONST2]
    vshufpd     xmm1, xmm0, xmm0, 1
    vaddsd      xmm0, xmm1, xmm0
Here CONST1 = [0x43300000, 0x45300000, 0, 0] and CONST2 = [0, 0x43300000, 0, 0x45300000].

Re: Almost Always Unsigned

#100

Post by Chu4eeno »

StellarScience wrote: post #87
nazcan wrote: post #20

Earlier quoted context omitted.

Thanks for the excerpts! I was trying to understand the reasoning, which seem to just be in the 2nd excerpt: - The rules of signed/unsigned are complicated and there is too much auto-conversion - does that mean languages that make this more explicit means this is fine? It just seems ideal to have stronger typing. - It is mentioned that you can initialized an unsigned int to "-2" - but that presumably could also be fi…

> I'm trying to separate out which is "don't do this in C/C++" and which is "don't do this in any language". To achieve high performance, any language would need to implement integer addition with a single machine instruction like 'ADD'. Languages can achieve more intuitive behavior by adding an operand check before the 'ADD', or by using an 'ADC' instruction and checking the carry bit afterwards. But adding branch s…

in C/C++ you have __builtin_add_overflow(), __builtin_sub_overflow(), __builtin_mul_overflow()
Post reply on HN