CODEWITHSUNDEEP
javaalgorithmmathsqrtmath.sqrt
user7664681
user7664681

Reputation:

Get approximate square root

I'm implementing Babylonian method to approximate the square root of number n using following formula :

nextGuess = (lastGuess + n / lastGuess) / 2;

So when nextGuess and lasGuess are almost identical, nextGuess is the approximated square root.

What am doing is checking if nextGuess and lastGuess is less than very small number such as 0.0001 then i can claim that nextGuess is the approximated square root of n. if not nextGuess become lastGuess.

So how i can implement that in the right way?

My current code:

public static void getApproximatedSquare(long n){
    DecimalFormat decimalFormat = new DecimalFormat("#.####");
    decimalFormat.setRoundingMode(RoundingMode.CEILING);

    double lastGuess = 1, nextGuess;

    nextGuess = (lastGuess + n / lastGuess) / 2;
    Double init =  0.0001;
    System.out.println(decimalFormat.format(init));
    if (Double.valueOf(decimalFormat.format(nextGuess)) <= init)
        //todo

}

Upvotes: 0

Views: 2293

Answers (4)

user1196549
user1196549

Reputation:

Using an absolute tolerance is always a bad idea because it doesn't take into account the order of magnitude of the argument. A relative error is better.

But in the case of the square root, I recommend a much better approach: make sure that your initial approximation is within a factor √2 of the exact root. This is obtained by halving the exponent of 2 in the floating-point representation of the argument. (If you can't access this exponent, you can obtain it by successive divisions or multiplications until to reach the interval [1, 2).)

Example: for 27, you have 16 ≤ 27 < 32. Then 1 ≤ √27 / 4 < √2, and you can start the iterations from 4.

Then perform four iterations of the Babylonian formula. No less, no more.

In the example, after four iterations, you obtain 5.19615242271, which is exact.

If you have the feeling that the successive halving or doubling process is slow and believe that Newton is faster, consider that (x + n / x) / 2 > x / 2, so that Newton actually converges slower than halvings and involves more arithmetic !

Upvotes: 1

Nepho
Nepho

Reputation: 1112

If nextGuess's value is 100% sure to go down and reach a good enough value, can't you just do this?

public static void getApproximatedSquare(long n){
    DecimalFormat decimalFormat = new DecimalFormat("#.####");
    decimalFormat.setRoundingMode(RoundingMode.CEILING);

    double lastGuess = n + 1;
    double nextGuess = n;
    double init      = 0.0001;

    while (lastGuess - nextGuess > init)
    {
        lastGuess = nextGuess;
        nextGuess = (lastGuess + n / lastGuess) / 2;
    }

    System.out.println(decimalFormat.format(init));
}

Upvotes: 0

Damiano
Damiano

Reputation: 811

Current draft of implementation has a few flaws:

  • I doubt you really need Double.valueOf(decimalFormat.format(...)), it just removes some precision from the result
  • Your convergence condition is not nextGuess < init but difference_between_nextGuess_and_lastGuess < init
  • You have to repeat the approximation until convergence, so you can't use just a if. You need a for or while or (as in my solution) do... while

  • This should work (at each step, it prints last and next guesses)

    public static double getApproximatedSquare(long n) {
    DecimalFormat decimalFormat = new DecimalFormat("#.####");
    decimalFormat.setRoundingMode(RoundingMode.CEILING);

    double lastGuess, nextGuess = 1;
    double init = 0.0001;
    do {
        lastGuess = nextGuess;
        nextGuess = (lastGuess + (double) n / lastGuess) / 2;
        System.out.println(decimalFormat.format(lastGuess)+" ---> "+decimalFormat.format(nextGuess));
    } while (Math.abs(lastGuess - nextGuess) >= init);
    return nextGuess;
}

Upvotes: 4

Felk
Felk

Reputation: 8224

As nextGuess approaches sqrt(n) from above, you can use this:

double lastGuess = n;
double nextGuess = n;
double epsilon = 1e-4;
while (lastGuess - nextGuess > epsilon) {
    lastGuess = nextGuess;
    nextGuess = (lastGuess + n / lastGuess) / 2;
}

Upvotes: -1

Related Questions