Division: Algorithms and user-submitted genAsm code

Integer Division on the Mill: User-contributions.

This page is for collecting ideas, pseudo-code and hopefully genAsm emulation sequences.

As in the parent page, please do NOT speculate on the Mill, per se. But alternative algorithms are most welcome. So, please feel free to add links to different ways to implement division.

Assumptions:

The rdiv* operator family (e.g. rdivu [[1]] and rdivs) provides an approximation to the reciprocal of its input argument. Scaling and precision are still TBD.

We can use integer operations (other than division), such as add, subtract, multiply, shift and count leading (and/or trailing) zeros.

---

Links: Wikipedia article on division algorithms: [2]

Wikipedia subsection on fast division algorithms: [3]

Note that the above link seems to make an implicit assumtion that floating-point math will be used. That's almost certainly not the case on the Mill, since we need to emulate division on family members that lack native floating point. Similarly, the pre-scaling outlined is optimized for (normalized) floating point values. So -- among other things -- the suggested constants may well not be correct (let alone optimal) for integer math to emulate division.