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.