Enhancement to speed of ISQRT

[Robert Smith]

1. Describe what you do, what happens, and what you expected
============================================================
a. Compute ISQRT for small and large integers (between 0 and 10e7.
b. ISQRT successfully computes it. See these benchmarks.
   http://paste.lisp.org/display/119381,1/raw
   http://paste.lisp.org/display/119381,2/raw
c. ISQRT should compute it even faster!

2. A complete repeatable test-case
==================================
A faster version provided here (also attached):

https://bitbucket.org/tarballs_are_good/numericl/src/d6284092b3ec/src/integer/isqrt.lisp

The benchmark used was [modulo the value in DOTIMES and argument to ITEST:

    (declaim (optimize (speed 3) (debug 0) (safety 0)))
    (defparameter dum-dum-pop 0)
    (defun itest (n ts &aux m1 m2)
      (progn
        (print 'isqrt) (terpri)
        (time (dotimes (i ts)
          (setq m1 (isqrt n))))
        (print 'my-isqrt) (terpri)
        (time (dotimes (i ts)
          (setq m2 (isqrt-fast n))))
        (print (list (integer-length m1) (integer-length m2)))))
    (dotimes (i 3)
      (setf dum-dum-pop (+ 7 (expt 11 (expt 10 i))))
      (format t "===================================================~%")
      (format t "x = 7 + 11^(10^~D); computed 10000000 times" i)
      (itest dum-dum-pop 1000000)
      (format t "~%===================================================~%"))

3. SBCL version as reported by "sbcl --version"
===============================================
SBCL 1.0.44
(Installed from source.)

4. Output from uname -a
=======================
Linux TheAmbiguousCase 2.6.35-25-generic #44-Ubuntu SMP Fri Jan 21 17:40:44 UTC 2011 x86_64 GNU/Linux

5. *FEATURES*.
==============
(:QUICKLISP :SB-BSD-SOCKETS-ADDRINFO :ASDF2 :ASDF :ANSI-CL :COMMON-LISP
 :SBCL :SB-DOC :SB-TEST :SB-LDB :SB-PACKAGE-LOCKS :SB-UNICODE :SB-EVAL
 :SB-SOURCE-LOCATIONS :IEEE-FLOATING-POINT :X86-64 :UNIX :ELF :LINUX
 :SB-THREAD :LARGEFILE :GENCGC :STACK-GROWS-DOWNWARD-NOT-UPWARD
 :C-STACK-IS-CONTROL-STACK :LINKAGE-TABLE :COMPARE-AND-SWAP-VOPS
 :UNWIND-TO-FRAME-AND-CALL-VOP :RAW-INSTANCE-INIT-VOPS
 :STACK-ALLOCATABLE-CLOSURES :STACK-ALLOCATABLE-VECTORS
 :STACK-ALLOCATABLE-LISTS :STACK-ALLOCATABLE-FIXED-OBJECTS
 :ALIEN-CALLBACKS :CYCLE-COUNTER :COMPLEX-FLOAT-VOPS :FLOAT-EQL-VOPS
 :INLINE-CONSTANTS :MEMORY-BARRIER-VOPS :OS-PROVIDES-DLOPEN
 :OS-PROVIDES-DLADDR :OS-PROVIDES-PUTWC :OS-PROVIDES-SUSECONDS-T
 :OS-PROVIDES-GETPROTOBY-R :OS-PROVIDES-POLL)

[Nikodemus Siivola (nikodemus)]

In 1.0.47.6.