Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!MCC.COM!MCC.COM!AI.gadbois
From: AI.gadbois@MCC.COM (David Gadbois)
Newsgroups: comp.lang.lisp
Subject: Re: isqrt
Message-ID: <19910606055232.5.GADBOIS@KISIN.ACA.MCC.COM>
Date: 6 Jun 91 05:52:00 GMT
Lines: 75


    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.

    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
    XL1200.......Symbolics XL1200 running Genera 8.0.2

    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
    XL1200        0.757 sec           0.178 sec          0.00122 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
    XL1200        7.257 sec           1.484 sec          0.00450 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
    XL1200       84.780 sec          20.910 sec          0.0120 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.

I have found that MCL (nee MACL) is a really nice second-generation
Common Lisp.  In most of the cases I have tested, it does better than
the UNIX-based Lisps.  Plus, you can get a decent development platform
for under $10K.  The ISQRT implementation is evidently a disappointment,
though.

--David Gadbois