From: Timm Ahrendt <ahrendt@cs.bonn.edu>
Subject: Re: algo to compute HUGE sqrt or division
Date: Thu, 28 Jan 1999 15:41:55 +0100
Newsgroups: comp.theory,sci.math
Keywords: Computing sqrt or quotients with very many digits of accuracy

I agree with Nick Maclaren that in this area you have to make use
of Newton-Raphson. 
I will add to notes to this hint:
- For large computations FFT-multiplication methods have to be used.
- Don't use "naive" Newton. See for example the paper of 
  Richard Brent how to use division-free Newton iterations. 
  There is another paper of Karp & Markstein about this topic which 
  includes a tricky idea how to speed up the last (and most expensive)
  iteration step.

Hope that helps, Timm.

Literature:
----------- 

  \bibitem{Brent:zero-find}
{\sc Brent, R.~P.}
\newblock Multiple-precision zero-finding methods and the complexity of
  elementary function evaluation.
\newblock In {\em Analytic Computational Complexity}, J.~F. Traub, Ed.
Academic
  Press, New York, 1976, pp.~151--176.

\bibitem{KaMa95:division}
{\sc Karp, A.~H., and Markstein, P.}
\newblock High precision division and square root.
\newblock Working draft, Hewlett Packard Laboratories, Palo Alto, CA
94304,
  Dec. 1995.
\newblock Submitted to {\em ACM Transactions on Mathematical Software}.



jerome@mycpu.org wrote:
> 
> I'm looking for an algorithm to compute really huge sqrt (beyond
> 200,000,000 bits of precision).
> 
> important: Assume i dont have enougth ram to store the entire number.
> 
> i'm looking for an division algorithm for numbers of the same
> size too.
==============================================================================
From: christer@neversoft.spam-b-gone.com (Christer Ericson)
Subject: Re: algo to compute HUGE sqrt or division
Date: Thu, 28 Jan 1999 18:33:29 GMT
Newsgroups: comp.theory,sci.math

For those who are interested, I found the Karp & Markstein
paper online at:

http://www.hpl.hp.com/techreports/93/HPL-93-42.html


On Thu, 28 Jan 1999 15:41:55 +0100, Timm Ahrendt <ahrendt@cs.bonn.edu> wrote:
[excerpt of previous post -- djr]
==============================================================================

From: "TwoBirds" <XXrs.1@ix.netcom.com>
Subject: Re: algo to compute HUGE sqrt or division
Date: Sat, 23 Jan 1999 23:56:04 -0800
Newsgroups: comp.theory,sci.math

http://www.lmu.edu/acad/personal/faculty/dmsmith/FMLIB.html


[original quoted -- djr]