30
\$\begingroup\$

I tried to develop a new way to check if a number is divisible by 9. I have written my code and it is working fine. I'm not allowed to use *,/ and %.

int isDivby9(int x)
{
    int status = 0; 
    int divby8 = 0;

        int orgx = x;
        if(x>=9)
        {
            divby8 = x >> 3;
            int olddivby8 = divby8;
            while(divby8 >= 9)
            {
                divby8 = divby8 - 9;
            }
            if(divby8 == (orgx - (olddivby8 << 3)))
            {
                status = 1;
            }
            else{
                status = 0;
            }
            x = divby8;
        }

    return status;
}

Can someone please check if this is a good way to check if a number is divisibility by 9? Is it too complex? Is there any better way to perform the same? I also referred to the logic given in geeksforgeeks.

\$\endgroup\$
  • 5
    \$\begingroup\$ Is it possible to count and sum digits easily in C? I don't know C, but I do know that a number is divisible by 9 if the sum of its digits is divisible by 9. That little factoid is likely what this problem is hoping you know, given the constraints. The resulting function would be simple then, using recursion; in psuedocode: if (numDigits ==1) then return 9==x; else, return isDivBy9(sumOfDigits(x)); \$\endgroup\$ – Willem Renzema Mar 27 '15 at 16:35
  • 4
    \$\begingroup\$ @WillemRenzema A number is divisible by 9 iff the sum of its digits in base 10 is divisible by 9, however, the variables are stored in base 2. Converting digits from two bases generally requires division. \$\endgroup\$ – twohundredping Mar 27 '15 at 16:55
  • 2
    \$\begingroup\$ I see no sign that you've designed or tested this program to work with negative numbers. Your question is about numbers, by which I presume you mean integers, not positive integers. \$\endgroup\$ – Eric Lippert Mar 27 '15 at 16:56
  • \$\begingroup\$ That is the part that surprises me both in the question and in the answers @EricLippert. Especially given how easy it is to extend ANY algorithm that can determine if positive numbers are divisible by 9. \$\endgroup\$ – twohundredping Mar 27 '15 at 17:00
  • 4
    \$\begingroup\$ Related: checking if a number is divisible by 3 \$\endgroup\$ – Simon Forsberg Mar 28 '15 at 13:43
40
\$\begingroup\$

I see some things that you might want to use to improve your code.

Use an early bailout

If the passed number x is less than 9, the routine can immediately return 0.

Eliminate multiples of 2

Since 9 and 2 have no common factors, you can speed up the operation (on average) by shifting the incoming x to the right until the least significant bit is non-zero.

Eliminate unused variables

With a minor restructuring of the code, you can eliminate most of the variables and make the code shorter, faster and easier to read.

Consider implementing a test program

You have apparently already done some testing, but posting the test with the code to be reviewed may help others review the code properly.

Putting it all together

Here's what I came up with using all of these suggestions:

#include <stdio.h>
#include <assert.h>

int isDivby9(int x)
{
    while (0 == (x & 1)) {
        x >>= 1;
    }
    if(x<9)
        return 0;

    int divby8 = x >> 3;
    while(divby8 >= 9) {
        divby8 -= 9;
    }
    return divby8 == (x & 7);
}

int main()
{
    for (int i=1; i < 1000000; ++i) 
        assert(isDivby9(i) == (i%9 == 0));
}

Results

On my machine (64-bit Linux box), the original code runs in 2.3 seconds, and the version above completes in 1.5 seconds; a considerable improvement in performance with identical mathematical results. By comparison, the straightforward approach in @Edenia's answer takes 18.8 seconds on the same machine.

All were compiled with gcc 4.9.2 with -O2 optimizations.

Updated algorithm

I couldn't stop thinking about this question because I knew there was a better algorithm, but just couldn't think of it. I finally came across this superb answer to a similar question on StackOverflow. With that excellent answer, I translated a finite state machine implemention into C and came up with this:

#include <limits.h>

