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 /*
   2  * Copyright (c) 1996, 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any


2393 
2394                 if ((workingExponent >>>= 1) != 0) {
2395                     partToSquare = partToSquare.square();
2396                 }
2397             }
2398             // Multiply back the (exponentiated) powers of two (quickly,
2399             // by shifting left)
2400             if (powersOfTwo > 0) {
2401                 answer = answer.shiftLeft(powersOfTwo*exponent);
2402             }
2403 
2404             if (signum < 0 && (exponent&1) == 1) {
2405                 return answer.negate();
2406             } else {
2407                 return answer;
2408             }
2409         }
2410     }
2411 
2412     /**






























































2413      * Returns a BigInteger whose value is the greatest common divisor of
2414      * {@code abs(this)} and {@code abs(val)}.  Returns 0 if
2415      * {@code this == 0 && val == 0}.
2416      *
2417      * @param  val value with which the GCD is to be computed.
2418      * @return {@code GCD(abs(this), abs(val))}
2419      */
2420     public BigInteger gcd(BigInteger val) {
2421         if (val.signum == 0)
2422             return this.abs();
2423         else if (this.signum == 0)
2424             return val.abs();
2425 
2426         MutableBigInteger a = new MutableBigInteger(this);
2427         MutableBigInteger b = new MutableBigInteger(val);
2428 
2429         MutableBigInteger result = a.hybridGCD(b);
2430 
2431         return result.toBigInteger(1);
2432     }


   1 /*
   2  * Copyright (c) 1996, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any


2393 
2394                 if ((workingExponent >>>= 1) != 0) {
2395                     partToSquare = partToSquare.square();
2396                 }
2397             }
2398             // Multiply back the (exponentiated) powers of two (quickly,
2399             // by shifting left)
2400             if (powersOfTwo > 0) {
2401                 answer = answer.shiftLeft(powersOfTwo*exponent);
2402             }
2403 
2404             if (signum < 0 && (exponent&1) == 1) {
2405                 return answer.negate();
2406             } else {
2407                 return answer;
2408             }
2409         }
2410     }
2411 
2412     /**
2413      * Implementation of the integer square root.
2414      *
2415      * @return the integer square root of this.
2416      * @throws ArithmeticException if {@code this} is negative
2417      * @since  1.9
2418      */
2419     private BigInteger implSqrt() {
2420         if (this.signum < 0) {
2421             throw new ArithmeticException("Negative BigInteger");
2422         } else if (this.signum == 0) { // this is zero
2423             return BigInteger.ZERO;
2424         } else if (this.mag.length == 1 &&
2425                    (this.mag[0] & LONG_MASK) < 4) { // result is unity
2426             return BigInteger.ONE;
2427         }
2428 
2429         return new MutableBigInteger(this.mag).sqrt().toBigInteger();
2430     }
2431 
2432     /**
2433      * Returns the integer square root of this BigInteger.  The integer square
2434      * root of the corresponding mathematical integer {@code n} is the largest
2435      * mathematical integer {@code s} such that {@code s*s <= n}.  It is equal
2436      * to the value of {@code floor(sqrt(n))}, where {@code sqrt(n)} denotes the
2437      * real square root of {@code n} treated as a real.  Note that the integer
2438      * square root will be less than the real square root if the latter is not
2439      * representable as an integral value.
2440      *
2441      * @return the integer square root of {@code this}
2442      * @throws ArithmeticException if {@code this} is negative.  (The square
2443      *         root of a negative integer {@code val} is
2444      *         {@code (i * sqrt(-val))} where <i>i</i> is the
2445      *         <i>imaginary unit</i> and is equal to
2446      *         {@code sqrt(-1)}.)
2447      * @since  1.9
2448      */
2449     public BigInteger sqrt() {
2450         return implSqrt();
2451     }
2452 
2453     /**
2454      * Returns an array of two BigIntegers containing the integer square root
2455      * {@code s} of {@code this} and its remainder {@code this - s*s},
2456      * respectively.
2457      *
2458      * @return an array of two BigIntegers with the integer square root at
2459      *         offset 0 and the remainder at offset 1
2460      * @throws ArithmeticException if {@code this} is negative.  (The square
2461      *         root of a negative integer {@code val} is
2462      *         {@code (i * sqrt(-val))} where <i>i</i> is the
2463      *         <i>imaginary unit</i> and is equal to
2464      *         {@code sqrt(-1)}.)
2465      * @see #sqrt()
2466      * @since  1.9
2467      */
2468     public BigInteger[] sqrtAndRemainder() {
2469         BigInteger s = implSqrt();
2470         BigInteger r = this.subtract(s.square());
2471         return new BigInteger[] {s, r};
2472     }
2473 
2474     /**
2475      * Returns a BigInteger whose value is the greatest common divisor of
2476      * {@code abs(this)} and {@code abs(val)}.  Returns 0 if
2477      * {@code this == 0 && val == 0}.
2478      *
2479      * @param  val value with which the GCD is to be computed.
2480      * @return {@code GCD(abs(this), abs(val))}
2481      */
2482     public BigInteger gcd(BigInteger val) {
2483         if (val.signum == 0)
2484             return this.abs();
2485         else if (this.signum == 0)
2486             return val.abs();
2487 
2488         MutableBigInteger a = new MutableBigInteger(this);
2489         MutableBigInteger b = new MutableBigInteger(val);
2490 
2491         MutableBigInteger result = a.hybridGCD(b);
2492 
2493         return result.toBigInteger(1);
2494     }