# Thread: Divide by 3 in ISR

1. But quzah you missed:
Originally Posted by Roaring_Tiger
Yes we can use + and - but not conditional as they add extra bytes and clock cycles.

Thanks
Which in turn means who ever is assigning this project/assignment is a freakin moron

2. Well, maybe the idea was to make you think.

Well, the binary representation of 1/3 is

0.0101010101...

This is the same as 1/4 + 1/16 + 1/64 ....

So x/3 = x/4 + x/16 + x/64 + ....

Where x/4 = x >> 2
x/16 = x >> 4
x/64 = x >> 6

...

Is this enough to get you going? (You have to figure out how many terms you need for a specified accuracy, givena range of possible input numbers.)

Regards,

Dave

3. Well, the binary representation of 1/3 is

0.0101010101
Can you please explain this to me? I'm not sure how you came up with that specific value to represent 1/3.

4. Originally Posted by quzah
You all apparently missed this statement:

That seems to clearly state that this is an assignment. Be it by self-study in a book, or a class, or whatever, it still sounds like an assignment, since they've stated that they're "only allowed to use". Thus, the above doesn't apply.

Quzah.
No, I didn't miss that. He even doesn't hold true to that statement when he accepts + and - as useful operators. In fact, he leads to using bit shifting operations instead of '/' because of wasted clock cycles. Optomization through obfuscation is a poorer choice than optomization through wise algorithm choices.

If indeed this is an assignment the rules should be stated clearly (i.e. I can only use '<<', '>>', '+', and '-').

5. Given an 4 bit number:
1010
From left to right the positions values are:
2^3, 2^2, 2^1, 2^0

Now extend the pattern to the decimal side
2^-1 = 1/2
2^-2 = 1/4
2^-3 = 1/8
2^-4 = 1/16

6. Originally Posted by itsme86
Can you please explain this to me? I'm not sure how you came up with that specific value to represent 1/3.

You could derive it any number of ways; you could prove it by mathematical induction. You could do lots of things. But since this is a programming forum, you could do it with a program.

Here's the code:

Code:
```#include <stdio.h>
int main()
{
int i, nextbit;
double x;

x = 1.0/3.0;

for (i = 0; i < 20; i++) {
x = x * 2.0;
if (x >= 1.0) {
nextbit = 1;
x -= 1.0;
}
else {
nextbit = 0;
}
printf("%2d: %d\n", i, nextbit);

}
return 0;
}```
This prints the first twenty bits, one at a time, as they are obtained from the floating point representation.

Regards,

Dave

7. Originally Posted by itsme86
No, I didn't miss that. He even doesn't hold true to that statement when he accepts + and - as useful operators. In fact, he leads to using bit shifting operations instead of '/' because of wasted clock cycles. Optomization through obfuscation is a poorer choice than optomization through wise algorithm choices.

If indeed this is an assignment the rules should be stated clearly (i.e. I can only use '<<', '>>', '+', and '-').
Well, I assume he has an assignment which requires the use of bitshifting, and allows for addition and subtraction. Though I'm not sure what they're trying to say about wasted clock cycles and "added bytes". I assumed it was a "Using bitshifting, create a way to divide by three. Addition and subtraction are allowed". That sort of thing.

Dave has shed light on the subject enough to easily complete the task. You can do it with a small loop, or just a single macro. Either way will get you fairly close to your goal. Dividing 10000 that way shows a loss of 2 on the true number. (3331 instead of 3333.) But it's nicely close.

Quzah.

8. Unless of course you are working on someone's pay check then a lose of 2 is too much

9. Originally Posted by Thantos
Unless of course you are working on someone's pay check then a lose of 2 is too much
Well if I was working with someone's paycheck, I wouldn't be using bitshifting.

Use Thantos' loop solution, and since you're required to use bitshifting, shift the results to the left once, then back to the right.
[/edit]

[edit2]
A fun combination of the two:
Code:
```unsigned short int div3( unsigned short int z )
{
unsigned short int x = (z>>2)+(z>>4)+(z>>6)+(z>>8)+(z>>10)+(z>>12)+(z>>14);
while( (z - (x + x + x)) >= 3 ) x++;

return x;
}```
[/edit2]

Quzah.

10. i ruled out a loop because it involves (supposedly-not allowed) conditionals?

11. Originally Posted by Thantos
But quzah you missed:

Which in turn means who ever is assigning this project/assignment is a freakin moron
Well, at the risk of being called a moron (I have been called worse, even though I am not an instructor), I would like to point out that sometimes there is a reason to know how to do such things.

For example, instead of our big powerful machines where the operation "divide by 3" is fast and cheap, lots of people are creating programs (in C) for embedded systems built around processors that don't have multiply and divide instructions. The run-time package may include software multiply and divide routines to support all possible C expressions, but they are not necessarily fast or cheap (in terms of memory usage and elapsed time considerations).

Since the Original Post mentioned an ISR (Interrupt Service Routine), there is an implied need for "fast". That is, since interrupts are typically turned off during execution of the ISR, other events may be missed if the ISR takes too long. A sequence of shift-add may very well be faster than a software division routine (or maybe not --- you tend to try lots of different approaches when you are programming down where the rubber meets the road).

Also, the use of conditional statements makes it much harder to know exactly how long a routine will take. In real-time systems it may be important that a routine takes the same amount of time regardless of the value of the datum being operated on.

So ... A fixed number of shift-add instructions may be a good approach. In any case, it could be useful to know that there are possibilities outside the obvious (j = i / 3).

Regards,

Dave

12. Why not just use assembly then? It's hard to control a C compiler, and most you can't. If the specific CPU doesn't support DIV then the C compiler should automagically get the division done for you however it can.

If one needs to make sure the source code matches the intended machine code then one needs to use assembly.

13. Originally Posted by itsme86
Why not just use assembly then? It's hard to control a C compiler, and most you can't. If the specific CPU doesn't support DIV then the C compiler should automagically get the division done for you however it can.

If one needs to make sure the source code matches the intended machine code then one needs to use assembly.
I agree. I also believe that knowing the implications of various alternatives is valuable. If I make a statement that, "ISRs are usually written in assembly language," how could I prove it? How could I disprove it? Does such a pronouncement come under the general category of "silly statements"?

Today's optimizing C compilers (even for small processors in embedded systems) are surprisingly efficient (sometimes, but also sometimes not).

Which is the best approach? Here I will make a flat statement:

It depends.

Thanks for your courtesy and considerate responses.

Dave

14. Originally Posted by Dave Evans
I agree. I also believe that knowing the implications of various alternatives is valuable. If I make a statement that, "ISRs are usually written in assembly language," how could I prove it? How could I disprove it? Does such a pronouncement come under the general category of "silly statements"?

Today's optimizing C compilers (even for small processors in embedded systems) are surprisingly efficient (sometimes, but also sometimes not).

Which is the best approach? Here I will make a flat statement:

It depends.

Thanks for your courtesy and considerate responses.

Dave
I wasn't saying that assembly is always more efficient, I was only saying that assembly almost always gives you more control over the finished machine language. Like you said, C optomizes and who's to say that the compiler won't turn all your hard work of into a simple DIV statement after all? Or vice versa, it could turn your 1/3 statement into a complex bitshift.

15. Roaring_Tiger, what type of ISR is it and what generates it?

Or is this homework?

gg