struct state {
    int nextstate[2];
};
int isDivby9 (int num)
{
    static const int HIGH_BIT = INT_MAX - (INT_MAX >> 1);
    static const struct state states[9] = { 
        {{0, 1}}, {{2, 3}}, {{4, 5}}, 
        {{6, 7}}, {{8, 0}}, {{1, 2}}, 
        {{3, 4}}, {{5, 6}}, {{7, 8}}
    };
    if (num < 0) 
        num = -num;        
    int s = 0;
    for ( ; num ; num <<= 1) {
        s = states[s].nextstate[(num & HIGH_BIT) ? 1 : 0];
    }
    return s==0;
}

Each bit, starting from the MSB, drives the state machine to the next state. The state is held in variable s and the branches for the 0 and 1 bits are the the two nextstate entries. It works well (including for negative numbers and zero) and is very fast. In fact, on my machine, this routine takes 0.045 seconds.

Updated results

In more concise timing tests on my machine, and adjusting all routines to also work correctly on negative numbers, here's what I found on this machine:

  861092 modulus operator
 1152840 JS1
 1581770 gnasher729
 2479987 Simon
 8961866 Edward DFA function

So the % operator is fastest, followed by @JS1's routine, followed by @gnasher729's, followed by @Simon's followed by the DFA routine (by a wide margin!)

Naturally, this might differ on different machines with different architectures, so as always, timing routines on your own actual hardware is recommended.

I learned some things that might well be useful for the next time I work on synthesizing my own logic or on an embedded microprocessor without a multiply instruction.

\$\endgroup\$
  • \$\begingroup\$ Why have you tested only positive numbers? \$\endgroup\$ – Eric Lippert Mar 27 '15 at 16:54
  • 6
    \$\begingroup\$ @EricLippert: simply because that's the domain over which the original function worked, so if it "worked fine" before, I infer that it's the domain of interest. \$\endgroup\$ – Edward Mar 27 '15 at 17:36
  • 6
    \$\begingroup\$ Though I see your point, this is a code review site; I assume that the person writing the code hasn't actually read or understood their assignment and they are copying random code off the internet in the hopes that it works. :-) \$\endgroup\$ – Eric Lippert Mar 27 '15 at 18:25
  • 6
    \$\begingroup\$ @EricLippert: I suppose I'm a little more optimistic about human behavior, so I hope your comments (and the test code I provided) might prompt a little more investigation into such questions as "Is 0 divisible by 9?" and "Is -81 divisible by 9?" \$\endgroup\$ – Edward Mar 27 '15 at 18:34
  • \$\begingroup\$ Unless numbers less than 9 are very likely, it doesn't seem like testing for that every time is really an optimization. \$\endgroup\$ – mattdm Mar 27 '15 at 20:33
19
\$\begingroup\$

After reading gnasher729 and Simon's answers, I was inspired to find the fastest possible way to do this.

Analysis of original function

The main problem with the original function is that it only uses the divide by 8 trick once. After that, it falls into this loop:

    while(divby8 >= 9)
    {
        divby8 = divby8 - 9;
    }

Given a large number, this loop could iterate for millions of iterations.

Faster solutions

Gnasher729 and Simon demonstrated solutions that used a small loop to reduce the original number by 6 and 3 bits respectively. Building upon their work, I came up with the following optimized solution:

int div9(int x)
{
    x = (x >> 15) - (x & 0x7fff);
    x = (x >> 9) - (x & 0x1ff);
    x = (x >> 6) + (x & 0x3f);
    x = (x >> 3) - (x & 0x7);
    return x == 0;
}

This function is meant to be used for 32-bit positive integers. For 64-bit positive integers, you can add this line at the beginning:

    x = (x >> 30) + (x & 0x3fffffff);

If negative integers are allowed, you can add this line at the beginning:

    if (x < 0) x = -x;

Just for fun

The original question did not allow multiply or modulo. But just for fun, let's see what would be the fastest method. For example, how fast is simply using modulo?

