001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.math;
019:
020: /**
021: * Static library that provides the basic arithmetic mutable operations for
022: * {@link BigInteger}. The operations provided are listed below.
023: * <ul type="circle">
024: * <li>Addition.</li>
025: * <li>Subtraction.</li>
026: * <li>Comparison.</li>
027: * </ul>
028: * In addition to this, some <i><b>Inplace</b></i> (mutable) methods are provided.
029: *
030: * @author Intel Middleware Product Division
031: * @author Instituto Tecnologico de Cordoba
032: */
033: class Elementary {
034:
035: /** Just to denote that this class can't be instantiated */
036: private Elementary() {
037: }
038:
039: /**
040: * Compares two arrays. All elements are treated as unsigned integers. The
041: * magnitude is the bit chain of elements in big-endian order.
042: *
043: * @param a the first array
044: * @param b the second array
045: * @param size the size of arrays
046: * @return 1 if a > b, -1 if a < b, 0 if a == b
047: */
048: static int compareArrays(final int[] a, final int[] b,
049: final int size) {
050: int i;
051: for (i = size - 1; (i >= 0) && (a[i] == b[i]); i--) {
052: ;
053: }
054: return ((i < 0) ? BigInteger.EQUALS
055: : (a[i] & 0xFFFFFFFFL) < (b[i] & 0xFFFFFFFFL) ? BigInteger.LESS
056: : BigInteger.GREATER);
057: }
058:
059: /** @see BigInteger#add(BigInteger) */
060: static BigInteger add(BigInteger op1, BigInteger op2) {
061: int resDigits[];
062: int resSign;
063: int op1Sign = op1.sign;
064: int op2Sign = op2.sign;
065:
066: if (op1Sign == 0) {
067: return op2;
068: }
069: if (op2Sign == 0) {
070: return op1;
071: }
072: int op1Len = op1.numberLength;
073: int op2Len = op2.numberLength;
074:
075: if (op1Len + op2Len == 2) {
076: long a = (op1.digits[0] & 0xFFFFFFFFL);
077: long b = (op2.digits[0] & 0xFFFFFFFFL);
078: long res;
079: int valueLo;
080: int valueHi;
081:
082: if (op1Sign == op2Sign) {
083: res = a + b;
084: valueLo = (int) res;
085: valueHi = (int) (res >>> 32);
086: return ((valueHi == 0) ? new BigInteger(op1Sign,
087: valueLo) : new BigInteger(op1Sign, 2,
088: new int[] { valueLo, valueHi }));
089: }
090: return BigInteger
091: .valueOf((op1Sign < 0) ? (b - a) : (a - b));
092: } else if (op1Sign == op2Sign) {
093: resSign = op1Sign;
094: // an augend should not be shorter than addend
095: resDigits = (op1Len >= op2Len) ? add(op1.digits, op1Len,
096: op2.digits, op2Len) : add(op2.digits, op2Len,
097: op1.digits, op1Len);
098: } else { // signs are different
099: int cmp = ((op1Len != op2Len) ? ((op1Len > op2Len) ? 1 : -1)
100: : compareArrays(op1.digits, op2.digits, op1Len));
101:
102: if (cmp == BigInteger.EQUALS) {
103: return BigInteger.ZERO;
104: }
105: // a minuend should not be shorter than subtrahend
106: if (cmp == BigInteger.GREATER) {
107: resSign = op1Sign;
108: resDigits = subtract(op1.digits, op1Len, op2.digits,
109: op2Len);
110: } else {
111: resSign = op2Sign;
112: resDigits = subtract(op2.digits, op2Len, op1.digits,
113: op1Len);
114: }
115: }
116: BigInteger res = new BigInteger(resSign, resDigits.length,
117: resDigits);
118: res.cutOffLeadingZeroes();
119: return res;
120: }
121:
122: /**
123: * Performs {@code res = a + b}.
124: */
125: private static void add(int res[], int a[], int aSize, int b[],
126: int bSize) {
127: // PRE: a.length < max(aSize, bSize)
128:
129: int i;
130: long carry = (a[0] & 0xFFFFFFFFL) + (b[0] & 0xFFFFFFFFL);
131:
132: res[0] = (int) carry;
133: carry >>= 32;
134:
135: if (aSize >= bSize) {
136: for (i = 1; i < bSize; i++) {
137: carry += (a[i] & 0xFFFFFFFFL) + (b[i] & 0xFFFFFFFFL);
138: res[i] = (int) carry;
139: carry >>= 32;
140: }
141: for (; i < aSize; i++) {
142: carry += a[i] & 0xFFFFFFFFL;
143: res[i] = (int) carry;
144: carry >>= 32;
145: }
146: } else {
147: for (i = 1; i < aSize; i++) {
148: carry += (a[i] & 0xFFFFFFFFL) + (b[i] & 0xFFFFFFFFL);
149: res[i] = (int) carry;
150: carry >>= 32;
151: }
152: for (; i < bSize; i++) {
153: carry += b[i] & 0xFFFFFFFFL;
154: res[i] = (int) carry;
155: carry >>= 32;
156: }
157: }
158: if (carry != 0) {
159: res[i] = (int) carry;
160: }
161: }
162:
163: /** @see BigInteger#subtract(BigInteger) */
164: static BigInteger subtract(BigInteger op1, BigInteger op2) {
165: int resSign;
166: int resDigits[];
167: int op1Sign = op1.sign;
168: int op2Sign = op2.sign;
169:
170: if (op2Sign == 0) {
171: return op1;
172: }
173: if (op1Sign == 0) {
174: return op2.negate();
175: }
176: int op1Len = op1.numberLength;
177: int op2Len = op2.numberLength;
178: if (op1Len + op2Len == 2) {
179: long a = (op1.digits[0] & 0xFFFFFFFFL);
180: long b = (op2.digits[0] & 0xFFFFFFFFL);
181: if (op1Sign < 0) {
182: a = -a;
183: }
184: if (op2Sign < 0) {
185: b = -b;
186: }
187: return BigInteger.valueOf(a - b);
188: }
189: int cmp = ((op1Len != op2Len) ? ((op1Len > op2Len) ? 1 : -1)
190: : Elementary.compareArrays(op1.digits, op2.digits,
191: op1Len));
192:
193: if (cmp == BigInteger.LESS) {
194: resSign = -op2Sign;
195: resDigits = (op1Sign == op2Sign) ? subtract(op2.digits,
196: op2Len, op1.digits, op1Len) : add(op2.digits,
197: op2Len, op1.digits, op1Len);
198: } else {
199: resSign = op1Sign;
200: if (op1Sign == op2Sign) {
201: if (cmp == BigInteger.EQUALS) {
202: return BigInteger.ZERO;
203: }
204: resDigits = subtract(op1.digits, op1Len, op2.digits,
205: op2Len);
206: } else {
207: resDigits = add(op1.digits, op1Len, op2.digits, op2Len);
208: }
209: }
210: BigInteger res = new BigInteger(resSign, resDigits.length,
211: resDigits);
212: res.cutOffLeadingZeroes();
213: return res;
214: }
215:
216: /**
217: * Performs {@code res = a - b}. It is assumed the magnitude of a is not
218: * less than the magnitude of b.
219: */
220: private static void subtract(int res[], int a[], int aSize,
221: int b[], int bSize) {
222: // PRE: a[] >= b[]
223: int i;
224: long borrow = 0;
225:
226: for (i = 0; i < bSize; i++) {
227: borrow += (a[i] & 0xFFFFFFFFL) - (b[i] & 0xFFFFFFFFL);
228: res[i] = (int) borrow;
229: borrow >>= 32; // -1 or 0
230: }
231: for (; i < aSize; i++) {
232: borrow += a[i] & 0xFFFFFFFFL;
233: res[i] = (int) borrow;
234: borrow >>= 32; // -1 or 0
235: }
236: }
237:
238: /**
239: * Addss the value represented by {@code b} to the value represented by
240: * {@code a}. It is assumed the magnitude of a is not less than the
241: * magnitude of b.
242: *
243: * @return {@code a + b}
244: */
245: private static int[] add(int a[], int aSize, int b[], int bSize) {
246: // PRE: a[] >= b[]
247: int res[] = new int[aSize + 1];
248: add(res, a, aSize, b, bSize);
249: return res;
250: }
251:
252: /**
253: * Performs {@code op1 += op2}. {@code op1} must have enough place to store
254: * the result (i.e. {@code op1.bitLength() >= op2.bitLength()}). Both
255: * should be positive (i.e. {@code op1 >= op2}).
256: *
257: * @param op1 the input minuend, and the output result.
258: * @param op2 the addend
259: */
260: static void inplaceAdd(BigInteger op1, BigInteger op2) {
261: // PRE: op1 >= op2 > 0
262: add(op1.digits, op1.digits, op1.numberLength, op2.digits,
263: op2.numberLength);
264: op1.numberLength = Math.min(Math.max(op1.numberLength,
265: op2.numberLength) + 1, op1.digits.length);
266: op1.cutOffLeadingZeroes();
267: op1.unCache();
268: }
269:
270: /**
271: * Adds an integer value to the array of integers remembering carry.
272: *
273: * @return a possible generated carry (0 or 1)
274: */
275: static int inplaceAdd(int a[], final int aSize, final int addend) {
276: long carry = addend & 0xFFFFFFFFL;
277:
278: for (int i = 0; (carry != 0) && (i < aSize); i++) {
279: carry += a[i] & 0xFFFFFFFFL;
280: a[i] = (int) carry;
281: carry >>= 32;
282: }
283: return (int) carry;
284: }
285:
286: /**
287: * Performs: {@code op1 += addend}. The number must to have place to hold a
288: * possible carry.
289: */
290: static void inplaceAdd(BigInteger op1, final int addend) {
291: int carry = inplaceAdd(op1.digits, op1.numberLength, addend);
292: if (carry == 1) {
293: op1.digits[op1.numberLength] = 1;
294: op1.numberLength++;
295: }
296: op1.unCache();
297: }
298:
299: /**
300: * Performs {@code op1 -= op2}. {@code op1} must have enough place to store
301: * the result (i.e. {@code op1.bitLength() >= op2.bitLength()}). Both
302: * should be positive (what implies that {@code op1 >= op2}).
303: *
304: * @param op1
305: * the input minuend, and the output result.
306: * @param op2
307: * the subtrahend
308: */
309: static void inplaceSubtract(BigInteger op1, BigInteger op2) {
310: // PRE: op1 >= op2 > 0
311: subtract(op1.digits, op1.digits, op1.numberLength, op2.digits,
312: op2.numberLength);
313: op1.cutOffLeadingZeroes();
314: op1.unCache();
315: }
316:
317: /**
318: * Performs {@code res = b - a}
319: */
320: private static void inverseSubtract(int res[], int a[], int aSize,
321: int b[], int bSize) {
322: int i;
323: long borrow = 0;
324: if (aSize < bSize) {
325: for (i = 0; i < aSize; i++) {
326: borrow += (b[i] & 0xFFFFFFFFL) - (a[i] & 0xFFFFFFFFL);
327: res[i] = (int) borrow;
328: borrow >>= 32; // -1 or 0
329: }
330: for (; i < bSize; i++) {
331: borrow += b[i] & 0xFFFFFFFFL;
332: res[i] = (int) borrow;
333: borrow >>= 32; // -1 or 0
334: }
335: } else {
336: for (i = 0; i < bSize; i++) {
337: borrow += (b[i] & 0xFFFFFFFFL) - (a[i] & 0xFFFFFFFFL);
338: res[i] = (int) borrow;
339: borrow >>= 32; // -1 or 0
340: }
341: for (; i < aSize; i++) {
342: borrow -= a[i] & 0xFFFFFFFFL;
343: res[i] = (int) borrow;
344: borrow >>= 32; // -1 or 0
345: }
346: }
347:
348: }
349:
350: /**
351: * Subtracts the value represented by {@code b} from the value represented
352: * by {@code a}. It is assumed the magnitude of a is not less than the
353: * magnitude of b.
354: *
355: * @return {@code a - b}
356: */
357: private static int[] subtract(int a[], int aSize, int b[], int bSize) {
358: // PRE: a[] >= b[]
359: int res[] = new int[aSize];
360: subtract(res, a, aSize, b, bSize);
361: return res;
362: }
363:
364: /**
365: * Same as
366: *
367: * @link #inplaceSubtract(BigInteger, BigInteger), but without the
368: * restriction of non-positive values
369: * @param op1
370: * should have enough space to save the result
371: * @param op2
372: */
373: static void completeInPlaceSubtract(BigInteger op1, BigInteger op2) {
374: int resultSign = op1.compareTo(op2);
375: if (op1.sign == 0) {
376: System.arraycopy(op2.digits, 0, op1.digits, 0,
377: op2.numberLength);
378: op1.sign = -op2.sign;
379: } else if (op1.sign != op2.sign) {
380: add(op1.digits, op1.digits, op1.numberLength, op2.digits,
381: op2.numberLength);
382: op1.sign = resultSign;
383: } else {
384: int sign = unsignedArraysCompare(op1.digits, op2.digits,
385: op1.numberLength, op2.numberLength);
386: if (sign > 0) {
387: subtract(op1.digits, op1.digits, op1.numberLength,
388: op2.digits, op2.numberLength); // op1 = op1 - op2
389: // op1.sign remains equal
390: } else {
391: inverseSubtract(op1.digits, op1.digits,
392: op1.numberLength, op2.digits, op2.numberLength); // op1 = op2 - op1
393: op1.sign = -op1.sign;
394: }
395: }
396: op1.numberLength = Math.max(op1.numberLength, op2.numberLength) + 1;
397: op1.cutOffLeadingZeroes();
398: op1.unCache();
399: }
400:
401: /**
402: * Same as @link #inplaceAdd(BigInteger, BigInteger), but without the restriction of
403: * non-positive values
404: * @param op1 any number
405: * @param op2 any number
406: */
407: static void completeInPlaceAdd(BigInteger op1, BigInteger op2) {
408: if (op1.sign == 0)
409: System.arraycopy(op2.digits, 0, op1.digits, 0,
410: op2.numberLength);
411: else if (op2.sign == 0)
412: return;
413: else if (op1.sign == op2.sign)
414: add(op1.digits, op1.digits, op1.numberLength, op2.digits,
415: op2.numberLength);
416: else {
417: int sign = unsignedArraysCompare(op1.digits, op2.digits,
418: op1.numberLength, op2.numberLength);
419: if (sign > 0)
420: subtract(op1.digits, op1.digits, op1.numberLength,
421: op2.digits, op2.numberLength);
422: else {
423: inverseSubtract(op1.digits, op1.digits,
424: op1.numberLength, op2.digits, op2.numberLength);
425: op1.sign = -op1.sign;
426: }
427: }
428: op1.numberLength = Math.max(op1.numberLength, op2.numberLength) + 1;
429: op1.cutOffLeadingZeroes();
430: op1.unCache();
431: }
432:
433: /**
434: * Compares two arrays, representing unsigned integer in little-endian order.
435: * Returns +1,0,-1 if a is - respective - greater, equal or lesser then b
436: */
437: private static int unsignedArraysCompare(int[] a, int[] b,
438: int aSize, int bSize) {
439: if (aSize > bSize)
440: return 1;
441: else if (aSize < bSize)
442: return -1;
443:
444: else {
445: int i;
446: for (i = aSize - 1; i >= 0 && a[i] == b[i]; i--)
447: ;
448: return i < 0 ? BigInteger.EQUALS
449: : ((a[i] & 0xFFFFFFFFL) < (b[i] & 0xFFFFFFFFL) ? BigInteger.LESS
450: : BigInteger.GREATER);
451: }
452: }
453:
454: }
|