< prev index next >

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

```8247782: typos in java.math
 ``` ``````2734 BigInteger result; 2735 if (m.testBit(0)) { // odd modulus 2736 result = base.oddModPow(exponent, m); 2737 } else { 2738 /* 2739 * Even modulus. Tear it into an "odd part" (m1) and power of two 2740 * (m2), exponentiate mod m1, manually exponentiate mod m2, and 2741 * use Chinese Remainder Theorem to combine results. 2742 */ 2743 2744 // Tear m apart into odd part (m1) and power of 2 (m2) 2745 int p = m.getLowestSetBit(); // Max pow of 2 that divides m 2746 2747 BigInteger m1 = m.shiftRight(p); // m/2**p 2748 BigInteger m2 = ONE.shiftLeft(p); // 2**p 2749 2750 // Calculate new base from m1 2751 BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0 2752 ? this.mod(m1) : this); 2753 2754 // Caculate (base ** exponent) mod m1. 2755 BigInteger a1 = (m1.equals(ONE) ? ZERO : 2756 base2.oddModPow(exponent, m1)); 2757 2758 // Calculate (this ** exponent) mod m2 2759 BigInteger a2 = base.modPow2(exponent, p); 2760 2761 // Combine results using Chinese Remainder Theorem 2762 BigInteger y1 = m2.modInverse(m1); 2763 BigInteger y2 = m1.modInverse(m2); 2764 2765 if (m.mag.length < MAX_MAG_LENGTH / 2) { 2766 result = a1.multiply(m2).multiply(y1).add(a2.multiply(m1).multiply(y2)).mod(m); 2767 } else { 2768 MutableBigInteger t1 = new MutableBigInteger(); 2769 new MutableBigInteger(a1.multiply(m2)).multiply(new MutableBigInteger(y1), t1); 2770 MutableBigInteger t2 = new MutableBigInteger(); 2771 new MutableBigInteger(a2.multiply(m1)).multiply(new MutableBigInteger(y2), t2); 2772 t1.add(t2); 2773 MutableBigInteger q = new MutableBigInteger(); 2774 result = t1.divide(new MutableBigInteger(m), q).toBigInteger(); ``````2888 * end of the exponent is unimportant, but it is filled with zero here.) 2889 * When the most-significant bit of this buffer becomes set, i.e. 2890 * (buf & tblmask) != 0, we have to decide what pattern to multiply 2891 * by, and when to do it. We decide, remember to do it in future 2892 * after a suitable number of squarings have passed (e.g. a pattern 2893 * of "100" in the buffer requires that we multiply by n^1 immediately; 2894 * a pattern of "110" calls for multiplying by n^3 after one more 2895 * squaring), clear the buffer, and continue. 2896 * 2897 * When we start, there is one more optimization: the result buffer 2898 * is implcitly one, so squaring it or multiplying by it can be 2899 * optimized away. Further, if we start with a pattern like "100" 2900 * in the lookahead window, rather than placing n into the buffer 2901 * and then starting to square it, we have already computed n^2 2902 * to compute the odd-powers table, so we can place that into 2903 * the buffer and save a squaring. 2904 * 2905 * This means that if you have a k-bit window, to compute n^z, 2906 * where z is the high k bits of the exponent, 1/2 of the time 2907 * it requires no squarings. 1/4 of the time, it requires 1 2908 * squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings. 2909 * And the remaining 1/2^(k-1) of the time, the top k bits are a 2910 * 1 followed by k-1 0 bits, so it again only requires k-2 2911 * squarings, not k-1. The average of these is 1. Add that 2912 * to the one squaring we have to do to compute the table, 2913 * and you'll see that a k-bit window saves k-2 squarings 2914 * as well as reducing the multiplies. (It actually doesn't 2915 * hurt in the case k = 1, either.) 2916 */ 2917 // Special case for exponent of one 2918 if (y.equals(ONE)) 2919 return this; 2920 2921 // Special case for base of zero 2922 if (signum == 0) 2923 return ZERO; 2924 2925 int[] base = mag.clone(); 2926 int[] exp = y.mag; 2927 int[] mod = z.mag; 2928 int modLen = mod.length; ``` ``` ``````2734 BigInteger result; 2735 if (m.testBit(0)) { // odd modulus 2736 result = base.oddModPow(exponent, m); 2737 } else { 2738 /* 2739 * Even modulus. Tear it into an "odd part" (m1) and power of two 2740 * (m2), exponentiate mod m1, manually exponentiate mod m2, and 2741 * use Chinese Remainder Theorem to combine results. 2742 */ 2743 2744 // Tear m apart into odd part (m1) and power of 2 (m2) 2745 int p = m.getLowestSetBit(); // Max pow of 2 that divides m 2746 2747 BigInteger m1 = m.shiftRight(p); // m/2**p 2748 BigInteger m2 = ONE.shiftLeft(p); // 2**p 2749 2750 // Calculate new base from m1 2751 BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0 2752 ? this.mod(m1) : this); 2753 2754 // Calculate (base ** exponent) mod m1. 2755 BigInteger a1 = (m1.equals(ONE) ? ZERO : 2756 base2.oddModPow(exponent, m1)); 2757 2758 // Calculate (this ** exponent) mod m2 2759 BigInteger a2 = base.modPow2(exponent, p); 2760 2761 // Combine results using Chinese Remainder Theorem 2762 BigInteger y1 = m2.modInverse(m1); 2763 BigInteger y2 = m1.modInverse(m2); 2764 2765 if (m.mag.length < MAX_MAG_LENGTH / 2) { 2766 result = a1.multiply(m2).multiply(y1).add(a2.multiply(m1).multiply(y2)).mod(m); 2767 } else { 2768 MutableBigInteger t1 = new MutableBigInteger(); 2769 new MutableBigInteger(a1.multiply(m2)).multiply(new MutableBigInteger(y1), t1); 2770 MutableBigInteger t2 = new MutableBigInteger(); 2771 new MutableBigInteger(a2.multiply(m1)).multiply(new MutableBigInteger(y2), t2); 2772 t1.add(t2); 2773 MutableBigInteger q = new MutableBigInteger(); 2774 result = t1.divide(new MutableBigInteger(m), q).toBigInteger(); ``````2888 * end of the exponent is unimportant, but it is filled with zero here.) 2889 * When the most-significant bit of this buffer becomes set, i.e. 2890 * (buf & tblmask) != 0, we have to decide what pattern to multiply 2891 * by, and when to do it. We decide, remember to do it in future 2892 * after a suitable number of squarings have passed (e.g. a pattern 2893 * of "100" in the buffer requires that we multiply by n^1 immediately; 2894 * a pattern of "110" calls for multiplying by n^3 after one more 2895 * squaring), clear the buffer, and continue. 2896 * 2897 * When we start, there is one more optimization: the result buffer 2898 * is implcitly one, so squaring it or multiplying by it can be 2899 * optimized away. Further, if we start with a pattern like "100" 2900 * in the lookahead window, rather than placing n into the buffer 2901 * and then starting to square it, we have already computed n^2 2902 * to compute the odd-powers table, so we can place that into 2903 * the buffer and save a squaring. 2904 * 2905 * This means that if you have a k-bit window, to compute n^z, 2906 * where z is the high k bits of the exponent, 1/2 of the time 2907 * it requires no squarings. 1/4 of the time, it requires 1 2908 * squaring, ... 1/2^(k-1) of the time, it requires k-2 squarings. 2909 * And the remaining 1/2^(k-1) of the time, the top k bits are a 2910 * 1 followed by k-1 0 bits, so it again only requires k-2 2911 * squarings, not k-1. The average of these is 1. Add that 2912 * to the one squaring we have to do to compute the table, 2913 * and you'll see that a k-bit window saves k-2 squarings 2914 * as well as reducing the multiplies. (It actually doesn't 2915 * hurt in the case k = 1, either.) 2916 */ 2917 // Special case for exponent of one 2918 if (y.equals(ONE)) 2919 return this; 2920 2921 // Special case for base of zero 2922 if (signum == 0) 2923 return ZERO; 2924 2925 int[] base = mag.clone(); 2926 int[] exp = y.mag; 2927 int[] mod = z.mag; 2928 int modLen = mod.length; ```