int div9(int x)
{
    return (x % 9) == 0;
}

Here is the fastest solution I could come up with, using multiply. This solution is based on this stackoverflow answer. The shift by 6 is to get the original number small enough to work with the multiply trick.

int div9(int x)
{
    x = (x >> 6) + (x & 0x3f);
    return (x * 0xe38e38e4u) < 0x1c71c71c;
}

Timing function

Here is the main function of my timing program. It tests all values from 0 to 0x7ffffff4. I chose to do it this way to avoid using i%9 in the test loop, since i%9 can take a significant amount of time compared to the actual functions being tested.

int main(void)
{
    int i;
    for (i=0;i<0x7ffffff5;i+=9) {
        if (div9(i+0) == 0) break;
        if (div9(i+1) == 1) break;
        if (div9(i+2) == 1) break;
        if (div9(i+3) == 1) break;
        if (div9(i+4) == 1) break;
        if (div9(i+5) == 1) break;
        if (div9(i+6) == 1) break;
        if (div9(i+7) == 1) break;
        if (div9(i+8) == 1) break;
    }
    if (i != 0x7ffffff5) {
        printf("Failed on 0x%08x\n", i);
        return 1;
    }
    return 0;
}

Timing results

Author              Time (seconds)
------              --------------
JS1 (multiply)           2.23
JS1 (modulo)             3.35
JS1 (shifts)             5.70
Gnasher729              16.90
Simon (opt)             30.40
Simon                   53.40

Simon (opt) is his function with only the shift by 3 loop. As you can see, it is faster without having the loop that checks for powers of 2.

\$\endgroup\$
  • \$\begingroup\$ Excellent work! I have added timing results to my own answer which verifies your relative results and also compares a few others. \$\endgroup\$ – Edward Mar 28 '15 at 18:23
16
\$\begingroup\$

I did not check if your code works, I assume it does since you say so.

Your code lacks consistency

if(divby8 == (orgx - (olddivby8 << 3)))
{
   //...
}

vs

else{
   //...
}

and

if(x>=9) vs while(divby8 >= 9)

I suggest using an automated formatting tool.

Avoid nesting

You can avoid nesting by inverting the outer if statement and returning 0. Your nesting isn't that deep so it isn't a major problem.

Unneeded code

I don't see any point of having these lines.

else{
    status = 0;
}
x = divby8;

Comments

You should add comments explaining why. Ex: On if(x>=9) you can add

// It cannot be divisible by 9 if it is less than 9 
\$\endgroup\$
  • \$\begingroup\$ Is there any way to avoid while loop in code? \$\endgroup\$ – kapil.thakar Mar 27 '15 at 14:34
  • \$\begingroup\$ You are right. I should remove the unwanted code as you have mentioned here. \$\endgroup\$ – kapil.thakar Mar 27 '15 at 14:35
  • \$\begingroup\$ @kapil.thakar, not sure how to do that. OK you should, but don't edit the question. \$\endgroup\$ – 422_unprocessable_entity Mar 27 '15 at 14:36
  • \$\begingroup\$ Sure and Thanks for your valuable suggestion. I want to vote up your answer but I am not able to do it as I don't have 15 points. \$\endgroup\$ – kapil.thakar Mar 27 '15 at 14:40
  • \$\begingroup\$ @kapil.thakar OK, Thanks, It's the thought that counts. Have fun coding :) You can also participate in the chat room when you have 20 rep. \$\endgroup\$ – 422_unprocessable_entity Mar 27 '15 at 14:41
11
\$\begingroup\$

If the input is large, the code will run for a very, very long time. If you changed the type from int to int64_t, it could run forever.

You could use the fact that 64 % 9 == 1, therefore (64x + y) % 9 == (x + y) % 9.

while (x >= 64) x = (x >> 6) + (x & 0x3f);
while (x >= 9) x -= 9;

