Re: guile & r5rs

[Radey Shouman <Radey_Shouman@splashtech.com>]

Jim Blandy <jimb@red-bean.com> writes:

I must have missed the message this was in reply to, please
forgive me if I've misconstrued.

> > The old favourite, Newton's iterative square root looks like:
> 
> Right; but you've totally skipped the interesting part.  It has to
> work in bignum arithmetic only.  We don't have rationals.  And
> we know exactly how much precision we need: we're looking for the
> integer closest to the true square root.

Newton's method is still a candidate, eg:

to solve x^2 = a :

x_new <-- x_old - (x_old ^ 2 - a) / (2 * x_old)

x_new <-- 1/2 * (x_old + a/x_old)

(define (in-sqrt a)
                     ;; Find a reasonable starting point:
    (let loop ((x (ash a (- (quotient (integer-length a) 2)))))
      (let ((x2 (quotient a x)))
        (let ((d2 (- x2 x)))
          (cond ((zero? d2) x)
                ((or (> d2 1) (< d2 -1))
                 (loop (ash (+ x x2) -1)))
                ((> x (- a (* x x)))
                 (min x x2))
                (else
                 (max x x2)))))))

>From some fooling around this seems to allocate bignums very roughly
20 times the size of the argument.

It's not clear to me that the integer nearest the answer is what's
needed.  Doesn't this depend on the representation of the floating
point answer?  Since the answers we would be dealing with would
all be greater than 2^512 or so, a 512 bit mantissa would be
necessary to distinguish two such numbers differing only by one.
Requiring the nearest integer sounds like massive overkill.