src/java.base/share/classes/java/math/BigInteger.java

Print this page
rev 12826 : 8032027: Add BigInteger square root methods
Summary: Add sqrt() and sqrtAndReminder() using Newton iteration
Reviewed-by: XXX

*** 1,7 **** /* ! * Copyright (c) 1996, 2014, 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 * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this --- 1,7 ---- /* ! * 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 * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this
*** 2408,2417 **** --- 2408,2479 ---- } } } /** + * 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}. * * @param val value with which the GCD is to be computed.