How does division work?

[JBotAlan]

Hey all,

I feel really dumb asking this question, but since I don't have a programming mentor I must rely on what I read, and the community. Since I don't know what to search for ("division" brought up tons of non-related posts...what else should I search for?) I am just going to post this. Sorry if it's a repeat.

If I'm using all integers, how will the RC calculate these:
30/7 = (It rounds to 4, so I assume I'd get 4)
70/6 = (This is where I'm confused...it's 11.6666..., but will the robot round it, or take the floor? Meaning, do I get 12, or 11? I don't have the hardware in front of me to experiment with...)

Thanks for helping with a n00b question...

JBot

[jtdowney]

If you are typecasting a float to an int. Such as

int i = (int) (70/6)

You will always get the floor.

[BigJ]

It will truncate the numbers after the decimal point.

[comphappy]

If you need the extra places the most efficient way to do it will be to bit shift the dividend, and remember that any time you need to do a calculation, you need to bit shift the result back. using bit shift instead of multiplying by something like 10 will save you a few clock cycles.

multiplication 8-bit by 8-bit method (if you multiply by an arbitrary value such as 10)
see here http://www.dcc.unicamp.br/~celio/mc4...los/mul8x8.asm

Program Memory : 14 locations
# of cycles : 71
RAM : 5 locations
That is a really big waist

bit shift method
c equivalent
x<<1;

can be done with the single asm command lrol (load and rotate left)

[Kevin Sevcik]

Originally Posted by comphappy

If you need the extra places the most efficient way to do it will be to bit shift the dividend, and remember that any time you need to do a calculation, you need to bit shift the result back. using bit shift instead of multiplying by something like 10 will save you a few clock cycles.

multiplication 8-bit by 8-bit method (if you multiply by an arbitrary value such as 10)
see here http://www.dcc.unicamp.br/~celio/mc4...los/mul8x8.asm

Program Memory : 14 locations
# of cycles : 71
RAM : 5 locations
That is a really big waist

bit shift method
c equivalent
x<<1;

can be done with the single asm command lrol (load and rotate left)

Noooooooo..... See, I too though I'd be clever and use fixed point math like this. But PIC's specification of ANSI C has an interesting quirk. All right shifts are treated as unsigned. So if you have a signed int (-500) that you right shift by one bit, you don't get -250. You get 32518. There are obviously ways to compensate like making sure all your values are positive by using offsets, etc. But don't just assume that >>1 is an innocent substitute for /2.

[comphappy]

I never use signed vars (why would i want to limit my self to a predetermined split), so this is not a problem that i face. Still implementing a macro or function to do this is would be much more efficient then that multiplication nonsense.
I could see how there might be issues with signed vars. seeing as it is spans 16 bits and has to manage the split, it would have to do some interesting stuff to move that all around, and not end up shoving data in to the + side. I would have to look at the asm and memory sim to see what is actually happening (when are they going to get some real debugging tools to work with these). Anyway while on this topic people might find this of interest.
http://www.microchipc.com/Hi-Tech_C_speed_optimization/
I am a little paranoid when it come to data size and clock cycles if you could not tell.

EDIT:
fyi the shift you have to do for signed is called Arithmetic Shift.

[JoeXIII'007]

Originally Posted by JBotAlan

Hey all,

I feel really dumb asking this question, but since I don't have a programming mentor I must rely on what I read, and the community. Since I don't know what to search for ("division" brought up tons of non-related posts...what else should I search for?) I am just going to post this. Sorry if it's a repeat.

If I'm using all integers, how will the RC calculate these:
30/7 = (It rounds to 4, so I assume I'd get 4)
70/6 = (This is where I'm confused...it's 11.6666..., but will the robot round it, or take the floor? Meaning, do I get 12, or 11? I don't have the hardware in front of me to experiment with...)

Thanks for helping with a n00b question...

JBot

Good question... it becomes much of a shocker when you start investigating computer science, you just got to grill it into you head a bit.

type int: The computer will basically divide it as many times evenly into whole number, not part of a whole, and not one more. Since all the computer knows is zeros and ones, at least for type int, it sticks to its whole number interpretation, and fills what it can.

Thus your 70/6 goes to 11... along with 66/6, 67, 68, 69, and 71/6. 72/6 will of course yield 12 though. (Truncation, not rounding... be careful about this difference)

Once you get into type double and float (i think), then the computer believes it can handle decimals, and it will give you decimal answers.


Side note somewhat related: The modulus (%) operator is amazingly useful if you want to find the remainder, for that is what it does. Its even more useful for determining if a given integer is odd or even given you divide by 2 (Example: 66 % 2 gives you 0 since it is even, 65 % 2 gives you 1 since it is odd).

So if I were to run through that above problem again, this time with modulus:

66 % 6 = 0
67........= 1
68........= 2
69........= 3
70........= 4
71........= 5
72........= 0

Have fun... and never be afraid to ask questions after a search goes nowhere.

-Joe

[Salik Syed]

Originally Posted by comphappy

If you need the extra places the most efficient way to do it will be to bit shift the dividend, and remember that any time you need to do a calculation, you need to bit shift the result back. using bit shift instead of multiplying by something like 10 will save you a few clock cycles.

multiplication 8-bit by 8-bit method (if you multiply by an arbitrary value such as 10)
see here http://www.dcc.unicamp.br/~celio/mc4...los/mul8x8.asm

Program Memory : 14 locations
# of cycles : 71
RAM : 5 locations
That is a really big waist

bit shift method
c equivalent
x<<1;

can be done with the single asm command lrol (load and rotate left)

I would warn against using this for the reasons outlined before (granted it *should* work)...
The key reason being that you as a programmer really shouldn't have to worry about things like that as it is the compilers problem. Most compilers are written so that operations are optimized (for special cases like the one above).
Unless you are writing hardware drivers you don't need to worry about assembly level optimization. Even hardware shaders (which are run directly on graphics cards) are now written in a C-like language rather than in assembly like before.

[comphappy]

Originally Posted by Salik Syed

I would warn against using this for the reasons outlined before (granted it *should* work)...
The key reason being that you as a programmer really shouldn't have to worry about things like that as it is the compilers problem. Most compilers are written so that operations are optimized (for special cases like the one above).
Unless you are writing hardware drivers you don't need to worry about assembly level optimization. Even hardware shaders (which are run directly on graphics cards) are now written in a C-like language rather than in assembly like before.

Once again we disagree on this point. I think the programmer should always be aware of what is going on in his software especially in embedded systems space and clock cycles are vital, then again this paranoia could stem from my work on drivers in the Linux Kernel.

[Bongle]

Originally Posted by JoeXIII'007

Side note somewhat related: The modulus (%) operator is amazingly useful if you want to find the remainder, for that is what it does. Its even more useful for determining if a given integer is odd or even given you divide by 2 (Example: 66 % 2 gives you 0 since it is even, 65 % 2 gives you 1 since it is odd).

A more efficient way of checking oddness or even-ness is to use bitwise AND with 1 (though a smart compiler will probably do this anyway).

Bitwise AND ands together each binary digit of the two inputs.

4 & 1 = 0
5 & 1 = 1
6 & 1 = 0

Binary example:
5 & 1:
0011 <-- 5
0001 <-- 1
0001 <-- 5 & 1

[Salik Syed]

Originally Posted by comphappy

Once again we disagree on this point. I think the programmer should always be aware of what is going on in his software especially in embedded systems space and clock cycles are vital, then again this paranoia could stem from my work on drivers in the Linux Kernel.

Point taken, though with moores law in effect, processing power is almost expendable and the problem with focusing on assembly optimization is that it will ALWAYS give you a linear return where as algorithmic optimization can often result in exponential returns. Most complex problems will be solved via algorithmic optimization. As computers get faster details like whether you %2 or >>1 won't matter (although even now those are already taken care of for you)

Still, I must agree that with embedded systems where there is extremely limited CPU/Memory that stuff does count.

[Jon Stratis]

Just to throw in my two cents here:

first for the OP - integer division ALWAYS truncates (at least it does it most of the major languages in use today). If you need more significant digits, by far the easiest solution is to typecast your variables (both the divisor and the dividend) - int a=1; int b=2; float c=((float) a)/((float) b); gives you c = 0.5.

Second, to the discussion on bitwise operations and performance: For these robots, you really don't need to be that concerned with performance. If you follow the KISS (keep it simple, stupid) strategy, you're code won't be long enough of complicated enough to make performance an issue. When it comes to the robot controller, the difference between doing something one way or another might be a few milliseconds, but the human operator is only operating on the scale of seconds, so the level of performance you might gain is going to be lost, unless you've made your code overly complex.

Last year, our code was probably two-three times more complex than it needed to be, because we were using it as a teaching tool more than anything else, and the same thing will be true this year. Even with that, though, there was absolutely no detectable performance degradation to the robot.

Yes, in some systems performance really does matter - i remember back in school making an AI for class and fine tuning everything, down to the point where each game state was sized to exactly fit into the processor cache and using optimizations for the specific brand/model of the processor being used, and in that case it did pay off in noticeable quantities. It's good as a programmer to be aware of performance, and even to be aware of the performance characteristics of the libraries you're using, but you also need to know when you need to apply that knowledge and when you don't.

[JohnC]

If you add 0.5, it will "round" to the nearest integer:

int x = (int)(40/9 + 0.5); // 40/9 = 4.444 repeating and rounds down to 4

int y = (int)(40/6 + 0.5); // 40/6 = 6.666 repeating, rounds up to 7

[dcbrown]

If you add 0.5, it will "round" to the nearest integer:

int x = (int)(40/9 + 0.5); // 40/9 = 4.444 repeating and rounds down to 4

int y = (int)(40/6 + 0.5); // 40/6 = 6.666 repeating, rounds up to 7

Tried this in C18 and the compile still comes up with the wrong answer.

174:                   var1 = (int)((40/6)+0.5);
 04464    0E06     MOVLW 0x6                                   << compiler gens 6
 04466    0101     MOVLB 0x1
 04468    6FE6     MOVWF 0xe6, BANKED
 0446A    6BE7     CLRF 0xe7, BANKED

Instead the following will generate the expected results:

175:                   var1 = (int)((40+(6/2))/6);
 0446C    0E07     MOVLW 0x7                                     << compiler gens 7
 0446E    6FE6     MOVWF 0xe6, BANKED
 04470    6BE7     CLRF 0xe7, BANKED

The above is the same as adding .5 to the end result, just before the actual division.

If you try this with variables in the formula instead of constants, then the compiler can't figure out the answer at compile-time and generates the necessary code to figure this out at run-time. Adding 0.5 may cause conversion into and out of floating point which are really slow operations.

A more correct integer based answer would be:

    var1 = ((var2*10)+(divisor*10)/2))/(divisor*10);

This changes the floating point .5 into an integer 5 and preserves precision. Or you can roll your own integer divide routine and add in rounding based upon the remainder being larger than half the divisor.

However, in the case of an odd divisor such as 9, the remainder can only be 4 or 5 - not 4.5. So this suggests the simplier form below of should yield the correct answer:

    var1 = ((var2+(divisor/2)) / divisor;

In the examples:
(40+(9/2)) / 9 = 44 / 9 = 4
(40+(6/2)) / 6 = 43 / 6 = 7

or did I mess up... again...

[Jon Stratis]

Originally Posted by JohnC

If you add 0.5, it will "round" to the nearest integer:

int x = (int)(40/9 + 0.5); // 40/9 = 4.444 repeating and rounds down to 4

int y = (int)(40/6 + 0.5); // 40/6 = 6.666 repeating, rounds up to 7

Nope - In C (and most languages), integer division will result in immediate truncation, not just truncation at the end. since the dividend and the divisor are both integers, it will calculate 40/9 to be 4, then add 0.5, then truncate as you put it into the integer, giving you 4 for the answer. 40/6 will calculate to 6, add 0.5 and truncate again and you'll get 6.

Instead, what you can try (for your example) is the following:

int x = (int)(40.0/9.0 + 0.5); // 40/9 = 4.444 repeating and rounds down to 4

int y = (int)(40.0/6.0 + 0.5); // 40/6 = 6.666 repeating, rounds up to 7

by adding the ".0" to the divisor and the dividend, you turn the division into a floating point operation, instead of an integer operation. That means that it won't truncate the result of the division, only the final result of the equation as you stick it into an integer. To accomplish this using variables instead of straight numbers, by far the easiest way is to typecast the variables:

int x = (int)(((float)dividend)/((float)divisor) + 0.5);

That tells the compiler that, for this one instance, you want it to treat the variables as floats instead of integers, meaning that it won't truncate any results in mid-computation.