Re: square root (Re: guile & r5rs)

[hjstein@bfr.co.il (Harvey J. Stein)]

Tel <telford@eng.uts.edu.au> writes:

 > >   (2) Tel's code is less memory-intensive (SZ = 3M), but slower
 > >   (root-test modified to take the sqrt procedure as argument)
 > 
 > Mine needs a better initial estimate, something like what Radey was
 > doing with integer-length. That should cut the iterations down.
 > I'm a bit unsure about the best way to do this.
 > 
 > >   guile> (root-test 1000 square-root)
 > >   #t
 > >   ;;; 92950  msec  (34280 msec in gc)
 > 
 > The garbage collection is quite high here which puzzles me because
 > I don't understand where my code is generating garbage, it just sets
 > some local variables and tail-chains. The same closure should be
 > holding all the local variables for all iterations. Roland stated that
 > this was done with debugging turned off so it shouldn't be going into
 > stack tracing. Why is it generating so much garbage?

You're code looks like this:

(define (square-root-recur C X)
  (let* ((x2 (quotient (+ (quotient (+ C X -1) X) X) 2)))
    (cond ((>= x2 X) X)
	  (else (square-root-recur C x2)))))

(define (square-root C)
  (cond ((< C 0) (please-install-complex-support))
	((< C 1) 0)
	(else (square-root-recur C C))))

I'd think each iteration would produce garbage as follows:

   (+ C X -1) - produces a new bignum
   (quotient (+ C X -1) X) creates another one.  1st one is
   inaccessable & thus eventually gets GCed.
   Adding above to X - new bignum, prev is thrown away.
   Another quotent call - another new bignum.
   Comparison - should return internal #t, no garbage,
   Tail call of square-root-recur - Previous value of X is thrown
   away & x2 is thrown away.

So I count 4 bignums created & thrown away per iteration.

-- 
Harvey J. Stein
BFM Financial Research
hjstein@bfr.co.il