summaryrefslogtreecommitdiffstats
path: root/root.scm
diff options
context:
space:
mode:
Diffstat (limited to 'root.scm')
-rw-r--r--root.scm28
1 files changed, 24 insertions, 4 deletions
diff --git a/root.scm b/root.scm
index 0a56bc9..3cfdc19 100644
--- a/root.scm
+++ b/root.scm
@@ -40,11 +40,31 @@
(next-fx (f next-x)))
(cond ((>= (abs next-fx) (abs fx)) x)
(else (loop next-x next-fx)))))))))))
+
+;;(define (integer-sqrt y)
+;; (newton:find-integer-root (lambda (x) (- (* x x) y))
+;; (lambda (x) (* 2 x))
+;; (ash 1 (quotient (integer-length y) 2))))
+
+;;;; http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/math/isqrt/isqrt.txt
+;;; Akira Kurihara
+;;; School of Mathematics
+;;; Japan Women's University
;@
-(define (integer-sqrt y)
- (newton:find-integer-root (lambda (x) (- (* x x) y))
- (lambda (x) (* 2 x))
- (ash 1 (quotient (integer-length y) 2))))
+(define (integer-sqrt n)
+ (cond ((> n 24) (let* ((length/4 (quotient (- (integer-length n) 1) 4))
+ (sqrt-top (integer-sqrt (ash n (* -2 length/4))))
+ (init-value (ash sqrt-top length/4))
+ (q (quotient n init-value))
+ (iterated-value (quotient (+ init-value q) 2)))
+ (if (odd? q) iterated-value
+ (let ((m (- iterated-value init-value)))
+ (if (< (remainder n init-value) (* m m))
+ (- iterated-value 1)
+ iterated-value)))))
+ ((> n 15) 4) ((> n 8) 3) ((> n 3) 2) ((> n 0) 1) ((> n -1) 0)
+ (else (slib:error 'integer-sqrt n))))
+
;@
(define (newton:find-root f df/dx x_0 prec)
(if (and (negative? prec) (integer? prec))