Even for the largest x you will have less than 20 loop iterations in total.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is by far the best solution so far for the stated problem. I built on your answer to create my own. \$\endgroup\$ – JS1 Mar 28 '15 at 10:57
  • 1
    \$\begingroup\$ Good answer! Also, since 64 % 9 == 1, we know that 2^(6*n) == 1 for n=0, 1, ... so one could speed things even further by using the same trick for 4096, 262144, 16777216, etc. \$\endgroup\$ – Edward Mar 28 '15 at 18:35
  • \$\begingroup\$ A refinement may be to avoid looping but instead if x>=262144 then run some hard-coded iterations; then if x>=4096, and then if x>=64. \$\endgroup\$ – supercat Mar 28 '15 at 22:33
  • 1
    \$\begingroup\$ After the first loop, x is guaranteed to be less than 64 = 8², so (using the fact that 8 ≡ -1 modulo 9) you could replace the last while loop with a simple return (x >> 3) == (x & 7). \$\endgroup\$ – Ilmari Karonen Mar 29 '15 at 12:15
  • \$\begingroup\$ @IlmariKaronen: Good point. If you did that and added x = (x >> 18) + (x & 0x3ffff) at the top, I believe this would run as fast as @JS1s solution for 32 bit numbers. \$\endgroup\$ – Michael Shaw Mar 29 '15 at 14:21
8
\$\begingroup\$
int divides9 (int number)
{
    int num;

    for(num = number; num > 0; num -= 9);

    return (num == 0);
}

Facing your restrictions, I could come up with this that appears to be different than your current approach. And smaller indeed.


Not only unnecessary, but also very confusing: The names you use are very long. Camel case is not very readable with long names.

  • PreferCamelCaseOverSnakeCaseForLongNames

  • prefer_snake_case_over_camel_case_for_long_names

Which one looks easier for reading? Right.

So you can replace isDivby9 with is_divisible_by9 or if you want to stick with abbreviated names - isdivsbl and specify the number that has to be check as a function argument.

What is orgx supposed to do? At the time I read it, I could not get any idea.

olddivby8 is even worse. That stands for all the names. Stick with a style and try to come up with a short name that makes perfect sense and is pretty much self-explaining.


Use spaces. Especially between declaration and an if statement.


Using bit operations for such arithmetic is a rare case, and not always that pretty. Especially if they are not needed. Exactly because it is a rare case you should not use them unless they are your only choice. They are harder for debugging.

\$\endgroup\$
  • 10
    \$\begingroup\$ Not the most efficient solution either… \$\endgroup\$ – 5gon12eder Mar 27 '15 at 14:40
  • 1
    \$\begingroup\$ By using addition instead of subtraction, you would see performance improvements. Just start num at 0, then increment by 9 each iteration. Your condition would then be num <= number \$\endgroup\$ – Evan Bechtol Mar 27 '15 at 15:02
  • 1
    \$\begingroup\$ Basically % is slow. And may cause some indecent problems in old C. nevertheless.. it is truly handy. \$\endgroup\$ – Edenia Mar 27 '15 at 15:08
  • 3
    \$\begingroup\$ "Which one looks easier for reading?" - I think they're equally easy to read. Also, isdivsbl is a terrible suggestion for a name. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Mar 27 '15 at 15:51
  • 2
    \$\begingroup\$ ThisIsPascalCase, thisIsCamelCase - see the difference? \$\endgroup\$ – Simon Forsberg Mar 28 '15 at 14:27
4
\$\begingroup\$

You tagged this question "beginner", but that algothithm on geeksforgeeks is fairly advanced. Are you sure you should be using it over the simple repeated addition or subtraction? In fact, you're still doing repeated subtraction by 9 when you do this:

while(divby8 >= 9)
    {
        divby8 = divby8 - 9;
    }

Thus, you're not getting the full benefit of the bitwise algorithm.

I altered @Edward's code (all good suggestions there) to more faithfully implement the algorithm you linked. The performance gain is significant -- timed on my machine at 0.018s for this vs 3.497s for @Edward's and 41.787s for @Edenia's.

