CODEWITHSUNDEEP
cgccroundingcortex-minteger-division
spizzak
spizzak

Reputation: 1147

Cortex M0+/GCC Division with Rounding

I'm trying to implement an integer division with rounding. Obviously, by default integer division does floor and I was thinking I could use the remainder to determine if I should add 1 to my result.

Processor cycles are at a premium in this solution (running at 10s of kHz), so I'm seeking ways to do this with minimal overhead or ideally get the result "for free" as part of the existing division calculation

My question is, does anyone know of a good way of achieving this on the G0 which does not actually have a division instruction. Do I need to go into the disassembly and just see what it's doing? Do I need to write my own assembly code? Are there accepted solutions for this?

Note: Quotient and divisor are both arbitrary, and not constant integers.

Upvotes: 0

Views: 190

Answers (1)

chux
chux

Reputation: 153303

My question is, does anyone know of a good way of achieving this on the G0 which does not actually have a division instruction.

I do not know of any general purpose approach faster than what the compiler would already do.

There are ways to be faster than general purpose code if:

  • The range of the numerator (dividend) is non-negative.

  • The range of the denominator (divisor) is positive.

  • We can ignore INT_MIN/-1

  • Rounding mode ties are away from 0 (shown below) rather than ties to even.

Let q = rounded_division(a, b)

  • General purpose:

Use div() which computes a/b and a%b in a single operation.

#include <stdlib.h>

div_t qr = div(a, b);
if (qr.quot >= 0) {
  if (a >= 0) { 
    if (b/2 > r.rem) qr.quot++;
  } else {
    if (b/2 < r.rem) qr.quot--;
  }  
} else {
  if (a >= 0) { 
    if (b/2 < r.rem) qr.quot--;
  } else {
    if (b/2 > r.rem) qr.quot++;
  }  
}
  • When a >= 0 and b > 0 and a + b/2 does not overflow:

Add half the divisor before dividing.

q = (a + b/2)/b;
  • When a + b/2 (a - b/2) does not overflow:

Add half (with select sign) to the divisor before dividing.

  // If a and b have the same sign ...
  if ((a < 0) == (b < 0)) {
    q = (a + b/2)/b;
  } else { 
    q = (a - b/2)/b;
  }

The rounding done here is "round to nearest, ties away from 0".

Some potential optimizations possible with sign compares yet often harder to understand. Often the compile will emit good code without such crafted code. Example:

  // if ((a < 0) == (b < 0)) {
  if (!((a ^ b) & INT_MIN)) {

Division by 0 and INT_MIN/-1 remain undefined behavior (UB).

(I hope I coded all the cases right.)

Upvotes: 2

Related Questions