From 69d4f1c761291d2c33c4b22454877402465b2c48 Mon Sep 17 00:00:00 2001 From: "Thomas Bushnell, BSG" Date: Sun, 4 Dec 2005 20:03:34 -0800 Subject: Import Debian changes 3a2-3 slib (3a2-3) unstable; urgency=low * Brought all source files up-to-date with upstream CVS. Repeat changes from version 3a2-1 in Makefile. --- root.scm | 28 ++++++++++++++++++++++++---- 1 file changed, 24 insertions(+), 4 deletions(-) (limited to 'root.scm') 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)) -- cgit v1.2.3