Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / First Aid / January 2007

Tip: Looking for answers? Try searching our database.

Square root

Thread view: 
f2prateek - 15 Jan 2007 16:49 GMT
What is the method of finding the square root of a number?
Boris Stumm - 15 Jan 2007 17:06 GMT
> What is the method of finding the square root of a number?

java.lang.Math.sqrt()
J. David Boyd - 15 Jan 2007 18:14 GMT
> What is the method of finding the square root of a number?

Here's one, that takes me back to high school:

http://www.qnet.fi/abehr/Achim/Calculators_SquareRoots.html
Gregory Toomey - 16 Jan 2007 12:36 GMT
>> What is the method of finding the square root of a number?
>
> Here's one, that takes me back to high school:
>
> http://www.qnet.fi/abehr/Achim/Calculators_SquareRoots.html

I read about that algorithm when I was 11. I've never seen a computer implementation of it.

gtoomey
J. David Boyd - 16 Jan 2007 15:58 GMT
>>> What is the method of finding the square root of a number?
>>
[quoted text clipped - 6 lines]
>
> gtoomey

Me either.  But I didn't think the O.P. was looking for a computer
algorithm, just a method.

Dave
John W. Kennedy - 16 Jan 2007 18:24 GMT
>>> What is the method of finding the square root of a number?
>>
[quoted text clipped - 4 lines]
> I read about that algorithm when I was 11. I've never seen a computer
> implementation of it.

Of course not. The Newton-Raphson iteration is much faster.

However, in some cases, the use of a square root indicates that the
actual thing to be computed is a Pythagorean sum. That can be calculated
better.

/**
 * Compute the Pythagorean Sum (I.E. what is the distance given Delta X,
 * and Delta Y)
 *
 * Traditionally, this is done as sqrt(x*x+y*y), but this has the
 * problem that the squared quantity can overflow long before the result
 * would have.
 *
 * Cleve Moler and Donald Morrison show (as documented in their article
 * in the IBM Journal of Research and Development, VOL27 No 6 NOV 83)
 * that this can actually computed more directly.
 *
 * Advantages of this algorithm: It never squares X or Y, so it never
 * overflows unless the answer does. It is very numerically stable. It
 * is very fast.
 *
 * This  code started life in MASM Assembley Language on a Univac. That
 * code was then ported to Fortran IV, on a Univac. That code was then
 * ported to C. That code was then ported to Ada. That code was then
 * used as the base of this port. SO.. it has a lot of inherited uglies.
 */

public class PythagoreanSum {

    /**
     * Calculate a Pythagorean sum
     *
     * @param x
     * @param y
     * @return sqrt(x*x + y*y), calculated directly
     */
    static public double sum(final double x, final double y) {
        final double delta_x = Math.abs(x);
        final double delta_y = Math.abs(y);
        double guess, errval;
        if (delta_x > delta_y) {
            guess = delta_x;
            errval = delta_y;
        } else {
            guess = delta_y;
            errval = delta_x;
        }
        // The following code is the loop unrolling of:
        // temp = error / guess;
        // r = temp * temp;
        // s = r / (r + 4.0);
        // guess += 2.0 * s * guess;
    // error *= s;
        // The loop is unrolled because checking for convergence takes
        // more time than the computation.
        // 1 iteration gives 1 significant digits in the result.
        // 2 iterations give 5 significant digits,
        // 3 iterations give 20 significant digits,
        // 4 iterations give 62 significant digits.
        // Etc. (The number of significant decimal digits roughly
        // triples with each iteration.)
        // The loop invariant is that SQRT(GUESS**2+ERROR**2) is the
        // Length with each iteration dramaticly shrinking ERROR.
        // After this we have one significant figure in the result
        double temp = errval / guess;
        double r = temp * temp;
        double s = r / (r + 4.0);
        guess += 2.0 * s * guess;
        // After this we have 6 significant digits in the result
        errval *= s;
        temp = errval / guess;
        r = temp * temp;
        s = r / (r + 4.0);
        guess += 2.0 * s * guess;
        // After this we have 20 significant digits in the result
        errval *= s;
        temp = errval / guess;
        r = temp * temp;
        s = r / (r + 4.0);
        guess += 2.0 * s * guess;
        return guess;
    }

    /**
     * Tester
     * @param args
     */
    public static void main(String[] args) {
        for (double i = 3.0, j = 4.0, k = 4.0;
            i < 1000.0; i += 2.0, j += 4.0, k += j) {
            System.out.println (i + '\t' + k + '\t' + sum(i, k));
        }
    }

}

Signature

John W. Kennedy
"The blind rulers of Logres
Nourished the land on a fallacy of rational virtue."
  -- Charles Williams.  "Taliessin through Logres: Prelude"

Eric Sosman - 17 Jan 2007 01:44 GMT
>>> What is the method of finding the square root of a number?
>>
[quoted text clipped - 4 lines]
> I read about that algorithm when I was 11. I've never seen a computer
> implementation of it.

    I did it once (in binary) for a integer square root routine.
A 256-place table of eight-bit approximations plus some scaling and
one or at most two Newton-Raphson iterations turned out to be faster,
though.

Signature

Eric Sosman
esosman@acm-dot-org.invalid



Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.