0

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 }
Improve this question
2
  • What answer would you expect for getApproximatedSquare(4611685984067649600L)? Commented Oct 13, 2017 at 16:06
  • @JamesKPolk that's why i'm using DecimalFormat the result would be 2147483640 and that's approximation value for your number. Commented Oct 13, 2017 at 16:10

4 Answers 4

Reset to default
4

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; }
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

it would be a perfect one if the nextGuess square is really equal to n, how i can make it exactly the same ?
1

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 !

Improve this answer

2 Comments

Because the argument is a long rather than a double or float, it's a little more complicated.
@JamesKPolk: the OP is using doubles for intermediate computation, so the input type does not matter. (By the way, the Babylonian method works equally well with pure integer arithmetic and maybe 3 iterations are enough.)
0

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)); }
Improve this answer

2 Comments

Why should nextGuess, the approximation, ever reach 0.0001 for every input number n? Did you mean something like while (|nextguess² - n| > init)?
Woops, looks like I made a mistake. Correcting it right now
-1

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; }
Improve this answer

Comments