Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++ functions for integer division with well defined rounding strategy

Tags:

c++

c++11

I want something in C++ that lets me do efficient integer division with specified rounding behavior, something like this:

div_down(-4,3)        ==> -2
div_up(4,3)           ==> 2
div_to_zero(-4,3)     ==> -1
div_to_nearest(5,3)   ==> 2

I'd like it to detect target machine behavior at compile time and generate the appropriate optimal implementations. Something similar for modulus would also be nice, abstracting out the undefined behavior for negative operands at compile time.

Does this exist?

If not, what's a nice way to make it? I can think of a few possible approaches:

  • Try to implement them as single expressions that statically optimize
  • Use constant expressions to detect target behavior and choose from multiple implementations, parhaps using templates (but how exactly?)
like image 927
jedediah Avatar asked Nov 15 '11 13:11

jedediah


2 Answers

This is what I've got so far, with the precondition d > 0. They all seem to work, but can they be simplified?

int div_down(int n, int d) {
  if (n < 0) {
    return -((d - n - 1) / d);
  } else {
    return n / d;
  }
}

int div_up(int n, int d) {
  if (n < 0) {
    return -(-n / d);
  } else {
    return (n + d - 1) / d;
  }
}

int div_to_zero(int n, int d) {
  return n / d;
}

int div_to_nearest(int n, int d) {
  if (n < 0) {
    return (n - d/2 + 1) / d;
  } else {
    return (n + d/2) / d;
  }
}
like image 112
jedediah Avatar answered Sep 29 '22 04:09

jedediah


An old post, but here it goes. Kindly accept & rate it if you like.

int div_to_zero(int n, int d) { return n / d; }
//as per C++11 standard note 80

int div_up(int n, int d) {
    return n / d + (((n < 0) ^ (d > 0)) && (n % d));
} //i.e. +1 iff (not exact int && positive result)

int div_down(int n, int d) {
    return n / d - (((n > 0) ^ (d > 0)) && (n % d));
} //i.e. +1 iff (not exact int && negative result)

int div_to_nearest(int n, int d) {
    return (2*n - d + 2*(true&&(n<0^d>0))*d) / (2*d); 
} //i.e. +-0.5 as per pre-rounding result sign, then div_to-zero 
//it however rounds numbers like +/- 3.5 towards 0 and not even.

Note: most modern compilers will use a single division operation for n/d and n%d used in conjunction. So performance wise these are best reducing memory moves.

like image 28
Atif Hussain Avatar answered Sep 29 '22 04:09

Atif Hussain