divisibility by 3

This is a discussion on divisibility by 3 within the C Programming forums, part of the General Programming Boards category; can we check the divisibility of a given number by 3 withoutusing operators like '/' or '%'. I want the ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    19

    divisibility by 3

    can we check the divisibility of a given number by 3 withoutusing operators like '/' or '%'.
    I want the efficient solution to this problem ..

    can someone help ??

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,165
    Yes (recursively add the digits in base 10 and check for divisibility when only one digit is left), but it will probably less efficient than using modulo at machine level.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    19
    yes right .. but still i have to check the divisibility when one digit is left .. as you said ...

    so the question is still same how to divide the number or check divisibility of a number by 3 [:-)]

  4. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    You can't figure that one out by yourself? Look at all of the single digit numbers that are divisible by 3, starting with 0. There you go. Hardcode those digits in as what are required.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,165
    yes right .. but still i have to check the divisibility when one digit is left .. as you said ...
    Indeed. I wonder how many non-negative integers less than ten are divisible by three...

    Though if you actually have to implement this, then most likely you would read the number as a string. If so, it makes more sense to add the first digit to the second, determine its remainder after division by three (perhaps by means of a switch with 19 cases), and add that remainder to the third digit, determine the new remainder, and so on until the entire numeric string is processed.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Well, do "old skool" division
    Using iterated subtraction (ie num -= divisor).
    if the remainder is 0, then the num is divisible by 3, otherwise it's not.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,165
    Well, do "old skool" division
    Using iterated subtraction (ie num -= divisor).
    if the remainder is 0, then the num is divisible by 3, otherwise it's not.
    That would be terribly inefficient though.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Sorry, didn't see they were asking for an efficient solution

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    I suspect that converting the number to a string involves extracting decimal digits by internally using / and % by 10 repeatedly (although hidden) so would probably be less efficient than a single explicit % by 3. On the other hand, the rule for testing a decimal number for divisibility by 3 relies on the fact that 10 is congruent to 1 mod 3, so for example the remainder of 6738430 mod 3 is the same as that of 673843 mod 3, and the rule follows by induction. In the same way, one can get a similar rule for testing a binary number for divisibility by 3 by noting that 4 is congruent to 1 mod 3, so 10001110010100 (base 2) has the same remainder mod 3 as 100011100101 (base 2). You just lop off the last 2 zeroes. This means that the remainder of 10110101001010 mod 3 is the same as that of 10 + 11 + 01 + 01 + 00 + 10 + 10. If the number is stored in an unsigned integral type, then one can repeatedly use "& 3" to read off the two rightmost binary digits, add to a running total, then ">>= 2" to right shift by 2. I doubt whether this would be more efficient unless it was implemented in hardware, though.

    Edit: Of course, there are tricks to speed it up - for example, the running total can be reduced immediately whenever it gets >= 100 (base 2), and each instance of 00 or 11 can be ignored, since they're both divisible by 3.

    Edit: Since 16 is congruent to 1 mod 3, the rule for testing for divisibility by 3 by testing the sum of the digits works for base 16 (hexadecimal) as well as base 10.

    Edit: Here you go:
    Code:
    unsigned int remainderby3(unsigned int i) { /* good for 32-bit unsigned int */
      i = (i & 65535) + (i >> 16);
      i = (i & 65535) + (i >> 16);
      i = (i & 255) + (i >> 8);
      i = (i & 255) + (i >> 8);
      i = (i & 15) + (i >> 4);
      i = (i & 15) + (i >> 4);
      i = (i & 3) + (i >> 2);
      i = (i & 3) + (i >> 2);
      return (i != 3)? i : 0;
    }
    Last edited by robatino; 06-29-2007 at 09:22 AM.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    I was quite skeptical of the function robatino posted, however I wrote a test program and I can tell you that it works for every number from 0 to 0x7FFFFFFF!

    I didn't do any speed tests though. It may be faster in some circumstances, but it increases the code size, so there will probably be cases where it is slower due to the code for some inner loop no longer fitting in the instruction cache any more.
    When you know already that the number is small, then some of the steps can obviously be removed, so I can definitely see cases where this will certainly be faster.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,165
    I suspect that converting the number to a string involves extracting decimal digits by internally using / and % by 10 repeatedly (although hidden) so would probably be less efficient than a single explicit % by 3.
    I am not well studied in I/O, but I had the impression that just reading it as a string would not require such a conversion.

    I am not so sure how concerned we should really be for fine tuning the performance beyond the general algorithm: this sounded like a homework question to me from the start.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Jul 2005
    Posts
    14
    Quote Originally Posted by laserlight View Post
    I am not well studied in I/O, but I had the impression that just reading it as a string would not require such a conversion.
    How else would you convert it?

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,165
    How else would you convert it?
    You do not convert it at all. The algorithm I outlined can work with chars.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by iMalc View Post
    I didn't do any speed tests though. It may be faster in some circumstances, but it increases the code size, so there will probably be cases where it is slower due to the code for some inner loop no longer fitting in the instruction cache any more.
    When you know already that the number is small, then some of the steps can obviously be removed, so I can definitely see cases where this will certainly be faster.
    This was just a quick-and-dirty implementation. The idea is that 2^n is congruent to 1 mod 3 when n is any even positive integer, so the add-the-digits test for divisibility by 3 works in base 4, 16, 64, 256, etc. So I do it first in base 65536 == 2^16, where a 32-bit unsigned int can be represented with 2 digits. I add the two digits, then repeat to take care of the carry and ensure that the result is just one digit. Then repeat with base 256 == 2^8 to reduce to a single base 256 digit, etc. Once down to a single base 4 digit, it's either 0, 1, 2, or 3, and I just replace 3 by 0. There's probably a way to avoid having two copies of each line. I'm guessing that this is slower than a simple %3 but haven't done speed tests. It could easily be faster if done in hardware.

  15. #15
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Quote Originally Posted by laserlight View Post
    You do not convert it at all. The algorithm I outlined can work with chars.
    I don't think he's starting with chars which is where you two lost each other, I think he is starting from an integer and not necessarily an input from the command line. So what he need is a general purpose function that takes an int and returns if it's divisible by 3 and therefore was stating it would be difficult to parse the individual digits without using / or %, but you could always convert the int to a string first with itoa or stringstreams
    Last edited by Darryl; 06-29-2007 at 03:50 PM.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

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