[no subject]

[d34676@tansei.cc.u-tokyo.ac.jp (Akira KURIHARA)]

Dear Lisper,

The function isqrt of MACL is extremely slow for extremely big integers.
Please, try and feel the followings.


(defun my-isqrt (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 my-isqrt-big (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 (my-isqrt-big 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)))


(setq x (+ (expt 3 3333) 333333333))

(time (my-isqrt x))

(time (my-isqrt-big x))

(time (isqrt x))

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-943-3131 ext-7243