Timeline for Integer version of c++ standard library midpoint
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 30, 2020 at 15:52 | comment | added | G. Sliepen | Let us continue this discussion in chat. | |
| Nov 30, 2020 at 15:50 | history | edited | G. Sliepen | CC BY-SA 4.0 |
deleted 605 characters in body
|
| Nov 30, 2020 at 13:45 | history | edited | Toby Speight | CC BY-SA 4.0 |
Typo fix
|
| Nov 29, 2020 at 22:44 | comment | added | namark |
I tried with gcc on x86_64, are you sure the assembly is the same for short and char? For example one of the failing cases looks like this midpoint(limits::max(), limits::min()) == T( 0) where T is singed char/short and limits is std::numeric_limits<T>.
|
|
| Nov 29, 2020 at 22:23 | comment | added | G. Sliepen | It's interesting that it doesn't pass the tests. What compiler and CPU architecture are you using? Clang and GCC produce the same assembly for your version as for mine. | |
| Nov 29, 2020 at 20:26 | comment | added | namark | The issue is not just signed overflow, it is promotion, which applies to all arithmetic, including unary minus, and prevents the modulo arithmetic that this method relies on. Your code still doesn't pass the tests, you probably need one or two more casts in your one-liner. Even if correct I think the code is less readable that way. That said nobody would even recognize what I wrote as code so who am I to judge. | |
| Nov 29, 2020 at 18:32 | history | edited | G. Sliepen | CC BY-SA 4.0 |
added 555 characters in body
|
| Nov 29, 2020 at 18:14 | comment | added | G. Sliepen |
I can only review the code you show here, so in that context the Unsigned template parameter is avoidable. If you need it in your code, then of course you should keep using it. If you want to be safe on platforms that do not have two's complement arithmetic, then still I would avoid the temporary variables, and write: return a + (b < a ? -Integer(-diff / 2) : Integer(diff / 2)).
|
|
| Nov 29, 2020 at 16:47 | comment | added | namark | It is possible that a single cast can be eliminated thanks to C++20's two's complement, but there are a lot more casts happening there, mainly to combat pesky promotion. I wonder what things might look like with something like safe_numerics library employed here, and what the codegen would be. | |
| Nov 29, 2020 at 16:43 | comment | added | namark |
The _2x does indeed mean 2 times, indicating that we are dealing with a number that is twice the range of our original (+1 bit), and only after properly halfing it can we assign it back to the original type. One should be familiar with 2's compliment to understand this code yes, but I think that's better than consider numerous edge cases. You might have not concidered char or short, and promotion rules, since you code is failing some test cases. You can check out the repo I linked, modify the midpoint there and run make test see the details.
|
|
| Nov 29, 2020 at 16:38 | comment | added | namark | I have Unsigned as template parameter to use the function for types other than the fundamental integers, without specializing std::make_unsigned_t, but that is out of context here, I wanted to discuss the implementation only, I was "forced" to include the signature. In context of standard spec of midpoint, I can criticize your signature as well to no end. | |
| Nov 29, 2020 at 14:50 | comment | added | G. Sliepen |
Hm now I wonder now if it should be -Integer(-diff / 2) or not, as you mentioned that this might be UB otherwise, but would it still be UB with C++20's mandatory two's complement signed integers?
|
|
| Nov 29, 2020 at 11:15 | history | answered | G. Sliepen | CC BY-SA 4.0 |