I took a shot at a faster division algorithm for unsigned ints, but am not certain that I really want to believe the timings I ended up with - and would appreciate some peer review. Here's my complete test code (n:numerator, d:denominator, q:quotient):
volatile unsigned q = 999; /* Quotient (result) variable */
/*-------------------------------------------------------------------------*/
/* udiv() - performs unsigned int division */
/*-------------------------------------------------------------------------*/
unsigned udiv(unsigned n,unsigned d)
{ unsigned char s = 1; /* Shift counter for early out testing */
unsigned r = 1, m = ~(~0u >> 1); /* Bottom and top bit masks */
/* unsigned */ q = 0; /* Quotient initialized to zero */
if (d) /* If denominator isn't zero */
{ if (n >= d) /* If numerator > denominator */
{ while (!(n & m)) m >>= 1; /* Find numerator MSB */
while (!(d & m)) /* Until denominator MSB matches mask */
{ d <<= 1; /* Shift denominator left one bit pos */
r <<= 1; /* Shift quotient bit to suit */
++s; /* Increase shift counter */
} /* end: denominator MSB search */
while (n && s--) /* Until numerator zero or end shift */
{ if (n >= d) /* If n < d then n is remainder (done) */
{ n -= d; /* Subtract partial quotient and */
q |= r; /* Insert bit into quotient */
} /* end: if n >= d */
d >>= 1; /* Shift divisor right one position */
r >>= 1; /* Shift quotient bit to match */
} /* end: until numerator zero */
} /* end: if numerator > denominator */
else q = 0; /* Numerator < denominator => zero */
} /* end: if not dividing by zero */
else q = ~0; /* Very ugly - division by zero! */
return q; /* Return the quotient to the caller */
} /* end: udiv() */
/*-------------------------------------------------------------------------*/
void setup(void)
{ unsigned n,d;
unsigned long t;
float a;
Serial.begin(115200);
t = micros();
for (n=0; n<=100; n++)
{ for (d=0; d<=100; d++)
{ // printf("%u/%u = %u\n",n,d,udiv(n,d));
q = udiv(n,d);
}
}
t = micros() - t;
a = (float)t / 101 / 101;
Serial.print("elapsed = ");
Serial.print(t);
Serial.print("usec, average = ");
Serial.print(a);
Serial.println("usec");
}
void loop(void)
{ Serial.println(q);
for (;;);
}
Here's what I got on my Serial monitor:
elapsed = 78580usec, average = 7.70usec
1
Edit: provided q with an initial value, added comments to udiv().
