Sign in to follow this  

Integer multiplication, division

This topic is 1925 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

[code]int16_t a = -255;
int16_t b = 409;
int16_t c = 1000;
int16_t result = a * b / c;[/code]

result: 26
expected: -104

What the heck is going on here?

Share this post


Link to post
Share on other sites
?255*409
104295

int16_t is signed 16bits, and thus it ranges from -32768 to 32767
as you can see, part of your equation is out of range, and will overflow the bits
-104 is correct, as far as the computer is concerned [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

i also believe (cant remember off the top of my head) that multiplication has presedence over division
which means that the multiplication happens first Edited by Kaptein

Share this post


Link to post
Share on other sites
But the final result -104 does not overflow the output buffer. It's clearly in the range, so it should be assigned no problem. I'm not sure I understand what's going on here.

Share this post


Link to post
Share on other sites
Actually, you're running out of precision in that operation. -255 * 409 is -104,295, but [font=courier new,courier,monospace]int16_t[font=arial,helvetica,sans-serif] [/font][/font]only has 16 bits of storage, which means it can only store values in the range ?32,768 to 32,767. So what happens? Your intermediate result gets chomped down to 16 bits *before* the divide happens, and the end result is a weird value due to [url="http://en.wikipedia.org/wiki/Integer_overflow"]overflow[/url].

What should you do about it? Use a bigger data type.

[quote name='Kaptein' timestamp='1349812004' post='4988451']
i also believe (cant remember off the top of my head) that multiplication has presedence over division
which means that the multiplication happens first
[/quote]
Not quite. Multiplication, division, and modulo all have the [url="http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B#Operator_precedence"]same precedence[/url]. I can't remember if the standard guarantees left to right evaluation in this case or not though. Edited by Cornstalks

Share this post


Link to post
Share on other sites
limitations for a declaration may cause some problems for calculation that is what causing problem with your calculation Edited by Uzumakis

Share this post


Link to post
Share on other sites
[quote name='Uzumakis' timestamp='1349812463' post='4988456']
try refreshing your compiler
[/quote]
Huh??? That makes no sense.

It's clearly due to overflow.

Share this post


Link to post
Share on other sites
I think you have found your answer from most of these replies. If you don't believe them then change them to int64_t and see the result

Share this post


Link to post
Share on other sites
[quote name='Cornstalks' timestamp='1349812336' post='4988454']
Actually, you're running out of precision in that operation. -255 * 409 is -104,295, but [font=courier new,courier,monospace]int16_t[font=arial,helvetica,sans-serif] [/font][/font]only has 16 bits of storage, which means it can only store values in the range ?32,768 to 32,767. So what happens? Your intermediate result gets chomped down to 16 bits *before* the divide happens, and the end result is a weird value due to [url="http://en.wikipedia.org/wiki/Integer_overflow"]overflow[/url].

What should you do about it? Use a bigger data type.

[/quote]

Could you please elaborate on that? What exactly is the factor that causes the calculation to be processed in 16-bit? Shouldn't the program detect that its running out of precision and automatically use a bigger (i.e. 32-bit) temporary buffer?

Which variables exactly should be increase in size?
EDIT: Is there a way to increase the temporary buffer size without changing the variable data types?

Share this post


Link to post
Share on other sites
The calculations are performed with 16 bits because the operands are 16 bits. The program is static and cannot dynamically expand the data types as necessary. Once compiled, it is compiled, and your program is compiled to use 16 bit integers. You can temporarily expand the type by casting the operands to int if you want the calculation to be performed in higher precision, though.
[code]
int16_t result = (int16_t)((int)a * (int)b / (int)c);
[/code]
On a side note, C++ does enforce integer promotion in this situation, so the result in C++ will be as you expected.
And on yet another side note, even when I tried to reproduce your results with VS2010 compiling the code as C code, I still get -104 so it appears it does integer promotion like C++ requires even in C.

Share this post


Link to post
Share on other sites
[quote name='Bismuth' timestamp='1349813240' post='4988462']
[quote name='Cornstalks' timestamp='1349812336' post='4988454']
Actually, you're running out of precision in that operation. -255 * 409 is -104,295, but [font=courier new,courier,monospace]int16_t[font=arial,helvetica,sans-serif] [/font][/font]only has 16 bits of storage, which means it can only store values in the range ?32,768 to 32,767. So what happens? Your intermediate result gets chomped down to 16 bits *before* the divide happens, and the end result is a weird value due to [url="http://en.wikipedia.org/wiki/Integer_overflow"]overflow[/url].

What should you do about it? Use a bigger data type.

[/quote]

Could you please elaborate on that? What exactly is the factor that causes the calculation to be processed in 16-bit? Shouldn't the program detect that its running out of precision and automatically use a bigger (i.e. 32-bit) temporary buffer?

Which variables exactly should be increase in size?
EDIT: Is there a way to increase the temporary buffer size without changing the variable data types?
[/quote]

That's not how it works. Yes there is something that causes the calculation to be processed in 16-bit...its the fact you told it that your values are all 16 bit signed integers. when you get an overflow, instead of crashing your program. The value gets wrapped around. so when you reach the max value, it goes back to 0 and starts counting up again.

Is there a reason you chose int16_t or did you copy it from somewhere. Like I said change it to int32_t or higher and see the results Edited by !Null

Share this post


Link to post
Share on other sites
Thank you for explaining the situation, this clears up my doubts. I am programming an application in AVR Studio 5.1 using gcc for an Atmega328p microcontroller. Due to limited RAM on a microcontroller (2 KB) I tend to stick to 8-bit and 16-bit variables. I did some tests and it seems that increasing at least one of the vars in the equation will produce the correct result.

This does not seem to work though.
int16_t result = (uint32_t)a * b / c; // does not work

I'll do some more tests.

Regards,
Bismuth

Share this post


Link to post
Share on other sites
[quote name='Brother Bob' timestamp='1349813870' post='4988466']
On a side note, C++ does enforce integer promotion in this situation, so the result in C++ will be as you expected.
And on yet another side note, even when I tried to reproduce your results with VS2010 compiling the code as C code, I still get -104 so it appears it does integer promotion like C++ requires even in C.
[/quote]
Actually, C has integer promotion rules as well (I'm pretty sure C++ got them from C in the first place). The only way that the result he's getting makes sense is if int on his compiler is 16-bits in which case manually casting to plain int isn't going to help either.

Share this post


Link to post
Share on other sites
[quote name='Bismuth' timestamp='1349814600' post='4988472']
Thank you for explaining the situation, this clears up my doubts. I am programming an application in AVR Studio 5.1 using gcc for an Atmega328p microcontroller. Due to limited RAM on a microcontroller (2 KB) I tend to stick to 8-bit and 16-bit variables. I did some tests and it seems that increasing at least one of the vars in the equation will produce the correct result.

This does not seem to work though.
int16_t result = (uint32_t)a * b / c; // does not work

I'll do some more tests.

Regards,
Bismuth
[/quote]
Your variable a holds a negative value and you're casting it to an unsigned integer. Unsigned variables cannot hold negative values. And yes, it is technically enough to cast just a or b, because the other operands will be promoted automatically.

[quote name='SiCrane' timestamp='1349814748' post='4988473']
[quote name='Brother Bob' timestamp='1349813870' post='4988466']
On a side note, C++ does enforce integer promotion in this situation, so the result in C++ will be as you expected.
And on yet another side note, even when I tried to reproduce your results with VS2010 compiling the code as C code, I still get -104 so it appears it does integer promotion like C++ requires even in C.
[/quote]
Actually, C has integer promotion rules as well (I'm pretty sure C++ got them from C in the first place). The only way that the result he's getting makes sense is if int on his compiler is 16-bits in which case manually casting to plain int isn't going to help either.
[/quote]
I was reading through both the C and C++ specification (the drafts only, but I doubt these details change) and the two were different in that C++ explicitly mentioned integer promotion for narrow integers and C did not; otherwise the wording was more or less identical. I did not read much more than that into it, so you may very well be right. Edited by Brother Bob

Share this post


Link to post
Share on other sites
[quote name='Brother Bob' timestamp='1349815016' post='4988474']
Your variable a holds a negative value and you're casting it to an unsigned integer. Unsigned variables cannot hold negative values. And yes, it is technically enough to cast just a or b, because the other operands will be promoted automatically.[/quote]
Eh, sorry it was a typo. I wonder why I typed uint anyway.

int16_t cc = (int32_t)aa * bb / (pe->fade_out); // This works.

Share this post


Link to post
Share on other sites
To clarify this a little bit, the C standard says this about evaluating an integer expression:
[quote]
If an [font=courier new,courier,monospace]int[font=arial,helvetica,sans-serif] [/font][/font]can represent all values of the original type, the value is converted to an [font=courier new,courier,monospace]int[/font]; otherwise, it is converted to an [font=courier new,courier,monospace]unsigned int[/font]. These are called the integer promotions. All other types are unchanged by the integer promotions.
[/quote]
If I'm understanding that right, on a 32-bit system (that is, when `int` is 32-bits), then yes, you'd get the right result of -104 because each operand is implicitly promoted to an `int`. But on a system where `int` is smaller than 32-bits, (like if `int` is 16-bits), then you'll have overflow. Which is exactly why you need to either use bigger datatypes or use that cast.

Share this post


Link to post
Share on other sites
[quote name='Cornstalks' timestamp='1349815741' post='4988478']
To clarify this a little bit, the C standard says this about evaluating an integer expression:
[quote]
If an [font=courier new,courier,monospace]int[font=arial,helvetica,sans-serif] [/font][/font]can represent all values of the original type, the value is converted to an [font=courier new,courier,monospace]int[/font]; otherwise, it is converted to an [font=courier new,courier,monospace]unsigned int[/font]. These are called the integer promotions. All other types are unchanged by the integer promotions.
[/quote]
If I'm understanding that right, on a 32-bit system (that is, when `int` is 32-bits), then yes, you'd get the right result of -104 because each operand is implicitly promoted to an `int`. But on a system where `int` is smaller than 32-bits, (like if `int` is 16-bits), then you'll have overflow. Which is exactly why you need to either use bigger datatypes or use that cast.
[/quote]

you live, you learn :)

Share this post


Link to post
Share on other sites
[quote name='Arthur Souza' timestamp='1349832552' post='4988563']
Just use 32 bit integers, I dont really see why trying so hard to use 16 bits, is there a reason for it?
[/quote]
The OP explained:
[quote name='Bismuth' timestamp='1349814600' post='4988472']
I am programming an application in AVR Studio 5.1 using gcc for an Atmega328p microcontroller. Due to limited RAM on a microcontroller (2 KB) I tend to stick to 8-bit and 16-bit variables.
[/quote]

Seems like a reasonable enough thing to do with limited memory.

Share this post


Link to post
Share on other sites
Sign in to follow this