C - Division from scratch

Question

I wrote this code where division can be done without using C's builtin operator:

#include <stdio.h>
#include <math.h>
int idiv(int a, int b) {
 return a * (pow(b, -1));
}
int main(void) {
 /* 15/3 is 5 */
 printf("%d\n", idiv(15, 3));
 return 0;
}

Is there anything I could do to make this code faster? I benchmarked it with the division operator and it was more than 10x faster.

• S.S. Anne: You can do this with integers rather than floating-point, see libdivide.com
• Reinderien: To be facetious, you could use inline assembly that uses the machine's divide instruction without using the "C built-in operator" and this would meet the requirement at face value. Why are you doing this?
• xilpex: @Reinderien -- The ARM architecture does not necessarily have a builtin division instruction.
• Reinderien: Sure, but you didn't specify which architecture you're on, or whether this needs to be portable. This question is littered with unknowns.
• xilpex: @Reinderien -- No this does not need to be portable-- it needs to work efficiently on ARM.

Answer 1

It is unclear what toolchain do you use and what is target processor. However, I can guess about performance degradation. pow function usually works with floating point values. Moreover, most probably power with negitive exp will also use division. I compiled following code with ARM gcc 8.2 with -O3 flag:

#include <math.h>
int idiv(int a, int b) {
 return a * (pow(b, -1));
}
int idiv2(int a, int b) {
 return a/b;
}

I've got following assebly listing:

idiv:
 push {r4, r5, r6, lr}
 mov r6, r0
 mov r0, r1
 bl __aeabi_i2d
 mov r2, r0
 mov r3, r1
 mov r0, #0
 ldr r1, .L4
 bl __aeabi_ddiv
 mov r4, r0
 mov r0, r6
 mov r5, r1
 bl __aeabi_i2d
 mov r2, r0
 mov r3, r1
 mov r0, r4
 mov r1, r5
 bl __aeabi_dmul
 bl __aeabi_d2iz
 pop {r4, r5, r6, pc}
.L4:
 .word 1072693248
idiv2:
 push {r4, lr}
 bl __aeabi_idiv
 pop {r4, pc}

From assebly code the reson of performance problems is obvious. And we still dependent on ABI. If you want to have code that uses only assebly instructions? then you can implement integer division with "shift and subtract". Or you can google for some open source implementation of it. For example I found one here. Here is slightly modified example from here:

void unsigned_divide(unsigned int dividend,
 unsigned int divisor,
 unsigned int *quotient,
 unsigned int *remainder )
{
 unsigned int t, num_bits;
 unsigned int q, bit, d;
 int i;
 *remainder = 0;
 *quotient = 0;
 if (divisor == 0)
 return;
 if (divisor > dividend) {
 *remainder = dividend;
 return;
 }
 if (divisor == dividend) {
 *quotient = 1;
 return;
 }
 num_bits = 32;
 while (*remainder < divisor) {
 bit = (dividend & 0x80000000) >> 31;
 *remainder = (*remainder << 1) | bit;
 d = dividend;
 dividend = dividend << 1;
 num_bits--;
 }
 /* The loop, above, always goes one iteration too far.
 To avoid inserting an "if" statement inside the loop
 the last iteration is simply reversed. */
 dividend = d;
 *remainder = *remainder >> 1;
 num_bits++;
 for (i = 0; i < num_bits; i++) {
 bit = (dividend & 0x80000000) >> 31;
 *remainder = (*remainder << 1) | bit;
 t = *remainder - divisor;
 q = !((t & 0x80000000) >> 31);
 dividend = dividend << 1;
 *quotient = (*quotient << 1) | q;
 if (q) {
 *remainder = t;
 }
 }
} /* unsigned_divide */
#define ABS(x) ((x) < 0 ? -(x) : (x))
void signed_divide(int dividend,
 int divisor,
 int *quotient,
 int *remainder )
{
 unsigned int dend, dor;
 unsigned int q, r;
 dend = ABS(dividend);
 dor = ABS(divisor);
 unsigned_divide( dend, dor, &q, &r );
 /* the sign of the remainder is the same as the sign of the dividend
 and the quotient is negated if the signs of the operands are
 opposite */
 *quotient = q;
 if (dividend < 0) {
 *remainder = -r;
 if (divisor > 0)
 *quotient = -q;
 }
 else { /* positive dividend */
 *remainder = r;
 if (divisor < 0)
 *quotient = -q;
 }
} /* signed_divide */

You can take any, verify it and optimize it according to your needs. Generalized functions are usually more complicated than specialized.