Cortex M0+/GCC Division with Rounding

Question

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.

If the number is positive (and there is headroom) add half the divisor before dividing. Negative - ditto but subtract half. If the divisor is positive you can obtain half by shifting. — Weather Vane, Feb 10 '23 at 19:09
For positive numbers: https://ideone.com/KAVUkW can be easily modified for negative. — Eugene Sh., Feb 10 '23 at 19:31
to do a/b but round up: `(a + (b - 1))/b`, round to nearest: `(a + b/2)/b`. Signed solution will be slightly different. All solutions are available in [Rounding integer division (instead of truncating)](https://stackoverflow.com/q/2422712/995714) — phuclv, Jun 25 '23 at 15:43
Does this answer your question? [Rounding integer division (instead of truncating)](https://stackoverflow.com/questions/2422712/rounding-integer-division-instead-of-truncating) — phuclv, Jun 25 '23 at 15:43

chux - Reinstate Monica · Answer 1 · 2023-02-11T04:57:36.880

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. Somewhat late. so will review again later.)

Cortex M0+/GCC Division with Rounding

1 Answers1