Floored Division

Users
1

My knowledge of floored division is like my usage of it in practice in over 30 years of programming, pretty well none. I cannot remember every using it in my line of work as only truncated division makes sense for the sort of applications I program which model physical phenomena of materials, structures and fluids. So take the following with a grain of salt.

The current code in Math.chpl is

proc divfloor(m: integral, n: integral) return
    if isNonnegative(m) then
      if isNonnegative(n) then m / n
      else                     (m - n - 1) / n
    else
      if isNonnegative(n) then (m - n + 1) / n
      else                     m / n;

This will generate branches in the code unless the compiler is extremely smart which is a tough ask.

It might be worth considered the following or something like it which, if the backend to the compiler is any good, will generate branch-less assembler.

proc divfloor(a : integral, b : integral)
{
    const d = a / b;

    return d - ((d * b != a ) & ((a < 0) ^ (b < 0)));
}

This algorithm, and its best mate which implements ceiling division and changes the subtraction in the return statement with addition, are certainly not as fast as their ?????pos friends, but they are much quicker than what is there today.

I would also stay away from the remainder operator.

Comments.

1 Like
2

Thanks, Damian! I'll need to think about it more, but I've added it to
the list of Math module things to track.

Lydia

3
4

Thanks John.

5

It could/should also be inlined for the case where the second argument is explicitly or even implicitly known at compile to exploit the optimizations done by the compiler for integer division.