# HG changeset patch
# User bpb
# Date 1443818818 25200
#      Fri Oct 02 13:46:58 2015 -0700
# Node ID 4cdb5bc5c1800cde6be9ec579bf4d8d2f8b4ae7c
# Parent  391f8994fe9eea94f5f8543a7ca13be02cf9aafd
8032027: Add BigInteger square root methods
Summary: Add sqrt() and sqrtAndReminder() using Newton iteration
Reviewed-by: XXX

diff --git a/src/java.base/share/classes/java/math/BigInteger.java b/src/java.base/share/classes/java/math/BigInteger.java
--- a/src/java.base/share/classes/java/math/BigInteger.java
+++ b/src/java.base/share/classes/java/math/BigInteger.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1996, 2014, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1996, 2015, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -2410,6 +2410,68 @@
     }
 
     /**
+     * Implementation of the integer square root.
+     *
+     * @return the integer square root of this.
+     * @throws ArithmeticException if {@code this} is negative
+     * @since  1.9
+     */
+    private BigInteger implSqrt() {
+        if (this.signum < 0) {
+            throw new ArithmeticException("Negative BigInteger");
+        } else if (this.signum == 0) { // this is zero
+            return BigInteger.ZERO;
+        } else if (this.mag.length == 1 &&
+                   (this.mag[0] & LONG_MASK) < 4) { // result is unity
+            return BigInteger.ONE;
+        }
+
+        return new MutableBigInteger(this.mag).sqrt().toBigInteger();
+    }
+
+    /**
+     * Returns the integer square root of this BigInteger.  The integer square
+     * root of the corresponding mathematical integer {@code n} is the largest
+     * mathematical integer {@code s} such that {@code s*s <= n}.  It is equal
+     * to the value of {@code floor(sqrt(n))}, where {@code sqrt(n)} denotes the
+     * real square root of {@code n} treated as a real.  Note that the integer
+     * square root will be less than the real square root if the latter is not
+     * representable as an integral value.
+     *
+     * @return the integer square root of {@code this}
+     * @throws ArithmeticException if {@code this} is negative.  (The square
+     *         root of a negative integer {@code val} is
+     *         {@code (i * sqrt(-val))} where <i>i</i> is the
+     *         <i>imaginary unit</i> and is equal to
+     *         {@code sqrt(-1)}.)
+     * @since  1.9
+     */
+    public BigInteger sqrt() {
+        return implSqrt();
+    }
+
+    /**
+     * Returns an array of two BigIntegers containing the integer square root
+     * {@code s} of {@code this} and its remainder {@code this - s*s},
+     * respectively.
+     *
+     * @return an array of two BigIntegers with the integer square root at
+     *         offset 0 and the remainder at offset 1
+     * @throws ArithmeticException if {@code this} is negative.  (The square
+     *         root of a negative integer {@code val} is
+     *         {@code (i * sqrt(-val))} where <i>i</i> is the
+     *         <i>imaginary unit</i> and is equal to
+     *         {@code sqrt(-1)}.)
+     * @see #sqrt()
+     * @since  1.9
+     */
+    public BigInteger[] sqrtAndRemainder() {
+        BigInteger s = implSqrt();
+        BigInteger r = this.subtract(s.square());
+        return new BigInteger[] {s, r};
+    }
+
+    /**
      * Returns a BigInteger whose value is the greatest common divisor of
      * {@code abs(this)} and {@code abs(val)}.  Returns 0 if
      * {@code this == 0 && val == 0}.
diff --git a/src/java.base/share/classes/java/math/MutableBigInteger.java b/src/java.base/share/classes/java/math/MutableBigInteger.java
--- a/src/java.base/share/classes/java/math/MutableBigInteger.java
+++ b/src/java.base/share/classes/java/math/MutableBigInteger.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1999, 2015, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -1867,6 +1867,74 @@
     }
 
     /**
+     * Calculate the integer square root {@code floor(sqrt(this))} where
+     * {@code sqrt(.)} denotes the mathematical square root.  The contents of
+     * {@code this} are <b>not</b> changed.
+     *
+     * @implNote The implementation is based on the material in
+     * Henry S. Warren, Jr., <i>Hacker's Delight (2nd ed.)</i> (Addison
+     * Wesley, 2013), 279-282.
+     *
+     * @throws ArithmeticException if the value returned by {@code bitLength()}
+     * overflows the range of {@code int}.
+     * @return the integer square root of {@code this}
+     * @since  1.9
+     */
+    MutableBigInteger sqrt() {
+        // Obtain number of bits needed to represent the number.
+        int bitLength = (int)this.bitLength();
+        if (bitLength != this.bitLength()) {
+            throw new ArithmeticException("bitLength() integer overflow");
+        }
+
+        // Initial value length is one more than floor(bitLength()/2).
+        int initBits = bitLength / 2 + 1;
+
+        // The bit length of intermediate values will be no more than 2 bits
+        // larger than the initial bit length, so size the values accordingly
+        // to minimize allocations. The number of ints in the initial guess is
+        // (initBits + 2 + 31)/32.
+        int intLength = (initBits + 33) / 32;
+
+        // Fill the lower initBits bits of the value array with ones.  This
+        // should provide an initial estimate greater than or equal to the
+        // actual integer square root.
+        int[] val = new int[intLength];
+        int initInts = initBits / 32;
+        Arrays.fill(val, 0, initInts, -1);
+        int excessBits = initBits % 32;
+        if (excessBits != 0) {
+            val[initInts] =
+                (int)((0xffffffff & LONG_MASK) >>> (32 - excessBits));
+        }
+
+        // Create the initial estimate from the value array.
+        MutableBigInteger xk = new MutableBigInteger(val);
+
+        // Create intermediate and next value containers and the constant two.
+        MutableBigInteger tmp = new MutableBigInteger(new int[intLength]);
+        MutableBigInteger xk1 = new MutableBigInteger(new int[intLength]);
+        MutableBigInteger two = new MutableBigInteger(2);
+
+        do {
+            // xk1 = (xk + n/xk)/2
+            this.divide(xk, tmp, false);
+            tmp.add(xk);
+            tmp.divide(two, xk1, false);
+
+            if (xk1.compare(xk) >= 0) {
+                return xk;
+            }
+
+            // xk = xk1
+            xk.copyValue(xk1);
+
+            xk1.reset();
+            tmp.reset();
+        } while (true);
+    }
+
+    /**
      * Calculate GCD of this and b. This and b are changed by the computation.
      */
     MutableBigInteger hybridGCD(MutableBigInteger b) {
diff --git a/test/java/math/BigInteger/BigIntegerTest.java b/test/java/math/BigInteger/BigIntegerTest.java
--- a/test/java/math/BigInteger/BigIntegerTest.java
+++ b/test/java/math/BigInteger/BigIntegerTest.java
@@ -26,7 +26,7 @@
  * @library /lib/testlibrary/
  * @build jdk.testlibrary.*
  * @run main BigIntegerTest
- * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 4026465 8074460 8078672
+ * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 4026465 8074460 8078672 8032027
  * @summary tests methods in BigInteger (use -Dseed=X to set PRNG seed)
  * @run main/timeout=400 BigIntegerTest
  * @author madbot
@@ -38,8 +38,12 @@
 import java.io.FileOutputStream;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
+import java.math.BigDecimal;
 import java.math.BigInteger;
 import java.util.Random;
+import java.util.stream.DoubleStream;
+import java.util.stream.IntStream;
+import java.util.stream.LongStream;
 import jdk.testlibrary.RandomFactory;
 
 /**
@@ -243,6 +247,173 @@
         report("square for " + order + " bits", failCount1);
     }
 
+    private static void fail(String msg) {
+        System.err.println(msg);
+        failure = true;
+    }
+
+    private static void fail(String msg, Object expected, Object actual) {
+        System.err.println(msg + " - expected: " + expected + ", actual: " + actual);
+        failure = true;
+    }
+
+    private static void squareRootSmall() {
+        // A negative value should cause an exception.
+        BigInteger n = BigInteger.ONE.negate();
+        BigInteger s;
+        try {
+            s = n.sqrt();
+            // If sqrt() does not throw an exception that is a failure.
+            fail("sqrt() of negative number did not throw an exception");
+        } catch (ArithmeticException expected) {
+            // A negative value should cause an exception and is not a failure.
+        }
+
+        // A zero value should return BigInteger.ZERO.
+        if (!BigInteger.valueOf(0).sqrt().equals(BigInteger.ZERO)) {
+            fail("sqrt(0) != BigInteger.ZERO");
+        }
+
+        // 1 <= value < 4 should return BigInteger.ONE.
+        long[] smalls = new long[] {1, 2, 3};
+        for (long small : smalls) {
+            if (!BigInteger.valueOf(small).sqrt().equals(BigInteger.ONE)) {
+                fail("sqrt("+small+") != 1");
+            }
+        }
+    }
+
+    private static void squareRootInt() {
+        IntStream ints = random.ints(SIZE, 4, Integer.MAX_VALUE);
+        ints.forEach(i -> {
+            BigInteger n = BigInteger.valueOf(i);
+            BigInteger n2 = n.pow(2);
+
+            // square root of n^2 -> n
+            BigInteger actual = n2.sqrt();
+            if (actual.compareTo(n) != 0) {
+                fail("sqrt(int)", n, actual);
+            }
+
+            // square root of n^2 + 1 -> n
+            BigInteger n2up = n2.add(BigInteger.ONE);
+            actual = n2up.sqrt();
+            if (actual.compareTo(n) != 0) {
+                fail("sqrt(int)", n, actual);
+            }
+
+            // square root of (n + 1)^2 - 1 -> n
+            BigInteger up = n.add(BigInteger.ONE).pow(2).subtract(BigInteger.ONE);
+            actual = up.sqrt();
+            if (actual.compareTo(n) != 0) {
+                fail("sqrt(int)", n, actual);
+            }
+        });
+    }
+
+    private static void squareRootLong() {
+        LongStream longs = random.longs(SIZE, (long)Integer.MAX_VALUE + 1L,
+            Long.MAX_VALUE);
+        longs.forEach(i -> {
+            BigInteger n = BigInteger.valueOf(i);
+            BigInteger n2 = n.pow(2);
+
+            // square root of n^2 -> n
+            BigInteger actual = n2.sqrt();
+            if (actual.compareTo(n) != 0) {
+                fail("sqrt(long)", n, actual);
+            }
+
+            // square root of n^2 + 1 -> n
+            BigInteger n2up = n2.add(BigInteger.ONE);
+            actual = n2up.sqrt();
+            if (actual.compareTo(n) != 0) {
+                fail("sqrt(long)", n, actual);
+            }
+
+            // square root of (n + 1)^2 - 1 -> n
+            BigInteger up = n.add(BigInteger.ONE).pow(2).subtract(BigInteger.ONE);
+            actual = up.sqrt();
+            if (actual.compareTo(n) != 0) {
+                fail("sqrt(long)", n, actual);
+            }
+        });
+    }
+
+    private static void squareRootDouble() {
+        DoubleStream doubles = random.doubles(SIZE,
+                (double)Long.MAX_VALUE + 1.0, Math.sqrt(Double.MAX_VALUE));
+        doubles.forEach(i -> {
+            BigInteger n = BigDecimal.valueOf(i).toBigInteger();
+            BigInteger n2 = n.pow(2);
+
+            // square root of n^2 -> n
+            BigInteger actual = n2.sqrt();
+            if (actual.compareTo(n) != 0) {
+                fail("sqrt(double)", n, actual);
+            }
+
+            // square root of n^2 + 1 -> n
+            BigInteger n2up = n2.add(BigInteger.ONE);
+            actual = n2up.sqrt();
+            if (actual.compareTo(n) != 0) {
+                fail("sqrt(double)", n, actual);
+            }
+
+            // square root of (n + 1)^2 - 1 -> n
+            BigInteger up = n.add(BigInteger.ONE).pow(2).subtract(BigInteger.ONE);
+            actual = up.sqrt();
+            if (actual.compareTo(n) != 0) {
+                fail("sqrt(double)", n, actual);
+            }
+        });
+    }
+
+    public static void squareRoot() {
+        squareRootSmall();
+        squareRootInt();
+        squareRootLong();
+        squareRootDouble();
+    }
+
+    public static void squareRootAndRemainder() {
+        IntStream bits = random.ints(SIZE, 3, Short.MAX_VALUE);
+        bits.forEach(i -> {
+            BigInteger n = new BigInteger(i, random);
+            BigInteger n2 = n.pow(2);
+
+            // square root of n^2 -> n
+            BigInteger[] actual = n2.sqrtAndRemainder();
+            if (actual[0].compareTo(n) != 0) {
+                fail("sqrtAndRemainder()[0]", n, actual[0]);
+            }
+            if (actual[1].compareTo(BigInteger.ZERO) != 0) {
+                fail("sqrtAndRemainder()[1]", BigInteger.ZERO, actual[1]);
+            }
+
+            // square root of n^2 + 1 -> n
+            BigInteger n2up = n2.add(BigInteger.ONE);
+            actual = n2up.sqrtAndRemainder();
+            if (actual[0].compareTo(n) != 0) {
+                fail("sqrtAndRemainder()[0]", n, actual[0]);
+            }
+            if (actual[1].compareTo(BigInteger.ONE) != 0) {
+                fail("sqrtAndRemainder()[1]", BigInteger.ONE, actual[1]);
+            }
+
+            // square root of (n + 1)^2 - 1 -> n
+            BigInteger up = n.add(BigInteger.ONE).pow(2).subtract(BigInteger.ONE);
+            actual = up.sqrtAndRemainder();
+            if (actual[0].compareTo(n) != 0) {
+                fail("sqrt(int)", n, actual[0]);
+            }
+            BigInteger r = up.subtract(n2);
+            if (actual[1].compareTo(r) != 0) {
+                fail("sqrtAndRemainder()[1]", r, actual[1]);
+            }
+        });
+    }
+
     public static void arithmetic(int order) {
         int failCount = 0;
 
@@ -1101,6 +1272,9 @@
         square(ORDER_KARATSUBA_SQUARE);
         square(ORDER_TOOM_COOK_SQUARE);
 
+        squareRoot();
+        squareRootAndRemainder();
+
         bitCount();
         bitLength();
         bitOps(order1);