But quzah you missed:
Which in turn means who ever is assigning this project/assignment is a freakin moronOriginally Posted by Roaring_Tiger
But quzah you missed:
Which in turn means who ever is assigning this project/assignment is a freakin moronOriginally Posted by Roaring_Tiger
Well, maybe the idea was to make you think.
Think about this:
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
Can you please explain this to me? I'm not sure how you came up with that specific value to represent 1/3.Well, the binary representation of 1/3 is
0.0101010101
If you understand what you're doing, you're not learning anything.
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.Originally Posted by quzah
If indeed this is an assignment the rules should be stated clearly (i.e. I can only use '<<', '>>', '+', and '-').
If you understand what you're doing, you're not learning anything.
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
Originally Posted by itsme86
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:
This prints the first twenty bits, one at a time, as they are obtained from the floating point representation.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; }
Regards,
Dave
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.Originally Posted by itsme86
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.
Hope is the first step on the road to disappointment.
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.Originally Posted by Thantos
[edit]
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:
[/edit2]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; }
Quzah.
Last edited by quzah; 08-19-2004 at 03:31 PM.
Hope is the first step on the road to disappointment.
i ruled out a loop because it involves (supposedly-not allowed) conditionals?
hello, internet!
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.Originally Posted by Thantos
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
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.
If you understand what you're doing, you're not learning anything.
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"?Originally Posted by itsme86
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.Originally Posted by Dave Evans
If you understand what you're doing, you're not learning anything.
Roaring_Tiger, what type of ISR is it and what generates it?
Or is this homework?
gg
Last edited by Codeplug; 08-19-2004 at 05:02 PM.