Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!cme!cam!ARTEMIS
From: miller@FS1.cam.nist.gov (Bruce R. Miller)
Newsgroups: comp.lang.lisp
Subject: Re: isqrt
Message-ID: <2885210567@ARTEMIS.cam.nist.gov>
Date: 6 Jun 91 15:22:47 GMT
References: <19910606055232.5.GADBOIS@KISIN.ACA.MCC.COM>
Sender: news@cam.nist.gov
Followup-To: comp.lang.lisp
Organization: NIST - Computing and Applied Mathematics Laboratory
Lines: 35


In article <19910606055232.5.GADBOIS@KISIN.ACA.MCC.COM>, David Gadbois writes: 
>     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" !). 

bruce
miller@cam.nist.gov