# Diff of /src/code/irrat.lisp

revision 1.10 by wlott, Fri Feb 14 23:45:06 1992 UTC revision 1.11 by ram, Mon Mar 1 15:24:54 1993 UTC
# Line 200  Line 200
200           (%sqrt number)))           (%sqrt number)))
201      ((complex) (exp (/ (log number) 2)))))      ((complex) (exp (/ (log number) 2)))))
202
;;; ISQRT:  Integer square root - isqrt(n)**2 <= n
;;; Upper and lower bounds on the result are estimated using integer-length.
;;; On each iteration, one of the bounds is replaced by their mean.
;;; The lower bound is returned when the bounds meet or differ by only 1.
;;; Initial bounds guarantee that lg(sqrt(n)) = lg(n)/2 iterations suffice.

(defun isqrt (n)
"Returns the root of the nearest integer less than
n which is a perfect square."
(if (and (integerp n) (not (minusp n)))
(do* ((lg (integer-length n))
(lo (ash 1 (ash (1- lg) -1)))
(hi (+ lo (ash lo (if (oddp lg) -1 0))))) ;tighten by 3/4 if possible.
((<= (1- hi) lo) lo)
(let ((mid (ash (+ lo hi) -1)))
(if (<= (* mid mid) n) (setq lo mid) (setq hi mid))))
(error "Isqrt: ~S argument must be a nonnegative integer" n)))

203
204  ;;;; Trigonometic and Related Functions  ;;;; Trigonometic and Related Functions
205

Legend:
 Removed from v.1.10 changed lines Added in v.1.11

 ViewVC Help Powered by ViewVC 1.1.5