3

I want to calculate square root of a big decimal in my application. Please don't suggest some third party utilities since i can't go in the loop of licencing. I have been using Newton-Raphson Method but since it uses pow and divide operation heavily. I can see it slowing down my application in profiler. Can you guys suggest me some good implementation for this? Either there can be some different algorithm than Newton-Raphson or may be if not then some faster implementation of it using bitwise operation.

Naman
  • 2,569
  • 4
  • 27
  • 44
  • The quadratic convergence of the newton method is hard to beat. Just make sure, you start with a good initial estimate of the square root. The square root calculated with double precision may be a good start. – Henry Jan 20 '14 at 08:34
  • @Naman For what are using pow function ? – Vikram Bhat Jan 20 '14 at 08:48
  • @VikramBhat I was using this implementation http://stackoverflow.com/questions/13649703/square-root-of-bigdecimal-in-java – Naman Jan 20 '14 at 10:58
  • 1
    @Naman do really need big decimal because big decimal is usually slower to primitive data types – Vikram Bhat Jan 20 '14 at 11:10
  • @Naman Prevent the recursive implementation as given in the answer but use iterative one because it takes a lot of stack space and slows down the speed. – Vikram Bhat Jan 20 '14 at 11:13
  • 1
    @Naman Use multiply instead of Pow(2) – Vikram Bhat Jan 20 '14 at 11:19
  • Newton Raphson for square roots is equivalent to the divide and average method, which may be simpler to implement (and involves one division, one add, and then one division by two). – Teepeemm Jan 20 '14 at 13:20
  • To compute square roots rapidly, one usually computes via the reciprocal square root, for which division-free iterations are readily available. Iterative schemes with cubic and higher convergence are well known (cubic is usually sufficient for double precision computation), see for example: http://numbers.computation.free.fr/Constants/Algorithms/inverse – njuffa Jan 20 '14 at 20:34
  • @njuffa This sounds interesting. I'll check the link, also if you can provide some more insight for implementation that would be great. – Naman Jan 21 '14 at 04:53
  • @Naman: Sorry, I am not familiar with Java or BigDecimal. You may want to re-arrange the arithmetic for the iterations in a manner most suitable for the native API. Except for zero and infinity, sqrt(x) = x * rsqrt(x). – njuffa Jan 21 '14 at 06:53

1 Answers1

0

You can use binary search to find square root. Something like that:

BigDecimal sqrt(BigDecimal a){
    BigDecimal left = BigDecimal.ZERO;
    BigDecimal right = a;

    for (int i = 0; i < BINARY_SEARCH_ITER_COUNT; ++i) {
        BigDecimal middle = left.add(right).divide(BigDecimal.valueOf(2));

        if (middle.multiply(middle).compareTo(a) < 0) {
            left = middle;
        } else {
            right = middle;
        }
    }

    return left.add(right).divide(BigDecimal.valueOf(2));
}

You can tune the number of iterations to match your precision and exectuion time requrements. But I don't know how this works in comparison with Newton-Raphson.

Fefer_Ivan
  • 116
  • 6