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; Hello All, I want to divide a number by integer value 3, without using / or *. I am only ...

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    175

    Divide by 3 in ISR

    Hello All,

    I want to divide a number by integer value 3, without using / or *. I am only allowed to use << and >>. Program should out put nearing value. For example.

    8/3 = 2.66 and answer with shift can be 3.
    7.3 = 2.33 and answer can be 2.


    I tried doing this but there is more deviation.
    Code:
    #define DIVIDE_BY_3(uS) ((uS<<4)>>6)
    Please let me know..

  2. #2
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    can you use + and -? conditionals?

    how did you come up with that piece of code, and why do you expect it to work? unless i dont have enough coffee in me, that divides by four.
    Last edited by moi; 08-19-2004 at 01:52 PM.
    hello, internet!

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    Yes we can use + and - but not conditional as they add extra bytes and clock cycles.

    Thanks

  4. #4
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Using bit shifting has a bigger chance of increasing code size and execution time then using conditionals

    A few other things to consider: Are you diving ints, doubles, unsigned, signed, postive, negative?
    Last edited by Thantos; 08-19-2004 at 02:00 PM.

  5. #5
    Super Moderator
    Join Date
    Sep 2001
    Posts
    4,913
    unless i dont have enough coffee in me, that divides by four.
    Well why don't you help the guy out and go chug some coffee!

  6. #6
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    Quote Originally Posted by sean_mackrory
    Well why don't you help the guy out and go chug some coffee!
    aww come on, i leave work in 25 minutes! i dont need to be hyper now

    but anyway, that macro, putting aside its ability to drop bits off the top, is the same as >> 2, which is just a straight division by 4
    hello, internet!

  7. #7
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Just by looking at some bit patterns I am pretty confident that it would be neigh impossible to divide by a non power of 2 using bit shifting without some serious lose (or possible) lose of data

  8. #8
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    Dividing sixteen bit unsigned value.

  9. #9
    Super Moderator
    Join Date
    Sep 2001
    Posts
    4,913
    I'd just like to echo Thantos. Look at how inaccurate your first examples are - and those numbers give a pretty best-case scenario.

  10. #10
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    using only + and >>, but really reaaly stupid imo

    Code:
    unsigned short div3 (unsigned short z)
    {
      unsigned long x = z; // make sure no overflow
      x = x + x + x +
          x + x + x +
          x + x + x +
          x + x + x +
          x + x + x +
          x + x + x +
          x + x + x; // multiply by 21
      x = x >> 6; // divide by 64
      return (unsigned short) x; // should not overflow
    }
    21/64 is roughly 1/3, so it kinda works, but it truncuates, not rounds

    perhaps there is a better solution
    hello, internet!

  11. #11
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    I think there is no solution until I add few more bytes.

  12. #12
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    Quote Originally Posted by Roaring_Tiger
    I think there is no solution until I add few more bytes.
    ?

    by the way, using the processor's integer divison is going to be way faster than any sort of hack
    hello, internet!

  13. #13
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,166
    Just use '/' for the love of everything holy. If you're looking to speed up your program then I'd start looking at algorithm changes/rewrites instead of trying to figure out how to divide by 3 faster.
    If you understand what you're doing, you're not learning anything.

  14. #14
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by moi
    using only + and >>, but really reaaly stupid imo

    Code:
    unsigned short div3 (unsigned short z)
    {
      unsigned long x = z; // make sure no overflow
      x = x + x + x +
          x + x + x +
          x + x + x +
          x + x + x +
          x + x + x +
          x + x + x +
          x + x + x; // multiply by 21
      x = x >> 6; // divide by 64
      return (unsigned short) x; // should not overflow
    }
    21/64 is roughly 1/3, so it kinda works, but it truncuates, not rounds

    perhaps there is a better solution
    Lets find out: 65535 (highest 16 bit unsigned) * 21 = 1376235 / 64 = 21503.671875
    65535 / 3 = 21845
    Difference: 341.328125
    Just a little bit off.

    The best bet is to use the subtraction method in a loop. Unless you are working with an ancient chip it can evaluate simple conditions quicker then it can do bit shifting or adding a number 21 times

    example:
    Code:
    int div_3(int remainder)
    {
      int quotient=0;
      for (;remainder>=3;remainder-=3,quotient++);
      if ( remainder >= 2)
        quotient++;
    
      return quotient;
    }

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by itsme86
    Just use '/' for the love of everything holy. If you're looking to speed up your program then I'd start looking at algorithm changes/rewrites instead of trying to figure out how to divide by 3 faster.
    You all apparently missed this statement:

    I am only allowed to use << and >>.
    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.
    Hope is the first step on the road to disappointment.

Page 1 of 3 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