Integers

[Paavo Helde]

Found a new C++ quiz question (in the hard way unfortunately). What does
the following program do when executed?

#include <iostream>
#include <stdint.h>
int main() {
uint16_t x = 50000;
uint16_t y = 50000;
uint32_t z = x*y;
std::cout << z << "\n";
}

Hint: when compiling with gcc do not forget the -ftrapv option.

[Marcel Mueller]

Am 03.01.19 um 14:04 schrieb Paavo Helde:

>
> Found a new C++ quiz question (in the hard way unfortunately). What does
> the following program do when executed?
>
> #include <iostream>
> #include <stdint.h>
> int main() {
>     uint16_t x = 50000;
>     uint16_t y = 50000;
>     uint32_t z = x*y;
>     std::cout << z << "\n";
> }

The result is platform dependent. When int has 16 bit it is just
undefined, because of the overflow.
In case of 32 bit int the result is still undefined because the result
does not fit into a 32 bit /signed/ int. However, the binary result of
the signed multiplication happens to be the same than the mathematical
correct result in case of 2's complement representation of signed numbers.


Marcel

[Paavo Helde]

Right, 32-bit int and 2's complement is the only environment I ever have
to care about, and knowing a bit of assembler there is no way how the
result could be wrong - that is, unless the compiler specifically ruins
it. When compiling the above with gcc on a common x86_64 Linux box:

> g++ -ftrapv -Wall -Wextra test1.cpp
> ./a.out
Aborted (core dumped)

Yes I know I asked it myself with the -ftrapv option, but I wanted to
use it in order to find out real bugs in the program, not the illusory ones.

[Öö Tiib]

But 50000 * 50000 does overflow when int is 32 bits and signed
overflow is explicitly classified as undefined behavior. It is not
illusory but actual undefined behavior. The compiler makers were
quite anal with their "optimizations" exploiting that kind of
"undefined behaviors" only recently.

[james...@alumni.caltech.edu]

If UINT_MAX == 0xFFFF, then x and y get multiplied as uint16_t values.
The product is well defined as 2500000000 modulo 0x10000 = 63744, which
then gets converted to uint31_t without change of value, with the result
that 63744 should be printed out by the cout.

In the extremely unlikely (but permitted) case that UINT_MAX > 65535
while INT_MAX < 65535, then x and y will both be promoted to unsigned
int before the multiplication, and the result will be 2500000000 modulo
(UINT_MAX+1ULL). This will be converted to uint32_t by taking it modulo
0x100000000, which might involve a change of value if
UINT_MAX > 0xFFFFFFFF. That value in decimal format will be printed out
by cout.

If INT_MAX > 65535, then x and y will both be promoted to int before the
multiplication. If so:

If INT_MAX >= 2500000000, then the multiplication will not overflow.
Converting the result to uint32_t in order to save it in z will leave
the value unchanged, and that is what will be printed out by cout.

Otherwise, the multiplication will overflow, with undefined behavior. However, if int is a 2's complement type, the actual behavior is likely to be exactly the same as the previous case.

Which of these cases applied when you found the answer "the hard way"?

[Paavo Helde]

32-bit int, 2's complement, gcc -ftrapv option. And of course the code
was not so simple as in this example, it was template code multiplying
large vectors of any numeric types.

[bitrex]

I think these type of interview questions are usually asked by places
who have a specific answer in mind and if you answer (correctly) with
"well, it depends" you're not going to get points for that - even the
interviewer hasn't fully thought it over.

I could've probably thought up the first paragraph UINT_MAX = 0xFFFF
case on the spot recalling unsigned integer overflow is generally
well-defined while signed is not but as for the rest of it I doubt it.
Do I win? Do I lose?

Unsigned integer wrap is listed by SEI CERT C++ standard as a "likely"
error with Severity: High - it's a security risk when indexing into
arrays hello stack overflow! I might frame my answer in terms of that
whatever happens exactly don't do it!

[bitrex]

With the possibly incorrect assumption that's in fact what it was,
depending on the job interview questions about common C++ mistakes which
are judged to be severe security risks when done wrong is probably a
good idea

[Alf P. Steinbach]

On 03.01.2019 17:24, james...@alumni.caltech.edu wrote:
> On Thursday, January 3, 2019 at 8:04:15 AM UTC-5, Paavo Helde wrote:
>> Found a new C++ quiz question (in the hard way unfortunately). What does
>> the following program do when executed?
>>
>> #include <iostream>
>> #include <stdint.h>
>> int main() {
>> uint16_t x = 50000;
>> uint16_t y = 50000;
>> uint32_t z = x*y;
>> std::cout << z << "\n";
>> }
>>
>> Hint: when compiling with gcc do not forget the -ftrapv option.
>
> If UINT_MAX == 0xFFFF, then x and y get multiplied as uint16_t values.

Effectively, but formally not quite.

In this case type `int` cannot represent all values of the source type
`uint16_t`, and so integral promotion of the operands to `*`, IF it is
performed, will convert them to `unsigned`. Which in this case is also
16 bits. So that's the “effectively”, but the formal type for the case
of promotion is `unsigned`, not `uint16_t`, which *might* be a distinct
type, e.g. `unsigned short`.

Promotion can happen when `uint16_t` is a distinct type from `unsigned`,
e.g. when it's `unsigned short`, so that it has lower conversion rank
than `int`.

Relevant standardese:

C++17 §8.6/2 about multiplicative operators, including `*`: “The usual
arithmetic conversions are performed on the operands and determine the
type of the result.”

