[ create a new paste ] login | about

Link: http://codepad.org/vujdiSPh    [ raw code | output | fork ]

mohit_at_codepad - C, pasted on Apr 3:
/* Problem statement: Write a function to perform integer division */
/* These numbers are signed integer and are ALWAYS positive */
/* Try to minimize the branch and number of operations */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>
#include <math.h>


/**
 * Calculate quotient and remainder
 * @param[in] nn Numerator
 * @param[in] dd Denominator
 * @param[out] pq Quotient if passed, zero otherwise
 * @param[out] pr Remainder if passed, zero otherwise
 * @ret 0 if passed, -1 if error
 */
void my_int_div(int nn, int dd, int *pq, int *pr) {
  assert(pq);
  assert(pr);

  *pq = *pr = 0;

  if(dd) {
    unsigned int n = abs(nn), d = abs(dd);
    const unsigned int sign = (nn < 0) == (dd < 0) ? 1 : -1;
    unsigned int pow2[sizeof n * CHAR_BIT] = {d};
    int idx = 0;

    /* Prepare table containing multiple of nth power of 2 */
    while(pow2[idx] < n) {
      pow2[idx+1] = pow2[idx] << 1;
      ++idx;
    }

    /* Keep subtracting for successive approximation */
    do {  /* Scope of betterment here */
      if( pow2[idx] <= n ) {
        n -= pow2[idx];
        *pq |= (1 << idx);
      }
    } while(idx--);

    *pr = n;

    *pq *= sign;
  } else {
    /* Handling for divide by zero error case */
    return -1;
  }
  return 0;
}

int main() {
  const int TEST_COUNT = 5000;
  int i;

  srand(0);

  for(i = 1; i <= TEST_COUNT; ++i) {
    const int n = rand();  /* Should I use unsigned??? */
    const int d = rand() % (RAND_MAX / (1 + rand() % 4));

    const int exp_q = (d == 0) ? 0 : (n / d);
    const int exp_r = (d == 0) ? 0 : (n % d);

    int act_q, act_r;
    my_int_div(n, d, &act_q, &act_r);

    if(exp_q != act_q || exp_r != act_r) {
      printf("exp_q = %d, act_q = %d, exp_r = %d, act_r = %d (for %d / %d)\n",
                      exp_q,      act_q,      exp_r,      act_r,  n,   d);
      return -1;
    } else {
      /* printf("%-4d: passed for %d / %d\n", i, n, d); */
    }
  }
  printf("All test cases passed\n");
  return 0;
}


Output:
1
All test cases passed


Create a new paste based on this one


Comments: