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      */
divideArrayByInt(int[] quotient, int[] dividend, final int dividendLength, final int divisor)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