#include <stdio.h>
#include <assert.h>

int isDivby9(int x)
{
    // early bailout when x is 0, otherwise the factor of 2 loop does not terminate.
    if (x == 0) {
        return 1;
    }

    // eliminate factors of 2
    while (0 == (x & 1)) {
        x >>= 1;
    }

    // repeatedly reduce the problem to testing whether (floor(x/8) - x%8) is divisible by 9
    // until we can use the trivial case of whether a number smaller than 9 is divisible by 9.
    // Note that x & 7 is not equal to x % 8 for negative numbers,
    // nor is floor(x/8) appropriate for negative numbers.
    // The algorithm requires a truncation toward 0, not to the next lower integer like floor() or >> 3 does.
    while (x >= 9) {
        x = (x >> 3) - (x & 7);
    }

    return x == 0;
}

int main()
{
    for (int i=0; i < 1000000; ++i)
        assert(isDivby9(i) == (i%9 == 0));
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You should primarily review the asker's code. \$\endgroup\$ – Jamal Mar 27 '15 at 20:32
  • \$\begingroup\$ I like this algorithm a lot along with Gnasher's. I wonder if it would be faster to eliminate the power of 2 loop. That loop uses a mask, compare, and shift (3 operations total) to process one bit of the input. The main loop uses a compare, shift, subtract, and mask (4 operations) to process 3 bits of the input. So I think you could just get rid of everything before the main loop. \$\endgroup\$ – JS1 Mar 28 '15 at 8:19
  • \$\begingroup\$ @Simon I built on your answer to come up with my own. And in doing so, I ran a timing test that showed your main loop is faster by itself without the factors of 2 loop. \$\endgroup\$ – JS1 Mar 28 '15 at 10:59
4
\$\begingroup\$

I really didn't like the way that @Edenia wrote the code, mine is like her's, only I think it is much cleaner and straightforward

    int isDivisibleBy(int number, int divisor)
    {
        for (int i = 0; i <= number; i += divisor)
        {
            if (i == number)
            {
                return 1;
            }
        }
        return 0;
    }

and this will work for any set of numbers and divisors.


The reason I like my code better is because the for loop is complete in a single block, while this may be aesthetic, it still seems cleaner to me. and we add up to the Number so on the final run we see whether or not we land on the number by incrementing of the divisor until we reach the number.

Neither @Edenia's nor my answer will work for Negative numbers, so please be wary of plugging in a negative number in there.


Because I was told this was not better than other code I formulated a while loop version of this code as well it is as follows and only checks the outcome once, and is still straight forward as to what it is doing.

int isDivisibleBy(int number, int divisor)
{
    int i = 0;
    while (i < number)
    {
        i += divisor;
    }
    return i == number;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ And it has to check on each iteration. You have interesting definition for "better". Also I don't know if I am the only one that thinks the C# part is more than irrelevant. \$\endgroup\$ – Edenia Mar 27 '15 at 15:20
  • \$\begingroup\$ this code is extendable, it has no magic numbers anywhere in the code. \$\endgroup\$ – Malachi Mar 27 '15 at 15:24
  • \$\begingroup\$ "It has no magic numbers anywhere in the code". Yes it doesn't have 9 despite the fact, everything is about it. Including the name of the function. Also yes it could be extended even more. Say.. debug checking etc. Different level of complexity.. \$\endgroup\$ – Edenia Mar 27 '15 at 15:26
  • 1
    \$\begingroup\$ It is. Now when I implied mine... the base method. it is more than obvious that it can be improved. The positive arithmetic was also mentioned already. I can't say it isn't better. Please don't take it as a race or something.. because it isn't. \$\endgroup\$ – Edenia Mar 27 '15 at 15:30
  • 2
    \$\begingroup\$ while ( (i += divisor) < number); \$\endgroup\$ – Edenia Mar 27 '15 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.