C++17 8/11.5 about usual arithmetic conversions: “Otherwise [not
floating point], the integral promotions (7.6) shall be performed on
both operands. Then the following rules shall be applied […]”

C++17 §7.6/1 about integral promotion: “A prvalue of an integer type
other than bool , char16_t , char32_t , or wchar_t whose integer
conversion rank (7.15) is less than the rank of int can be converted to
a prvalue of type int if int can represent all the values of the source
type; otherwise, the source prvalue can be converted to a prvalue of
type unsigned int”

C++17 $7.15/1.3, about conversion ranks: “The rank of long long int
shall be greater than the rank of long int, which shall be greater than
the rank of int, which shall be greater than the rank of short int,
which shall be greater than the rank of signed char.”

C++17 $7.15/1.4: “The rank of any unsigned integer type shall equal the
rank of the corresponding signed integer type.”

So, in the case where promotion is performed, which as far as I can see
is only when `uint16_t` is defined as `unsigned short`, the result type
is `unsigned`, not `uint16_t`.

Disclaimer: it's late in the day for me, AND I don't have a
standard-conforming 16-bit C++ compiler to try this out on. But. Still
sounds right when I read what I wrote! :)

> The product is well defined as 2500000000 modulo 0x10000 = 63744, which
> then gets converted to uint31_t without change of value, with the result
> that 63744 should be printed out by the cout.
>
> In the extremely unlikely (but permitted) case that UINT_MAX > 65535
> while INT_MAX < 65535, then x and y will both be promoted to unsigned
> int before the multiplication, and the result will be 2500000000 modulo
> (UINT_MAX+1ULL). This will be converted to uint32_t by taking it modulo
> 0x100000000, which might involve a change of value if
> UINT_MAX > 0xFFFFFFFF. That value in decimal format will be printed out
> by cout.
>
> If INT_MAX > 65535, then x and y will both be promoted to int before the
> multiplication. If so:
>
> If INT_MAX >= 2500000000, then the multiplication will not overflow.
> Converting the result to uint32_t in order to save it in z will leave
> the value unchanged, and that is what will be printed out by cout.
>
> Otherwise, the multiplication will overflow, with undefined behavior. However, if int is a 2's complement type, the actual behavior is likely to be exactly the same as the previous case.
>
> Which of these cases applied when you found the answer "the hard way"?

Cheers!,

- Alf

[james...@alumni.caltech.edu]

So, does the range of behavior described above match how your template
should behave, depending upon the types involved? If not, you should
change your code so the defined behavior does match your desires.
Assuming that the template parameters corresponding to uint16_t and
uint32_t are named T and U respectively, then

U z = U(x)*U(y);

might reduce the number of unexpected results (depending upon what you're expecting).

However you said that this template is intended for use with any numeric
type. keep in mind that if T, for instance, is double, and U is float,
there's the possibility that x*y might have a value that is in the
normal range of values for float, but U(x) might fail because x is too
big, or U(y) might suffer unnecessary loss of precision because y is too
small; either way, U(x)*U(y) would not give the best result.

Similar but more complicated issues arise if T is a complex type, and U
is a real type.

[james...@alumni.caltech.edu]

Simply saying "it depends" would certainly not win points. However,
giving a correct and complete description of how it depends upon the
features of the implementation should win me the maximum possible
points. I can imagine two possible exceptions: the interviewer doesn't
recognize it as a correct answer, or is afraid of hiring someone who
knows more than he does. Either way, it's probably not a place I'd want
to work.

[james...@alumni.caltech.edu]

You're right. But no matter how uint16_t is typedef'd, the result is always multiplication as unsigned 16 bit integers. I decided to gloss over that complication in a posting that was already overly-complex.

[bitrex]

<https://herbsutter.com/2018/11/13/trip-report-fall-iso-c-standards-meeting-san-diego/>

"For comparison, even excluding the biggest paper which was the updated
C++ standard working draft which appears in every mailing, the
pre-meeting mailing was enormous:

By word count, it exceeded Shakespeare’s complete published works."

They write like they're proud of this!

[Siri Cruise]

Turing created integers, all the rest is the work of IEEE.

--
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @
'I desire mercy, not sacrifice.' /|\
The first law of discordiamism: The more energy This post / \
to make order is nore energy made into entropy. insults Islam. Mohammed

[james...@alumni.caltech.edu]

On Thursday, January 3, 2019 at 2:50:45 PM UTC-5, bitrex wrote:
...

> <https://herbsutter.com/2018/11/13/trip-report-fall-iso-c-standards-meeting-san-diego/>
>
> "For comparison, even excluding the biggest paper which was the updated
> C++ standard working draft which appears in every mailing, the
> pre-meeting mailing was enormous:
>
> By word count, it exceeded Shakespeare’s complete published works."
>
> They write like they're proud of this!

Keep in mind that that's the total size of the proposals for changes to
the C++ standard. If he is indeed proud of that number it's only because
that large it shows the amount of interest people have in the C++
standard. His use of "enormous" implies to me that he thought it was an
appallingly large amount of text to have to read.

[bitrex]

I think I'd prefer to read the complete published works of Shakespeare
if there's an option...

[Paavo Helde]

Thanks for the suggestions, this seems the way to go.

>
> However you said that this template is intended for use with any numeric
> type. keep in mind that if T, for instance, is double, and U is float,
> there's the possibility that x*y might have a value that is in the
> normal range of values for float, but U(x) might fail because x is too
> big, or U(y) might suffer unnecessary loss of precision because y is too
> small; either way, U(x)*U(y) would not give the best result.
>
> Similar but more complicated issues arise if T is a complex type, and U
> is a real type.

That's good to keep in mind too.