From: David Gadbois
Subject: Re: isqrt
Date: 
Message-ID: <19910609062237.3.GADBOIS@KISIN.ACA.MCC.COM>
    Date: 6 Jun 91 15:22:47 GMT
    From: ······@FS1.cam.nist.gov (Bruce R. Miller)

    In article <························@KISIN.ACA.MCC.COM>, I write: 
    >     Date: 5 Jun 91 13:32:11 GMT
    >     From: ······@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