Get approximate square root

2018-07-01 01:34:39

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

}

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;
}

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 !

如果nextGuess的价值是100％肯定会下降并达到足够的价值，那么你不能这样做吗？

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));
}

链接地址: http://www.djcxy.com/p/86644.html

上一篇: 从void和boolean方法返回多个值

下一篇: 获取近似平方根