1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package java.math; 19 20 /** 21 * Static library that provides all operations related with division and modular 22 * arithmetic to {@link BigInteger}. Some methods are provided in both mutable 23 * and immutable way. There are several variants provided listed below: 24 * 25 * <ul type="circle"> 26 * <li> <b>Division</b> 27 * <ul type="circle"> 28 * <li>{@link BigInteger} division and remainder by {@link BigInteger}.</li> 29 * <li>{@link BigInteger} division and remainder by {@code int}.</li> 30 * <li><i>gcd</i> between {@link BigInteger} numbers.</li> 31 * </ul> 32 * </li> 33 * <li> <b>Modular arithmetic </b> 34 * <ul type="circle"> 35 * <li>Modular exponentiation between {@link BigInteger} numbers.</li> 36 * <li>Modular inverse of a {@link BigInteger} numbers.</li> 37 * </ul> 38 * </li> 39 *</ul> 40 */ 41 class Division { 42 43 /** 44 * Divides an array by an integer value. Implements the Knuth's division 45 * algorithm. See D. Knuth, The Art of Computer Programming, vol. 2. 46 * 47 * @return remainder 48 */ 49 static int divideArrayByInt(int[] quotient, int[] dividend, final int dividendLength, 50 final int divisor) { 51 52 long rem = 0; 53 long bLong = divisor & 0xffffffffL; 54 55 for (int i = dividendLength - 1; i >= 0; i--) { 56 long temp = (rem << 32) | (dividend[i] & 0xffffffffL); 57 long quot; 58 if (temp >= 0) { 59 quot = (temp / bLong); 60 rem = (temp % bLong); 61 } else { 62 /* 63 * make the dividend positive shifting it right by 1 bit then 64 * get the quotient an remainder and correct them properly 65 */ 66 long aPos = temp >>> 1; 67 long bPos = divisor >>> 1; 68 quot = aPos / bPos; 69 rem = aPos % bPos; 70 // double the remainder and add 1 if a is odd 71 rem = (rem << 1) + (temp & 1); 72 if ((divisor & 1) != 0) { 73 // the divisor is odd 74 if (quot <= rem) { 75 rem -= quot; 76 } else { 77 if (quot - rem <= bLong) { 78 rem += bLong - quot; 79 quot -= 1; 80 } else { 81 rem += (bLong << 1) - quot; 82 quot -= 2; 83 } 84 } 85 } 86 } 87 quotient[i] = (int) (quot & 0xffffffffL); 88 } 89 return (int) rem; 90 } 91 } 92
