AI.gadbois@MCC.COM (David Gadbois) (06/09/91)
Date: 6 Jun 91 15:22:47 GMT
From: miller@FS1.cam.nist.gov (Bruce R. Miller)
In article <19910606055232.5.GADBOIS@KISIN.ACA.MCC.COM>, I write:
> Date: 5 Jun 91 13:32:11 GMT
> From: d34676@tansei.cc.u-tokyo.ac.jp (Akira Kurihara)
>
> I am interested in the speed of a Common Lisp function isqrt
> for extremely big bignums.
>
> I added the results of running the test on a Symbolics machine.
> The results for the builtin ISQRT are surprising. While I
> normally run screaming from numeric code, I had a look at the
> source, and it uses one of those clever bit-twiddling tricks that
> appears to calculate the result in O( (INTEGER-LENGTH n) ) time.
> One of the "numerical recipes" books probably has an explanation
> of it.
Actually, one of the compiler books probably has an explanation of
it!
I did the same computations (but using Genera 8.0.1, in case it
matters) and got essentially the same results as you did. I mailed
the results directly to Akira -- with one change:
Apparently the symbolics knows that isqrt has no `real' side-effects
and optimizes it out -- the disassembled code reveals no call to
isqrt -- and I doubt that isqrt is stashed in microcode! To trick
the compiler, I changed each timing body to
(setq result n)
(setq result (fast-isqrt-mid1 n))
...
(setq result (isqrt n))
and redid the tests. Everything was the same except the isqrt
timings which now are essentially the same as fast-isqrt-mid1 (which
_is_ "one of those clever bit-twiddling tricks" !).
Gack, how embarrassing. I should have know better. By way of penance,
here are the updated collected figures:
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
XL1200.......Symbolics XL1200 running Genera 8.0.2
CMUCL........CMU Common Lisp (10-May-1991) sun4/330 running sunos 4.0.3
^^^^^^^^^^^^^^^
Is this Python? Running under SUNOS!? Where can I get
a copy?
AKCL.........Austin KCL Version 1.505 sun4/330 running sunos 4.0.3
DS3100A......Allegro (version?) on DECStation 3100
DS3100L......Lucid Common Lisp 4.0 on DEC DS-3100
DS5000.......Lucid Common Lisp 4.0 on DEC DS-5000
*** For 1000 digits ***
fast-isqrt-mid1 fast-isqrt-rec isqrt faster-isqrt-rec
MACL 1.250 0.317 174
lucid 2.72 0.63 11.91
akcl 2.400 0.567 2.483
XL1200 0.757 0.178 0.729 0.111
CMUCL 0.610 0.080 234.340
AKCL 2.517 0.550 2.483
DS3100A 0.884 0.517
DS3100L 2.34 .55 11.54
DS5000 1.34 .32 6.57
*** For 3000 digits ***
fast-isqrt-mid1 fast-isqrt-rec isqrt faster-isqrt-rec
MACL 12.233 2.450 4503
lucid 27.68 5.45 102.12
akcl 24.567 5.100 24.567
XL1200 7.257 1.484 6.612 0.853
CMUCL 5.710 1.170 (> 1 hour)
AKCL 24.050 4.817 24.950
DS3100A 7.30 4.02
DS3100L 23.87 4.71 95.85
DS5000 13.69 2.70 54.10
*** For 10000 digits ***
fast-isqrt-mid1 fast-isqrt-rec isqrt faster-isqrt-rec
MACL 142 35 very long
lucid 327.75 80.31 1126.10
akcl 273.917 64.367 275.783
XL1200 84.780 20.910 83.085 9.205
CMUCL 37.720 5.470 very long
AKCL 276.617 68.950 272.317
DS3100A 107. 43.8
DS3100L 283.89 69.54 1052.86
DS5000 161.16 39.61 605.57
--David Gadbois