Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!sun-barr!ccut!yayoi!tansei1!d34676
From: d34676@tansei.cc.u-tokyo.ac.jp (Akira Kurihara)
Newsgroups: comp.lang.lisp
Subject: isqrt
Message-ID: <543@tansei1.tansei.cc.u-tokyo.ac.jp>
Date: 5 Jun 91 13:32:11 GMT
Sender: news@tansei.cc.u-tokyo.ac.jp
Organization: Computer Centre, University of Tokyo
Lines: 179


I am interested in the speed of a Common Lisp function isqrt
for extremely big bignums.

I compared three functions:

fast-isqrt-mid1.....given below
fast-isqrt-rec......given below
isqrt...............a Common Lisp function

These functions should return the same value.
I tried it on the following three environments:

MACL.........Macintosh Allegro Common Lisp 1.3.2 on Mac SE
             accelerated with 25 MHz 68020
lucid........Lucid Sun Common Lisp 4 on SPARCstation IPC
akcl.........Austin Kyoto Common Lisp 1.530 on SPARCstation IPC

I tried to calculate isqrt of:

(* 2 (expt 10 2000)).....to get  1000 digits of square root of 2
(* 2 (expt 10 6000)).....to get  3000 digits of square root of 2
(* 2 (expt 10 20000))....to get 10000 digits of square root of 2

Here is the result.

*** For 1000 digits ***

           fast-isqrt-mid1     fast-isqrt-rec         isqrt
MACL          1.250 sec           0.317 sec        174     sec
lucid         2.72  sec           0.63  sec         11.91  sec
akcl          2.400 sec           0.567 sec          2.483 sec

*** For 3000 digits ***

           fast-isqrt-mid1     fast-isqrt-rec         isqrt
MACL         12.233 sec           2.450 sec       4503     sec
lucid        27.68  sec           5.45  sec        102.12  sec
akcl         24.567 sec           5.100 sec         24.567 sec

*** For 10000 digits ***

           fast-isqrt-mid1     fast-isqrt-rec         isqrt
MACL        142     sec          35     sec         very long
lucid       327.75  sec          80.31  sec       1126.10  sec
akcl        273.917 sec          64.367 sec        275.783 sec

Looking at this table,
(1) 25 MHz 68020 Macintosh can be as twice as faster than SPARCstation IPC
as far as it is concerned with division of bignums by bignums.
(2) akcl is a little bit faster than lucid at least as far as it is
concerned with division of bignums by bignums.
(3) isqrt = fast-isqrt-mid1 on akcl ?

I appreciate very much if you would evaluate the following forms

(isqrt-time-comparison (* 2 (expt 10 2000)) 1 1)

(isqrt-time-comparison (* 2 (expt 10 6000)) 1 1)

(isqrt-time-comparison (* 2 (expt 10 20000)) 1 1)

on a different environment, and e-mail it to me. The function
isqrt-time-comparison is given below.

Also, if you have a faster function, would you inform me?

Thank you.

---

(defun fast-isqrt-simple (n &aux init-value iterated-value)
  "argument n must be a non-negative integer."
  (cond
   ((zerop n)
    0)
   (t
    (setq init-value 1)
    ; do iteration once
    (setq iterated-value (floor (+ init-value (floor n init-value)) 2))
    (setq init-value iterated-value)
    (loop
      ; do iteration, same as above
      (setq iterated-value (floor (+ init-value (floor n init-value)) 2))
      (if (>= iterated-value init-value) (return init-value))
      (setq init-value iterated-value)))))


(defun fast-isqrt-mid1 (n &aux n-len init-value iterated-value)
  "argument n must be a non-negative integer"
  (cond
   ((> n 24)		; theoretically (> n 0) ,i.e., n-len > 0
    (setq n-len (integer-length n))
    (if (evenp n-len)
      (setq init-value (ash 1 (ash n-len -1)))
      (setq init-value (ash 2 (ash n-len -1))))
    (loop
      (setq iterated-value (ash (+ init-value (floor n init-value)) -1))
      (if (not (< iterated-value init-value))
        (return init-value)
        (setq init-value iterated-value))))
   ((> n 15) 4)
   ((> n  8) 3)
   ((> n  3) 2)
   ((> n  0) 1)
   ((> n -1) 0)
   (t nil)))


(defun fast-isqrt-rec (n &aux n-len-quarter n-half n-half-isqrt
                       init-value iterated-value)
  "argument n must be a non-negative integer"
  (cond
   ((> n 24)		; theoretically (> n 7) ,i.e., n-len-quarter > 0
    (setq n-len-quarter (ash (integer-length n) -2))
    (setq n-half (ash n (- (ash n-len-quarter 1))))
    (setq n-half-isqrt (fast-isqrt-rec n-half))
    (setq init-value (ash (1+ n-half-isqrt) n-len-quarter))
    (loop
      (setq iterated-value (ash (+ init-value (floor n init-value)) -1))
      (if (not (< iterated-value init-value))
        (return init-value)
        (setq init-value iterated-value))))
   ((> n 15) 4)
   ((> n  8) 3)
   ((> n  3) 2)
   ((> n  0) 1)
   ((> n -1) 0)
   (t nil)))


(defun isqrt-time-comparison (n1 how-many iteration-times &aux n2)
  (setq n2 (+ n1 how-many))
  (print "do nothing")
  (time
   (let ((n n1))
     (loop
       (if (not (< n n2)) (return))
       (dotimes (i-t iteration-times)
         )
       (incf n))))
  (print "fast-isqrt-mid1")
  (time
   (let ((n n1))
     (loop
       (if (not (< n n2)) (return))
       (dotimes (i-t iteration-times)
         (fast-isqrt-mid1 n))
       (incf n))))
  (print "fast-isqrt-rec")
  (time
   (let ((n n1))
     (loop
       (if (not (< n n2)) (return))
       (dotimes (i-t iteration-times)
         (fast-isqrt-rec n))
       (incf n))))
  (print "isqrt")
  (time
   (let ((n n1))
     (loop
       (if (not (< n n2)) (return))
       (dotimes (i-t iteration-times)
         (isqrt n))
       (incf n))))
  nil)

----

Akira Kurihara

d34676@tansei.cc.u-tokyo.ac.jp

School of Mathematics
Japan Women's University
Mejirodai 2-8-1, Bunkyo-ku
Tokyo 112
Japan
03-3943-3131 ext-7243