Re: New version of sqrtrem.c

[Kevin Ryde]

Rick Coupland <address@hidden> writes:
>
> I am attaching a new version of sqrtrem.c.  This uses a new algorithm
> which I developed.

Paul Zimmermann has also contributed a new sqrt, based on a paper by
him, which you might like to compare,

        "Karatsuba Square Root", INRIA Research Report 3805, November
        1999, `http://www.inria.fr/RRRT/RR-3805.html'

I measure your routine as about the same (or just a touch slower at
big sizes) than his.  I guess that's not surprising since both, if I'm
not mistaken, effectively limit the sizes of the divisions at each
step, which the gmp 3.1.1 routine didn't do (or didn't do as well as
is possible).

An alternative idea you might have seen in doc/projects.html is to
calculate a fixed point approximation to 1/sqrt and avoid divisions
altogether.  In practice division is roughly 2 to 4 times slower than
multiplication so this has some potential, though the final "sqrt = A
* 1/sqrt" would I guess be a full size multiply (or the high half of
such) and might kill any savings.