| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package java.math; |
| |
| /** |
| * Static library that provides all operations related with division and modular |
| * arithmetic to {@link BigInteger}. Some methods are provided in both mutable |
| * and immutable way. There are several variants provided listed below: |
| * |
| * <ul type="circle"> |
| * <li> <b>Division</b> |
| * <ul type="circle"> |
| * <li>{@link BigInteger} division and remainder by {@link BigInteger}.</li> |
| * <li>{@link BigInteger} division and remainder by {@code int}.</li> |
| * <li><i>gcd</i> between {@link BigInteger} numbers.</li> |
| * </ul> |
| * </li> |
| * <li> <b>Modular arithmetic </b> |
| * <ul type="circle"> |
| * <li>Modular exponentiation between {@link BigInteger} numbers.</li> |
| * <li>Modular inverse of a {@link BigInteger} numbers.</li> |
| * </ul> |
| * </li> |
| *</ul> |
| */ |
| class Division { |
| |
| /** |
| * Divides an array by an integer value. Implements the Knuth's division |
| * algorithm. See D. Knuth, The Art of Computer Programming, vol. 2. |
| * |
| * @return remainder |
| */ |
| static int divideArrayByInt(int[] quotient, int[] dividend, final int dividendLength, |
| final int divisor) { |
| |
| long rem = 0; |
| long bLong = divisor & 0xffffffffL; |
| |
| for (int i = dividendLength - 1; i >= 0; i--) { |
| long temp = (rem << 32) | (dividend[i] & 0xffffffffL); |
| long quot; |
| if (temp >= 0) { |
| quot = (temp / bLong); |
| rem = (temp % bLong); |
| } else { |
| /* |
| * make the dividend positive shifting it right by 1 bit then |
| * get the quotient an remainder and correct them properly |
| */ |
| long aPos = temp >>> 1; |
| long bPos = divisor >>> 1; |
| quot = aPos / bPos; |
| rem = aPos % bPos; |
| // double the remainder and add 1 if a is odd |
| rem = (rem << 1) + (temp & 1); |
| if ((divisor & 1) != 0) { |
| // the divisor is odd |
| if (quot <= rem) { |
| rem -= quot; |
| } else { |
| if (quot - rem <= bLong) { |
| rem += bLong - quot; |
| quot -= 1; |
| } else { |
| rem += (bLong << 1) - quot; |
| quot -= 2; |
| } |
| } |
| } |
| } |
| quotient[i] = (int) (quot & 0xffffffffL); |
| } |
| return (int) rem; |
| } |
| } |
