Faster ISQRT on small (about fixnum sized) numbers.
authorLutz Euler <lutz.euler@freenet.de>
Mon, 29 Apr 2013 20:57:41 +0000 (22:57 +0200)
committerLutz Euler <lutz.euler@freenet.de>
Mon, 29 Apr 2013 20:57:41 +0000 (22:57 +0200)
commitdabb26b93be9bbf2718951ea2200fca874d3d587
tree8bc832d43005abc8bfd59d84094430d3ddde2d76
parent62f92bd02e9c04a46893ff9e7b88acdaeab230fa
Faster ISQRT on small (about fixnum sized) numbers.

ISQRT is implemented using a recursive algorithm for arguments above 24
which is compiled using generic arithmetic only (as it must support both
fixnums and bignums).

Improve this by compiling this recursive part twice, once using generic
and once fixnum-only arithmetic, and dispatching on function entry into
the applicable part. For maximum speed, the fixnum part recurs directly
into itself, thereby avoiding further type dispatching.

This makes ISQRT run about three times as fast on fixnum inputs while
the generated code is about 40 percent larger (both measured on x86-64).
For bignums a speedup can be seen, too, as ISQRT always recurs into
fixnum territory eventually, but the relative gain obviously becomes
smaller very fast with increasing size of the argument.

I have changed the variable names in the recursive part; they no longer
have an "n-" prefix as this in SBCL by convention means "number of" and
as the argument of the recursive part is no longer visibly "n".

Slightly augment the test case.
NEWS
src/code/numbers.lisp
tests/arith.pure.lisp