1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can do this with integers rather than floating-point, see libdivide.com \$\endgroup\$ – S.S. Anne Jun 26 at 19:28
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Reinderien Jun 26 at 19:49
  • \$\begingroup\$ @Reinderien -- The ARM architecture does not necessarily have a builtin division instruction. \$\endgroup\$ – xilpex Jun 26 at 19:53
  • 1
    \$\begingroup\$ Sure, but you didn't specify which architecture you're on, or whether this needs to be portable. This question is littered with unknowns. \$\endgroup\$ – Reinderien Jun 26 at 19:53
  • \$\begingroup\$ @Reinderien -- No this does not need to be portable-- it needs to work efficiently on ARM. \$\endgroup\$ – xilpex Jun 26 at 19:54
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

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.