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
18package 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 */
41class 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