I received some results on (time ...) of isqrt and similar functions
for very big bignums.
I requested to calculate essentially (isqrt (* 2 (expt 10 (* 2 d))))
for d = 1000, 3000, 10000.
The following is what I received and compiled. I hope I made no mistake
while making this table.
Be sure that this table tells you ONLY about:
(A) whether the system is fast for bignum operation, especially division.
(B) whether the algorithm of isqrt for bignum is fast.
*** Lisps and Machines ***
(1) CMU Common Lisp (10-May-1991) on sun4/330
(2) Genera 8.0.1 on Symbolics XL1200
(3) Genera 8.0.2 on Symbolics XL1200
(4) Allegro Common Lisp on SPARCstation2
(5) Macintosh Allegro Common Lisp 1.3.2 on Mac SE accelerated with 25 MHz 68020
(6) Lucid Common Lisp 4.0 on DEC 5000
(7) Lucid Sun Common Lisp 4.0 on SPARCstation2
(8) Macintosh Allegro Common Lisp 1.3.1 on Mac IIcx
(9) Macintosh Common Lisp 2.0b1p2 on Macintosh IIx
(a) Austin Kyoto Common Lisp 1.505 on sun4/330
(b) Austin Kyoto Common Lisp 1.530 on SPARCstation IPC
(c) Lucid Common Lisp 4.0 on DEC 3100
(d) Lucid Sun Common Lisp 4 on SPARCstation IPC
(e) Allegro Common Lisp on DEC 3100
*** For 1,000 digits *** (time is in second)
fast-isqrt-mid1 fast-isqrt-rec isqrt
(1) 0.610 0.080 234.340
(2) 0.728583 0.179719 0.731269
(3) 0.757 0.178 0.729
(4) 0.984 0.217 1.917
(5) 1.250 0.317 174
(6) 1.34 0.32 6.57
(7) 1.47 0.35 7.34
(8) 1.983 0.467 272.867
(9) 2.150 0.567 0.633
(a) 2.517 0.550 2.483
(b) 2.400 0.567 2.483
(c) 2.34 0.55 11.54
(d) 2.72 0.63 11.91
(e) 3.534 0.800 5.216
*** For 3,000 digits *** (time is in second)
fast-isqrt-mid1 fast-isqrt-rec isqrt
(1) 5.710 1.170 very long (> 1 hour)
(2) 7.114492 1.422794 6.636563
(3) 7.257 1.484 6.612
(4) 10.067 1.966 19.634
(5) 12.233 2.450 4503
(6) 13.69 2.70 54.10
(7) 15.06 2.97 64.05
(8) 19.583 3.917 7164.333
(9) 20.117 4.083 4.150
(a) 24.050 4.817 24.950
(b) 24.567 5.100 24.567
(c) 23.87 4.71 95.85
(d) 27.68 5.45 102.12
(e) 36.717 7.200 54.283
*** For 10,000 digits *** (time is in second)
fast-isqrt-mid1 fast-isqrt-rec isqrt
(1) 37.720 5.470 very long
(2) 83.216370 20.502718 83.681786
(3) 84.780 20.910 83.085
(4) 117.650 28.783 233.984
(5) 142 35 very long
(6) 161.16 39.61 605.57
(7) 179.34 44.87 719.45
(8) 229.183 56.467 very long
(9) 229.383 56.500 56.533
(a) 276.617 68.950 272.317
(b) 273.917 64.367 275.783
(c) 283.89 69.54 1052.86
(d) 327.75 80.31 1126.10
(e) 435.350 106.617 645.550
Potential Problem:
(i) Under some environment with a wise compiler, the function
isqrt-time-comparison, which I posted earlier, is over-optimized
for our purpose. If so, (time ...) will return almost 0 second.
(ii) ····@cambridge.apple.com suggested me the following
>Also, it is best to pass a simple function call to the TIME macro.
>If you pass a complex form to TIME, then the timing will include
>the time used to process the complex form. This processing may
>involve invoking the compiler.
So, probably it is safe to do something like:
(let* ((how-many-dig 1000) ; this is for d = 1000
(n (* 2 (expt 10 (* 2 how-many-dig)))))
(terpri)
(princ "sqrt of 2 -> ")
(princ how-many-dig)
(princ " digits")
(terpri)
(time (fast-isqrt-mid1 n))
(time (fast-isqrt-rec n))
(time (isqrt n))
nil)
Also, I received a function isqrt-newton (given below) from
·······@aspen.Berkeley.EDU, which is twice as fast as fast-isqrt-rec.
I followed his proof that this function returns correct answer.
I believe that, as far as one employs Newton's method, no one can
make functions which is twice as fast as isqrt-newton.
(defun isqrt-newton (n &aux n-len-quarter n-half n-half-isqrt
init-value q r m iterated-value)
"argument must be a non-negative integer"
(cond
((> n 24) ; theoretically (> n 15) ,i.e., n-len-quarter > 0
(setq n-len-quarter (ash (- (integer-length n) 1) -2))
(setq n-half (ash n (- (ash n-len-quarter 1))))
(setq n-half-isqrt (isqrt-newton n-half))
(setq init-value (ash n-half-isqrt n-len-quarter))
(multiple-value-setq (q r) (floor n init-value))
(setq iterated-value (ash (+ init-value q) -1))
(cond ((oddp q)
iterated-value)
(t
(setq m (- iterated-value init-value))
(if (> (* m m) r)
(1- iterated-value)
iterated-value))))
((> n 15) 4)
((> n 8) 3)
((> n 3) 2)
((> n 0) 1)
((> n -1) 0)
(t nil)))
--
Akira Kurihara
······@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