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 ??

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.

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 [:-)]

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.

Quote:

---

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.

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.

Quote:

---

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.

Sorry, didn't see they were asking for an efficient solution ;)

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;
}

---

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.

Quote:

---

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.

Quote:

---

Originally Posted by laserlight

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?

Quote:

---

How else would you convert it?

---

You do not convert it at all. The algorithm I outlined can work with chars.

Quote:

---

Originally Posted by iMalc

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.

Quote:

---

Originally Posted by laserlight

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

Quote:

---

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 %

---

Ah, that makes sense.

For those of you that follow the contest forum I submit this:

Code:

---

bool divby3(int num)
{
    int dividend = (double)num * .3333 + .1;
    int remainder = num-(dividend * 3);
    return remainder == 0;
}

---

For those that don't follow the contest forum, this is not a serious answer(though it works).

I think that operator * is like / and %, so if this is a homework question as I suspect, Brij cannot use it anyway.

If you have an efficient operation for counting the number of nonzero bits in an unsigned int (like some processors do) you can use

Code:

---

int divisible3(unsigned int x) {

  do {
    x = abs(countbits(x & 0xAAAAAAAA) - countbits(x & 0x55555555));
  } while (x > 3);

  return x == 0;
}

---

Quote:

---

Originally Posted by Darryl

For those of you that follow the contest forum I submit this:

Code:

---

bool divby3(int num)
{
    int dividend = (double)num * .3333 + .1;
    int remainder = num-(dividend * 3);
    return remainder == 0;
}

---

For those that don't follow the contest forum, this is not a serious answer(though it works).

---

Sorry mate,

Code:

---

3003 * .3333 = 1000.8999
+ .1 = 1000.9999
* 3 = 3002.9997

---

Quote:

---

Originally Posted by laserlight

I think that operator * is like / and %, so if this is a homework question as I suspect, Brij cannot use it anyway.

---

If this is a homework assignment, it probably is assigned because there's so many different ways to solve it. I don't see how solving it with multiplication is really less valid than bit counting.

[QUOTE=QuestionC;654440]Sorry mate,

Code:

---

3003 * .3333 = 1000.8999
+ .1 = 1000.9999
* 3 = 3002.9997

---

/QUOTE]

I can always add more 3s to extend its useful range.
Plus, it was only meant as a joke based on the contest thread I linked to.

Speaking of counting the number of bits in an unsigned int, I found this interesting bit of speculation. http://www.moyogo.com/blog/2005/09/secret-opcodes.html