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

```
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 /** |