ArbitraryPrecisionSqrt.java

Below is the syntax highlighted version of ArbitraryPrecisionSqrt.java from §9.2 Floating Point.

/******************************************************************************
 *  Compilation:  javac ArbitraryPrecisionSqrt.java
 *  Execution:    java ArbitraryPrecisionSqrt x n
 *
 *  Computer the square of an integer with n digits of precision,
 *  using Newton's method.
 *
 *  % java ArbitraryPrecisionSqrt 2 50
 *  1.4142135623730950488016887242096980785696718753769
 *
 *  % java ArbitraryPrecisionSqrt 100 50
 *  10.000000000000000000000000000000000000000000000000
 *
 *  % java ArbitraryPrecisionSqrt 5 1000000
 *  2.2360679774997896964091736...026774457574830645269
 *
 ******************************************************************************/


import java.math.BigInteger;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.math.MathContext;

public class ArbitraryPrecisionSqrt {
    private static final BigDecimal TWO = new BigDecimal(2);

    // Reference: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots
    public static BigDecimal sqrt(int x, int n) {
        if (x <= 0) throw new IllegalArgumentException("x must be a positive integer: " + x);
        if (n <= 0) throw new IllegalArgumentException("n must be a positive integer: " + n);

        // initial estimate (find smallest power of 2 >= sqrt(x))
        int initial = 1;
        while (initial*initial < x) {
            initial *= 2;
        }

        // 1 + lg(n) iterations of Newton's method
        // (1 iteration needed to get 1 decimal digit of precision; each subsequent
        //  iteration at least doubles the number of significant digits)
        BigDecimal t = new BigDecimal(initial);
        BigDecimal c = new BigDecimal(x);
        for (int precision = 1; precision <= 2*n; precision *= 2) {
            MathContext context = new MathContext(1 + 2*precision, RoundingMode.HALF_EVEN);
            t = c.divide(t, context).add(t).divide(TWO, context);
        }
        return t.round(new MathContext(n, RoundingMode.HALF_EVEN));
    }

    public static void main(String[] args) {
        int x = Integer.parseInt(args[0]);
        int n = Integer.parseInt(args[1]);
        BigDecimal result = sqrt(x, n);
        StdOut.println(result);
    }
}