Re: square root (Re: guile & r5rs)

[roland.kaufmann@space.at]

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

    [[integer square root code omitted, but see note (2) below]]

    tel> That seems to get the same answer as bc for the numbers that
    tel> I felt like checking. Probably raiding a different bignum
    tel> library is better than figuring it all out again, unless
    tel> there are some very special requirements for guile that I'm
    tel> not aware of. Isn't the source for bc a GPL item anyhow?
What about using SLIB?

  (require 'root)
  (require 'random)			; just to generate arguments
  (define (root-test digits)
 "Test SLIB integer-sqrt for random argument with 2 * DIGITS decimal digits."
    (let* ((ran (random (expt 10 digits)))
	   (root (integer-sqrt (* ran ran))))
      (= ran root)))

(using slib2a6) this causes a stack overflow in Guile 1.3.1 
(from today's CVS) for DIGITS >= 118

  $ guile -q
  guile> (load "slib.scm") ;; see (1)
  guile> (load "root.scm")
  guile> (assert-repl-verbosity #t)
  ;;; 10  msec  (0 msec in gc)
  guile> (root-test 100)    
  #t
  ;;; 140  msec  (0 msec in gc)
  guile> (root-test 118)
  #t
  ;;; 240  msec  (120 msec in gc)
  guile> (root-test 119)
  ERROR: Stack overflow
  ABORT: (stack-overflow)
  guile> (debug-set! stack 0)
  (stack 0 debug depth 20 maxdepth 1000 frames 3 indent 10 procnames cheap)
  ;;; 40  msec  (0 msec in gc)
  guile> (root-test 119)
  #t
  ;;; 120  msec  (0 msec in gc)
  guile> (root-test 200)    
  #t
  ;;; 350  msec  (120 msec in gc)
  guile> (debug-disable 'debug)
  (stack 0 depth 20 maxdepth 1000 frames 3 indent 10 procnames cheap)
  ;;; 20  msec  (0 msec in gc)
  guile> (root-test 1000)
  #t
  ;;; 2850  msec  (140 msec in gc)
  guile> (root-test 5000)    
  #t
  ;;; 68420  msec  (1570 msec in gc)

Memory consumption runs a bit high for my taste--maybe there's a leak?

USER       PID %CPU %MEM   SZ  RSS TT       S    START  TIME COMMAND
kf       14527  1.2  1.0  800  596 pts/6    S 21:41:07  0:00 egrep PID|gui
kf       14495  0.0  5.721176 3576 pts/4    S 21:07:39  1:26 guile -q


  (1) 
  ;; slib.scm - make SLIB available to Guile 1.3.1
  (set! %load-path (cons "/home/kf/prog/funprog/" %load-path))
  (use-modules (ice-9 slib))

  (2) Tel's code is less memory-intensive (SZ = 3M), but slower
  (root-test modified to take the sqrt procedure as argument)

  guile> (root-test 100 square-root)
  #t
  ;;; 720  msec  (230 msec in gc)
  guile> (root-test 118  square-root)
  #t
  ;;; 1060  msec  (590 msec in gc)
  guile> (root-test 119 square-root)
  #t
  ;;; 930  msec  (470 msec in gc)
  guile> (root-test 200  square-root)
  #t
  ;;; 2650  msec  (1440 msec in gc)
  guile> (debug-disable 'debug)
  (stack 20000 depth 20 maxdepth 1000 frames 3 indent 10 procnames cheap)
  ;;; 20  msec  (0 msec in gc)
  guile> (root-test 1000 square-root)
  #t
  ;;; 92950  msec  (34280 msec in gc)

					    Regards,
						Roland