< prev index next >
test/java/math/BigInteger/BigIntegerTest.java
Print this page
rev 12854 : 8032027: Add BigInteger square root methods
Summary: Add sqrt() and sqrtAndReminder() using Newton iteration
Reviewed-by: XXX
@@ -24,11 +24,11 @@
/*
* @test
* @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
* @key randomness
*/
@@ -36,12 +36,16 @@
import java.io.File;
import java.io.FileInputStream;
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;
/**
* This is a simple test class created to ensure that the results
* generated by BigInteger adhere to certain identities. Passing
@@ -241,10 +245,177 @@
failCount1++;
}
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("sqrtAndRemainder()[0]", 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;
for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(order);
@@ -1099,10 +1270,13 @@
square(ORDER_MEDIUM);
square(ORDER_KARATSUBA_SQUARE);
square(ORDER_TOOM_COOK_SQUARE);
+ squareRoot();
+ squareRootAndRemainder();
+
bitCount();
bitLength();
bitOps(order1);
bitwise(order1);
< prev index next >