Divide by 3 in ISR

This is a discussion on Divide by 3 in ISR within the C Programming forums, part of the General Programming Boards category; But quzah you missed: Originally Posted by Roaring_Tiger Yes we can use + and - but not conditional as they ...

  1. #16
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    But quzah you missed:
    Quote 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. #17
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    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

  3. #18
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    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.
    If you understand what you're doing, you're not learning anything.

  4. #19
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    Quote 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 '-').
    If you understand what you're doing, you're not learning anything.

  5. #20
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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. #21
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote 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. #22
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote 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.
    Hope is the first step on the road to disappointment.

  8. #23
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Unless of course you are working on someone's pay check then a lose of 2 is too much

  9. #24
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote 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.

    [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:
    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.
    Last edited by quzah; 08-19-2004 at 03:31 PM.
    Hope is the first step on the road to disappointment.

  10. #25
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    i ruled out a loop because it involves (supposedly-not allowed) conditionals?
    hello, internet!

  11. #26
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote 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. #27
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    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.

  13. #28
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote 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. #29
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    Quote 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.
    If you understand what you're doing, you're not learning anything.

  15. #30
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    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.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Divide 64bit number
    By freeindy in forum C Programming
    Replies: 4
    Last Post: 10-01-2007, 03:56 AM
  2. Divide and Conquer: array in the reverse order
    By Steamer in forum C Programming
    Replies: 11
    Last Post: 03-08-2004, 06:31 PM
  3. severe beating of divide by zero
    By muttski in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 11-22-2002, 04:54 PM
  4. divide and conquer
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 06-13-2002, 09:52 AM
  5. Calling ISR w/o interrupt
    By VirtualAce in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 11-02-2001, 04:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21