From: Erik Varga <erik.varga256@gm...>  20140513 20:01:20

Hi all, As some of you might know, I will be working on optimizing integer division by constants in sbcl during the summer. I'll describe my current plans here for anyone who's interested. I'd be happy to get some feedback or comments. I'm planning to use some methods described in these two papers: (1) Division by Invariant Integers using Multiplication (https://gmplib.org/~tege/divcnstpldi94.pdf) (2) NBit Unsigned Division Via NBit MultiplyAdd (http://arith.polito.it/final/paper104.pdf) Both papers aim to reduce the division X/Y to something like (A*X+B)/2^M and they assume that X and Y fit in N bits (the word size). The method currently used in sbcl for simplifying truncated unsigned division is described in (1) (figure 4.2). The problem with this method is that A can be bigger than N bits, and in this case the transformed code will be a bit more complicated. (2) doesn't have this problem, so I'm planning to replace the current method with that one for unsigned truncated/floored division. (1) also describes methods for signed truncation and flooring (it calls them "rounding towards zero" and "rounding towards negative infinity"). I'm planning to implement these for the signed floor and truncate. Since these numbers are signed, we have an additional bit, so there shouldn't be a problem with A being to large if I understand things correctly. In (1), the floored division is done by using the truncated division and adjusting the operands by 1 where necessary. It's pretty straightforward to do something similar for ceiling division, so I'm planning to use this adjusting to adapt the previously described unsigned truncation algorithm for the unsigned ceiling and the signed one for the signed ceiling. That's it for now, if anyone has further ideas or suggestions, I'd be glad to hear them. Best regards, Erik 