From: HJSmith@ix.netcom.com (Harry J. Smith)
Newsgroups: sci.math
Subject: Re: algorithm of sqr
Date: Sat, 19 Oct 1996 20:24:28 GMT

gabbriel@dada.it (Winston2) wrote:

>Hallo everybody! I'd like to know which is the algorithm to calculate
>x^(1/2)... I need to put the procedure into quickbasic program, and I
>need to have a great quantity of decimals (i.e. the first 50000)

>Can you help me?

>Thanx

>Winston2

If you are going to compute y = x^(1/2) to 50,000 decimal places, first compute
z = x^(-1/2) and then y = x*z. This way there will be no long divisions in the
calculations.

To compute z = x^(-1/2), iterate on

       z = (1 - x*z*z)*z/2 + z

-Harry

-- 
| Harry J. Smith, 19628 Via Monte Dr., Saratoga, CA 95070-4522, USA
| Home Phone: 1 408 741-0406, Work Phone: 1 408 235-5088 (Voice Mail)
| E-mail: HJSmith@ix.netcom.com, Fax: 1 408 235-2019
| Web site: http://www.netcom.com/~hjsmith
--
==============================================================================
From: Email_To...Hans.Olsson@dna.lth.se (Hans Olsson)
Newsgroups: sci.math.num-analysis
Subject: Re: square root calculation
Date: 30 Jan 1998 15:57:04 GMT

In article <6asbnf$3b2$1@nets3.rz.RWTH-Aachen.DE>,
Helmut Jarausch <jarausch@numa1.igpm.rwth-aachen.de> wrote:
>In article <34D16DF4.45DE3832@ilx020.iil.intel.com>, Zvi Avidor <zavidor@ilx020.iil.intel.com> writes:
>|> Can anyone give me a fast and accurate algorithm of sqrt calculation. ?
>
>Herons method (about 2000 years old) is still the best  

It depends on the computer and your numbers (and accuracy requirements).

>the iteration  x_{n+1} = ( x_n + R/x_n )/2   computes  sqrt(R).
>It's equivalent to applying Newtons method  to  x^2-R = 0;

The problem is that R/x_n can be expensive, which you can avoid by computing
1/sqrt(R) from Newton's applied to R-1/x^2 giving:

x_{n+1}= x_n/2 *(x_n^2*R-3)

It requires better starting values but converges quadratically to
1/sqrt(R). You can then compute an approximation of sqrt(R) by x_n *R

>If  R  varies in a wide range, you take different initial values (x_0)
>for different ranges. But be sure that branching is not more expensive than
>what you save by that.

This still holds.


--
// Homepage  http://www.dna.lth.se/home/Hans_Olsson/
// Email To..Hans.Olsson@dna.lth.se [Please no junk e-mail]