1 /*
2 * Copyright (c) 1999, 2013, 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
1850 }
1851
1852 // Approximate the quotient and remainder
1853 q = (n >>> 1) / (dLong >>> 1);
1854 r = n - q*dLong;
1855
1856 // Correct the approximation
1857 while (r < 0) {
1858 r += dLong;
1859 q--;
1860 }
1861 while (r >= dLong) {
1862 r -= dLong;
1863 q++;
1864 }
1865 // n - q*dlong == r && 0 <= r <dLong, hence we're done.
1866 return (r << 32) | (q & LONG_MASK);
1867 }
1868
1869 /**
1870 * Calculate GCD of this and b. This and b are changed by the computation.
1871 */
1872 MutableBigInteger hybridGCD(MutableBigInteger b) {
1873 // Use Euclid's algorithm until the numbers are approximately the
1874 // same length, then use the binary GCD algorithm to find the GCD.
1875 MutableBigInteger a = this;
1876 MutableBigInteger q = new MutableBigInteger();
1877
1878 while (b.intLen != 0) {
1879 if (Math.abs(a.intLen - b.intLen) < 2)
1880 return a.binaryGCD(b);
1881
1882 MutableBigInteger r = a.divide(b, q);
1883 a = b;
1884 b = r;
1885 }
1886 return a;
1887 }
1888
1889 /**
|
1 /*
2 * Copyright (c) 1999, 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
1850 }
1851
1852 // Approximate the quotient and remainder
1853 q = (n >>> 1) / (dLong >>> 1);
1854 r = n - q*dLong;
1855
1856 // Correct the approximation
1857 while (r < 0) {
1858 r += dLong;
1859 q--;
1860 }
1861 while (r >= dLong) {
1862 r -= dLong;
1863 q++;
1864 }
1865 // n - q*dlong == r && 0 <= r <dLong, hence we're done.
1866 return (r << 32) | (q & LONG_MASK);
1867 }
1868
1869 /**
1870 * Calculate the integer square root {@code floor(sqrt(this))} where
1871 * {@code sqrt(.)} denotes the mathematical square root. The contents of
1872 * {@code this} are <b>not</b> changed.
1873 *
1874 * @implNote The implementation is based on the material in
1875 * Henry S. Warren, Jr., <i>Hacker's Delight (2nd ed.)</i> (Addison
1876 * Wesley, 2013), 279-282.
1877 *
1878 * @throws ArithmeticException if the value returned by {@code bitLength()}
1879 * overflows the range of {@code int}.
1880 * @return the integer square root of {@code this}
1881 * @since 1.9
1882 */
1883 MutableBigInteger sqrt() {
1884 // Obtain number of bits needed to represent the number.
1885 int bitLength = (int)this.bitLength();
1886 if (bitLength != this.bitLength()) {
1887 throw new ArithmeticException("bitLength() integer overflow");
1888 }
1889
1890 // Initial value length is one more than floor(bitLength()/2).
1891 int initBits = bitLength / 2 + 1;
1892
1893 // The bit length of intermediate values will be no more than 2 bits
1894 // larger than the initial bit length, so size the values accordingly
1895 // to minimize allocations. The number of ints in the initial guess is
1896 // (initBits + 2 + 31)/32.
1897 int intLength = (initBits + 33) / 32;
1898
1899 // Fill the lower initBits bits of the value array with ones. This
1900 // should provide an initial estimate greater than or equal to the
1901 // actual integer square root.
1902 int[] val = new int[intLength];
1903 int initInts = initBits / 32;
1904 Arrays.fill(val, 0, initInts, -1);
1905 int excessBits = initBits % 32;
1906 if (excessBits != 0) {
1907 val[initInts] =
1908 (int)((0xffffffff & LONG_MASK) >>> (32 - excessBits));
1909 }
1910
1911 // Create the initial estimate from the value array.
1912 MutableBigInteger xk = new MutableBigInteger(val);
1913
1914 // Create intermediate and next value containers and the constant two.
1915 MutableBigInteger tmp = new MutableBigInteger(new int[intLength]);
1916 MutableBigInteger xk1 = new MutableBigInteger(new int[intLength]);
1917 MutableBigInteger two = new MutableBigInteger(2);
1918
1919 do {
1920 // xk1 = (xk + n/xk)/2
1921 this.divide(xk, tmp, false);
1922 tmp.add(xk);
1923 tmp.divide(two, xk1, false);
1924
1925 if (xk1.compare(xk) >= 0) {
1926 return xk;
1927 }
1928
1929 // xk = xk1
1930 xk.copyValue(xk1);
1931
1932 xk1.reset();
1933 tmp.reset();
1934 } while (true);
1935 }
1936
1937 /**
1938 * Calculate GCD of this and b. This and b are changed by the computation.
1939 */
1940 MutableBigInteger hybridGCD(MutableBigInteger b) {
1941 // Use Euclid's algorithm until the numbers are approximately the
1942 // same length, then use the binary GCD algorithm to find the GCD.
1943 MutableBigInteger a = this;
1944 MutableBigInteger q = new MutableBigInteger();
1945
1946 while (b.intLen != 0) {
1947 if (Math.abs(a.intLen - b.intLen) < 2)
1948 return a.binaryGCD(b);
1949
1950 MutableBigInteger r = a.divide(b, q);
1951 a = b;
1952 b = r;
1953 }
1954 return a;
1955 }
1956
1957 /**
|