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 wrote:
>In article <34D16DF4.45DE3832@ilx020.iil.intel.com>, Zvi Avidor 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]