More efficient integer division by multiplication
authorPaul Khuong <pvk@pvk.ca>
Sun, 14 Aug 2011 20:46:01 +0000 (16:46 -0400)
committerPaul Khuong <pvk@pvk.ca>
Sun, 14 Aug 2011 20:46:01 +0000 (16:46 -0400)
commitf17e3d27d7ff599f9443d011d17017a2a858c81a
treecd1b0537b6c9a744d3c7e3525e944f299e711b89
parent4e431db581c21b8d54119e2892567f5fc09562f1
More efficient integer division by multiplication

 * Exploit restricted range for inputs (e.g. fixnums).

 * When the divisor is even, simplify with a mask instead of a shift.

 * Clean up the code a bit: we don't want modular arithmetic, it's
   actually all guaranteed not to wrap around.

 * Change the test so that larger divisors are a bit more likely to
   get tested too.

 * Lots more things can be done, including generalizing the transform
   to pretty much arbitrary rational divisor, or avoiding the costly
   general code sequence in nearly all cases.  Unfortunately, it's a
   lot of (somewhat original, at that) code, and can be fairly slow;
   if it matters to someone, I can try and find a compromise (contrib?).
src/compiler/srctran.lisp
tests/arith.pure.lisp