Thread: divisibility by 3

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.

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.

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.

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.

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.

How else would you convert it?

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

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