Jump to content

  • Log In with Google      Sign In   
  • Create Account

Integer multiplication, division


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
17 replies to this topic

#1 Bismuth   Members   -  Reputation: 105

Like
0Likes
Like

Posted 09 October 2012 - 01:37 PM

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

result: 26
expected: -104

What the heck is going on here?

Sponsor:

#2 Kaptein   Prime Members   -  Reputation: 2180

Like
0Likes
Like

Posted 09 October 2012 - 01:46 PM

?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 Posted Image

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, 09 October 2012 - 01:50 PM.


#3 Bismuth   Members   -  Reputation: 105

Like
0Likes
Like

Posted 09 October 2012 - 01:51 PM

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.

#4 Cornstalks   Crossbones+   -  Reputation: 6991

Like
1Likes
Like

Posted 09 October 2012 - 01:52 PM

Actually, you're running out of precision in that operation. -255 * 409 is -104,295, but int16_t 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 overflow.

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

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

Not quite. Multiplication, division, and modulo all have the same precedence. I can't remember if the standard guarantees left to right evaluation in this case or not though.

Edited by Cornstalks, 09 October 2012 - 01:54 PM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#5 Uzumakis   Members   -  Reputation: 130

Like
-4Likes
Like

Posted 09 October 2012 - 01:54 PM

limitations for a declaration may cause some problems for calculation that is what causing problem with your calculation

Edited by Uzumakis, 09 October 2012 - 01:57 PM.


#6 Cornstalks   Crossbones+   -  Reputation: 6991

Like
1Likes
Like

Posted 09 October 2012 - 01:56 PM

try refreshing your compiler

Huh??? That makes no sense.

It's clearly due to overflow.
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#7 !Null   Members   -  Reputation: 380

Like
1Likes
Like

Posted 09 October 2012 - 01:57 PM

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
/********************************************************************************\
/**********************He Who Dares, Wins**********************************\
/********************************************************************************\

#8 Bismuth   Members   -  Reputation: 105

Like
0Likes
Like

Posted 09 October 2012 - 02:07 PM

Actually, you're running out of precision in that operation. -255 * 409 is -104,295, but int16_t 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 overflow.

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


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?

#9 Brother Bob   Moderators   -  Reputation: 8607

Like
3Likes
Like

Posted 09 October 2012 - 02:17 PM

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.
int16_t result = (int16_t)((int)a * (int)b / (int)c);
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.

#10 !Null   Members   -  Reputation: 380

Like
1Likes
Like

Posted 09 October 2012 - 02:18 PM


Actually, you're running out of precision in that operation. -255 * 409 is -104,295, but int16_t 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 overflow.

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


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?


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, 09 October 2012 - 02:19 PM.

/********************************************************************************\
/**********************He Who Dares, Wins**********************************\
/********************************************************************************\

#11 Bismuth   Members   -  Reputation: 105

Like
0Likes
Like

Posted 09 October 2012 - 02:30 PM

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

#12 SiCrane   Moderators   -  Reputation: 9671

Like
1Likes
Like

Posted 09 October 2012 - 02:32 PM

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.

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.

#13 Brother Bob   Moderators   -  Reputation: 8607

Like
1Likes
Like

Posted 09 October 2012 - 02:36 PM

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

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.


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.

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.

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, 09 October 2012 - 02:38 PM.


#14 Bismuth   Members   -  Reputation: 105

Like
0Likes
Like

Posted 09 October 2012 - 02:44 PM

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.

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.

#15 Cornstalks   Crossbones+   -  Reputation: 6991

Like
2Likes
Like

Posted 09 October 2012 - 02:49 PM

To clarify this a little bit, the C standard says this about evaluating an integer expression:

If an int can represent all values of the original type, the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions. All other types are unchanged by the integer promotions.

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.
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#16 Kaptein   Prime Members   -  Reputation: 2180

Like
0Likes
Like

Posted 09 October 2012 - 03:40 PM

To clarify this a little bit, the C standard says this about evaluating an integer expression:


If an int can represent all values of the original type, the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions. All other types are unchanged by the integer promotions.

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.


you live, you learn :)

#17 Arthur Souza   Members   -  Reputation: 1419

Like
0Likes
Like

Posted 09 October 2012 - 07:29 PM

Just use 32 bit integers, I dont really see why trying so hard to use 16 bits, is there a reason for it?

A.

Lotus - Action RPG In development http://www.gamedev.n...die-rpg-engine/ |
Personal blog In Portuguese: lotuzgames.wordpress.com |


#18 Cornstalks   Crossbones+   -  Reputation: 6991

Like
1Likes
Like

Posted 09 October 2012 - 07:40 PM

Just use 32 bit integers, I dont really see why trying so hard to use 16 bits, is there a reason for it?

The OP explained:

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.


Seems like a reasonable enough thing to do with limited memory.
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS