Ignore:
Timestamp:
09/02/03 17:50:32 (19 years ago)
Author:
piso
Message:

ISQRT

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/j/src/org/armedbear/lisp/numbers.lisp

    r3552 r3557  
    22;;;
    33;;; Copyright (C) 2003 Peter Graves
    4 ;;; $Id: numbers.lisp,v 1.8 2003-09-02 16:15:20 piso Exp $
     4;;; $Id: numbers.lisp,v 1.9 2003-09-02 17:49:54 piso Exp $
    55;;;
    66;;; This program is free software; you can redistribute it and/or
     
    163163                               rational
    164164                               rationalize)))
     165
     166
     167
     168;;; From discussion on comp.lang.lisp and Akira Kurihara.
     169(defun isqrt (n)
     170  "Returns the root of the nearest integer less than n which is a perfect
     171   square."
     172  (declare (type unsigned-byte n) (values unsigned-byte))
     173  ;; theoretically (> n 7) ,i.e., n-len-quarter > 0
     174  (if (and (fixnump n) (<= n 24))
     175      (cond ((> n 15) 4)
     176      ((> n  8) 3)
     177      ((> n  3) 2)
     178      ((> n  0) 1)
     179      (t 0))
     180      (let* ((n-len-quarter (ash (integer-length n) -2))
     181       (n-half (ash n (- (ash n-len-quarter 1))))
     182       (n-half-isqrt (isqrt n-half))
     183       (init-value (ash (1+ n-half-isqrt) n-len-quarter)))
     184  (loop
     185    (let ((iterated-value
     186     (ash (+ init-value (truncate n init-value)) -1)))
     187      (unless (< iterated-value init-value)
     188        (return init-value))
     189      (setq init-value iterated-value))))))
Note: See TracChangeset for help on using the changeset viewer.