```   1 /*
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.  Oracle designates this
8  * particular file as subject to the "Classpath" exception as provided
9  * by Oracle in the LICENSE file that accompanied this code.
10  *
11  * This code is distributed in the hope that it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14  * version 2 for more details (a copy is included in the LICENSE file that
15  * accompanied this code).
16  *
17  * You should have received a copy of the GNU General Public License version
18  * 2 along with this work; if not, write to the Free Software Foundation,
19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20  *
21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22  * or visit www.oracle.com if you need additional information or have any
23  * questions.
24  */
25
26 /*
28  */
29
30 package java.math;
31
32 import static java.math.BigInteger.LONG_MASK;
33 import java.util.Arrays;
34 import java.util.Objects;
35
36 /**
37  * Immutable, arbitrary-precision signed decimal numbers.  A
38  * {@code BigDecimal} consists of an arbitrary precision integer
39  * <i>unscaled value</i> and a 32-bit integer <i>scale</i>.  If zero
40  * or positive, the scale is the number of digits to the right of the
41  * decimal point.  If negative, the unscaled value of the number is
42  * multiplied by ten to the power of the negation of the scale.  The
43  * value of the number represented by the {@code BigDecimal} is
44  * therefore <code>(unscaledValue &times; 10<sup>-scale</sup>)</code>.
45  *
46  * <p>The {@code BigDecimal} class provides operations for
47  * arithmetic, scale manipulation, rounding, comparison, hashing, and
48  * format conversion.  The {@link #toString} method provides a
49  * canonical representation of a {@code BigDecimal}.
50  *
51  * <p>The {@code BigDecimal} class gives its user complete control
52  * over rounding behavior.  If no rounding mode is specified and the
53  * exact result cannot be represented, an exception is thrown;
54  * otherwise, calculations can be carried out to a chosen precision
55  * and rounding mode by supplying an appropriate {@link MathContext}
56  * object to the operation.  In either case, eight <em>rounding
57  * modes</em> are provided for the control of rounding.  Using the
58  * integer fields in this class (such as {@link #ROUND_HALF_UP}) to
59  * represent rounding mode is deprecated; the enumeration values
60  * of the {@code RoundingMode} {@code enum}, (such as {@link
61  * RoundingMode#HALF_UP}) should be used instead.
62  *
63  * <p>When a {@code MathContext} object is supplied with a precision
64  * setting of 0 (for example, {@link MathContext#UNLIMITED}),
65  * arithmetic operations are exact, as are the arithmetic methods
66  * which take no {@code MathContext} object.  (This is the only
67  * behavior that was supported in releases prior to 5.)  As a
68  * corollary of computing the exact result, the rounding mode setting
69  * of a {@code MathContext} object with a precision setting of 0 is
70  * not used and thus irrelevant.  In the case of divide, the exact
71  * quotient could have an infinitely long decimal expansion; for
72  * example, 1 divided by 3.  If the quotient has a nonterminating
73  * decimal expansion and the operation is specified to return an exact
74  * result, an {@code ArithmeticException} is thrown.  Otherwise, the
75  * exact result of the division is returned, as done for other
76  * operations.
77  *
78  * <p>When the precision setting is not 0, the rules of
79  * {@code BigDecimal} arithmetic are broadly compatible with selected
80  * modes of operation of the arithmetic defined in ANSI X3.274-1996
81  * and ANSI X3.274-1996/AM 1-2000 (section 7.4).  Unlike those
82  * standards, {@code BigDecimal} includes many rounding modes, which
83  * were mandatory for division in {@code BigDecimal} releases prior
84  * to 5.  Any conflicts between these ANSI standards and the
85  * {@code BigDecimal} specification are resolved in favor of
86  * {@code BigDecimal}.
87  *
88  * <p>Since the same numerical value can have different
89  * representations (with different scales), the rules of arithmetic
90  * and rounding must specify both the numerical result and the scale
91  * used in the result's representation.
92  *
93  *
94  * <p>In general the rounding modes and precision setting determine
95  * how operations return results with a limited number of digits when
96  * the exact result has more digits (perhaps infinitely many in the
97  * case of division and square root) than the number of digits returned.
98  *
99  * First, the
100  * total number of digits to return is specified by the
101  * {@code MathContext}'s {@code precision} setting; this determines
102  * the result's <i>precision</i>.  The digit count starts from the
103  * leftmost nonzero digit of the exact result.  The rounding mode
104  * determines how any discarded trailing digits affect the returned
105  * result.
106  *
107  * <p>For all arithmetic operators , the operation is carried out as
108  * though an exact intermediate result were first calculated and then
109  * rounded to the number of digits specified by the precision setting
110  * (if necessary), using the selected rounding mode.  If the exact
111  * result is not returned, some digit positions of the exact result
112  * are discarded.  When rounding increases the magnitude of the
113  * returned result, it is possible for a new digit position to be
114  * created by a carry propagating to a leading {@literal "9"} digit.
115  * For example, rounding the value 999.9 to three digits rounding up
116  * would be numerically equal to one thousand, represented as
117  * 100&times;10<sup>1</sup>.  In such cases, the new {@literal "1"} is
118  * the leading digit position of the returned result.
119  *
120  * <p>Besides a logical exact result, each arithmetic operation has a
121  * preferred scale for representing a result.  The preferred
122  * scale for each operation is listed in the table below.
123  *
124  * <table class="striped" style="text-align:left">
125  * <caption>Preferred Scales for Results of Arithmetic Operations
126  * </caption>
128  * <tr><th scope="col">Operation</th><th scope="col">Preferred Scale of Result</th></tr>
130  * <tbody>
132  * <tr><th scope="row">Subtract</th><td>max(minuend.scale(), subtrahend.scale())</td>
133  * <tr><th scope="row">Multiply</th><td>multiplier.scale() + multiplicand.scale()</td>
134  * <tr><th scope="row">Divide</th><td>dividend.scale() - divisor.scale()</td>
135  * <tr><th scope="row">Square root</th><td>radicand.scale()/2</td>
136  * </tbody>
137  * </table>
138  *
139  * These scales are the ones used by the methods which return exact
140  * arithmetic results; except that an exact divide may have to use a
141  * larger scale since the exact result may have more digits.  For
142  * example, {@code 1/32} is {@code 0.03125}.
143  *
144  * <p>Before rounding, the scale of the logical exact intermediate
145  * result is the preferred scale for that operation.  If the exact
146  * numerical result cannot be represented in {@code precision}
147  * digits, rounding selects the set of digits to return and the scale
148  * of the result is reduced from the scale of the intermediate result
149  * to the least scale which can represent the {@code precision}
150  * digits actually returned.  If the exact result can be represented
151  * with at most {@code precision} digits, the representation
152  * of the result with the scale closest to the preferred scale is
153  * returned.  In particular, an exactly representable quotient may be
154  * represented in fewer than {@code precision} digits by removing
155  * trailing zeros and decreasing the scale.  For example, rounding to
156  * three digits using the {@linkplain RoundingMode#FLOOR floor}
157  * rounding mode, <br>
158  *
159  * {@code 19/100 = 0.19   // integer=19,  scale=2} <br>
160  *
161  * but<br>
162  *
163  * {@code 21/110 = 0.190  // integer=190, scale=3} <br>
164  *
165  * <p>Note that for add, subtract, and multiply, the reduction in
166  * scale will equal the number of digit positions of the exact result
167  * which are discarded. If the rounding causes a carry propagation to
168  * create a new high-order digit position, an additional digit of the
169  * result is discarded than when no new digit position is created.
170  *
171  * <p>Other methods may have slightly different rounding semantics.
172  * For example, the result of the {@code pow} method using the
173  * {@linkplain #pow(int, MathContext) specified algorithm} can
174  * occasionally differ from the rounded mathematical result by more
175  * than one unit in the last place, one <i>{@linkplain #ulp() ulp}</i>.
176  *
177  * <p>Two types of operations are provided for manipulating the scale
178  * of a {@code BigDecimal}: scaling/rounding operations and decimal
179  * point motion operations.  Scaling/rounding operations ({@link
180  * #setScale setScale} and {@link #round round}) return a
181  * {@code BigDecimal} whose value is approximately (or exactly) equal
182  * to that of the operand, but whose scale or precision is the
183  * specified value; that is, they increase or decrease the precision
184  * of the stored number with minimal effect on its value.  Decimal
185  * point motion operations ({@link #movePointLeft movePointLeft} and
186  * {@link #movePointRight movePointRight}) return a
187  * {@code BigDecimal} created from the operand by moving the decimal
188  * point a specified distance in the specified direction.
189  *
190  * <p>For the sake of brevity and clarity, pseudo-code is used
191  * throughout the descriptions of {@code BigDecimal} methods.  The
192  * pseudo-code expression {@code (i + j)} is shorthand for "a
193  * {@code BigDecimal} whose value is that of the {@code BigDecimal}
194  * {@code i} added to that of the {@code BigDecimal}
195  * {@code j}." The pseudo-code expression {@code (i == j)} is
196  * shorthand for "{@code true} if and only if the
197  * {@code BigDecimal} {@code i} represents the same value as the
198  * {@code BigDecimal} {@code j}." Other pseudo-code expressions
199  * are interpreted similarly.  Square brackets are used to represent
200  * the particular {@code BigInteger} and scale pair defining a
201  * {@code BigDecimal} value; for example [19, 2] is the
202  * {@code BigDecimal} numerically equal to 0.19 having a scale of 2.
203  *
204  *
205  * <p>All methods and constructors for this class throw
206  * {@code NullPointerException} when passed a {@code null} object
207  * reference for any input parameter.
208  *
209  * @apiNote Care should be exercised if {@code BigDecimal} objects
210  * are used as keys in a {@link java.util.SortedMap SortedMap} or
211  * elements in a {@link java.util.SortedSet SortedSet} since
212  * {@code BigDecimal}'s <i>natural ordering</i> is <em>inconsistent
213  * with equals</em>.  See {@link Comparable}, {@link
214  * java.util.SortedMap} or {@link java.util.SortedSet} for more
215  * information.
216  *
217  * @see     BigInteger
218  * @see     MathContext
219  * @see     RoundingMode
220  * @see     java.util.SortedMap
221  * @see     java.util.SortedSet
222  * @author  Josh Bloch
223  * @author  Mike Cowlishaw
224  * @author  Joseph D. Darcy
225  * @author  Sergey V. Kuksenko
226  * @since 1.1
227  */
228 public class BigDecimal extends Number implements Comparable<BigDecimal> {
229     /**
230      * The unscaled value of this BigDecimal, as returned by {@link
231      * #unscaledValue}.
232      *
233      * @serial
234      * @see #unscaledValue
235      */
236     private final BigInteger intVal;
237
238     /**
239      * The scale of this BigDecimal, as returned by {@link #scale}.
240      *
241      * @serial
242      * @see #scale
243      */
244     private final int scale;  // Note: this may have any value, so
245                               // calculations must be done in longs
246
247     /**
248      * The number of decimal digits in this BigDecimal, or 0 if the
249      * number of digits are not known (lookaside information).  If
250      * nonzero, the value is guaranteed correct.  Use the precision()
251      * method to obtain and set the value if it might be 0.  This
252      * field is mutable until set nonzero.
253      *
254      * @since  1.5
255      */
256     private transient int precision;
257
258     /**
259      * Used to store the canonical string representation, if computed.
260      */
261     private transient String stringCache;
262
263     /**
264      * Sentinel value for {@link #intCompact} indicating the
265      * significand information is only available from {@code intVal}.
266      */
267     static final long INFLATED = Long.MIN_VALUE;
268
269     private static final BigInteger INFLATED_BIGINT = BigInteger.valueOf(INFLATED);
270
271     /**
272      * If the absolute value of the significand of this BigDecimal is
273      * less than or equal to {@code Long.MAX_VALUE}, the value can be
274      * compactly stored in this field and used in computations.
275      */
276     private final transient long intCompact;
277
278     // All 18-digit base ten strings fit into a long; not all 19-digit
279     // strings will
280     private static final int MAX_COMPACT_DIGITS = 18;
281
282     /* Appease the serialization gods */
283     private static final long serialVersionUID = 6108874887143696463L;
284
285     private static final ThreadLocal<StringBuilderHelper>
287         @Override
288         protected StringBuilderHelper initialValue() {
289             return new StringBuilderHelper();
290         }
291     };
292
293     // Cache of common small BigDecimal values.
294     private static final BigDecimal ZERO_THROUGH_TEN[] = {
295         new BigDecimal(BigInteger.ZERO,       0,  0, 1),
296         new BigDecimal(BigInteger.ONE,        1,  0, 1),
297         new BigDecimal(BigInteger.TWO,        2,  0, 1),
298         new BigDecimal(BigInteger.valueOf(3), 3,  0, 1),
299         new BigDecimal(BigInteger.valueOf(4), 4,  0, 1),
300         new BigDecimal(BigInteger.valueOf(5), 5,  0, 1),
301         new BigDecimal(BigInteger.valueOf(6), 6,  0, 1),
302         new BigDecimal(BigInteger.valueOf(7), 7,  0, 1),
303         new BigDecimal(BigInteger.valueOf(8), 8,  0, 1),
304         new BigDecimal(BigInteger.valueOf(9), 9,  0, 1),
305         new BigDecimal(BigInteger.TEN,        10, 0, 2),
306     };
307
308     // Cache of zero scaled by 0 - 15
309     private static final BigDecimal[] ZERO_SCALED_BY = {
310         ZERO_THROUGH_TEN[0],
311         new BigDecimal(BigInteger.ZERO, 0, 1, 1),
312         new BigDecimal(BigInteger.ZERO, 0, 2, 1),
313         new BigDecimal(BigInteger.ZERO, 0, 3, 1),
314         new BigDecimal(BigInteger.ZERO, 0, 4, 1),
315         new BigDecimal(BigInteger.ZERO, 0, 5, 1),
316         new BigDecimal(BigInteger.ZERO, 0, 6, 1),
317         new BigDecimal(BigInteger.ZERO, 0, 7, 1),
318         new BigDecimal(BigInteger.ZERO, 0, 8, 1),
319         new BigDecimal(BigInteger.ZERO, 0, 9, 1),
320         new BigDecimal(BigInteger.ZERO, 0, 10, 1),
321         new BigDecimal(BigInteger.ZERO, 0, 11, 1),
322         new BigDecimal(BigInteger.ZERO, 0, 12, 1),
323         new BigDecimal(BigInteger.ZERO, 0, 13, 1),
324         new BigDecimal(BigInteger.ZERO, 0, 14, 1),
325         new BigDecimal(BigInteger.ZERO, 0, 15, 1),
326     };
327
328     // Half of Long.MIN_VALUE & Long.MAX_VALUE.
329     private static final long HALF_LONG_MAX_VALUE = Long.MAX_VALUE / 2;
330     private static final long HALF_LONG_MIN_VALUE = Long.MIN_VALUE / 2;
331
332     // Constants
333     /**
334      * The value 0, with a scale of 0.
335      *
336      * @since  1.5
337      */
338     public static final BigDecimal ZERO =
339         ZERO_THROUGH_TEN[0];
340
341     /**
342      * The value 1, with a scale of 0.
343      *
344      * @since  1.5
345      */
346     public static final BigDecimal ONE =
347         ZERO_THROUGH_TEN[1];
348
349     /**
350      * The value 10, with a scale of 0.
351      *
352      * @since  1.5
353      */
354     public static final BigDecimal TEN =
355         ZERO_THROUGH_TEN[10];
356
357     /**
358      * The value 0.1, with a scale of 1.
359      */
360     private static final BigDecimal ONE_TENTH = valueOf(1L, 1);
361
362     /**
363      * The value 0.5, with a scale of 1.
364      */
365     private static final BigDecimal ONE_HALF = valueOf(5L, 1);
366
367     // Constructors
368
369     /**
370      * Trusted package private constructor.
371      * Trusted simply means if val is INFLATED, intVal could not be null and
372      * if intVal is null, val could not be INFLATED.
373      */
374     BigDecimal(BigInteger intVal, long val, int scale, int prec) {
375         this.scale = scale;
376         this.precision = prec;
377         this.intCompact = val;
378         this.intVal = intVal;
379     }
380
381     /**
382      * Translates a character array representation of a
383      * {@code BigDecimal} into a {@code BigDecimal}, accepting the
384      * same sequence of characters as the {@link #BigDecimal(String)}
385      * constructor, while allowing a sub-array to be specified.
386      *
387      * @implNote If the sequence of characters is already available
388      * within a character array, using this constructor is faster than
389      * converting the {@code char} array to string and using the
390      * {@code BigDecimal(String)} constructor.
391      *
392      * @param  in {@code char} array that is the source of characters.
393      * @param  offset first character in the array to inspect.
394      * @param  len number of characters to consider.
395      * @throws NumberFormatException if {@code in} is not a valid
396      *         representation of a {@code BigDecimal} or the defined subarray
397      *         is not wholly within {@code in}.
398      * @since  1.5
399      */
400     public BigDecimal(char[] in, int offset, int len) {
401         this(in,offset,len,MathContext.UNLIMITED);
402     }
403
404     /**
405      * Translates a character array representation of a
406      * {@code BigDecimal} into a {@code BigDecimal}, accepting the
407      * same sequence of characters as the {@link #BigDecimal(String)}
408      * constructor, while allowing a sub-array to be specified and
409      * with rounding according to the context settings.
410      *
411      * @implNote If the sequence of characters is already available
412      * within a character array, using this constructor is faster than
413      * converting the {@code char} array to string and using the
414      * {@code BigDecimal(String)} constructor.
415      *
416      * @param  in {@code char} array that is the source of characters.
417      * @param  offset first character in the array to inspect.
418      * @param  len number of characters to consider.
419      * @param  mc the context to use.
420      * @throws ArithmeticException if the result is inexact but the
421      *         rounding mode is {@code UNNECESSARY}.
422      * @throws NumberFormatException if {@code in} is not a valid
423      *         representation of a {@code BigDecimal} or the defined subarray
424      *         is not wholly within {@code in}.
425      * @since  1.5
426      */
427     public BigDecimal(char[] in, int offset, int len, MathContext mc) {
428         // protect against huge length, negative values, and integer overflow
429         try {
430             Objects.checkFromIndexSize(offset, len, in.length);
431         } catch (IndexOutOfBoundsException e) {
432             throw new NumberFormatException
433                 ("Bad offset or len arguments for char[] input.");
434         }
435
436         // This is the primary string to BigDecimal constructor; all
437         // incoming strings end up here; it uses explicit (inline)
438         // parsing for speed and generates at most one intermediate
439         // (temporary) object (a char[] array) for non-compact case.
440
441         // Use locals for all fields values until completion
442         int prec = 0;                 // record precision value
443         int scl = 0;                  // record scale value
444         long rs = 0;                  // the compact value in long
445         BigInteger rb = null;         // the inflated value in BigInteger
446         // use array bounds checking to handle too-long, len == 0,
447         // bad offset, etc.
448         try {
449             // handle the sign
450             boolean isneg = false;          // assume positive
451             if (in[offset] == '-') {
452                 isneg = true;               // leading minus means negative
453                 offset++;
454                 len--;
455             } else if (in[offset] == '+') { // leading + allowed
456                 offset++;
457                 len--;
458             }
459
460             // should now be at numeric part of the significand
461             boolean dot = false;             // true when there is a '.'
462             long exp = 0;                    // exponent
463             char c;                          // current character
464             boolean isCompact = (len <= MAX_COMPACT_DIGITS);
465             // integer significand array & idx is the index to it. The array
466             // is ONLY used when we can't use a compact representation.
467             int idx = 0;
468             if (isCompact) {
469                 // First compact case, we need not to preserve the character
470                 // and we can just compute the value in place.
471                 for (; len > 0; offset++, len--) {
472                     c = in[offset];
473                     if ((c == '0')) { // have zero
474                         if (prec == 0)
475                             prec = 1;
476                         else if (rs != 0) {
477                             rs *= 10;
478                             ++prec;
479                         } // else digit is a redundant leading zero
480                         if (dot)
481                             ++scl;
482                     } else if ((c >= '1' && c <= '9')) { // have digit
483                         int digit = c - '0';
484                         if (prec != 1 || rs != 0)
485                             ++prec; // prec unchanged if preceded by 0s
486                         rs = rs * 10 + digit;
487                         if (dot)
488                             ++scl;
489                     } else if (c == '.') {   // have dot
490                         // have dot
491                         if (dot) // two dots
492                             throw new NumberFormatException("Character array"
493                                 + " contains more than one decimal point.");
494                         dot = true;
495                     } else if (Character.isDigit(c)) { // slow path
496                         int digit = Character.digit(c, 10);
497                         if (digit == 0) {
498                             if (prec == 0)
499                                 prec = 1;
500                             else if (rs != 0) {
501                                 rs *= 10;
502                                 ++prec;
503                             } // else digit is a redundant leading zero
504                         } else {
505                             if (prec != 1 || rs != 0)
506                                 ++prec; // prec unchanged if preceded by 0s
507                             rs = rs * 10 + digit;
508                         }
509                         if (dot)
510                             ++scl;
511                     } else if ((c == 'e') || (c == 'E')) {
512                         exp = parseExp(in, offset, len);
513                         // Next test is required for backwards compatibility
514                         if ((int) exp != exp) // overflow
515                             throw new NumberFormatException("Exponent overflow.");
516                         break; // [saves a test]
517                     } else {
518                         throw new NumberFormatException("Character " + c
519                             + " is neither a decimal digit number, decimal point, nor"
520                             + " \"e\" notation exponential mark.");
521                     }
522                 }
523                 if (prec == 0) // no digits found
524                     throw new NumberFormatException("No digits found.");
525                 // Adjust scale if exp is not zero.
526                 if (exp != 0) { // had significant exponent
527                     scl = adjustScale(scl, exp);
528                 }
529                 rs = isneg ? -rs : rs;
530                 int mcp = mc.precision;
531                 int drop = prec - mcp; // prec has range [1, MAX_INT], mcp has range [0, MAX_INT];
532                                        // therefore, this subtract cannot overflow
533                 if (mcp > 0 && drop > 0) {  // do rounding
534                     while (drop > 0) {
535                         scl = checkScaleNonZero((long) scl - drop);
536                         rs = divideAndRound(rs, LONG_TEN_POWERS_TABLE[drop], mc.roundingMode.oldMode);
537                         prec = longDigitLength(rs);
538                         drop = prec - mcp;
539                     }
540                 }
541             } else {
542                 char coeff[] = new char[len];
543                 for (; len > 0; offset++, len--) {
544                     c = in[offset];
545                     // have digit
546                     if ((c >= '0' && c <= '9') || Character.isDigit(c)) {
547                         // First compact case, we need not to preserve the character
548                         // and we can just compute the value in place.
549                         if (c == '0' || Character.digit(c, 10) == 0) {
550                             if (prec == 0) {
551                                 coeff[idx] = c;
552                                 prec = 1;
553                             } else if (idx != 0) {
554                                 coeff[idx++] = c;
555                                 ++prec;
556                             } // else c must be a redundant leading zero
557                         } else {
558                             if (prec != 1 || idx != 0)
559                                 ++prec; // prec unchanged if preceded by 0s
560                             coeff[idx++] = c;
561                         }
562                         if (dot)
563                             ++scl;
564                         continue;
565                     }
566                     // have dot
567                     if (c == '.') {
568                         // have dot
569                         if (dot) // two dots
570                             throw new NumberFormatException("Character array"
571                                 + " contains more than one decimal point.");
572                         dot = true;
573                         continue;
574                     }
575                     // exponent expected
576                     if ((c != 'e') && (c != 'E'))
577                         throw new NumberFormatException("Character array"
578                             + " is missing \"e\" notation exponential mark.");
579                     exp = parseExp(in, offset, len);
580                     // Next test is required for backwards compatibility
581                     if ((int) exp != exp) // overflow
582                         throw new NumberFormatException("Exponent overflow.");
583                     break; // [saves a test]
584                 }
585                 // here when no characters left
586                 if (prec == 0) // no digits found
587                     throw new NumberFormatException("No digits found.");
588                 // Adjust scale if exp is not zero.
589                 if (exp != 0) { // had significant exponent
590                     scl = adjustScale(scl, exp);
591                 }
592                 // Remove leading zeros from precision (digits count)
593                 rb = new BigInteger(coeff, isneg ? -1 : 1, prec);
594                 rs = compactValFor(rb);
595                 int mcp = mc.precision;
596                 if (mcp > 0 && (prec > mcp)) {
597                     if (rs == INFLATED) {
598                         int drop = prec - mcp;
599                         while (drop > 0) {
600                             scl = checkScaleNonZero((long) scl - drop);
601                             rb = divideAndRoundByTenPow(rb, drop, mc.roundingMode.oldMode);
602                             rs = compactValFor(rb);
603                             if (rs != INFLATED) {
604                                 prec = longDigitLength(rs);
605                                 break;
606                             }
607                             prec = bigDigitLength(rb);
608                             drop = prec - mcp;
609                         }
610                     }
611                     if (rs != INFLATED) {
612                         int drop = prec - mcp;
613                         while (drop > 0) {
614                             scl = checkScaleNonZero((long) scl - drop);
615                             rs = divideAndRound(rs, LONG_TEN_POWERS_TABLE[drop], mc.roundingMode.oldMode);
616                             prec = longDigitLength(rs);
617                             drop = prec - mcp;
618                         }
619                         rb = null;
620                     }
621                 }
622             }
623         } catch (ArrayIndexOutOfBoundsException | NegativeArraySizeException e) {
624             NumberFormatException nfe = new NumberFormatException();
625             nfe.initCause(e);
626             throw nfe;
627         }
628         this.scale = scl;
629         this.precision = prec;
630         this.intCompact = rs;
631         this.intVal = rb;
632     }
633
634     private int adjustScale(int scl, long exp) {
635         long adjustedScale = scl - exp;
636         if (adjustedScale > Integer.MAX_VALUE || adjustedScale < Integer.MIN_VALUE)
637             throw new NumberFormatException("Scale out of range.");
638         scl = (int) adjustedScale;
639         return scl;
640     }
641
642     /*
643      * parse exponent
644      */
645     private static long parseExp(char[] in, int offset, int len){
646         long exp = 0;
647         offset++;
648         char c = in[offset];
649         len--;
650         boolean negexp = (c == '-');
651         // optional sign
652         if (negexp || c == '+') {
653             offset++;
654             c = in[offset];
655             len--;
656         }
657         if (len <= 0) // no exponent digits
658             throw new NumberFormatException("No exponent digits.");
659         // skip leading zeros in the exponent
660         while (len > 10 && (c=='0' || (Character.digit(c, 10) == 0))) {
661             offset++;
662             c = in[offset];
663             len--;
664         }
665         if (len > 10) // too many nonzero exponent digits
666             throw new NumberFormatException("Too many nonzero exponent digits.");
667         // c now holds first digit of exponent
668         for (;; len--) {
669             int v;
670             if (c >= '0' && c <= '9') {
671                 v = c - '0';
672             } else {
673                 v = Character.digit(c, 10);
674                 if (v < 0) // not a digit
675                     throw new NumberFormatException("Not a digit.");
676             }
677             exp = exp * 10 + v;
678             if (len == 1)
679                 break; // that was final character
680             offset++;
681             c = in[offset];
682         }
683         if (negexp) // apply sign
684             exp = -exp;
685         return exp;
686     }
687
688     /**
689      * Translates a character array representation of a
690      * {@code BigDecimal} into a {@code BigDecimal}, accepting the
691      * same sequence of characters as the {@link #BigDecimal(String)}
692      * constructor.
693      *
694      * @implNote If the sequence of characters is already available
695      * as a character array, using this constructor is faster than
696      * converting the {@code char} array to string and using the
697      * {@code BigDecimal(String)} constructor.
698      *
699      * @param in {@code char} array that is the source of characters.
700      * @throws NumberFormatException if {@code in} is not a valid
701      *         representation of a {@code BigDecimal}.
702      * @since  1.5
703      */
704     public BigDecimal(char[] in) {
705         this(in, 0, in.length);
706     }
707
708     /**
709      * Translates a character array representation of a
710      * {@code BigDecimal} into a {@code BigDecimal}, accepting the
711      * same sequence of characters as the {@link #BigDecimal(String)}
712      * constructor and with rounding according to the context
713      * settings.
714      *
715      * @implNote If the sequence of characters is already available
716      * as a character array, using this constructor is faster than
717      * converting the {@code char} array to string and using the
718      * {@code BigDecimal(String)} constructor.
719      *
720      * @param  in {@code char} array that is the source of characters.
721      * @param  mc the context to use.
722      * @throws ArithmeticException if the result is inexact but the
723      *         rounding mode is {@code UNNECESSARY}.
724      * @throws NumberFormatException if {@code in} is not a valid
725      *         representation of a {@code BigDecimal}.
726      * @since  1.5
727      */
728     public BigDecimal(char[] in, MathContext mc) {
729         this(in, 0, in.length, mc);
730     }
731
732     /**
733      * Translates the string representation of a {@code BigDecimal}
734      * into a {@code BigDecimal}.  The string representation consists
735      * of an optional sign, {@code '+'} (<code> '\u002B'</code>) or
736      * {@code '-'} (<code>'\u002D'</code>), followed by a sequence of
737      * zero or more decimal digits ("the integer"), optionally
738      * followed by a fraction, optionally followed by an exponent.
739      *
740      * <p>The fraction consists of a decimal point followed by zero
741      * or more decimal digits.  The string must contain at least one
742      * digit in either the integer or the fraction.  The number formed
743      * by the sign, the integer and the fraction is referred to as the
744      * <i>significand</i>.
745      *
746      * <p>The exponent consists of the character {@code 'e'}
747      * (<code>'\u0065'</code>) or {@code 'E'} (<code>'\u0045'</code>)
748      * followed by one or more decimal digits.  The value of the
749      * exponent must lie between -{@link Integer#MAX_VALUE} ({@link
750      * Integer#MIN_VALUE}+1) and {@link Integer#MAX_VALUE}, inclusive.
751      *
752      * <p>More formally, the strings this constructor accepts are
753      * described by the following grammar:
754      * <blockquote>
755      * <dl>
756      * <dt><i>BigDecimalString:</i>
757      * <dd><i>Sign<sub>opt</sub> Significand Exponent<sub>opt</sub></i>
758      * <dt><i>Sign:</i>
759      * <dd>{@code +}
760      * <dd>{@code -}
761      * <dt><i>Significand:</i>
762      * <dd><i>IntegerPart</i> {@code .} <i>FractionPart<sub>opt</sub></i>
763      * <dd>{@code .} <i>FractionPart</i>
764      * <dd><i>IntegerPart</i>
765      * <dt><i>IntegerPart:</i>
766      * <dd><i>Digits</i>
767      * <dt><i>FractionPart:</i>
768      * <dd><i>Digits</i>
769      * <dt><i>Exponent:</i>
770      * <dd><i>ExponentIndicator SignedInteger</i>
771      * <dt><i>ExponentIndicator:</i>
772      * <dd>{@code e}
773      * <dd>{@code E}
774      * <dt><i>SignedInteger:</i>
775      * <dd><i>Sign<sub>opt</sub> Digits</i>
776      * <dt><i>Digits:</i>
777      * <dd><i>Digit</i>
778      * <dd><i>Digits Digit</i>
779      * <dt><i>Digit:</i>
780      * <dd>any character for which {@link Character#isDigit}
781      * returns {@code true}, including 0, 1, 2 ...
782      * </dl>
783      * </blockquote>
784      *
785      * <p>The scale of the returned {@code BigDecimal} will be the
786      * number of digits in the fraction, or zero if the string
787      * contains no decimal point, subject to adjustment for any
788      * exponent; if the string contains an exponent, the exponent is
789      * subtracted from the scale.  The value of the resulting scale
790      * must lie between {@code Integer.MIN_VALUE} and
791      * {@code Integer.MAX_VALUE}, inclusive.
792      *
793      * <p>The character-to-digit mapping is provided by {@link
794      * java.lang.Character#digit} set to convert to radix 10.  The
795      * String may not contain any extraneous characters (whitespace,
796      * for example).
797      *
798      * <p><b>Examples:</b><br>
799      * The value of the returned {@code BigDecimal} is equal to
800      * <i>significand</i> &times; 10<sup>&nbsp;<i>exponent</i></sup>.
801      * For each string on the left, the resulting representation
802      * [{@code BigInteger}, {@code scale}] is shown on the right.
803      * <pre>
804      * "0"            [0,0]
805      * "0.00"         [0,2]
806      * "123"          [123,0]
807      * "-123"         [-123,0]
808      * "1.23E3"       [123,-1]
809      * "1.23E+3"      [123,-1]
810      * "12.3E+7"      [123,-6]
811      * "12.0"         [120,1]
812      * "12.3"         [123,1]
813      * "0.00123"      [123,5]
814      * "-1.23E-12"    [-123,14]
815      * "1234.5E-4"    [12345,5]
816      * "0E+7"         [0,-7]
817      * "-0"           [0,0]
818      * </pre>
819      *
820      * @apiNote For values other than {@code float} and
821      * {@code double} NaN and &plusmn;Infinity, this constructor is
822      * compatible with the values returned by {@link Float#toString}
823      * and {@link Double#toString}.  This is generally the preferred
824      * way to convert a {@code float} or {@code double} into a
825      * BigDecimal, as it doesn't suffer from the unpredictability of
826      * the {@link #BigDecimal(double)} constructor.
827      *
828      * @param val String representation of {@code BigDecimal}.
829      *
830      * @throws NumberFormatException if {@code val} is not a valid
831      *         representation of a {@code BigDecimal}.
832      */
833     public BigDecimal(String val) {
834         this(val.toCharArray(), 0, val.length());
835     }
836
837     /**
838      * Translates the string representation of a {@code BigDecimal}
839      * into a {@code BigDecimal}, accepting the same strings as the
840      * {@link #BigDecimal(String)} constructor, with rounding
841      * according to the context settings.
842      *
843      * @param  val string representation of a {@code BigDecimal}.
844      * @param  mc the context to use.
845      * @throws ArithmeticException if the result is inexact but the
846      *         rounding mode is {@code UNNECESSARY}.
847      * @throws NumberFormatException if {@code val} is not a valid
848      *         representation of a BigDecimal.
849      * @since  1.5
850      */
851     public BigDecimal(String val, MathContext mc) {
852         this(val.toCharArray(), 0, val.length(), mc);
853     }
854
855     /**
856      * Translates a {@code double} into a {@code BigDecimal} which
857      * is the exact decimal representation of the {@code double}'s
858      * binary floating-point value.  The scale of the returned
859      * {@code BigDecimal} is the smallest value such that
860      * <code>(10<sup>scale</sup> &times; val)</code> is an integer.
861      * <p>
862      * <b>Notes:</b>
863      * <ol>
864      * <li>
865      * The results of this constructor can be somewhat unpredictable.
866      * One might assume that writing {@code new BigDecimal(0.1)} in
867      * Java creates a {@code BigDecimal} which is exactly equal to
868      * 0.1 (an unscaled value of 1, with a scale of 1), but it is
869      * actually equal to
870      * 0.1000000000000000055511151231257827021181583404541015625.
871      * This is because 0.1 cannot be represented exactly as a
872      * {@code double} (or, for that matter, as a binary fraction of
873      * any finite length).  Thus, the value that is being passed
874      * <em>in</em> to the constructor is not exactly equal to 0.1,
875      * appearances notwithstanding.
876      *
877      * <li>
878      * The {@code String} constructor, on the other hand, is
879      * perfectly predictable: writing {@code new BigDecimal("0.1")}
880      * creates a {@code BigDecimal} which is <em>exactly</em> equal to
881      * 0.1, as one would expect.  Therefore, it is generally
882      * recommended that the {@linkplain #BigDecimal(String)
883      * String constructor} be used in preference to this one.
884      *
885      * <li>
886      * When a {@code double} must be used as a source for a
887      * {@code BigDecimal}, note that this constructor provides an
888      * exact conversion; it does not give the same result as
889      * converting the {@code double} to a {@code String} using the
890      * {@link Double#toString(double)} method and then using the
891      * {@link #BigDecimal(String)} constructor.  To get that result,
892      * use the {@code static} {@link #valueOf(double)} method.
893      * </ol>
894      *
895      * @param val {@code double} value to be converted to
896      *        {@code BigDecimal}.
897      * @throws NumberFormatException if {@code val} is infinite or NaN.
898      */
899     public BigDecimal(double val) {
900         this(val,MathContext.UNLIMITED);
901     }
902
903     /**
904      * Translates a {@code double} into a {@code BigDecimal}, with
905      * rounding according to the context settings.  The scale of the
906      * {@code BigDecimal} is the smallest value such that
907      * <code>(10<sup>scale</sup> &times; val)</code> is an integer.
908      *
909      * <p>The results of this constructor can be somewhat unpredictable
910      * and its use is generally not recommended; see the notes under
911      * the {@link #BigDecimal(double)} constructor.
912      *
913      * @param  val {@code double} value to be converted to
914      *         {@code BigDecimal}.
915      * @param  mc the context to use.
916      * @throws ArithmeticException if the result is inexact but the
917      *         RoundingMode is UNNECESSARY.
918      * @throws NumberFormatException if {@code val} is infinite or NaN.
919      * @since  1.5
920      */
921     public BigDecimal(double val, MathContext mc) {
922         if (Double.isInfinite(val) || Double.isNaN(val))
923             throw new NumberFormatException("Infinite or NaN");
924         // Translate the double into sign, exponent and significand, according
925         // to the formulae in JLS, Section 20.10.22.
926         long valBits = Double.doubleToLongBits(val);
927         int sign = ((valBits >> 63) == 0 ? 1 : -1);
928         int exponent = (int) ((valBits >> 52) & 0x7ffL);
929         long significand = (exponent == 0
930                 ? (valBits & ((1L << 52) - 1)) << 1
931                 : (valBits & ((1L << 52) - 1)) | (1L << 52));
932         exponent -= 1075;
933         // At this point, val == sign * significand * 2**exponent.
934
935         /*
936          * Special case zero to supress nonterminating normalization and bogus
937          * scale calculation.
938          */
939         if (significand == 0) {
940             this.intVal = BigInteger.ZERO;
941             this.scale = 0;
942             this.intCompact = 0;
943             this.precision = 1;
944             return;
945         }
946         // Normalize
947         while ((significand & 1) == 0) { // i.e., significand is even
948             significand >>= 1;
949             exponent++;
950         }
951         int scl = 0;
952         // Calculate intVal and scale
953         BigInteger rb;
954         long compactVal = sign * significand;
955         if (exponent == 0) {
956             rb = (compactVal == INFLATED) ? INFLATED_BIGINT : null;
957         } else {
958             if (exponent < 0) {
959                 rb = BigInteger.valueOf(5).pow(-exponent).multiply(compactVal);
960                 scl = -exponent;
961             } else { //  (exponent > 0)
962                 rb = BigInteger.TWO.pow(exponent).multiply(compactVal);
963             }
964             compactVal = compactValFor(rb);
965         }
966         int prec = 0;
967         int mcp = mc.precision;
968         if (mcp > 0) { // do rounding
969             int mode = mc.roundingMode.oldMode;
970             int drop;
971             if (compactVal == INFLATED) {
972                 prec = bigDigitLength(rb);
973                 drop = prec - mcp;
974                 while (drop > 0) {
975                     scl = checkScaleNonZero((long) scl - drop);
976                     rb = divideAndRoundByTenPow(rb, drop, mode);
977                     compactVal = compactValFor(rb);
978                     if (compactVal != INFLATED) {
979                         break;
980                     }
981                     prec = bigDigitLength(rb);
982                     drop = prec - mcp;
983                 }
984             }
985             if (compactVal != INFLATED) {
986                 prec = longDigitLength(compactVal);
987                 drop = prec - mcp;
988                 while (drop > 0) {
989                     scl = checkScaleNonZero((long) scl - drop);
990                     compactVal = divideAndRound(compactVal, LONG_TEN_POWERS_TABLE[drop], mc.roundingMode.oldMode);
991                     prec = longDigitLength(compactVal);
992                     drop = prec - mcp;
993                 }
994                 rb = null;
995             }
996         }
997         this.intVal = rb;
998         this.intCompact = compactVal;
999         this.scale = scl;
1000         this.precision = prec;
1001     }
1002
1003     /**
1004      * Translates a {@code BigInteger} into a {@code BigDecimal}.
1005      * The scale of the {@code BigDecimal} is zero.
1006      *
1007      * @param val {@code BigInteger} value to be converted to
1008      *            {@code BigDecimal}.
1009      */
1010     public BigDecimal(BigInteger val) {
1011         scale = 0;
1012         intVal = val;
1013         intCompact = compactValFor(val);
1014     }
1015
1016     /**
1017      * Translates a {@code BigInteger} into a {@code BigDecimal}
1018      * rounding according to the context settings.  The scale of the
1019      * {@code BigDecimal} is zero.
1020      *
1021      * @param val {@code BigInteger} value to be converted to
1022      *            {@code BigDecimal}.
1023      * @param  mc the context to use.
1024      * @throws ArithmeticException if the result is inexact but the
1025      *         rounding mode is {@code UNNECESSARY}.
1026      * @since  1.5
1027      */
1028     public BigDecimal(BigInteger val, MathContext mc) {
1029         this(val,0,mc);
1030     }
1031
1032     /**
1033      * Translates a {@code BigInteger} unscaled value and an
1034      * {@code int} scale into a {@code BigDecimal}.  The value of
1035      * the {@code BigDecimal} is
1036      * <code>(unscaledVal &times; 10<sup>-scale</sup>)</code>.
1037      *
1038      * @param unscaledVal unscaled value of the {@code BigDecimal}.
1039      * @param scale scale of the {@code BigDecimal}.
1040      */
1041     public BigDecimal(BigInteger unscaledVal, int scale) {
1042         // Negative scales are now allowed
1043         this.intVal = unscaledVal;
1044         this.intCompact = compactValFor(unscaledVal);
1045         this.scale = scale;
1046     }
1047
1048     /**
1049      * Translates a {@code BigInteger} unscaled value and an
1050      * {@code int} scale into a {@code BigDecimal}, with rounding
1051      * according to the context settings.  The value of the
1052      * {@code BigDecimal} is <code>(unscaledVal &times;
1053      * 10<sup>-scale</sup>)</code>, rounded according to the
1054      * {@code precision} and rounding mode settings.
1055      *
1056      * @param  unscaledVal unscaled value of the {@code BigDecimal}.
1057      * @param  scale scale of the {@code BigDecimal}.
1058      * @param  mc the context to use.
1059      * @throws ArithmeticException if the result is inexact but the
1060      *         rounding mode is {@code UNNECESSARY}.
1061      * @since  1.5
1062      */
1063     public BigDecimal(BigInteger unscaledVal, int scale, MathContext mc) {
1064         long compactVal = compactValFor(unscaledVal);
1065         int mcp = mc.precision;
1066         int prec = 0;
1067         if (mcp > 0) { // do rounding
1068             int mode = mc.roundingMode.oldMode;
1069             if (compactVal == INFLATED) {
1070                 prec = bigDigitLength(unscaledVal);
1071                 int drop = prec - mcp;
1072                 while (drop > 0) {
1073                     scale = checkScaleNonZero((long) scale - drop);
1074                     unscaledVal = divideAndRoundByTenPow(unscaledVal, drop, mode);
1075                     compactVal = compactValFor(unscaledVal);
1076                     if (compactVal != INFLATED) {
1077                         break;
1078                     }
1079                     prec = bigDigitLength(unscaledVal);
1080                     drop = prec - mcp;
1081                 }
1082             }
1083             if (compactVal != INFLATED) {
1084                 prec = longDigitLength(compactVal);
1085                 int drop = prec - mcp;     // drop can't be more than 18
1086                 while (drop > 0) {
1087                     scale = checkScaleNonZero((long) scale - drop);
1088                     compactVal = divideAndRound(compactVal, LONG_TEN_POWERS_TABLE[drop], mode);
1089                     prec = longDigitLength(compactVal);
1090                     drop = prec - mcp;
1091                 }
1092                 unscaledVal = null;
1093             }
1094         }
1095         this.intVal = unscaledVal;
1096         this.intCompact = compactVal;
1097         this.scale = scale;
1098         this.precision = prec;
1099     }
1100
1101     /**
1102      * Translates an {@code int} into a {@code BigDecimal}.  The
1103      * scale of the {@code BigDecimal} is zero.
1104      *
1105      * @param val {@code int} value to be converted to
1106      *            {@code BigDecimal}.
1107      * @since  1.5
1108      */
1109     public BigDecimal(int val) {
1110         this.intCompact = val;
1111         this.scale = 0;
1112         this.intVal = null;
1113     }
1114
1115     /**
1116      * Translates an {@code int} into a {@code BigDecimal}, with
1117      * rounding according to the context settings.  The scale of the
1118      * {@code BigDecimal}, before any rounding, is zero.
1119      *
1120      * @param  val {@code int} value to be converted to {@code BigDecimal}.
1121      * @param  mc the context to use.
1122      * @throws ArithmeticException if the result is inexact but the
1123      *         rounding mode is {@code UNNECESSARY}.
1124      * @since  1.5
1125      */
1126     public BigDecimal(int val, MathContext mc) {
1127         int mcp = mc.precision;
1128         long compactVal = val;
1129         int scl = 0;
1130         int prec = 0;
1131         if (mcp > 0) { // do rounding
1132             prec = longDigitLength(compactVal);
1133             int drop = prec - mcp; // drop can't be more than 18
1134             while (drop > 0) {
1135                 scl = checkScaleNonZero((long) scl - drop);
1136                 compactVal = divideAndRound(compactVal, LONG_TEN_POWERS_TABLE[drop], mc.roundingMode.oldMode);
1137                 prec = longDigitLength(compactVal);
1138                 drop = prec - mcp;
1139             }
1140         }
1141         this.intVal = null;
1142         this.intCompact = compactVal;
1143         this.scale = scl;
1144         this.precision = prec;
1145     }
1146
1147     /**
1148      * Translates a {@code long} into a {@code BigDecimal}.  The
1149      * scale of the {@code BigDecimal} is zero.
1150      *
1151      * @param val {@code long} value to be converted to {@code BigDecimal}.
1152      * @since  1.5
1153      */
1154     public BigDecimal(long val) {
1155         this.intCompact = val;
1156         this.intVal = (val == INFLATED) ? INFLATED_BIGINT : null;
1157         this.scale = 0;
1158     }
1159
1160     /**
1161      * Translates a {@code long} into a {@code BigDecimal}, with
1162      * rounding according to the context settings.  The scale of the
1163      * {@code BigDecimal}, before any rounding, is zero.
1164      *
1165      * @param  val {@code long} value to be converted to {@code BigDecimal}.
1166      * @param  mc the context to use.
1167      * @throws ArithmeticException if the result is inexact but the
1168      *         rounding mode is {@code UNNECESSARY}.
1169      * @since  1.5
1170      */
1171     public BigDecimal(long val, MathContext mc) {
1172         int mcp = mc.precision;
1173         int mode = mc.roundingMode.oldMode;
1174         int prec = 0;
1175         int scl = 0;
1176         BigInteger rb = (val == INFLATED) ? INFLATED_BIGINT : null;
1177         if (mcp > 0) { // do rounding
1178             if (val == INFLATED) {
1179                 prec = 19;
1180                 int drop = prec - mcp;
1181                 while (drop > 0) {
1182                     scl = checkScaleNonZero((long) scl - drop);
1183                     rb = divideAndRoundByTenPow(rb, drop, mode);
1184                     val = compactValFor(rb);
1185                     if (val != INFLATED) {
1186                         break;
1187                     }
1188                     prec = bigDigitLength(rb);
1189                     drop = prec - mcp;
1190                 }
1191             }
1192             if (val != INFLATED) {
1193                 prec = longDigitLength(val);
1194                 int drop = prec - mcp;
1195                 while (drop > 0) {
1196                     scl = checkScaleNonZero((long) scl - drop);
1197                     val = divideAndRound(val, LONG_TEN_POWERS_TABLE[drop], mc.roundingMode.oldMode);
1198                     prec = longDigitLength(val);
1199                     drop = prec - mcp;
1200                 }
1201                 rb = null;
1202             }
1203         }
1204         this.intVal = rb;
1205         this.intCompact = val;
1206         this.scale = scl;
1207         this.precision = prec;
1208     }
1209
1210     // Static Factory Methods
1211
1212     /**
1213      * Translates a {@code long} unscaled value and an
1214      * {@code int} scale into a {@code BigDecimal}.
1215      *
1216      * @apiNote This static factory method is provided in preference
1217      * to a ({@code long}, {@code int}) constructor because it allows
1218      * for reuse of frequently used {@code BigDecimal} values.
1219      *
1220      * @param unscaledVal unscaled value of the {@code BigDecimal}.
1221      * @param scale scale of the {@code BigDecimal}.
1222      * @return a {@code BigDecimal} whose value is
1223      *         <code>(unscaledVal &times; 10<sup>-scale</sup>)</code>.
1224      */
1225     public static BigDecimal valueOf(long unscaledVal, int scale) {
1226         if (scale == 0)
1227             return valueOf(unscaledVal);
1228         else if (unscaledVal == 0) {
1229             return zeroValueOf(scale);
1230         }
1231         return new BigDecimal(unscaledVal == INFLATED ?
1232                               INFLATED_BIGINT : null,
1233                               unscaledVal, scale, 0);
1234     }
1235
1236     /**
1237      * Translates a {@code long} value into a {@code BigDecimal}
1238      * with a scale of zero.
1239      *
1240      * @apiNote This static factory method is provided in preference
1241      * to a ({@code long}) constructor because it allows for reuse of
1242      * frequently used {@code BigDecimal} values.
1243      *
1244      * @param val value of the {@code BigDecimal}.
1245      * @return a {@code BigDecimal} whose value is {@code val}.
1246      */
1247     public static BigDecimal valueOf(long val) {
1248         if (val >= 0 && val < ZERO_THROUGH_TEN.length)
1249             return ZERO_THROUGH_TEN[(int)val];
1250         else if (val != INFLATED)
1251             return new BigDecimal(null, val, 0, 0);
1252         return new BigDecimal(INFLATED_BIGINT, val, 0, 0);
1253     }
1254
1255     static BigDecimal valueOf(long unscaledVal, int scale, int prec) {
1256         if (scale == 0 && unscaledVal >= 0 && unscaledVal < ZERO_THROUGH_TEN.length) {
1257             return ZERO_THROUGH_TEN[(int) unscaledVal];
1258         } else if (unscaledVal == 0) {
1259             return zeroValueOf(scale);
1260         }
1261         return new BigDecimal(unscaledVal == INFLATED ? INFLATED_BIGINT : null,
1262                 unscaledVal, scale, prec);
1263     }
1264
1265     static BigDecimal valueOf(BigInteger intVal, int scale, int prec) {
1266         long val = compactValFor(intVal);
1267         if (val == 0) {
1268             return zeroValueOf(scale);
1269         } else if (scale == 0 && val >= 0 && val < ZERO_THROUGH_TEN.length) {
1270             return ZERO_THROUGH_TEN[(int) val];
1271         }
1272         return new BigDecimal(intVal, val, scale, prec);
1273     }
1274
1275     static BigDecimal zeroValueOf(int scale) {
1276         if (scale >= 0 && scale < ZERO_SCALED_BY.length)
1277             return ZERO_SCALED_BY[scale];
1278         else
1279             return new BigDecimal(BigInteger.ZERO, 0, scale, 1);
1280     }
1281
1282     /**
1283      * Translates a {@code double} into a {@code BigDecimal}, using
1284      * the {@code double}'s canonical string representation provided
1285      * by the {@link Double#toString(double)} method.
1286      *
1287      * @apiNote This is generally the preferred way to convert a
1288      * {@code double} (or {@code float}) into a {@code BigDecimal}, as
1289      * the value returned is equal to that resulting from constructing
1290      * a {@code BigDecimal} from the result of using {@link
1291      * Double#toString(double)}.
1292      *
1293      * @param  val {@code double} to convert to a {@code BigDecimal}.
1294      * @return a {@code BigDecimal} whose value is equal to or approximately
1295      *         equal to the value of {@code val}.
1296      * @throws NumberFormatException if {@code val} is infinite or NaN.
1297      * @since  1.5
1298      */
1299     public static BigDecimal valueOf(double val) {
1300         // Reminder: a zero double returns '0.0', so we cannot fastpath
1301         // to use the constant ZERO.  This might be important enough to
1302         // justify a factory approach, a cache, or a few private
1303         // constants, later.
1304         return new BigDecimal(Double.toString(val));
1305     }
1306
1307     // Arithmetic Operations
1308     /**
1309      * Returns a {@code BigDecimal} whose value is {@code (this +
1310      * augend)}, and whose scale is {@code max(this.scale(),
1311      * augend.scale())}.
1312      *
1313      * @param  augend value to be added to this {@code BigDecimal}.
1314      * @return {@code this + augend}
1315      */
1316     public BigDecimal add(BigDecimal augend) {
1317         if (this.intCompact != INFLATED) {
1318             if ((augend.intCompact != INFLATED)) {
1319                 return add(this.intCompact, this.scale, augend.intCompact, augend.scale);
1320             } else {
1321                 return add(this.intCompact, this.scale, augend.intVal, augend.scale);
1322             }
1323         } else {
1324             if ((augend.intCompact != INFLATED)) {
1325                 return add(augend.intCompact, augend.scale, this.intVal, this.scale);
1326             } else {
1327                 return add(this.intVal, this.scale, augend.intVal, augend.scale);
1328             }
1329         }
1330     }
1331
1332     /**
1333      * Returns a {@code BigDecimal} whose value is {@code (this + augend)},
1334      * with rounding according to the context settings.
1335      *
1336      * If either number is zero and the precision setting is nonzero then
1337      * the other number, rounded if necessary, is used as the result.
1338      *
1339      * @param  augend value to be added to this {@code BigDecimal}.
1340      * @param  mc the context to use.
1341      * @return {@code this + augend}, rounded as necessary.
1342      * @throws ArithmeticException if the result is inexact but the
1343      *         rounding mode is {@code UNNECESSARY}.
1344      * @since  1.5
1345      */
1346     public BigDecimal add(BigDecimal augend, MathContext mc) {
1347         if (mc.precision == 0)
1349         BigDecimal lhs = this;
1350
1351         // If either number is zero then the other number, rounded and
1352         // scaled if necessary, is used as the result.
1353         {
1354             boolean lhsIsZero = lhs.signum() == 0;
1355             boolean augendIsZero = augend.signum() == 0;
1356
1357             if (lhsIsZero || augendIsZero) {
1358                 int preferredScale = Math.max(lhs.scale(), augend.scale());
1359                 BigDecimal result;
1360
1361                 if (lhsIsZero && augendIsZero)
1362                     return zeroValueOf(preferredScale);
1363                 result = lhsIsZero ? doRound(augend, mc) : doRound(lhs, mc);
1364
1365                 if (result.scale() == preferredScale)
1366                     return result;
1367                 else if (result.scale() > preferredScale) {
1368                     return stripZerosToMatchScale(result.intVal, result.intCompact, result.scale, preferredScale);
1369                 } else { // result.scale < preferredScale
1370                     int precisionDiff = mc.precision - result.precision();
1371                     int scaleDiff     = preferredScale - result.scale();
1372
1373                     if (precisionDiff >= scaleDiff)
1374                         return result.setScale(preferredScale); // can achieve target scale
1375                     else
1376                         return result.setScale(result.scale() + precisionDiff);
1377                 }
1378             }
1379         }
1380
1381         long padding = (long) lhs.scale - augend.scale;
1382         if (padding != 0) { // scales differ; alignment needed
1383             BigDecimal arg[] = preAlign(lhs, augend, padding, mc);
1384             matchScale(arg);
1385             lhs = arg[0];
1386             augend = arg[1];
1387         }
1388         return doRound(lhs.inflated().add(augend.inflated()), lhs.scale, mc);
1389     }
1390
1391     /**
1392      * Returns an array of length two, the sum of whose entries is
1393      * equal to the rounded sum of the {@code BigDecimal} arguments.
1394      *
1395      * <p>If the digit positions of the arguments have a sufficient
1396      * gap between them, the value smaller in magnitude can be
1397      * condensed into a {@literal "sticky bit"} and the end result will
1398      * round the same way <em>if</em> the precision of the final
1399      * result does not include the high order digit of the small
1400      * magnitude operand.
1401      *
1402      * <p>Note that while strictly speaking this is an optimization,
1403      * it makes a much wider range of additions practical.
1404      *
1405      * <p>This corresponds to a pre-shift operation in a fixed
1406      * precision floating-point adder; this method is complicated by
1407      * variable precision of the result as determined by the
1408      * MathContext.  A more nuanced operation could implement a
1409      * {@literal "right shift"} on the smaller magnitude operand so
1410      * that the number of digits of the smaller operand could be
1411      * reduced even though the significands partially overlapped.
1412      */
1413     private BigDecimal[] preAlign(BigDecimal lhs, BigDecimal augend, long padding, MathContext mc) {
1414         assert padding != 0;
1415         BigDecimal big;
1416         BigDecimal small;
1417
1418         if (padding < 0) { // lhs is big; augend is small
1419             big = lhs;
1420             small = augend;
1421         } else { // lhs is small; augend is big
1422             big = augend;
1423             small = lhs;
1424         }
1425
1426         /*
1427          * This is the estimated scale of an ulp of the result; it assumes that
1428          * the result doesn't have a carry-out on a true add (e.g. 999 + 1 =>
1429          * 1000) or any subtractive cancellation on borrowing (e.g. 100 - 1.2 =>
1430          * 98.8)
1431          */
1432         long estResultUlpScale = (long) big.scale - big.precision() + mc.precision;
1433
1434         /*
1435          * The low-order digit position of big is big.scale().  This
1436          * is true regardless of whether big has a positive or
1437          * negative scale.  The high-order digit position of small is
1438          * small.scale - (small.precision() - 1).  To do the full
1439          * condensation, the digit positions of big and small must be
1440          * disjoint *and* the digit positions of small should not be
1441          * directly visible in the result.
1442          */
1443         long smallHighDigitPos = (long) small.scale - small.precision() + 1;
1444         if (smallHighDigitPos > big.scale + 2 && // big and small disjoint
1445             smallHighDigitPos > estResultUlpScale + 2) { // small digits not visible
1446             small = BigDecimal.valueOf(small.signum(), this.checkScale(Math.max(big.scale, estResultUlpScale) + 3));
1447         }
1448
1449         // Since addition is symmetric, preserving input order in
1450         // returned operands doesn't matter
1451         BigDecimal[] result = {big, small};
1452         return result;
1453     }
1454
1455     /**
1456      * Returns a {@code BigDecimal} whose value is {@code (this -
1457      * subtrahend)}, and whose scale is {@code max(this.scale(),
1458      * subtrahend.scale())}.
1459      *
1460      * @param  subtrahend value to be subtracted from this {@code BigDecimal}.
1461      * @return {@code this - subtrahend}
1462      */
1463     public BigDecimal subtract(BigDecimal subtrahend) {
1464         if (this.intCompact != INFLATED) {
1465             if ((subtrahend.intCompact != INFLATED)) {
1466                 return add(this.intCompact, this.scale, -subtrahend.intCompact, subtrahend.scale);
1467             } else {
1468                 return add(this.intCompact, this.scale, subtrahend.intVal.negate(), subtrahend.scale);
1469             }
1470         } else {
1471             if ((subtrahend.intCompact != INFLATED)) {
1472                 // Pair of subtrahend values given before pair of
1473                 // values from this BigDecimal to avoid need for
1475                 return add(-subtrahend.intCompact, subtrahend.scale, this.intVal, this.scale);
1476             } else {
1477                 return add(this.intVal, this.scale, subtrahend.intVal.negate(), subtrahend.scale);
1478             }
1479         }
1480     }
1481
1482     /**
1483      * Returns a {@code BigDecimal} whose value is {@code (this - subtrahend)},
1484      * with rounding according to the context settings.
1485      *
1486      * If {@code subtrahend} is zero then this, rounded if necessary, is used as the
1487      * result.  If this is zero then the result is {@code subtrahend.negate(mc)}.
1488      *
1489      * @param  subtrahend value to be subtracted from this {@code BigDecimal}.
1490      * @param  mc the context to use.
1491      * @return {@code this - subtrahend}, rounded as necessary.
1492      * @throws ArithmeticException if the result is inexact but the
1493      *         rounding mode is {@code UNNECESSARY}.
1494      * @since  1.5
1495      */
1496     public BigDecimal subtract(BigDecimal subtrahend, MathContext mc) {
1497         if (mc.precision == 0)
1498             return subtract(subtrahend);
1499         // share the special rounding code in add()
1500         return add(subtrahend.negate(), mc);
1501     }
1502
1503     /**
1504      * Returns a {@code BigDecimal} whose value is <code>(this &times;
1505      * multiplicand)</code>, and whose scale is {@code (this.scale() +
1506      * multiplicand.scale())}.
1507      *
1508      * @param  multiplicand value to be multiplied by this {@code BigDecimal}.
1509      * @return {@code this * multiplicand}
1510      */
1511     public BigDecimal multiply(BigDecimal multiplicand) {
1512         int productScale = checkScale((long) scale + multiplicand.scale);
1513         if (this.intCompact != INFLATED) {
1514             if ((multiplicand.intCompact != INFLATED)) {
1515                 return multiply(this.intCompact, multiplicand.intCompact, productScale);
1516             } else {
1517                 return multiply(this.intCompact, multiplicand.intVal, productScale);
1518             }
1519         } else {
1520             if ((multiplicand.intCompact != INFLATED)) {
1521                 return multiply(multiplicand.intCompact, this.intVal, productScale);
1522             } else {
1523                 return multiply(this.intVal, multiplicand.intVal, productScale);
1524             }
1525         }
1526     }
1527
1528     /**
1529      * Returns a {@code BigDecimal} whose value is <code>(this &times;
1530      * multiplicand)</code>, with rounding according to the context settings.
1531      *
1532      * @param  multiplicand value to be multiplied by this {@code BigDecimal}.
1533      * @param  mc the context to use.
1534      * @return {@code this * multiplicand}, rounded as necessary.
1535      * @throws ArithmeticException if the result is inexact but the
1536      *         rounding mode is {@code UNNECESSARY}.
1537      * @since  1.5
1538      */
1539     public BigDecimal multiply(BigDecimal multiplicand, MathContext mc) {
1540         if (mc.precision == 0)
1541             return multiply(multiplicand);
1542         int productScale = checkScale((long) scale + multiplicand.scale);
1543         if (this.intCompact != INFLATED) {
1544             if ((multiplicand.intCompact != INFLATED)) {
1545                 return multiplyAndRound(this.intCompact, multiplicand.intCompact, productScale, mc);
1546             } else {
1547                 return multiplyAndRound(this.intCompact, multiplicand.intVal, productScale, mc);
1548             }
1549         } else {
1550             if ((multiplicand.intCompact != INFLATED)) {
1551                 return multiplyAndRound(multiplicand.intCompact, this.intVal, productScale, mc);
1552             } else {
1553                 return multiplyAndRound(this.intVal, multiplicand.intVal, productScale, mc);
1554             }
1555         }
1556     }
1557
1558     /**
1559      * Returns a {@code BigDecimal} whose value is {@code (this /
1560      * divisor)}, and whose scale is as specified.  If rounding must
1561      * be performed to generate a result with the specified scale, the
1562      * specified rounding mode is applied.
1563      *
1564      * @deprecated The method {@link #divide(BigDecimal, int, RoundingMode)}
1565      * should be used in preference to this legacy method.
1566      *
1567      * @param  divisor value by which this {@code BigDecimal} is to be divided.
1568      * @param  scale scale of the {@code BigDecimal} quotient to be returned.
1569      * @param  roundingMode rounding mode to apply.
1570      * @return {@code this / divisor}
1571      * @throws ArithmeticException if {@code divisor} is zero,
1572      *         {@code roundingMode==ROUND_UNNECESSARY} and
1573      *         the specified scale is insufficient to represent the result
1574      *         of the division exactly.
1575      * @throws IllegalArgumentException if {@code roundingMode} does not
1576      *         represent a valid rounding mode.
1577      * @see    #ROUND_UP
1578      * @see    #ROUND_DOWN
1579      * @see    #ROUND_CEILING
1580      * @see    #ROUND_FLOOR
1581      * @see    #ROUND_HALF_UP
1582      * @see    #ROUND_HALF_DOWN
1583      * @see    #ROUND_HALF_EVEN
1584      * @see    #ROUND_UNNECESSARY
1585      */
1586     @Deprecated(since="9")
1587     public BigDecimal divide(BigDecimal divisor, int scale, int roundingMode) {
1588         if (roundingMode < ROUND_UP || roundingMode > ROUND_UNNECESSARY)
1589             throw new IllegalArgumentException("Invalid rounding mode");
1590         if (this.intCompact != INFLATED) {
1591             if ((divisor.intCompact != INFLATED)) {
1592                 return divide(this.intCompact, this.scale, divisor.intCompact, divisor.scale, scale, roundingMode);
1593             } else {
1594                 return divide(this.intCompact, this.scale, divisor.intVal, divisor.scale, scale, roundingMode);
1595             }
1596         } else {
1597             if ((divisor.intCompact != INFLATED)) {
1598                 return divide(this.intVal, this.scale, divisor.intCompact, divisor.scale, scale, roundingMode);
1599             } else {
1600                 return divide(this.intVal, this.scale, divisor.intVal, divisor.scale, scale, roundingMode);
1601             }
1602         }
1603     }
1604
1605     /**
1606      * Returns a {@code BigDecimal} whose value is {@code (this /
1607      * divisor)}, and whose scale is as specified.  If rounding must
1608      * be performed to generate a result with the specified scale, the
1609      * specified rounding mode is applied.
1610      *
1611      * @param  divisor value by which this {@code BigDecimal} is to be divided.
1612      * @param  scale scale of the {@code BigDecimal} quotient to be returned.
1613      * @param  roundingMode rounding mode to apply.
1614      * @return {@code this / divisor}
1615      * @throws ArithmeticException if {@code divisor} is zero,
1616      *         {@code roundingMode==RoundingMode.UNNECESSARY} and
1617      *         the specified scale is insufficient to represent the result
1618      *         of the division exactly.
1619      * @since 1.5
1620      */
1621     public BigDecimal divide(BigDecimal divisor, int scale, RoundingMode roundingMode) {
1622         return divide(divisor, scale, roundingMode.oldMode);
1623     }
1624
1625     /**
1626      * Returns a {@code BigDecimal} whose value is {@code (this /
1627      * divisor)}, and whose scale is {@code this.scale()}.  If
1628      * rounding must be performed to generate a result with the given
1629      * scale, the specified rounding mode is applied.
1630      *
1631      * @deprecated The method {@link #divide(BigDecimal, RoundingMode)}
1632      * should be used in preference to this legacy method.
1633      *
1634      * @param  divisor value by which this {@code BigDecimal} is to be divided.
1635      * @param  roundingMode rounding mode to apply.
1636      * @return {@code this / divisor}
1637      * @throws ArithmeticException if {@code divisor==0}, or
1638      *         {@code roundingMode==ROUND_UNNECESSARY} and
1639      *         {@code this.scale()} is insufficient to represent the result
1640      *         of the division exactly.
1641      * @throws IllegalArgumentException if {@code roundingMode} does not
1642      *         represent a valid rounding mode.
1643      * @see    #ROUND_UP
1644      * @see    #ROUND_DOWN
1645      * @see    #ROUND_CEILING
1646      * @see    #ROUND_FLOOR
1647      * @see    #ROUND_HALF_UP
1648      * @see    #ROUND_HALF_DOWN
1649      * @see    #ROUND_HALF_EVEN
1650      * @see    #ROUND_UNNECESSARY
1651      */
1652     @Deprecated(since="9")
1653     public BigDecimal divide(BigDecimal divisor, int roundingMode) {
1654         return this.divide(divisor, scale, roundingMode);
1655     }
1656
1657     /**
1658      * Returns a {@code BigDecimal} whose value is {@code (this /
1659      * divisor)}, and whose scale is {@code this.scale()}.  If
1660      * rounding must be performed to generate a result with the given
1661      * scale, the specified rounding mode is applied.
1662      *
1663      * @param  divisor value by which this {@code BigDecimal} is to be divided.
1664      * @param  roundingMode rounding mode to apply.
1665      * @return {@code this / divisor}
1666      * @throws ArithmeticException if {@code divisor==0}, or
1667      *         {@code roundingMode==RoundingMode.UNNECESSARY} and
1668      *         {@code this.scale()} is insufficient to represent the result
1669      *         of the division exactly.
1670      * @since 1.5
1671      */
1672     public BigDecimal divide(BigDecimal divisor, RoundingMode roundingMode) {
1673         return this.divide(divisor, scale, roundingMode.oldMode);
1674     }
1675
1676     /**
1677      * Returns a {@code BigDecimal} whose value is {@code (this /
1678      * divisor)}, and whose preferred scale is {@code (this.scale() -
1679      * divisor.scale())}; if the exact quotient cannot be
1680      * represented (because it has a non-terminating decimal
1681      * expansion) an {@code ArithmeticException} is thrown.
1682      *
1683      * @param  divisor value by which this {@code BigDecimal} is to be divided.
1684      * @throws ArithmeticException if the exact quotient does not have a
1685      *         terminating decimal expansion
1686      * @return {@code this / divisor}
1687      * @since 1.5
1688      * @author Joseph D. Darcy
1689      */
1690     public BigDecimal divide(BigDecimal divisor) {
1691         /*
1692          * Handle zero cases first.
1693          */
1694         if (divisor.signum() == 0) {   // x/0
1695             if (this.signum() == 0)    // 0/0
1696                 throw new ArithmeticException("Division undefined");  // NaN
1697             throw new ArithmeticException("Division by zero");
1698         }
1699
1700         // Calculate preferred scale
1701         int preferredScale = saturateLong((long) this.scale - divisor.scale);
1702
1703         if (this.signum() == 0) // 0/y
1704             return zeroValueOf(preferredScale);
1705         else {
1706             /*
1707              * If the quotient this/divisor has a terminating decimal
1708              * expansion, the expansion can have no more than
1709              * (a.precision() + ceil(10*b.precision)/3) digits.
1710              * Therefore, create a MathContext object with this
1711              * precision and do a divide with the UNNECESSARY rounding
1712              * mode.
1713              */
1714             MathContext mc = new MathContext( (int)Math.min(this.precision() +
1715                                                             (long)Math.ceil(10.0*divisor.precision()/3.0),
1716                                                             Integer.MAX_VALUE),
1717                                               RoundingMode.UNNECESSARY);
1718             BigDecimal quotient;
1719             try {
1720                 quotient = this.divide(divisor, mc);
1721             } catch (ArithmeticException e) {
1722                 throw new ArithmeticException("Non-terminating decimal expansion; " +
1723                                               "no exact representable decimal result.");
1724             }
1725
1726             int quotientScale = quotient.scale();
1727
1728             // divide(BigDecimal, mc) tries to adjust the quotient to
1729             // the desired one by removing trailing zeros; since the
1730             // exact divide method does not have an explicit digit
1731             // limit, we can add zeros too.
1732             if (preferredScale > quotientScale)
1733                 return quotient.setScale(preferredScale, ROUND_UNNECESSARY);
1734
1735             return quotient;
1736         }
1737     }
1738
1739     /**
1740      * Returns a {@code BigDecimal} whose value is {@code (this /
1741      * divisor)}, with rounding according to the context settings.
1742      *
1743      * @param  divisor value by which this {@code BigDecimal} is to be divided.
1744      * @param  mc the context to use.
1745      * @return {@code this / divisor}, rounded as necessary.
1746      * @throws ArithmeticException if the result is inexact but the
1747      *         rounding mode is {@code UNNECESSARY} or
1748      *         {@code mc.precision == 0} and the quotient has a
1749      *         non-terminating decimal expansion.
1750      * @since  1.5
1751      */
1752     public BigDecimal divide(BigDecimal divisor, MathContext mc) {
1753         int mcp = mc.precision;
1754         if (mcp == 0)
1755             return divide(divisor);
1756
1757         BigDecimal dividend = this;
1758         long preferredScale = (long)dividend.scale - divisor.scale;
1759         // Now calculate the answer.  We use the existing
1760         // divide-and-round method, but as this rounds to scale we have
1761         // to normalize the values here to achieve the desired result.
1762         // For x/y we first handle y=0 and x=0, and then normalize x and
1763         // y to give x' and y' with the following constraints:
1764         //   (a) 0.1 <= x' < 1
1765         //   (b)  x' <= y' < 10*x'
1766         // Dividing x'/y' with the required scale set to mc.precision then
1767         // will give a result in the range 0.1 to 1 rounded to exactly
1768         // the right number of digits (except in the case of a result of
1769         // 1.000... which can arise when x=y, or when rounding overflows
1770         // The 1.000... case will reduce properly to 1.
1771         if (divisor.signum() == 0) {      // x/0
1772             if (dividend.signum() == 0)    // 0/0
1773                 throw new ArithmeticException("Division undefined");  // NaN
1774             throw new ArithmeticException("Division by zero");
1775         }
1776         if (dividend.signum() == 0) // 0/y
1777             return zeroValueOf(saturateLong(preferredScale));
1778         int xscale = dividend.precision();
1779         int yscale = divisor.precision();
1780         if(dividend.intCompact!=INFLATED) {
1781             if(divisor.intCompact!=INFLATED) {
1782                 return divide(dividend.intCompact, xscale, divisor.intCompact, yscale, preferredScale, mc);
1783             } else {
1784                 return divide(dividend.intCompact, xscale, divisor.intVal, yscale, preferredScale, mc);
1785             }
1786         } else {
1787             if(divisor.intCompact!=INFLATED) {
1788                 return divide(dividend.intVal, xscale, divisor.intCompact, yscale, preferredScale, mc);
1789             } else {
1790                 return divide(dividend.intVal, xscale, divisor.intVal, yscale, preferredScale, mc);
1791             }
1792         }
1793     }
1794
1795     /**
1796      * Returns a {@code BigDecimal} whose value is the integer part
1797      * of the quotient {@code (this / divisor)} rounded down.  The
1798      * preferred scale of the result is {@code (this.scale() -
1799      * divisor.scale())}.
1800      *
1801      * @param  divisor value by which this {@code BigDecimal} is to be divided.
1802      * @return The integer part of {@code this / divisor}.
1803      * @throws ArithmeticException if {@code divisor==0}
1804      * @since  1.5
1805      */
1806     public BigDecimal divideToIntegralValue(BigDecimal divisor) {
1807         // Calculate preferred scale
1808         int preferredScale = saturateLong((long) this.scale - divisor.scale);
1809         if (this.compareMagnitude(divisor) < 0) {
1810             // much faster when this << divisor
1811             return zeroValueOf(preferredScale);
1812         }
1813
1814         if (this.signum() == 0 && divisor.signum() != 0)
1815             return this.setScale(preferredScale, ROUND_UNNECESSARY);
1816
1817         // Perform a divide with enough digits to round to a correct
1818         // integer value; then remove any fractional digits
1819
1820         int maxDigits = (int)Math.min(this.precision() +
1821                                       (long)Math.ceil(10.0*divisor.precision()/3.0) +
1822                                       Math.abs((long)this.scale() - divisor.scale()) + 2,
1823                                       Integer.MAX_VALUE);
1824         BigDecimal quotient = this.divide(divisor, new MathContext(maxDigits,
1825                                                                    RoundingMode.DOWN));
1826         if (quotient.scale > 0) {
1827             quotient = quotient.setScale(0, RoundingMode.DOWN);
1828             quotient = stripZerosToMatchScale(quotient.intVal, quotient.intCompact, quotient.scale, preferredScale);
1829         }
1830
1831         if (quotient.scale < preferredScale) {
1832             // pad with zeros if necessary
1833             quotient = quotient.setScale(preferredScale, ROUND_UNNECESSARY);
1834         }
1835
1836         return quotient;
1837     }
1838
1839     /**
1840      * Returns a {@code BigDecimal} whose value is the integer part
1841      * of {@code (this / divisor)}.  Since the integer part of the
1842      * exact quotient does not depend on the rounding mode, the
1843      * rounding mode does not affect the values returned by this
1844      * method.  The preferred scale of the result is
1845      * {@code (this.scale() - divisor.scale())}.  An
1846      * {@code ArithmeticException} is thrown if the integer part of
1847      * the exact quotient needs more than {@code mc.precision}
1848      * digits.
1849      *
1850      * @param  divisor value by which this {@code BigDecimal} is to be divided.
1851      * @param  mc the context to use.
1852      * @return The integer part of {@code this / divisor}.
1853      * @throws ArithmeticException if {@code divisor==0}
1854      * @throws ArithmeticException if {@code mc.precision} {@literal >} 0 and the result
1855      *         requires a precision of more than {@code mc.precision} digits.
1856      * @since  1.5
1857      * @author Joseph D. Darcy
1858      */
1859     public BigDecimal divideToIntegralValue(BigDecimal divisor, MathContext mc) {
1860         if (mc.precision == 0 || // exact result
1861             (this.compareMagnitude(divisor) < 0)) // zero result
1862             return divideToIntegralValue(divisor);
1863
1864         // Calculate preferred scale
1865         int preferredScale = saturateLong((long)this.scale - divisor.scale);
1866
1867         /*
1868          * Perform a normal divide to mc.precision digits.  If the
1869          * remainder has absolute value less than the divisor, the
1870          * integer portion of the quotient fits into mc.precision
1871          * digits.  Next, remove any fractional digits from the
1872          * quotient and adjust the scale to the preferred value.
1873          */
1874         BigDecimal result = this.divide(divisor, new MathContext(mc.precision, RoundingMode.DOWN));
1875
1876         if (result.scale() < 0) {
1877             /*
1878              * Result is an integer. See if quotient represents the
1879              * full integer portion of the exact quotient; if it does,
1880              * the computed remainder will be less than the divisor.
1881              */
1882             BigDecimal product = result.multiply(divisor);
1883             // If the quotient is the full integer value,
1884             // |dividend-product| < |divisor|.
1885             if (this.subtract(product).compareMagnitude(divisor) >= 0) {
1886                 throw new ArithmeticException("Division impossible");
1887             }
1888         } else if (result.scale() > 0) {
1889             /*
1890              * Integer portion of quotient will fit into precision
1891              * digits; recompute quotient to scale 0 to avoid double
1892              * rounding and then try to adjust, if necessary.
1893              */
1894             result = result.setScale(0, RoundingMode.DOWN);
1895         }
1896         // else result.scale() == 0;
1897
1898         int precisionDiff;
1899         if ((preferredScale > result.scale()) &&
1900             (precisionDiff = mc.precision - result.precision()) > 0) {
1901             return result.setScale(result.scale() +
1902                                    Math.min(precisionDiff, preferredScale - result.scale) );
1903         } else {
1904             return stripZerosToMatchScale(result.intVal,result.intCompact,result.scale,preferredScale);
1905         }
1906     }
1907
1908     /**
1909      * Returns a {@code BigDecimal} whose value is {@code (this % divisor)}.
1910      *
1911      * <p>The remainder is given by
1912      * {@code this.subtract(this.divideToIntegralValue(divisor).multiply(divisor))}.
1913      * Note that this is <em>not</em> the modulo operation (the result can be
1914      * negative).
1915      *
1916      * @param  divisor value by which this {@code BigDecimal} is to be divided.
1917      * @return {@code this % divisor}.
1918      * @throws ArithmeticException if {@code divisor==0}
1919      * @since  1.5
1920      */
1921     public BigDecimal remainder(BigDecimal divisor) {
1922         BigDecimal divrem[] = this.divideAndRemainder(divisor);
1923         return divrem[1];
1924     }
1925
1926
1927     /**
1928      * Returns a {@code BigDecimal} whose value is {@code (this %
1929      * divisor)}, with rounding according to the context settings.
1930      * The {@code MathContext} settings affect the implicit divide
1931      * used to compute the remainder.  The remainder computation
1932      * itself is by definition exact.  Therefore, the remainder may
1933      * contain more than {@code mc.getPrecision()} digits.
1934      *
1935      * <p>The remainder is given by
1936      * {@code this.subtract(this.divideToIntegralValue(divisor,
1937      * mc).multiply(divisor))}.  Note that this is not the modulo
1938      * operation (the result can be negative).
1939      *
1940      * @param  divisor value by which this {@code BigDecimal} is to be divided.
1941      * @param  mc the context to use.
1942      * @return {@code this % divisor}, rounded as necessary.
1943      * @throws ArithmeticException if {@code divisor==0}
1944      * @throws ArithmeticException if the result is inexact but the
1945      *         rounding mode is {@code UNNECESSARY}, or {@code mc.precision}
1946      *         {@literal >} 0 and the result of {@code this.divideToIntgralValue(divisor)} would
1947      *         require a precision of more than {@code mc.precision} digits.
1948      * @see    #divideToIntegralValue(java.math.BigDecimal, java.math.MathContext)
1949      * @since  1.5
1950      */
1951     public BigDecimal remainder(BigDecimal divisor, MathContext mc) {
1952         BigDecimal divrem[] = this.divideAndRemainder(divisor, mc);
1953         return divrem[1];
1954     }
1955
1956     /**
1957      * Returns a two-element {@code BigDecimal} array containing the
1958      * result of {@code divideToIntegralValue} followed by the result of
1959      * {@code remainder} on the two operands.
1960      *
1961      * <p>Note that if both the integer quotient and remainder are
1962      * needed, this method is faster than using the
1963      * {@code divideToIntegralValue} and {@code remainder} methods
1964      * separately because the division need only be carried out once.
1965      *
1966      * @param  divisor value by which this {@code BigDecimal} is to be divided,
1967      *         and the remainder computed.
1968      * @return a two element {@code BigDecimal} array: the quotient
1969      *         (the result of {@code divideToIntegralValue}) is the initial element
1970      *         and the remainder is the final element.
1971      * @throws ArithmeticException if {@code divisor==0}
1972      * @see    #divideToIntegralValue(java.math.BigDecimal, java.math.MathContext)
1973      * @see    #remainder(java.math.BigDecimal, java.math.MathContext)
1974      * @since  1.5
1975      */
1976     public BigDecimal[] divideAndRemainder(BigDecimal divisor) {
1977         // we use the identity  x = i * y + r to determine r
1978         BigDecimal[] result = new BigDecimal[2];
1979
1980         result[0] = this.divideToIntegralValue(divisor);
1981         result[1] = this.subtract(result[0].multiply(divisor));
1982         return result;
1983     }
1984
1985     /**
1986      * Returns a two-element {@code BigDecimal} array containing the
1987      * result of {@code divideToIntegralValue} followed by the result of
1988      * {@code remainder} on the two operands calculated with rounding
1989      * according to the context settings.
1990      *
1991      * <p>Note that if both the integer quotient and remainder are
1992      * needed, this method is faster than using the
1993      * {@code divideToIntegralValue} and {@code remainder} methods
1994      * separately because the division need only be carried out once.
1995      *
1996      * @param  divisor value by which this {@code BigDecimal} is to be divided,
1997      *         and the remainder computed.
1998      * @param  mc the context to use.
1999      * @return a two element {@code BigDecimal} array: the quotient
2000      *         (the result of {@code divideToIntegralValue}) is the
2001      *         initial element and the remainder is the final element.
2002      * @throws ArithmeticException if {@code divisor==0}
2003      * @throws ArithmeticException if the result is inexact but the
2004      *         rounding mode is {@code UNNECESSARY}, or {@code mc.precision}
2005      *         {@literal >} 0 and the result of {@code this.divideToIntgralValue(divisor)} would
2006      *         require a precision of more than {@code mc.precision} digits.
2007      * @see    #divideToIntegralValue(java.math.BigDecimal, java.math.MathContext)
2008      * @see    #remainder(java.math.BigDecimal, java.math.MathContext)
2009      * @since  1.5
2010      */
2011     public BigDecimal[] divideAndRemainder(BigDecimal divisor, MathContext mc) {
2012         if (mc.precision == 0)
2013             return divideAndRemainder(divisor);
2014
2015         BigDecimal[] result = new BigDecimal[2];
2016         BigDecimal lhs = this;
2017
2018         result[0] = lhs.divideToIntegralValue(divisor, mc);
2019         result[1] = lhs.subtract(result[0].multiply(divisor));
2020         return result;
2021     }
2022
2023     /**
2024      * Returns an approximation to the square root of {@code this}
2025      * with rounding according to the context settings.
2026      *
2027      * <p>The preferred scale of the returned result is equal to
2028      * {@code this.scale()/2}. The value of the returned result is
2029      * always within one ulp of the exact decimal value for the
2030      * precision in question.  If the rounding mode is {@link
2031      * RoundingMode#HALF_UP HALF_UP}, {@link RoundingMode#HALF_DOWN
2032      * HALF_DOWN}, or {@link RoundingMode#HALF_EVEN HALF_EVEN}, the
2033      * result is within one half an ulp of the exact decimal value.
2034      *
2035      * <p>Special case:
2036      * <ul>
2037      * <li> The square root of a number numerically equal to {@code
2038      * ZERO} is numerically equal to {@code ZERO} with a preferred
2039      * scale according to the general rule above. In particular, for
2040      * {@code ZERO}, {@code ZERO.sqrt(mc).equals(ZERO)} is true with
2041      * any {@code MathContext} as an argument.
2042      * </ul>
2043      *
2044      * @param mc the context to use.
2045      * @return the square root of {@code this}.
2046      * @throws ArithmeticException if {@code this} is less than zero.
2047      * @throws ArithmeticException if an exact result is requested
2048      * ({@code mc.getPrecision()==0}) and there is no finite decimal
2049      * expansion of the exact result
2050      * @throws ArithmeticException if
2051      * {@code (mc.getRoundingMode()==RoundingMode.UNNECESSARY}) and
2052      * the exact result cannot fit in {@code mc.getPrecision()}
2053      * digits.
2054      * @see BigInteger#sqrt()
2055      * @since  9
2056      */
2057     public BigDecimal sqrt(MathContext mc) {
2058         int signum = signum();
2059         if (signum == 1) {
2060             /*
2061              * The following code draws on the algorithm presented in
2062              * "Properly Rounded Variable Precision Square Root," Hull and
2063              * Abrham, ACM Transactions on Mathematical Software, Vol 11,
2064              * No. 3, September 1985, Pages 229-237.
2065              *
2066              * The BigDecimal computational model differs from the one
2067              * presented in the paper in several ways: first BigDecimal
2068              * numbers aren't necessarily normalized, second many more
2069              * rounding modes are supported, including UNNECESSARY, and
2070              * exact results can be requested.
2071              *
2072              * The main steps of the algorithm below are as follows,
2073              * first argument reduce the value to the numerical range
2074              * [1, 10) using the following relations:
2075              *
2076              * x = y * 10 ^ exp
2077              * sqrt(x) = sqrt(y) * 10^(exp / 2) if exp is even
2078              * sqrt(x) = sqrt(y/10) * 10 ^((exp+1)/2) is exp is odd
2079              *
2080              * Then use Newton's iteration on the reduced value to compute
2081              * the numerical digits of the desired result.
2082              *
2083              * Finally, scale back to the desired exponent range and
2084              * perform any adjustment to get the preferred scale in the
2085              * representation.
2086              */
2087
2088             // The code below favors relative simplicity over checking
2089             // for special cases that could run faster.
2090
2091             int preferredScale = this.scale()/2;
2092             BigDecimal zeroWithFinalPreferredScale = valueOf(0L, preferredScale);
2093
2094             // First phase of numerical normalization, strip trailing
2095             // zeros and check for even powers of 10.
2096             BigDecimal stripped = this.stripTrailingZeros();
2097             int strippedScale = stripped.scale();
2098
2099             // Numerically sqrt(10^2N) = 10^N
2100             if (stripped.isPowerOfTen() &&
2101                 strippedScale % 2 == 0) {
2102                 BigDecimal result = valueOf(1L, strippedScale/2);
2103                 if (result.scale() != preferredScale) {
2104                     // Adjust to requested precision and preferred
2105                     // scale as appropriate.
2106                     result = result.add(zeroWithFinalPreferredScale, mc);
2107                 }
2108                 return result;
2109             }
2110
2111             // After stripTrailingZeros, the representation is normalized as
2112             //
2113             // unscaledValue * 10^(-scale)
2114             //
2115             // where unscaledValue is an integer with the mimimum
2116             // precision for the cohort of the numerical value. To
2117             // allow binary floating-point hardware to be used to get
2118             // approximately a 15 digit approximation to the square
2119             // root, it is helpful to instead normalize this so that
2120             // the significand portion is to right of the decimal
2121             // point by roughly (scale() - precision() +1).
2122
2123             // Now the precision / scale adjustment
2124             int scaleAdjust = 0;
2125             int scale = stripped.scale() - stripped.precision() + 1;
2126             if (scale % 2 == 0) {
2127                 scaleAdjust = scale;
2128             } else {
2129                 scaleAdjust = scale - 1;
2130             }
2131
2132             BigDecimal working = stripped.scaleByPowerOfTen(scaleAdjust);
2133
2134             assert  // Verify 0.1 <= working < 10
2135                 ONE_TENTH.compareTo(working) <= 0 && working.compareTo(TEN) < 0;
2136
2137             // Use good ole' Math.sqrt to get the initial guess for
2138             // the Newton iteration, good to at least 15 decimal
2139             // digits. This approach does incur the cost of a
2140             //
2141             // BigDecimal -> double -> BigDecimal
2142             //
2143             // conversion cycle, but it avoids the need for several
2144             // Newton iterations in BigDecimal arithmetic to get the
2145             // working answer to 15 digits of precision. If many fewer
2146             // than 15 digits were needed, it might be faster to do
2147             // the loop entirely in BigDecimal arithmetic.
2148             //
2149             // (A double value might have as much many as 17 decimal
2150             // digits of precision; it depends on the relative density
2151             // of binary and decimal numbers at different regions of
2152             // the number line.)
2153             //
2154             // (It would be possible to check for certain special
2155             // cases to avoid doing any Newton iterations. For
2156             // example, if the BigDecimal -> double conversion was
2157             // known to be exact and the rounding mode had a
2158             // low-enough precision, the post-Newton rounding logic
2159             // could be applied directly.)
2160
2161             BigDecimal guess = new BigDecimal(Math.sqrt(working.doubleValue()));
2162             int guessPrecision = 15;
2163             int originalPrecision = mc.getPrecision();
2164             int targetPrecision;
2165
2166             // If an exact value is requested, it must only need about
2167             // half of the input digits to represent since multiplying
2168             // an N digit number by itself yield a 2N-1 digit or 2N
2169             // digit result.
2170             if (originalPrecision == 0) {
2171                 targetPrecision = stripped.precision()/2 + 1;
2172             } else {
2173                 targetPrecision = originalPrecision;
2174             }
2175
2176             // When setting the precision to use inside the Newton
2177             // iteration loop, take care to avoid the case where the
2178             // precision of the input exceeds the requested precision
2179             // and rounding the input value too soon.
2180             BigDecimal approx = guess;
2181             int workingPrecision = working.precision();
2182             do {
2183                 int tmpPrecision = Math.max(Math.max(guessPrecision, targetPrecision + 2),
2184                                            workingPrecision);
2185                 MathContext mcTmp = new MathContext(tmpPrecision, RoundingMode.HALF_EVEN);
2186                 // approx = 0.5 * (approx + fraction / approx)
2187                 approx = ONE_HALF.multiply(approx.add(working.divide(approx, mcTmp), mcTmp));
2188                 guessPrecision *= 2;
2189             } while (guessPrecision < targetPrecision + 2);
2190
2191             BigDecimal result;
2192             RoundingMode targetRm = mc.getRoundingMode();
2193             if (targetRm == RoundingMode.UNNECESSARY || originalPrecision == 0) {
2194                 RoundingMode tmpRm =
2195                     (targetRm == RoundingMode.UNNECESSARY) ? RoundingMode.DOWN : targetRm;
2196                 MathContext mcTmp = new MathContext(targetPrecision, tmpRm);
2197                 result = approx.scaleByPowerOfTen(-scaleAdjust/2).round(mcTmp);
2198
2199                 // If result*result != this numerically, the square
2200                 // root isn't exact
2201                 if (this.subtract(result.multiply(result)).compareTo(ZERO) != 0) {
2202                     throw new ArithmeticException("Computed square root not exact.");
2203                 }
2204             } else {
2205                 result = approx.scaleByPowerOfTen(-scaleAdjust/2).round(mc);
2206             }
2207
2208             if (result.scale() != preferredScale) {
2209                 // The preferred scale of an add is
2210                 // max(addend.scale(), augend.scale()). Therefore, if
2211                 // the scale of the result is first minimized using
2212                 // stripTrailingZeros(), adding a zero of the
2213                 // preferred scale rounding the correct precision will
2214                 // perform the proper scale vs precision tradeoffs.
2215                 result = result.stripTrailingZeros().
2217                         new MathContext(originalPrecision, RoundingMode.UNNECESSARY));
2218             }
2219             assert squareRootResultAssertions(result, mc);
2220             return result;
2221         } else {
2222             switch (signum) {
2223             case -1:
2224                 throw new ArithmeticException("Attempted square root " +
2225                                               "of negative BigDecimal");
2226             case 0:
2227                 return valueOf(0L, scale()/2);
2228
2229             default:
2230                 throw new AssertionError("Bad value from signum");
2231             }
2232         }
2233     }
2234
2235     private boolean isPowerOfTen() {
2236         return BigInteger.ONE.equals(this.unscaledValue());
2237     }
2238
2239     /**
2240      * For nonzero values, check numerical correctness properties of
2241      * the computed result for the chosen rounding mode.
2242      *
2243      * For the directed roundings, for DOWN and FLOOR, result^2 must
2244      * be {@code <=} the input and (result+ulp)^2 must be {@code >} the
2245      * input. Conversely, for UP and CEIL, result^2 must be {@code >=} the
2246      * input and (result-ulp)^2 must be {@code <} the input.
2247      */
2248     private boolean squareRootResultAssertions(BigDecimal result, MathContext mc) {
2249         if (result.signum() == 0) {
2250             return squareRootZeroResultAssertions(result, mc);
2251         } else {
2252             RoundingMode rm = mc.getRoundingMode();
2253             BigDecimal ulp = result.ulp();
2254             BigDecimal neighborUp   = result.add(ulp);
2255             // Make neighbor down accurate even for powers of ten
2256             if (this.isPowerOfTen()) {
2257                 ulp = ulp.divide(TEN);
2258             }
2259             BigDecimal neighborDown = result.subtract(ulp);
2260
2261             // Both the starting value and result should be nonzero and positive.
2262             if (result.signum() != 1 ||
2263                 this.signum() != 1) {
2264                 return false;
2265             }
2266
2267             switch (rm) {
2268             case DOWN:
2269             case FLOOR:
2270                 return
2271                     result.multiply(result).compareTo(this)         <= 0 &&
2272                     neighborUp.multiply(neighborUp).compareTo(this) > 0;
2273
2274             case UP:
2275             case CEILING:
2276                 return
2277                     result.multiply(result).compareTo(this)             >= 0 &&
2278                     neighborDown.multiply(neighborDown).compareTo(this) < 0;
2279
2280             case HALF_DOWN:
2281             case HALF_EVEN:
2282             case HALF_UP:
2283                 BigDecimal err = result.multiply(result).subtract(this).abs();
2284                 BigDecimal errUp = neighborUp.multiply(neighborUp).subtract(this);
2285                 BigDecimal errDown =  this.subtract(neighborDown.multiply(neighborDown));
2286                 // All error values should be positive so don't need to
2287                 // compare absolute values.
2288
2289                 int err_comp_errUp = err.compareTo(errUp);
2290                 int err_comp_errDown = err.compareTo(errDown);
2291
2292                 return
2293                     errUp.signum()   == 1 &&
2294                     errDown.signum() == 1 &&
2295
2296                     err_comp_errUp   <= 0 &&
2297                     err_comp_errDown <= 0 &&
2298
2299                     ((err_comp_errUp   == 0 ) ? err_comp_errDown < 0 : true) &&
2300                     ((err_comp_errDown == 0 ) ? err_comp_errUp   < 0 : true);
2301                 // && could check for digit conditions for ties too
2302
2303             default: // Definition of UNNECESSARY already verified.
2304                 return true;
2305             }
2306         }
2307     }
2308
2309     private boolean squareRootZeroResultAssertions(BigDecimal result, MathContext mc) {
2310         return this.compareTo(ZERO) == 0;
2311     }
2312
2313     /**
2314      * Returns a {@code BigDecimal} whose value is
2315      * <code>(this<sup>n</sup>)</code>, The power is computed exactly, to
2316      * unlimited precision.
2317      *
2318      * <p>The parameter {@code n} must be in the range 0 through
2319      * 999999999, inclusive.  {@code ZERO.pow(0)} returns {@link
2320      * #ONE}.
2321      *
2322      * Note that future releases may expand the allowable exponent
2323      * range of this method.
2324      *
2325      * @param  n power to raise this {@code BigDecimal} to.
2326      * @return <code>this<sup>n</sup></code>
2327      * @throws ArithmeticException if {@code n} is out of range.
2328      * @since  1.5
2329      */
2330     public BigDecimal pow(int n) {
2331         if (n < 0 || n > 999999999)
2332             throw new ArithmeticException("Invalid operation");
2333         // No need to calculate pow(n) if result will over/underflow.
2334         // Don't attempt to support "supernormal" numbers.
2335         int newScale = checkScale((long)scale * n);
2336         return new BigDecimal(this.inflated().pow(n), newScale);
2337     }
2338
2339
2340     /**
2341      * Returns a {@code BigDecimal} whose value is
2342      * <code>(this<sup>n</sup>)</code>.  The current implementation uses
2343      * the core algorithm defined in ANSI standard X3.274-1996 with
2344      * rounding according to the context settings.  In general, the
2345      * returned numerical value is within two ulps of the exact
2346      * numerical value for the chosen precision.  Note that future
2347      * releases may use a different algorithm with a decreased
2348      * allowable error bound and increased allowable exponent range.
2349      *
2350      * <p>The X3.274-1996 algorithm is:
2351      *
2352      * <ul>
2353      * <li> An {@code ArithmeticException} exception is thrown if
2354      *  <ul>
2355      *    <li>{@code abs(n) > 999999999}
2356      *    <li>{@code mc.precision == 0} and {@code n < 0}
2357      *    <li>{@code mc.precision > 0} and {@code n} has more than
2358      *    {@code mc.precision} decimal digits
2359      *  </ul>
2360      *
2361      * <li> if {@code n} is zero, {@link #ONE} is returned even if
2362      * {@code this} is zero, otherwise
2363      * <ul>
2364      *   <li> if {@code n} is positive, the result is calculated via
2365      *   the repeated squaring technique into a single accumulator.
2366      *   The individual multiplications with the accumulator use the
2367      *   same math context settings as in {@code mc} except for a
2368      *   precision increased to {@code mc.precision + elength + 1}
2369      *   where {@code elength} is the number of decimal digits in
2370      *   {@code n}.
2371      *
2372      *   <li> if {@code n} is negative, the result is calculated as if
2373      *   {@code n} were positive; this value is then divided into one
2374      *   using the working precision specified above.
2375      *
2376      *   <li> The final value from either the positive or negative case
2377      *   is then rounded to the destination precision.
2378      *   </ul>
2379      * </ul>
2380      *
2381      * @param  n power to raise this {@code BigDecimal} to.
2382      * @param  mc the context to use.
2383      * @return <code>this<sup>n</sup></code> using the ANSI standard X3.274-1996
2384      *         algorithm
2385      * @throws ArithmeticException if the result is inexact but the
2386      *         rounding mode is {@code UNNECESSARY}, or {@code n} is out
2387      *         of range.
2388      * @since  1.5
2389      */
2390     public BigDecimal pow(int n, MathContext mc) {
2391         if (mc.precision == 0)
2392             return pow(n);
2393         if (n < -999999999 || n > 999999999)
2394             throw new ArithmeticException("Invalid operation");
2395         if (n == 0)
2396             return ONE;                      // x**0 == 1 in X3.274
2397         BigDecimal lhs = this;
2398         MathContext workmc = mc;           // working settings
2399         int mag = Math.abs(n);               // magnitude of n
2400         if (mc.precision > 0) {
2401             int elength = longDigitLength(mag); // length of n in digits
2402             if (elength > mc.precision)        // X3.274 rule
2403                 throw new ArithmeticException("Invalid operation");
2404             workmc = new MathContext(mc.precision + elength + 1,
2405                                       mc.roundingMode);
2406         }
2407         // ready to carry out power calculation...
2408         BigDecimal acc = ONE;           // accumulator
2409         boolean seenbit = false;        // set once we've seen a 1-bit
2410         for (int i=1;;i++) {            // for each bit [top bit ignored]
2411             mag += mag;                 // shift left 1 bit
2412             if (mag < 0) {              // top bit is set
2413                 seenbit = true;         // OK, we're off
2414                 acc = acc.multiply(lhs, workmc); // acc=acc*x
2415             }
2416             if (i == 31)
2417                 break;                  // that was the last bit
2418             if (seenbit)
2419                 acc=acc.multiply(acc, workmc);   // acc=acc*acc [square]
2420                 // else (!seenbit) no point in squaring ONE
2421         }
2422         // if negative n, calculate the reciprocal using working precision
2423         if (n < 0) // [hence mc.precision>0]
2424             acc=ONE.divide(acc, workmc);
2425         // round to final precision and strip zeros
2426         return doRound(acc, mc);
2427     }
2428
2429     /**
2430      * Returns a {@code BigDecimal} whose value is the absolute value
2431      * of this {@code BigDecimal}, and whose scale is
2432      * {@code this.scale()}.
2433      *
2434      * @return {@code abs(this)}
2435      */
2436     public BigDecimal abs() {
2437         return (signum() < 0 ? negate() : this);
2438     }
2439
2440     /**
2441      * Returns a {@code BigDecimal} whose value is the absolute value
2442      * of this {@code BigDecimal}, with rounding according to the
2443      * context settings.
2444      *
2445      * @param mc the context to use.
2446      * @return {@code abs(this)}, rounded as necessary.
2447      * @throws ArithmeticException if the result is inexact but the
2448      *         rounding mode is {@code UNNECESSARY}.
2449      * @since 1.5
2450      */
2451     public BigDecimal abs(MathContext mc) {
2452         return (signum() < 0 ? negate(mc) : plus(mc));
2453     }
2454
2455     /**
2456      * Returns a {@code BigDecimal} whose value is {@code (-this)},
2457      * and whose scale is {@code this.scale()}.
2458      *
2459      * @return {@code -this}.
2460      */
2461     public BigDecimal negate() {
2462         if (intCompact == INFLATED) {
2463             return new BigDecimal(intVal.negate(), INFLATED, scale, precision);
2464         } else {
2465             return valueOf(-intCompact, scale, precision);
2466         }
2467     }
2468
2469     /**
2470      * Returns a {@code BigDecimal} whose value is {@code (-this)},
2471      * with rounding according to the context settings.
2472      *
2473      * @param mc the context to use.
2474      * @return {@code -this}, rounded as necessary.
2475      * @throws ArithmeticException if the result is inexact but the
2476      *         rounding mode is {@code UNNECESSARY}.
2477      * @since  1.5
2478      */
2479     public BigDecimal negate(MathContext mc) {
2480         return negate().plus(mc);
2481     }
2482
2483     /**
2484      * Returns a {@code BigDecimal} whose value is {@code (+this)}, and whose
2485      * scale is {@code this.scale()}.
2486      *
2487      * <p>This method, which simply returns this {@code BigDecimal}
2488      * is included for symmetry with the unary minus method {@link
2489      * #negate()}.
2490      *
2491      * @return {@code this}.
2492      * @see #negate()
2493      * @since  1.5
2494      */
2495     public BigDecimal plus() {
2496         return this;
2497     }
2498
2499     /**
2500      * Returns a {@code BigDecimal} whose value is {@code (+this)},
2501      * with rounding according to the context settings.
2502      *
2503      * <p>The effect of this method is identical to that of the {@link
2504      * #round(MathContext)} method.
2505      *
2506      * @param mc the context to use.
2507      * @return {@code this}, rounded as necessary.  A zero result will
2508      *         have a scale of 0.
2509      * @throws ArithmeticException if the result is inexact but the
2510      *         rounding mode is {@code UNNECESSARY}.
2511      * @see    #round(MathContext)
2512      * @since  1.5
2513      */
2514     public BigDecimal plus(MathContext mc) {
2515         if (mc.precision == 0)                 // no rounding please
2516             return this;
2517         return doRound(this, mc);
2518     }
2519
2520     /**
2521      * Returns the signum function of this {@code BigDecimal}.
2522      *
2523      * @return -1, 0, or 1 as the value of this {@code BigDecimal}
2524      *         is negative, zero, or positive.
2525      */
2526     public int signum() {
2527         return (intCompact != INFLATED)?
2528             Long.signum(intCompact):
2529             intVal.signum();
2530     }
2531
2532     /**
2533      * Returns the <i>scale</i> of this {@code BigDecimal}.  If zero
2534      * or positive, the scale is the number of digits to the right of
2535      * the decimal point.  If negative, the unscaled value of the
2536      * number is multiplied by ten to the power of the negation of the
2537      * scale.  For example, a scale of {@code -3} means the unscaled
2538      * value is multiplied by 1000.
2539      *
2540      * @return the scale of this {@code BigDecimal}.
2541      */
2542     public int scale() {
2543         return scale;
2544     }
2545
2546     /**
2547      * Returns the <i>precision</i> of this {@code BigDecimal}.  (The
2548      * precision is the number of digits in the unscaled value.)
2549      *
2550      * <p>The precision of a zero value is 1.
2551      *
2552      * @return the precision of this {@code BigDecimal}.
2553      * @since  1.5
2554      */
2555     public int precision() {
2556         int result = precision;
2557         if (result == 0) {
2558             long s = intCompact;
2559             if (s != INFLATED)
2560                 result = longDigitLength(s);
2561             else
2562                 result = bigDigitLength(intVal);
2563             precision = result;
2564         }
2565         return result;
2566     }
2567
2568
2569     /**
2570      * Returns a {@code BigInteger} whose value is the <i>unscaled
2571      * value</i> of this {@code BigDecimal}.  (Computes <code>(this *
2572      * 10<sup>this.scale()</sup>)</code>.)
2573      *
2574      * @return the unscaled value of this {@code BigDecimal}.
2575      * @since  1.2
2576      */
2577     public BigInteger unscaledValue() {
2578         return this.inflated();
2579     }
2580
2581     // Rounding Modes
2582
2583     /**
2584      * Rounding mode to round away from zero.  Always increments the
2585      * digit prior to a nonzero discarded fraction.  Note that this rounding
2586      * mode never decreases the magnitude of the calculated value.
2587      *
2588      * @deprecated Use {@link RoundingMode#UP} instead.
2589      */
2590     @Deprecated(since="9")
2591     public static final int ROUND_UP =           0;
2592
2593     /**
2594      * Rounding mode to round towards zero.  Never increments the digit
2595      * prior to a discarded fraction (i.e., truncates).  Note that this
2596      * rounding mode never increases the magnitude of the calculated value.
2597      *
2598      * @deprecated Use {@link RoundingMode#DOWN} instead.
2599      */
2600     @Deprecated(since="9")
2601     public static final int ROUND_DOWN =         1;
2602
2603     /**
2604      * Rounding mode to round towards positive infinity.  If the
2605      * {@code BigDecimal} is positive, behaves as for
2606      * {@code ROUND_UP}; if negative, behaves as for
2607      * {@code ROUND_DOWN}.  Note that this rounding mode never
2608      * decreases the calculated value.
2609      *
2610      * @deprecated Use {@link RoundingMode#CEILING} instead.
2611      */
2612     @Deprecated(since="9")
2613     public static final int ROUND_CEILING =      2;
2614
2615     /**
2616      * Rounding mode to round towards negative infinity.  If the
2617      * {@code BigDecimal} is positive, behave as for
2618      * {@code ROUND_DOWN}; if negative, behave as for
2619      * {@code ROUND_UP}.  Note that this rounding mode never
2620      * increases the calculated value.
2621      *
2622      * @deprecated Use {@link RoundingMode#FLOOR} instead.
2623      */
2624     @Deprecated(since="9")
2625     public static final int ROUND_FLOOR =        3;
2626
2627     /**
2628      * Rounding mode to round towards {@literal "nearest neighbor"}
2629      * unless both neighbors are equidistant, in which case round up.
2630      * Behaves as for {@code ROUND_UP} if the discarded fraction is
2631      * &ge; 0.5; otherwise, behaves as for {@code ROUND_DOWN}.  Note
2632      * that this is the rounding mode that most of us were taught in
2633      * grade school.
2634      *
2635      * @deprecated Use {@link RoundingMode#HALF_UP} instead.
2636      */
2637     @Deprecated(since="9")
2638     public static final int ROUND_HALF_UP =      4;
2639
2640     /**
2641      * Rounding mode to round towards {@literal "nearest neighbor"}
2642      * unless both neighbors are equidistant, in which case round
2643      * down.  Behaves as for {@code ROUND_UP} if the discarded
2644      * fraction is {@literal >} 0.5; otherwise, behaves as for
2645      * {@code ROUND_DOWN}.
2646      *
2647      * @deprecated Use {@link RoundingMode#HALF_DOWN} instead.
2648      */
2649     @Deprecated(since="9")
2650     public static final int ROUND_HALF_DOWN =    5;
2651
2652     /**
2653      * Rounding mode to round towards the {@literal "nearest neighbor"}
2654      * unless both neighbors are equidistant, in which case, round
2655      * towards the even neighbor.  Behaves as for
2656      * {@code ROUND_HALF_UP} if the digit to the left of the
2657      * discarded fraction is odd; behaves as for
2658      * {@code ROUND_HALF_DOWN} if it's even.  Note that this is the
2659      * rounding mode that minimizes cumulative error when applied
2660      * repeatedly over a sequence of calculations.
2661      *
2662      * @deprecated Use {@link RoundingMode#HALF_EVEN} instead.
2663      */
2664     @Deprecated(since="9")
2665     public static final int ROUND_HALF_EVEN =    6;
2666
2667     /**
2668      * Rounding mode to assert that the requested operation has an exact
2669      * result, hence no rounding is necessary.  If this rounding mode is
2670      * specified on an operation that yields an inexact result, an
2671      * {@code ArithmeticException} is thrown.
2672      *
2673      * @deprecated Use {@link RoundingMode#UNNECESSARY} instead.
2674      */
2675     @Deprecated(since="9")
2676     public static final int ROUND_UNNECESSARY =  7;
2677
2678
2679     // Scaling/Rounding Operations
2680
2681     /**
2682      * Returns a {@code BigDecimal} rounded according to the
2683      * {@code MathContext} settings.  If the precision setting is 0 then
2684      * no rounding takes place.
2685      *
2686      * <p>The effect of this method is identical to that of the
2687      * {@link #plus(MathContext)} method.
2688      *
2689      * @param mc the context to use.
2690      * @return a {@code BigDecimal} rounded according to the
2691      *         {@code MathContext} settings.
2692      * @throws ArithmeticException if the rounding mode is
2693      *         {@code UNNECESSARY} and the
2694      *         {@code BigDecimal}  operation would require rounding.
2695      * @see    #plus(MathContext)
2696      * @since  1.5
2697      */
2698     public BigDecimal round(MathContext mc) {
2699         return plus(mc);
2700     }
2701
2702     /**
2703      * Returns a {@code BigDecimal} whose scale is the specified
2704      * value, and whose unscaled value is determined by multiplying or
2705      * dividing this {@code BigDecimal}'s unscaled value by the
2706      * appropriate power of ten to maintain its overall value.  If the
2707      * scale is reduced by the operation, the unscaled value must be
2708      * divided (rather than multiplied), and the value may be changed;
2709      * in this case, the specified rounding mode is applied to the
2710      * division.
2711      *
2712      * @apiNote Since BigDecimal objects are immutable, calls of
2713      * this method do <em>not</em> result in the original object being
2714      * modified, contrary to the usual convention of having methods
2715      * named <code>set<i>X</i></code> mutate field <i>{@code X}</i>.
2716      * Instead, {@code setScale} returns an object with the proper
2717      * scale; the returned object may or may not be newly allocated.
2718      *
2719      * @param  newScale scale of the {@code BigDecimal} value to be returned.
2720      * @param  roundingMode The rounding mode to apply.
2721      * @return a {@code BigDecimal} whose scale is the specified value,
2722      *         and whose unscaled value is determined by multiplying or
2723      *         dividing this {@code BigDecimal}'s unscaled value by the
2724      *         appropriate power of ten to maintain its overall value.
2725      * @throws ArithmeticException if {@code roundingMode==UNNECESSARY}
2726      *         and the specified scaling operation would require
2727      *         rounding.
2728      * @see    RoundingMode
2729      * @since  1.5
2730      */
2731     public BigDecimal setScale(int newScale, RoundingMode roundingMode) {
2732         return setScale(newScale, roundingMode.oldMode);
2733     }
2734
2735     /**
2736      * Returns a {@code BigDecimal} whose scale is the specified
2737      * value, and whose unscaled value is determined by multiplying or
2738      * dividing this {@code BigDecimal}'s unscaled value by the
2739      * appropriate power of ten to maintain its overall value.  If the
2740      * scale is reduced by the operation, the unscaled value must be
2741      * divided (rather than multiplied), and the value may be changed;
2742      * in this case, the specified rounding mode is applied to the
2743      * division.
2744      *
2745      * @apiNote Since BigDecimal objects are immutable, calls of
2746      * this method do <em>not</em> result in the original object being
2747      * modified, contrary to the usual convention of having methods
2748      * named <code>set<i>X</i></code> mutate field <i>{@code X}</i>.
2749      * Instead, {@code setScale} returns an object with the proper
2750      * scale; the returned object may or may not be newly allocated.
2751      *
2752      * @deprecated The method {@link #setScale(int, RoundingMode)} should
2753      * be used in preference to this legacy method.
2754      *
2755      * @param  newScale scale of the {@code BigDecimal} value to be returned.
2756      * @param  roundingMode The rounding mode to apply.
2757      * @return a {@code BigDecimal} whose scale is the specified value,
2758      *         and whose unscaled value is determined by multiplying or
2759      *         dividing this {@code BigDecimal}'s unscaled value by the
2760      *         appropriate power of ten to maintain its overall value.
2761      * @throws ArithmeticException if {@code roundingMode==ROUND_UNNECESSARY}
2762      *         and the specified scaling operation would require
2763      *         rounding.
2764      * @throws IllegalArgumentException if {@code roundingMode} does not
2765      *         represent a valid rounding mode.
2766      * @see    #ROUND_UP
2767      * @see    #ROUND_DOWN
2768      * @see    #ROUND_CEILING
2769      * @see    #ROUND_FLOOR
2770      * @see    #ROUND_HALF_UP
2771      * @see    #ROUND_HALF_DOWN
2772      * @see    #ROUND_HALF_EVEN
2773      * @see    #ROUND_UNNECESSARY
2774      */
2775     @Deprecated(since="9")
2776     public BigDecimal setScale(int newScale, int roundingMode) {
2777         if (roundingMode < ROUND_UP || roundingMode > ROUND_UNNECESSARY)
2778             throw new IllegalArgumentException("Invalid rounding mode");
2779
2780         int oldScale = this.scale;
2781         if (newScale == oldScale)        // easy case
2782             return this;
2783         if (this.signum() == 0)            // zero can have any scale
2784             return zeroValueOf(newScale);
2785         if(this.intCompact!=INFLATED) {
2786             long rs = this.intCompact;
2787             if (newScale > oldScale) {
2788                 int raise = checkScale((long) newScale - oldScale);
2789                 if ((rs = longMultiplyPowerTen(rs, raise)) != INFLATED) {
2790                     return valueOf(rs,newScale);
2791                 }
2792                 BigInteger rb = bigMultiplyPowerTen(raise);
2793                 return new BigDecimal(rb, INFLATED, newScale, (precision > 0) ? precision + raise : 0);
2794             } else {
2795                 // newScale < oldScale -- drop some digits
2796                 // Can't predict the precision due to the effect of rounding.
2797                 int drop = checkScale((long) oldScale - newScale);
2798                 if (drop < LONG_TEN_POWERS_TABLE.length) {
2799                     return divideAndRound(rs, LONG_TEN_POWERS_TABLE[drop], newScale, roundingMode, newScale);
2800                 } else {
2801                     return divideAndRound(this.inflated(), bigTenToThe(drop), newScale, roundingMode, newScale);
2802                 }
2803             }
2804         } else {
2805             if (newScale > oldScale) {
2806                 int raise = checkScale((long) newScale - oldScale);
2807                 BigInteger rb = bigMultiplyPowerTen(this.intVal,raise);
2808                 return new BigDecimal(rb, INFLATED, newScale, (precision > 0) ? precision + raise : 0);
2809             } else {
2810                 // newScale < oldScale -- drop some digits
2811                 // Can't predict the precision due to the effect of rounding.
2812                 int drop = checkScale((long) oldScale - newScale);
2813                 if (drop < LONG_TEN_POWERS_TABLE.length)
2814                     return divideAndRound(this.intVal, LONG_TEN_POWERS_TABLE[drop], newScale, roundingMode,
2815                                           newScale);
2816                 else
2817                     return divideAndRound(this.intVal,  bigTenToThe(drop), newScale, roundingMode, newScale);
2818             }
2819         }
2820     }
2821
2822     /**
2823      * Returns a {@code BigDecimal} whose scale is the specified
2824      * value, and whose value is numerically equal to this
2825      * {@code BigDecimal}'s.  Throws an {@code ArithmeticException}
2826      * if this is not possible.
2827      *
2828      * <p>This call is typically used to increase the scale, in which
2829      * case it is guaranteed that there exists a {@code BigDecimal}
2830      * of the specified scale and the correct value.  The call can
2831      * also be used to reduce the scale if the caller knows that the
2832      * {@code BigDecimal} has sufficiently many zeros at the end of
2833      * its fractional part (i.e., factors of ten in its integer value)
2834      * to allow for the rescaling without changing its value.
2835      *
2836      * <p>This method returns the same result as the two-argument
2837      * versions of {@code setScale}, but saves the caller the trouble
2838      * of specifying a rounding mode in cases where it is irrelevant.
2839      *
2840      * @apiNote Since {@code BigDecimal} objects are immutable,
2841      * calls of this method do <em>not</em> result in the original
2842      * object being modified, contrary to the usual convention of
2843      * having methods named <code>set<i>X</i></code> mutate field
2844      * <i>{@code X}</i>.  Instead, {@code setScale} returns an
2845      * object with the proper scale; the returned object may or may
2846      * not be newly allocated.
2847      *
2848      * @param  newScale scale of the {@code BigDecimal} value to be returned.
2849      * @return a {@code BigDecimal} whose scale is the specified value, and
2850      *         whose unscaled value is determined by multiplying or dividing
2851      *         this {@code BigDecimal}'s unscaled value by the appropriate
2852      *         power of ten to maintain its overall value.
2853      * @throws ArithmeticException if the specified scaling operation would
2854      *         require rounding.
2855      * @see    #setScale(int, int)
2856      * @see    #setScale(int, RoundingMode)
2857      */
2858     public BigDecimal setScale(int newScale) {
2859         return setScale(newScale, ROUND_UNNECESSARY);
2860     }
2861
2862     // Decimal Point Motion Operations
2863
2864     /**
2865      * Returns a {@code BigDecimal} which is equivalent to this one
2866      * with the decimal point moved {@code n} places to the left.  If
2867      * {@code n} is non-negative, the call merely adds {@code n} to
2868      * the scale.  If {@code n} is negative, the call is equivalent
2869      * to {@code movePointRight(-n)}.  The {@code BigDecimal}
2870      * returned by this call has value <code>(this &times;
2871      * 10<sup>-n</sup>)</code> and scale {@code max(this.scale()+n,
2872      * 0)}.
2873      *
2874      * @param  n number of places to move the decimal point to the left.
2875      * @return a {@code BigDecimal} which is equivalent to this one with the
2876      *         decimal point moved {@code n} places to the left.
2877      * @throws ArithmeticException if scale overflows.
2878      */
2879     public BigDecimal movePointLeft(int n) {
2880         if (n == 0) return this;
2881
2882         // Cannot use movePointRight(-n) in case of n==Integer.MIN_VALUE
2883         int newScale = checkScale((long)scale + n);
2884         BigDecimal num = new BigDecimal(intVal, intCompact, newScale, 0);
2885         return num.scale < 0 ? num.setScale(0, ROUND_UNNECESSARY) : num;
2886     }
2887
2888     /**
2889      * Returns a {@code BigDecimal} which is equivalent to this one
2890      * with the decimal point moved {@code n} places to the right.
2891      * If {@code n} is non-negative, the call merely subtracts
2892      * {@code n} from the scale.  If {@code n} is negative, the call
2893      * is equivalent to {@code movePointLeft(-n)}.  The
2894      * {@code BigDecimal} returned by this call has value <code>(this
2895      * &times; 10<sup>n</sup>)</code> and scale {@code max(this.scale()-n,
2896      * 0)}.
2897      *
2898      * @param  n number of places to move the decimal point to the right.
2899      * @return a {@code BigDecimal} which is equivalent to this one
2900      *         with the decimal point moved {@code n} places to the right.
2901      * @throws ArithmeticException if scale overflows.
2902      */
2903     public BigDecimal movePointRight(int n) {
2904         if (n == 0) return this;
2905
2906         // Cannot use movePointLeft(-n) in case of n==Integer.MIN_VALUE
2907         int newScale = checkScale((long)scale - n);
2908         BigDecimal num = new BigDecimal(intVal, intCompact, newScale, 0);
2909         return num.scale < 0 ? num.setScale(0, ROUND_UNNECESSARY) : num;
2910     }
2911
2912     /**
2913      * Returns a BigDecimal whose numerical value is equal to
2914      * ({@code this} * 10<sup>n</sup>).  The scale of
2915      * the result is {@code (this.scale() - n)}.
2916      *
2917      * @param n the exponent power of ten to scale by
2918      * @return a BigDecimal whose numerical value is equal to
2919      * ({@code this} * 10<sup>n</sup>)
2920      * @throws ArithmeticException if the scale would be
2921      *         outside the range of a 32-bit integer.
2922      *
2923      * @since 1.5
2924      */
2925     public BigDecimal scaleByPowerOfTen(int n) {
2926         return new BigDecimal(intVal, intCompact,
2927                               checkScale((long)scale - n), precision);
2928     }
2929
2930     /**
2931      * Returns a {@code BigDecimal} which is numerically equal to
2932      * this one but with any trailing zeros removed from the
2933      * representation.  For example, stripping the trailing zeros from
2934      * the {@code BigDecimal} value {@code 600.0}, which has
2935      * [{@code BigInteger}, {@code scale}] components equals to
2936      * [6000, 1], yields {@code 6E2} with [{@code BigInteger},
2937      * {@code scale}] components equals to [6, -2].  If
2938      * this BigDecimal is numerically equal to zero, then
2939      * {@code BigDecimal.ZERO} is returned.
2940      *
2941      * @return a numerically equal {@code BigDecimal} with any
2942      * trailing zeros removed.
2943      * @since 1.5
2944      */
2945     public BigDecimal stripTrailingZeros() {
2946         if (intCompact == 0 || (intVal != null && intVal.signum() == 0)) {
2947             return BigDecimal.ZERO;
2948         } else if (intCompact != INFLATED) {
2949             return createAndStripZerosToMatchScale(intCompact, scale, Long.MIN_VALUE);
2950         } else {
2951             return createAndStripZerosToMatchScale(intVal, scale, Long.MIN_VALUE);
2952         }
2953     }
2954
2955     // Comparison Operations
2956
2957     /**
2958      * Compares this {@code BigDecimal} with the specified
2959      * {@code BigDecimal}.  Two {@code BigDecimal} objects that are
2960      * equal in value but have a different scale (like 2.0 and 2.00)
2961      * are considered equal by this method.  This method is provided
2962      * in preference to individual methods for each of the six boolean
2963      * comparison operators ({@literal <}, ==,
2964      * {@literal >}, {@literal >=}, !=, {@literal <=}).  The
2965      * suggested idiom for performing these comparisons is:
2966      * {@code (x.compareTo(y)} &lt;<i>op</i>&gt; {@code 0)}, where
2967      * &lt;<i>op</i>&gt; is one of the six comparison operators.
2968      *
2969      * @param  val {@code BigDecimal} to which this {@code BigDecimal} is
2970      *         to be compared.
2971      * @return -1, 0, or 1 as this {@code BigDecimal} is numerically
2972      *          less than, equal to, or greater than {@code val}.
2973      */
2974     @Override
2975     public int compareTo(BigDecimal val) {
2976         // Quick path for equal scale and non-inflated case.
2977         if (scale == val.scale) {
2978             long xs = intCompact;
2979             long ys = val.intCompact;
2980             if (xs != INFLATED && ys != INFLATED)
2981                 return xs != ys ? ((xs > ys) ? 1 : -1) : 0;
2982         }
2983         int xsign = this.signum();
2984         int ysign = val.signum();
2985         if (xsign != ysign)
2986             return (xsign > ysign) ? 1 : -1;
2987         if (xsign == 0)
2988             return 0;
2989         int cmp = compareMagnitude(val);
2990         return (xsign > 0) ? cmp : -cmp;
2991     }
2992
2993     /**
2994      * Version of compareTo that ignores sign.
2995      */
2996     private int compareMagnitude(BigDecimal val) {
2997         // Match scales, avoid unnecessary inflation
2998         long ys = val.intCompact;
2999         long xs = this.intCompact;
3000         if (xs == 0)
3001             return (ys == 0) ? 0 : -1;
3002         if (ys == 0)
3003             return 1;
3004
3005         long sdiff = (long)this.scale - val.scale;
3006         if (sdiff != 0) {
3007             // Avoid matching scales if the (adjusted) exponents differ
3008             long xae = (long)this.precision() - this.scale;   // [-1]
3009             long yae = (long)val.precision() - val.scale;     // [-1]
3010             if (xae < yae)
3011                 return -1;
3012             if (xae > yae)
3013                 return 1;
3014             if (sdiff < 0) {
3015                 // The cases sdiff <= Integer.MIN_VALUE intentionally fall through.
3016                 if ( sdiff > Integer.MIN_VALUE &&
3017                       (xs == INFLATED ||
3018                       (xs = longMultiplyPowerTen(xs, (int)-sdiff)) == INFLATED) &&
3019                      ys == INFLATED) {
3020                     BigInteger rb = bigMultiplyPowerTen((int)-sdiff);
3021                     return rb.compareMagnitude(val.intVal);
3022                 }
3023             } else { // sdiff > 0
3024                 // The cases sdiff > Integer.MAX_VALUE intentionally fall through.
3025                 if ( sdiff <= Integer.MAX_VALUE &&
3026                       (ys == INFLATED ||
3027                       (ys = longMultiplyPowerTen(ys, (int)sdiff)) == INFLATED) &&
3028                      xs == INFLATED) {
3029                     BigInteger rb = val.bigMultiplyPowerTen((int)sdiff);
3030                     return this.intVal.compareMagnitude(rb);
3031                 }
3032             }
3033         }
3034         if (xs != INFLATED)
3035             return (ys != INFLATED) ? longCompareMagnitude(xs, ys) : -1;
3036         else if (ys != INFLATED)
3037             return 1;
3038         else
3039             return this.intVal.compareMagnitude(val.intVal);
3040     }
3041
3042     /**
3043      * Compares this {@code BigDecimal} with the specified
3044      * {@code Object} for equality.  Unlike {@link
3045      * #compareTo(BigDecimal) compareTo}, this method considers two
3046      * {@code BigDecimal} objects equal only if they are equal in
3047      * value and scale (thus 2.0 is not equal to 2.00 when compared by
3048      * this method).
3049      *
3050      * @param  x {@code Object} to which this {@code BigDecimal} is
3051      *         to be compared.
3052      * @return {@code true} if and only if the specified {@code Object} is a
3053      *         {@code BigDecimal} whose value and scale are equal to this
3054      *         {@code BigDecimal}'s.
3055      * @see    #compareTo(java.math.BigDecimal)
3056      * @see    #hashCode
3057      */
3058     @Override
3059     public boolean equals(Object x) {
3060         if (!(x instanceof BigDecimal))
3061             return false;
3062         BigDecimal xDec = (BigDecimal) x;
3063         if (x == this)
3064             return true;
3065         if (scale != xDec.scale)
3066             return false;
3067         long s = this.intCompact;
3068         long xs = xDec.intCompact;
3069         if (s != INFLATED) {
3070             if (xs == INFLATED)
3071                 xs = compactValFor(xDec.intVal);
3072             return xs == s;
3073         } else if (xs != INFLATED)
3074             return xs == compactValFor(this.intVal);
3075
3076         return this.inflated().equals(xDec.inflated());
3077     }
3078
3079     /**
3080      * Returns the minimum of this {@code BigDecimal} and
3081      * {@code val}.
3082      *
3083      * @param  val value with which the minimum is to be computed.
3084      * @return the {@code BigDecimal} whose value is the lesser of this
3085      *         {@code BigDecimal} and {@code val}.  If they are equal,
3086      *         as defined by the {@link #compareTo(BigDecimal) compareTo}
3087      *         method, {@code this} is returned.
3088      * @see    #compareTo(java.math.BigDecimal)
3089      */
3090     public BigDecimal min(BigDecimal val) {
3091         return (compareTo(val) <= 0 ? this : val);
3092     }
3093
3094     /**
3095      * Returns the maximum of this {@code BigDecimal} and {@code val}.
3096      *
3097      * @param  val value with which the maximum is to be computed.
3098      * @return the {@code BigDecimal} whose value is the greater of this
3099      *         {@code BigDecimal} and {@code val}.  If they are equal,
3100      *         as defined by the {@link #compareTo(BigDecimal) compareTo}
3101      *         method, {@code this} is returned.
3102      * @see    #compareTo(java.math.BigDecimal)
3103      */
3104     public BigDecimal max(BigDecimal val) {
3105         return (compareTo(val) >= 0 ? this : val);
3106     }
3107
3108     // Hash Function
3109
3110     /**
3111      * Returns the hash code for this {@code BigDecimal}.  Note that
3112      * two {@code BigDecimal} objects that are numerically equal but
3113      * differ in scale (like 2.0 and 2.00) will generally <em>not</em>
3114      * have the same hash code.
3115      *
3116      * @return hash code for this {@code BigDecimal}.
3117      * @see #equals(Object)
3118      */
3119     @Override
3120     public int hashCode() {
3121         if (intCompact != INFLATED) {
3122             long val2 = (intCompact < 0)? -intCompact : intCompact;
3123             int temp = (int)( ((int)(val2 >>> 32)) * 31  +
3124                               (val2 & LONG_MASK));
3125             return 31*((intCompact < 0) ?-temp:temp) + scale;
3126         } else
3127             return 31*intVal.hashCode() + scale;
3128     }
3129
3130     // Format Converters
3131
3132     /**
3133      * Returns the string representation of this {@code BigDecimal},
3134      * using scientific notation if an exponent is needed.
3135      *
3136      * <p>A standard canonical string form of the {@code BigDecimal}
3137      * is created as though by the following steps: first, the
3138      * absolute value of the unscaled value of the {@code BigDecimal}
3139      * is converted to a string in base ten using the characters
3140      * {@code '0'} through {@code '9'} with no leading zeros (except
3141      * if its value is zero, in which case a single {@code '0'}
3142      * character is used).
3143      *
3144      * <p>Next, an <i>adjusted exponent</i> is calculated; this is the
3145      * negated scale, plus the number of characters in the converted
3146      * unscaled value, less one.  That is,
3147      * {@code -scale+(ulength-1)}, where {@code ulength} is the
3148      * length of the absolute value of the unscaled value in decimal
3149      * digits (its <i>precision</i>).
3150      *
3151      * <p>If the scale is greater than or equal to zero and the
3152      * adjusted exponent is greater than or equal to {@code -6}, the
3153      * number will be converted to a character form without using
3154      * exponential notation.  In this case, if the scale is zero then
3155      * no decimal point is added and if the scale is positive a
3156      * decimal point will be inserted with the scale specifying the
3157      * number of characters to the right of the decimal point.
3158      * {@code '0'} characters are added to the left of the converted
3159      * unscaled value as necessary.  If no character precedes the
3160      * decimal point after this insertion then a conventional
3161      * {@code '0'} character is prefixed.
3162      *
3163      * <p>Otherwise (that is, if the scale is negative, or the
3164      * adjusted exponent is less than {@code -6}), the number will be
3165      * converted to a character form using exponential notation.  In
3166      * this case, if the converted {@code BigInteger} has more than
3167      * one digit a decimal point is inserted after the first digit.
3168      * An exponent in character form is then suffixed to the converted
3169      * unscaled value (perhaps with inserted decimal point); this
3170      * comprises the letter {@code 'E'} followed immediately by the
3171      * adjusted exponent converted to a character form.  The latter is
3172      * in base ten, using the characters {@code '0'} through
3173      * {@code '9'} with no leading zeros, and is always prefixed by a
3174      * sign character {@code '-'} (<code>'\u002D'</code>) if the
3175      * adjusted exponent is negative, {@code '+'}
3176      * (<code>'\u002B'</code>) otherwise).
3177      *
3178      * <p>Finally, the entire string is prefixed by a minus sign
3179      * character {@code '-'} (<code>'\u002D'</code>) if the unscaled
3180      * value is less than zero.  No sign character is prefixed if the
3181      * unscaled value is zero or positive.
3182      *
3183      * <p><b>Examples:</b>
3184      * <p>For each representation [<i>unscaled value</i>, <i>scale</i>]
3185      * on the left, the resulting string is shown on the right.
3186      * <pre>
3187      * [123,0]      "123"
3188      * [-123,0]     "-123"
3189      * [123,-1]     "1.23E+3"
3190      * [123,-3]     "1.23E+5"
3191      * [123,1]      "12.3"
3192      * [123,5]      "0.00123"
3193      * [123,10]     "1.23E-8"
3194      * [-123,12]    "-1.23E-10"
3195      * </pre>
3196      *
3197      * <b>Notes:</b>
3198      * <ol>
3199      *
3200      * <li>There is a one-to-one mapping between the distinguishable
3201      * {@code BigDecimal} values and the result of this conversion.
3202      * That is, every distinguishable {@code BigDecimal} value
3203      * (unscaled value and scale) has a unique string representation
3204      * as a result of using {@code toString}.  If that string
3205      * representation is converted back to a {@code BigDecimal} using
3206      * the {@link #BigDecimal(String)} constructor, then the original
3207      * value will be recovered.
3208      *
3209      * <li>The string produced for a given number is always the same;
3210      * it is not affected by locale.  This means that it can be used
3211      * as a canonical string representation for exchanging decimal
3212      * data, or as a key for a Hashtable, etc.  Locale-sensitive
3213      * number formatting and parsing is handled by the {@link
3214      * java.text.NumberFormat} class and its subclasses.
3215      *
3216      * <li>The {@link #toEngineeringString} method may be used for
3217      * presenting numbers with exponents in engineering notation, and the
3218      * {@link #setScale(int,RoundingMode) setScale} method may be used for
3219      * rounding a {@code BigDecimal} so it has a known number of digits after
3220      * the decimal point.
3221      *
3222      * <li>The digit-to-character mapping provided by
3223      * {@code Character.forDigit} is used.
3224      *
3225      * </ol>
3226      *
3227      * @return string representation of this {@code BigDecimal}.
3228      * @see    Character#forDigit
3229      * @see    #BigDecimal(java.lang.String)
3230      */
3231     @Override
3232     public String toString() {
3233         String sc = stringCache;
3234         if (sc == null) {
3235             stringCache = sc = layoutChars(true);
3236         }
3237         return sc;
3238     }
3239
3240     /**
3241      * Returns a string representation of this {@code BigDecimal},
3242      * using engineering notation if an exponent is needed.
3243      *
3244      * <p>Returns a string that represents the {@code BigDecimal} as
3245      * described in the {@link #toString()} method, except that if
3246      * exponential notation is used, the power of ten is adjusted to
3247      * be a multiple of three (engineering notation) such that the
3248      * integer part of nonzero values will be in the range 1 through
3249      * 999.  If exponential notation is used for zero values, a
3250      * decimal point and one or two fractional zero digits are used so
3251      * that the scale of the zero value is preserved.  Note that
3252      * unlike the output of {@link #toString()}, the output of this
3253      * method is <em>not</em> guaranteed to recover the same [integer,
3254      * scale] pair of this {@code BigDecimal} if the output string is
3255      * converting back to a {@code BigDecimal} using the {@linkplain
3256      * #BigDecimal(String) string constructor}.  The result of this method meets
3257      * the weaker constraint of always producing a numerically equal
3258      * result from applying the string constructor to the method's output.
3259      *
3260      * @return string representation of this {@code BigDecimal}, using
3261      *         engineering notation if an exponent is needed.
3262      * @since  1.5
3263      */
3264     public String toEngineeringString() {
3265         return layoutChars(false);
3266     }
3267
3268     /**
3269      * Returns a string representation of this {@code BigDecimal}
3270      * without an exponent field.  For values with a positive scale,
3271      * the number of digits to the right of the decimal point is used
3272      * to indicate scale.  For values with a zero or negative scale,
3273      * the resulting string is generated as if the value were
3274      * converted to a numerically equal value with zero scale and as
3275      * if all the trailing zeros of the zero scale value were present
3276      * in the result.
3277      *
3278      * The entire string is prefixed by a minus sign character '-'
3279      * (<code>'\u002D'</code>) if the unscaled value is less than
3280      * zero. No sign character is prefixed if the unscaled value is
3281      * zero or positive.
3282      *
3283      * Note that if the result of this method is passed to the
3284      * {@linkplain #BigDecimal(String) string constructor}, only the
3285      * numerical value of this {@code BigDecimal} will necessarily be
3286      * recovered; the representation of the new {@code BigDecimal}
3287      * may have a different scale.  In particular, if this
3288      * {@code BigDecimal} has a negative scale, the string resulting
3289      * from this method will have a scale of zero when processed by
3290      * the string constructor.
3291      *
3292      * (This method behaves analogously to the {@code toString}
3293      * method in 1.4 and earlier releases.)
3294      *
3295      * @return a string representation of this {@code BigDecimal}
3296      * without an exponent field.
3297      * @since 1.5
3298      * @see #toString()
3299      * @see #toEngineeringString()
3300      */
3301     public String toPlainString() {
3302         if(scale==0) {
3303             if(intCompact!=INFLATED) {
3304                 return Long.toString(intCompact);
3305             } else {
3306                 return intVal.toString();
3307             }
3308         }
3309         if(this.scale<0) { // No decimal point
3310             if(signum()==0) {
3311                 return "0";
3312             }
3313             int trailingZeros = checkScaleNonZero((-(long)scale));
3314             StringBuilder buf;
3315             if(intCompact!=INFLATED) {
3316                 buf = new StringBuilder(20+trailingZeros);
3317                 buf.append(intCompact);
3318             } else {
3319                 String str = intVal.toString();
3320                 buf = new StringBuilder(str.length()+trailingZeros);
3321                 buf.append(str);
3322             }
3323             for (int i = 0; i < trailingZeros; i++) {
3324                 buf.append('0');
3325             }
3326             return buf.toString();
3327         }
3328         String str ;
3329         if(intCompact!=INFLATED) {
3330             str = Long.toString(Math.abs(intCompact));
3331         } else {
3332             str = intVal.abs().toString();
3333         }
3334         return getValueString(signum(), str, scale);
3335     }
3336
3337     /* Returns a digit.digit string */
3338     private String getValueString(int signum, String intString, int scale) {
3339         /* Insert decimal point */
3340         StringBuilder buf;
3341         int insertionPoint = intString.length() - scale;
3342         if (insertionPoint == 0) {  /* Point goes right before intVal */
3343             return (signum<0 ? "-0." : "0.") + intString;
3344         } else if (insertionPoint > 0) { /* Point goes inside intVal */
3345             buf = new StringBuilder(intString);
3346             buf.insert(insertionPoint, '.');
3347             if (signum < 0)
3348                 buf.insert(0, '-');
3349         } else { /* We must insert zeros between point and intVal */
3350             buf = new StringBuilder(3-insertionPoint + intString.length());
3351             buf.append(signum<0 ? "-0." : "0.");
3352             for (int i=0; i<-insertionPoint; i++) {
3353                 buf.append('0');
3354             }
3355             buf.append(intString);
3356         }
3357         return buf.toString();
3358     }
3359
3360     /**
3361      * Converts this {@code BigDecimal} to a {@code BigInteger}.
3362      * This conversion is analogous to the
3363      * <i>narrowing primitive conversion</i> from {@code double} to
3364      * {@code long} as defined in
3365      * <cite>The Java&trade; Language Specification</cite>:
3366      * any fractional part of this
3367      * {@code BigDecimal} will be discarded.  Note that this
3368      * conversion can lose information about the precision of the
3369      * {@code BigDecimal} value.
3370      * <p>
3371      * To have an exception thrown if the conversion is inexact (in
3372      * other words if a nonzero fractional part is discarded), use the
3373      * {@link #toBigIntegerExact()} method.
3374      *
3375      * @return this {@code BigDecimal} converted to a {@code BigInteger}.
3376      * @jls 5.1.3 Narrowing Primitive Conversion
3377      */
3378     public BigInteger toBigInteger() {
3379         // force to an integer, quietly
3380         return this.setScale(0, ROUND_DOWN).inflated();
3381     }
3382
3383     /**
3384      * Converts this {@code BigDecimal} to a {@code BigInteger},
3385      * checking for lost information.  An exception is thrown if this
3386      * {@code BigDecimal} has a nonzero fractional part.
3387      *
3388      * @return this {@code BigDecimal} converted to a {@code BigInteger}.
3389      * @throws ArithmeticException if {@code this} has a nonzero
3390      *         fractional part.
3391      * @since  1.5
3392      */
3393     public BigInteger toBigIntegerExact() {
3394         // round to an integer, with Exception if decimal part non-0
3395         return this.setScale(0, ROUND_UNNECESSARY).inflated();
3396     }
3397
3398     /**
3399      * Converts this {@code BigDecimal} to a {@code long}.
3400      * This conversion is analogous to the
3401      * <i>narrowing primitive conversion</i> from {@code double} to
3402      * {@code short} as defined in
3403      * <cite>The Java&trade; Language Specification</cite>:
3404      * any fractional part of this
3405      * {@code BigDecimal} will be discarded, and if the resulting
3406      * "{@code BigInteger}" is too big to fit in a
3407      * {@code long}, only the low-order 64 bits are returned.
3408      * Note that this conversion can lose information about the
3409      * overall magnitude and precision of this {@code BigDecimal} value as well
3410      * as return a result with the opposite sign.
3411      *
3412      * @return this {@code BigDecimal} converted to a {@code long}.
3413      * @jls 5.1.3 Narrowing Primitive Conversion
3414      */
3415     @Override
3416     public long longValue(){
3417         return (intCompact != INFLATED && scale == 0) ?
3418             intCompact:
3419             toBigInteger().longValue();
3420     }
3421
3422     /**
3423      * Converts this {@code BigDecimal} to a {@code long}, checking
3424      * for lost information.  If this {@code BigDecimal} has a
3425      * nonzero fractional part or is out of the possible range for a
3426      * {@code long} result then an {@code ArithmeticException} is
3427      * thrown.
3428      *
3429      * @return this {@code BigDecimal} converted to a {@code long}.
3430      * @throws ArithmeticException if {@code this} has a nonzero
3431      *         fractional part, or will not fit in a {@code long}.
3432      * @since  1.5
3433      */
3434     public long longValueExact() {
3435         if (intCompact != INFLATED && scale == 0)
3436             return intCompact;
3437         // If more than 19 digits in integer part it cannot possibly fit
3438         if ((precision() - scale) > 19) // [OK for negative scale too]
3439             throw new java.lang.ArithmeticException("Overflow");
3440         // Fastpath zero and < 1.0 numbers (the latter can be very slow
3441         // to round if very small)
3442         if (this.signum() == 0)
3443             return 0;
3444         if ((this.precision() - this.scale) <= 0)
3445             throw new ArithmeticException("Rounding necessary");
3446         // round to an integer, with Exception if decimal part non-0
3447         BigDecimal num = this.setScale(0, ROUND_UNNECESSARY);
3448         if (num.precision() >= 19) // need to check carefully
3449             LongOverflow.check(num);
3450         return num.inflated().longValue();
3451     }
3452
3453     private static class LongOverflow {
3454         /** BigInteger equal to Long.MIN_VALUE. */
3455         private static final BigInteger LONGMIN = BigInteger.valueOf(Long.MIN_VALUE);
3456
3457         /** BigInteger equal to Long.MAX_VALUE. */
3458         private static final BigInteger LONGMAX = BigInteger.valueOf(Long.MAX_VALUE);
3459
3460         public static void check(BigDecimal num) {
3461             BigInteger intVal = num.inflated();
3462             if (intVal.compareTo(LONGMIN) < 0 ||
3463                 intVal.compareTo(LONGMAX) > 0)
3464                 throw new java.lang.ArithmeticException("Overflow");
3465         }
3466     }
3467
3468     /**
3469      * Converts this {@code BigDecimal} to an {@code int}.
3470      * This conversion is analogous to the
3471      * <i>narrowing primitive conversion</i> from {@code double} to
3472      * {@code short} as defined in
3473      * <cite>The Java&trade; Language Specification</cite>:
3474      * any fractional part of this
3475      * {@code BigDecimal} will be discarded, and if the resulting
3476      * "{@code BigInteger}" is too big to fit in an
3477      * {@code int}, only the low-order 32 bits are returned.
3478      * Note that this conversion can lose information about the
3479      * overall magnitude and precision of this {@code BigDecimal}
3480      * value as well as return a result with the opposite sign.
3481      *
3482      * @return this {@code BigDecimal} converted to an {@code int}.
3483      * @jls 5.1.3 Narrowing Primitive Conversion
3484      */
3485     @Override
3486     public int intValue() {
3487         return  (intCompact != INFLATED && scale == 0) ?
3488             (int)intCompact :
3489             toBigInteger().intValue();
3490     }
3491
3492     /**
3493      * Converts this {@code BigDecimal} to an {@code int}, checking
3494      * for lost information.  If this {@code BigDecimal} has a
3495      * nonzero fractional part or is out of the possible range for an
3496      * {@code int} result then an {@code ArithmeticException} is
3497      * thrown.
3498      *
3499      * @return this {@code BigDecimal} converted to an {@code int}.
3500      * @throws ArithmeticException if {@code this} has a nonzero
3501      *         fractional part, or will not fit in an {@code int}.
3502      * @since  1.5
3503      */
3504     public int intValueExact() {
3505        long num;
3506        num = this.longValueExact();     // will check decimal part
3507        if ((int)num != num)
3508            throw new java.lang.ArithmeticException("Overflow");
3509        return (int)num;
3510     }
3511
3512     /**
3513      * Converts this {@code BigDecimal} to a {@code short}, checking
3514      * for lost information.  If this {@code BigDecimal} has a
3515      * nonzero fractional part or is out of the possible range for a
3516      * {@code short} result then an {@code ArithmeticException} is
3517      * thrown.
3518      *
3519      * @return this {@code BigDecimal} converted to a {@code short}.
3520      * @throws ArithmeticException if {@code this} has a nonzero
3521      *         fractional part, or will not fit in a {@code short}.
3522      * @since  1.5
3523      */
3524     public short shortValueExact() {
3525        long num;
3526        num = this.longValueExact();     // will check decimal part
3527        if ((short)num != num)
3528            throw new java.lang.ArithmeticException("Overflow");
3529        return (short)num;
3530     }
3531
3532     /**
3533      * Converts this {@code BigDecimal} to a {@code byte}, checking
3534      * for lost information.  If this {@code BigDecimal} has a
3535      * nonzero fractional part or is out of the possible range for a
3536      * {@code byte} result then an {@code ArithmeticException} is
3537      * thrown.
3538      *
3539      * @return this {@code BigDecimal} converted to a {@code byte}.
3540      * @throws ArithmeticException if {@code this} has a nonzero
3541      *         fractional part, or will not fit in a {@code byte}.
3542      * @since  1.5
3543      */
3544     public byte byteValueExact() {
3545        long num;
3546        num = this.longValueExact();     // will check decimal part
3547        if ((byte)num != num)
3548            throw new java.lang.ArithmeticException("Overflow");
3549        return (byte)num;
3550     }
3551
3552     /**
3553      * Converts this {@code BigDecimal} to a {@code float}.
3554      * This conversion is similar to the
3555      * <i>narrowing primitive conversion</i> from {@code double} to
3556      * {@code float} as defined in
3557      * <cite>The Java&trade; Language Specification</cite>:
3558      * if this {@code BigDecimal} has too great a
3559      * magnitude to represent as a {@code float}, it will be
3560      * converted to {@link Float#NEGATIVE_INFINITY} or {@link
3561      * Float#POSITIVE_INFINITY} as appropriate.  Note that even when
3562      * the return value is finite, this conversion can lose
3563      * information about the precision of the {@code BigDecimal}
3564      * value.
3565      *
3566      * @return this {@code BigDecimal} converted to a {@code float}.
3567      * @jls 5.1.3 Narrowing Primitive Conversion
3568      */
3569     @Override
3570     public float floatValue(){
3571         if(intCompact != INFLATED) {
3572             if (scale == 0) {
3573                 return (float)intCompact;
3574             } else {
3575                 /*
3576                  * If both intCompact and the scale can be exactly
3577                  * represented as float values, perform a single float
3578                  * multiply or divide to compute the (properly
3579                  * rounded) result.
3580                  */
3581                 if (Math.abs(intCompact) < 1L<<22 ) {
3582                     // Don't have too guard against
3583                     // Math.abs(MIN_VALUE) because of outer check
3584                     // against INFLATED.
3585                     if (scale > 0 && scale < FLOAT_10_POW.length) {
3586                         return (float)intCompact / FLOAT_10_POW[scale];
3587                     } else if (scale < 0 && scale > -FLOAT_10_POW.length) {
3588                         return (float)intCompact * FLOAT_10_POW[-scale];
3589                     }
3590                 }
3591             }
3592         }
3593         // Somewhat inefficient, but guaranteed to work.
3594         return Float.parseFloat(this.toString());
3595     }
3596
3597     /**
3598      * Converts this {@code BigDecimal} to a {@code double}.
3599      * This conversion is similar to the
3600      * <i>narrowing primitive conversion</i> from {@code double} to
3601      * {@code float} as defined in
3602      * <cite>The Java&trade; Language Specification</cite>:
3603      * if this {@code BigDecimal} has too great a
3604      * magnitude represent as a {@code double}, it will be
3605      * converted to {@link Double#NEGATIVE_INFINITY} or {@link
3606      * Double#POSITIVE_INFINITY} as appropriate.  Note that even when
3607      * the return value is finite, this conversion can lose
3608      * information about the precision of the {@code BigDecimal}
3609      * value.
3610      *
3611      * @return this {@code BigDecimal} converted to a {@code double}.
3612      * @jls 5.1.3 Narrowing Primitive Conversion
3613      */
3614     @Override
3615     public double doubleValue(){
3616         if(intCompact != INFLATED) {
3617             if (scale == 0) {
3618                 return (double)intCompact;
3619             } else {
3620                 /*
3621                  * If both intCompact and the scale can be exactly
3622                  * represented as double values, perform a single
3623                  * double multiply or divide to compute the (properly
3624                  * rounded) result.
3625                  */
3626                 if (Math.abs(intCompact) < 1L<<52 ) {
3627                     // Don't have too guard against
3628                     // Math.abs(MIN_VALUE) because of outer check
3629                     // against INFLATED.
3630                     if (scale > 0 && scale < DOUBLE_10_POW.length) {
3631                         return (double)intCompact / DOUBLE_10_POW[scale];
3632                     } else if (scale < 0 && scale > -DOUBLE_10_POW.length) {
3633                         return (double)intCompact * DOUBLE_10_POW[-scale];
3634                     }
3635                 }
3636             }
3637         }
3638         // Somewhat inefficient, but guaranteed to work.
3639         return Double.parseDouble(this.toString());
3640     }
3641
3642     /**
3643      * Powers of 10 which can be represented exactly in {@code
3644      * double}.
3645      */
3646     private static final double DOUBLE_10_POW[] = {
3647         1.0e0,  1.0e1,  1.0e2,  1.0e3,  1.0e4,  1.0e5,
3648         1.0e6,  1.0e7,  1.0e8,  1.0e9,  1.0e10, 1.0e11,
3649         1.0e12, 1.0e13, 1.0e14, 1.0e15, 1.0e16, 1.0e17,
3650         1.0e18, 1.0e19, 1.0e20, 1.0e21, 1.0e22
3651     };
3652
3653     /**
3654      * Powers of 10 which can be represented exactly in {@code
3655      * float}.
3656      */
3657     private static final float FLOAT_10_POW[] = {
3658         1.0e0f, 1.0e1f, 1.0e2f, 1.0e3f, 1.0e4f, 1.0e5f,
3659         1.0e6f, 1.0e7f, 1.0e8f, 1.0e9f, 1.0e10f
3660     };
3661
3662     /**
3663      * Returns the size of an ulp, a unit in the last place, of this
3664      * {@code BigDecimal}.  An ulp of a nonzero {@code BigDecimal}
3665      * value is the positive distance between this value and the
3666      * {@code BigDecimal} value next larger in magnitude with the
3667      * same number of digits.  An ulp of a zero value is numerically
3668      * equal to 1 with the scale of {@code this}.  The result is
3669      * stored with the same scale as {@code this} so the result
3670      * for zero and nonzero values is equal to {@code [1,
3671      * this.scale()]}.
3672      *
3673      * @return the size of an ulp of {@code this}
3674      * @since 1.5
3675      */
3676     public BigDecimal ulp() {
3677         return BigDecimal.valueOf(1, this.scale(), 1);
3678     }
3679
3680     // Private class to build a string representation for BigDecimal object.
3681     // "StringBuilderHelper" is constructed as a thread local variable so it is
3682     // thread safe. The StringBuilder field acts as a buffer to hold the temporary
3683     // representation of BigDecimal. The cmpCharArray holds all the characters for
3684     // the compact representation of BigDecimal (except for '-' sign' if it is
3685     // negative) if its intCompact field is not INFLATED. It is shared by all
3686     // calls to toString() and its variants in that particular thread.
3687     static class StringBuilderHelper {
3688         final StringBuilder sb;    // Placeholder for BigDecimal string
3689         final char[] cmpCharArray; // character array to place the intCompact
3690
3691         StringBuilderHelper() {
3692             sb = new StringBuilder();
3693             // All non negative longs can be made to fit into 19 character array.
3694             cmpCharArray = new char[19];
3695         }
3696
3697         // Accessors.
3698         StringBuilder getStringBuilder() {
3699             sb.setLength(0);
3700             return sb;
3701         }
3702
3703         char[] getCompactCharArray() {
3704             return cmpCharArray;
3705         }
3706
3707         /**
3708          * Places characters representing the intCompact in {@code long} into
3709          * cmpCharArray and returns the offset to the array where the
3710          * representation starts.
3711          *
3712          * @param intCompact the number to put into the cmpCharArray.
3713          * @return offset to the array where the representation starts.
3714          * Note: intCompact must be greater or equal to zero.
3715          */
3716         int putIntCompact(long intCompact) {
3717             assert intCompact >= 0;
3718
3719             long q;
3720             int r;
3721             // since we start from the least significant digit, charPos points to
3722             // the last character in cmpCharArray.
3723             int charPos = cmpCharArray.length;
3724
3725             // Get 2 digits/iteration using longs until quotient fits into an int
3726             while (intCompact > Integer.MAX_VALUE) {
3727                 q = intCompact / 100;
3728                 r = (int)(intCompact - q * 100);
3729                 intCompact = q;
3730                 cmpCharArray[--charPos] = DIGIT_ONES[r];
3731                 cmpCharArray[--charPos] = DIGIT_TENS[r];
3732             }
3733
3734             // Get 2 digits/iteration using ints when i2 >= 100
3735             int q2;
3736             int i2 = (int)intCompact;
3737             while (i2 >= 100) {
3738                 q2 = i2 / 100;
3739                 r  = i2 - q2 * 100;
3740                 i2 = q2;
3741                 cmpCharArray[--charPos] = DIGIT_ONES[r];
3742                 cmpCharArray[--charPos] = DIGIT_TENS[r];
3743             }
3744
3745             cmpCharArray[--charPos] = DIGIT_ONES[i2];
3746             if (i2 >= 10)
3747                 cmpCharArray[--charPos] = DIGIT_TENS[i2];
3748
3749             return charPos;
3750         }
3751
3752         static final char[] DIGIT_TENS = {
3753             '0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
3754             '1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
3755             '2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
3756             '3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
3757             '4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
3758             '5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
3759             '6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
3760             '7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
3761             '8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
3762             '9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
3763         };
3764
3765         static final char[] DIGIT_ONES = {
3766             '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
3767             '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
3768             '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
3769             '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
3770             '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
3771             '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
3772             '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
3773             '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
3774             '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
3775             '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
3776         };
3777     }
3778
3779     /**
3780      * Lay out this {@code BigDecimal} into a {@code char[]} array.
3781      * The Java 1.2 equivalent to this was called {@code getValueString}.
3782      *
3783      * @param  sci {@code true} for Scientific exponential notation;
3784      *          {@code false} for Engineering
3785      * @return string with canonical string representation of this
3786      *         {@code BigDecimal}
3787      */
3788     private String layoutChars(boolean sci) {
3789         if (scale == 0)                      // zero scale is trivial
3790             return (intCompact != INFLATED) ?
3791                 Long.toString(intCompact):
3792                 intVal.toString();
3793         if (scale == 2  &&
3794             intCompact >= 0 && intCompact < Integer.MAX_VALUE) {
3795             // currency fast path
3796             int lowInt = (int)intCompact % 100;
3797             int highInt = (int)intCompact / 100;
3798             return (Integer.toString(highInt) + '.' +
3799                     StringBuilderHelper.DIGIT_TENS[lowInt] +
3800                     StringBuilderHelper.DIGIT_ONES[lowInt]) ;
3801         }
3802
3803         StringBuilderHelper sbHelper = threadLocalStringBuilderHelper.get();
3804         char[] coeff;
3805         int offset;  // offset is the starting index for coeff array
3806         // Get the significand as an absolute value
3807         if (intCompact != INFLATED) {
3808             offset = sbHelper.putIntCompact(Math.abs(intCompact));
3809             coeff  = sbHelper.getCompactCharArray();
3810         } else {
3811             offset = 0;
3812             coeff  = intVal.abs().toString().toCharArray();
3813         }
3814
3815         // Construct a buffer, with sufficient capacity for all cases.
3816         // If E-notation is needed, length will be: +1 if negative, +1
3817         // if '.' needed, +2 for "E+", + up to 10 for adjusted exponent.
3818         // Otherwise it could have +1 if negative, plus leading "0.00000"
3819         StringBuilder buf = sbHelper.getStringBuilder();
3820         if (signum() < 0)             // prefix '-' if negative
3821             buf.append('-');
3822         int coeffLen = coeff.length - offset;
3823         long adjusted = -(long)scale + (coeffLen -1);
3824         if ((scale >= 0) && (adjusted >= -6)) { // plain number
3825             int pad = scale - coeffLen;         // count of padding zeros
3826             if (pad >= 0) {                     // 0.xxx form
3827                 buf.append('0');
3828                 buf.append('.');
3830                     buf.append('0');
3831                 }
3832                 buf.append(coeff, offset, coeffLen);
3833             } else {                         // xx.xx form
3834                 buf.append(coeff, offset, -pad);
3835                 buf.append('.');
3836                 buf.append(coeff, -pad + offset, scale);
3837             }
3838         } else { // E-notation is needed
3839             if (sci) {                       // Scientific notation
3840                 buf.append(coeff[offset]);   // first character
3841                 if (coeffLen > 1) {          // more to come
3842                     buf.append('.');
3843                     buf.append(coeff, offset + 1, coeffLen - 1);
3844                 }
3845             } else {                         // Engineering notation
3846                 int sig = (int)(adjusted % 3);
3847                 if (sig < 0)
3848                     sig += 3;                // [adjusted was negative]
3849                 adjusted -= sig;             // now a multiple of 3
3850                 sig++;
3851                 if (signum() == 0) {
3852                     switch (sig) {
3853                     case 1:
3854                         buf.append('0'); // exponent is a multiple of three
3855                         break;
3856                     case 2:
3857                         buf.append("0.00");
3858                         adjusted += 3;
3859                         break;
3860                     case 3:
3861                         buf.append("0.0");
3862                         adjusted += 3;
3863                         break;
3864                     default:
3865                         throw new AssertionError("Unexpected sig value " + sig);
3866                     }
3867                 } else if (sig >= coeffLen) {   // significand all in integer
3868                     buf.append(coeff, offset, coeffLen);
3869                     // may need some zeros, too
3870                     for (int i = sig - coeffLen; i > 0; i--) {
3871                         buf.append('0');
3872                     }
3873                 } else {                     // xx.xxE form
3874                     buf.append(coeff, offset, sig);
3875                     buf.append('.');
3876                     buf.append(coeff, offset + sig, coeffLen - sig);
3877                 }
3878             }
3879             if (adjusted != 0) {             // [!sci could have made 0]
3880                 buf.append('E');
3881                 if (adjusted > 0)            // force sign for positive
3882                     buf.append('+');
3884             }
3885         }
3886         return buf.toString();
3887     }
3888
3889     /**
3890      * Return 10 to the power n, as a {@code BigInteger}.
3891      *
3892      * @param  n the power of ten to be returned (>=0)
3893      * @return a {@code BigInteger} with the value (10<sup>n</sup>)
3894      */
3895     private static BigInteger bigTenToThe(int n) {
3896         if (n < 0)
3897             return BigInteger.ZERO;
3898
3899         if (n < BIG_TEN_POWERS_TABLE_MAX) {
3900             BigInteger[] pows = BIG_TEN_POWERS_TABLE;
3901             if (n < pows.length)
3902                 return pows[n];
3903             else
3904                 return expandBigIntegerTenPowers(n);
3905         }
3906
3907         return BigInteger.TEN.pow(n);
3908     }
3909
3910     /**
3911      * Expand the BIG_TEN_POWERS_TABLE array to contain at least 10**n.
3912      *
3913      * @param n the power of ten to be returned (>=0)
3914      * @return a {@code BigDecimal} with the value (10<sup>n</sup>) and
3915      *         in the meantime, the BIG_TEN_POWERS_TABLE array gets
3916      *         expanded to the size greater than n.
3917      */
3918     private static BigInteger expandBigIntegerTenPowers(int n) {
3919         synchronized(BigDecimal.class) {
3920             BigInteger[] pows = BIG_TEN_POWERS_TABLE;
3921             int curLen = pows.length;
3922             // The following comparison and the above synchronized statement is
3923             // to prevent multiple threads from expanding the same array.
3924             if (curLen <= n) {
3925                 int newLen = curLen << 1;
3926                 while (newLen <= n) {
3927                     newLen <<= 1;
3928                 }
3929                 pows = Arrays.copyOf(pows, newLen);
3930                 for (int i = curLen; i < newLen; i++) {
3931                     pows[i] = pows[i - 1].multiply(BigInteger.TEN);
3932                 }
3933                 // Based on the following facts:
3934                 // 1. pows is a private local varible;
3935                 // 2. the following store is a volatile store.
3936                 // the newly created array elements can be safely published.
3937                 BIG_TEN_POWERS_TABLE = pows;
3938             }
3939             return pows[n];
3940         }
3941     }
3942
3943     private static final long[] LONG_TEN_POWERS_TABLE = {
3944         1,                     // 0 / 10^0
3945         10,                    // 1 / 10^1
3946         100,                   // 2 / 10^2
3947         1000,                  // 3 / 10^3
3948         10000,                 // 4 / 10^4
3949         100000,                // 5 / 10^5
3950         1000000,               // 6 / 10^6
3951         10000000,              // 7 / 10^7
3952         100000000,             // 8 / 10^8
3953         1000000000,            // 9 / 10^9
3954         10000000000L,          // 10 / 10^10
3955         100000000000L,         // 11 / 10^11
3956         1000000000000L,        // 12 / 10^12
3957         10000000000000L,       // 13 / 10^13
3958         100000000000000L,      // 14 / 10^14
3959         1000000000000000L,     // 15 / 10^15
3960         10000000000000000L,    // 16 / 10^16
3961         100000000000000000L,   // 17 / 10^17
3962         1000000000000000000L   // 18 / 10^18
3963     };
3964
3965     private static volatile BigInteger BIG_TEN_POWERS_TABLE[] = {
3966         BigInteger.ONE,
3967         BigInteger.valueOf(10),
3968         BigInteger.valueOf(100),
3969         BigInteger.valueOf(1000),
3970         BigInteger.valueOf(10000),
3971         BigInteger.valueOf(100000),
3972         BigInteger.valueOf(1000000),
3973         BigInteger.valueOf(10000000),
3974         BigInteger.valueOf(100000000),
3975         BigInteger.valueOf(1000000000),
3976         BigInteger.valueOf(10000000000L),
3977         BigInteger.valueOf(100000000000L),
3978         BigInteger.valueOf(1000000000000L),
3979         BigInteger.valueOf(10000000000000L),
3980         BigInteger.valueOf(100000000000000L),
3981         BigInteger.valueOf(1000000000000000L),
3982         BigInteger.valueOf(10000000000000000L),
3983         BigInteger.valueOf(100000000000000000L),
3984         BigInteger.valueOf(1000000000000000000L)
3985     };
3986
3987     private static final int BIG_TEN_POWERS_TABLE_INITLEN =
3988         BIG_TEN_POWERS_TABLE.length;
3989     private static final int BIG_TEN_POWERS_TABLE_MAX =
3990         16 * BIG_TEN_POWERS_TABLE_INITLEN;
3991
3992     private static final long THRESHOLDS_TABLE[] = {
3993         Long.MAX_VALUE,                     // 0
3994         Long.MAX_VALUE/10L,                 // 1
3995         Long.MAX_VALUE/100L,                // 2
3996         Long.MAX_VALUE/1000L,               // 3
3997         Long.MAX_VALUE/10000L,              // 4
3998         Long.MAX_VALUE/100000L,             // 5
3999         Long.MAX_VALUE/1000000L,            // 6
4000         Long.MAX_VALUE/10000000L,           // 7
4001         Long.MAX_VALUE/100000000L,          // 8
4002         Long.MAX_VALUE/1000000000L,         // 9
4003         Long.MAX_VALUE/10000000000L,        // 10
4004         Long.MAX_VALUE/100000000000L,       // 11
4005         Long.MAX_VALUE/1000000000000L,      // 12
4006         Long.MAX_VALUE/10000000000000L,     // 13
4007         Long.MAX_VALUE/100000000000000L,    // 14
4008         Long.MAX_VALUE/1000000000000000L,   // 15
4009         Long.MAX_VALUE/10000000000000000L,  // 16
4010         Long.MAX_VALUE/100000000000000000L, // 17
4011         Long.MAX_VALUE/1000000000000000000L // 18
4012     };
4013
4014     /**
4015      * Compute val * 10 ^ n; return this product if it is
4016      * representable as a long, INFLATED otherwise.
4017      */
4018     private static long longMultiplyPowerTen(long val, int n) {
4019         if (val == 0 || n <= 0)
4020             return val;
4021         long[] tab = LONG_TEN_POWERS_TABLE;
4022         long[] bounds = THRESHOLDS_TABLE;
4023         if (n < tab.length && n < bounds.length) {
4024             long tenpower = tab[n];
4025             if (val == 1)
4026                 return tenpower;
4027             if (Math.abs(val) <= bounds[n])
4028                 return val * tenpower;
4029         }
4030         return INFLATED;
4031     }
4032
4033     /**
4034      * Compute this * 10 ^ n.
4035      * Needed mainly to allow special casing to trap zero value
4036      */
4037     private BigInteger bigMultiplyPowerTen(int n) {
4038         if (n <= 0)
4039             return this.inflated();
4040
4041         if (intCompact != INFLATED)
4042             return bigTenToThe(n).multiply(intCompact);
4043         else
4044             return intVal.multiply(bigTenToThe(n));
4045     }
4046
4047     /**
4048      * Returns appropriate BigInteger from intVal field if intVal is
4049      * null, i.e. the compact representation is in use.
4050      */
4051     private BigInteger inflated() {
4052         if (intVal == null) {
4053             return BigInteger.valueOf(intCompact);
4054         }
4055         return intVal;
4056     }
4057
4058     /**
4059      * Match the scales of two {@code BigDecimal}s to align their
4060      * least significant digits.
4061      *
4062      * <p>If the scales of val[0] and val[1] differ, rescale
4063      * (non-destructively) the lower-scaled {@code BigDecimal} so
4064      * they match.  That is, the lower-scaled reference will be
4065      * replaced by a reference to a new object with the same scale as
4066      * the other {@code BigDecimal}.
4067      *
4068      * @param  val array of two elements referring to the two
4069      *         {@code BigDecimal}s to be aligned.
4070      */
4071     private static void matchScale(BigDecimal[] val) {
4072         if (val[0].scale < val[1].scale) {
4073             val[0] = val[0].setScale(val[1].scale, ROUND_UNNECESSARY);
4074         } else if (val[1].scale < val[0].scale) {
4075             val[1] = val[1].setScale(val[0].scale, ROUND_UNNECESSARY);
4076         }
4077     }
4078
4079     private static class UnsafeHolder {
4080         private static final jdk.internal.misc.Unsafe unsafe
4081                 = jdk.internal.misc.Unsafe.getUnsafe();
4082         private static final long intCompactOffset
4083                 = unsafe.objectFieldOffset(BigDecimal.class, "intCompact");
4084         private static final long intValOffset
4085                 = unsafe.objectFieldOffset(BigDecimal.class, "intVal");
4086
4087         static void setIntCompact(BigDecimal bd, long val) {
4088             unsafe.putLong(bd, intCompactOffset, val);
4089         }
4090
4091         static void setIntValVolatile(BigDecimal bd, BigInteger val) {
4092             unsafe.putReferenceVolatile(bd, intValOffset, val);
4093         }
4094     }
4095
4096     /**
4097      * Reconstitute the {@code BigDecimal} instance from a stream (that is,
4098      * deserialize it).
4099      *
4100      * @param s the stream being read.
4101      */
4102     private void readObject(java.io.ObjectInputStream s)
4103         throws java.io.IOException, ClassNotFoundException {
4104         // Read in all fields
4106         // validate possibly bad fields
4107         if (intVal == null) {
4108             String message = "BigDecimal: null intVal in stream";
4109             throw new java.io.StreamCorruptedException(message);
4110         // [all values of scale are now allowed]
4111         }
4112         UnsafeHolder.setIntCompact(this, compactValFor(intVal));
4113     }
4114
4115    /**
4116     * Serialize this {@code BigDecimal} to the stream in question
4117     *
4118     * @param s the stream to serialize to.
4119     */
4120    private void writeObject(java.io.ObjectOutputStream s)
4121        throws java.io.IOException {
4122        // Must inflate to maintain compatible serial form.
4123        if (this.intVal == null)
4124            UnsafeHolder.setIntValVolatile(this, BigInteger.valueOf(this.intCompact));
4125        // Could reset intVal back to null if it has to be set.
4126        s.defaultWriteObject();
4127    }
4128
4129     /**
4130      * Returns the length of the absolute value of a {@code long}, in decimal
4131      * digits.
4132      *
4133      * @param x the {@code long}
4134      * @return the length of the unscaled value, in deciaml digits.
4135      */
4136     static int longDigitLength(long x) {
4137         /*
4138          * As described in "Bit Twiddling Hacks" by Sean Anderson,
4139          * (http://graphics.stanford.edu/~seander/bithacks.html)
4140          * integer log 10 of x is within 1 of (1233/4096)* (1 +
4141          * integer log 2 of x). The fraction 1233/4096 approximates
4142          * log10(2). So we first do a version of log2 (a variant of
4143          * Long class with pre-checks and opposite directionality) and
4144          * then scale and check against powers table. This is a little
4145          * simpler in present context than the version in Hacker's
4146          * Delight sec 11-4. Adding one to bit length allows comparing
4147          * downward from the LONG_TEN_POWERS_TABLE that we need
4148          * anyway.
4149          */
4150         assert x != BigDecimal.INFLATED;
4151         if (x < 0)
4152             x = -x;
4153         if (x < 10) // must screen for 0, might as well 10
4154             return 1;
4155         int r = ((64 - Long.numberOfLeadingZeros(x) + 1) * 1233) >>> 12;
4156         long[] tab = LONG_TEN_POWERS_TABLE;
4157         // if r >= length, must have max possible digits for long
4158         return (r >= tab.length || x < tab[r]) ? r : r + 1;
4159     }
4160
4161     /**
4162      * Returns the length of the absolute value of a BigInteger, in
4163      * decimal digits.
4164      *
4165      * @param b the BigInteger
4166      * @return the length of the unscaled value, in decimal digits
4167      */
4168     private static int bigDigitLength(BigInteger b) {
4169         /*
4170          * Same idea as the long version, but we need a better
4171          * approximation of log10(2). Using 646456993/2^31
4172          * is accurate up to max possible reported bitLength.
4173          */
4174         if (b.signum == 0)
4175             return 1;
4176         int r = (int)((((long)b.bitLength() + 1) * 646456993) >>> 31);
4177         return b.compareMagnitude(bigTenToThe(r)) < 0? r : r+1;
4178     }
4179
4180     /**
4181      * Check a scale for Underflow or Overflow.  If this BigDecimal is
4182      * nonzero, throw an exception if the scale is outof range. If this
4183      * is zero, saturate the scale to the extreme value of the right
4184      * sign if the scale is out of range.
4185      *
4186      * @param val The new scale.
4187      * @throws ArithmeticException (overflow or underflow) if the new
4188      *         scale is out of range.
4189      * @return validated scale as an int.
4190      */
4191     private int checkScale(long val) {
4192         int asInt = (int)val;
4193         if (asInt != val) {
4194             asInt = val>Integer.MAX_VALUE ? Integer.MAX_VALUE : Integer.MIN_VALUE;
4195             BigInteger b;
4196             if (intCompact != 0 &&
4197                 ((b = intVal) == null || b.signum() != 0))
4198                 throw new ArithmeticException(asInt>0 ? "Underflow":"Overflow");
4199         }
4200         return asInt;
4201     }
4202
4203    /**
4204      * Returns the compact value for given {@code BigInteger}, or
4205      * INFLATED if too big. Relies on internal representation of
4206      * {@code BigInteger}.
4207      */
4208     private static long compactValFor(BigInteger b) {
4209         int[] m = b.mag;
4210         int len = m.length;
4211         if (len == 0)
4212             return 0;
4213         int d = m[0];
4214         if (len > 2 || (len == 2 && d < 0))
4215             return INFLATED;
4216
4217         long u = (len == 2)?
4218             (((long) m[1] & LONG_MASK) + (((long)d) << 32)) :
4219             (((long)d)   & LONG_MASK);
4220         return (b.signum < 0)? -u : u;
4221     }
4222
4223     private static int longCompareMagnitude(long x, long y) {
4224         if (x < 0)
4225             x = -x;
4226         if (y < 0)
4227             y = -y;
4228         return (x < y) ? -1 : ((x == y) ? 0 : 1);
4229     }
4230
4231     private static int saturateLong(long s) {
4232         int i = (int)s;
4233         return (s == i) ? i : (s < 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE);
4234     }
4235
4236     /*
4237      * Internal printing routine
4238      */
4239     private static void print(String name, BigDecimal bd) {
4240         System.err.format("%s:\tintCompact %d\tintVal %d\tscale %d\tprecision %d%n",
4241                           name,
4242                           bd.intCompact,
4243                           bd.intVal,
4244                           bd.scale,
4245                           bd.precision);
4246     }
4247
4248     /**
4249      * Check internal invariants of this BigDecimal.  These invariants
4250      * include:
4251      *
4252      * <ul>
4253      *
4254      * <li>The object must be initialized; either intCompact must not be
4255      * INFLATED or intVal is non-null.  Both of these conditions may
4256      * be true.
4257      *
4258      * <li>If both intCompact and intVal and set, their values must be
4259      * consistent.
4260      *
4261      * <li>If precision is nonzero, it must have the right value.
4262      * </ul>
4263      *
4264      * Note: Since this is an audit method, we are not supposed to change the
4265      * state of this BigDecimal object.
4266      */
4267     private BigDecimal audit() {
4268         if (intCompact == INFLATED) {
4269             if (intVal == null) {
4270                 print("audit", this);
4271                 throw new AssertionError("null intVal");
4272             }
4273             // Check precision
4274             if (precision > 0 && precision != bigDigitLength(intVal)) {
4275                 print("audit", this);
4276                 throw new AssertionError("precision mismatch");
4277             }
4278         } else {
4279             if (intVal != null) {
4280                 long val = intVal.longValue();
4281                 if (val != intCompact) {
4282                     print("audit", this);
4283                     throw new AssertionError("Inconsistent state, intCompact=" +
4284                                              intCompact + "\t intVal=" + val);
4285                 }
4286             }
4287             // Check precision
4288             if (precision > 0 && precision != longDigitLength(intCompact)) {
4289                 print("audit", this);
4290                 throw new AssertionError("precision mismatch");
4291             }
4292         }
4293         return this;
4294     }
4295
4296     /* the same as checkScale where value!=0 */
4297     private static int checkScaleNonZero(long val) {
4298         int asInt = (int)val;
4299         if (asInt != val) {
4300             throw new ArithmeticException(asInt>0 ? "Underflow":"Overflow");
4301         }
4302         return asInt;
4303     }
4304
4305     private static int checkScale(long intCompact, long val) {
4306         int asInt = (int)val;
4307         if (asInt != val) {
4308             asInt = val>Integer.MAX_VALUE ? Integer.MAX_VALUE : Integer.MIN_VALUE;
4309             if (intCompact != 0)
4310                 throw new ArithmeticException(asInt>0 ? "Underflow":"Overflow");
4311         }
4312         return asInt;
4313     }
4314
4315     private static int checkScale(BigInteger intVal, long val) {
4316         int asInt = (int)val;
4317         if (asInt != val) {
4318             asInt = val>Integer.MAX_VALUE ? Integer.MAX_VALUE : Integer.MIN_VALUE;
4319             if (intVal.signum() != 0)
4320                 throw new ArithmeticException(asInt>0 ? "Underflow":"Overflow");
4321         }
4322         return asInt;
4323     }
4324
4325     /**
4326      * Returns a {@code BigDecimal} rounded according to the MathContext
4327      * settings;
4328      * If rounding is needed a new {@code BigDecimal} is created and returned.
4329      *
4330      * @param val the value to be rounded
4331      * @param mc the context to use.
4332      * @return a {@code BigDecimal} rounded according to the MathContext
4333      *         settings.  May return {@code value}, if no rounding needed.
4334      * @throws ArithmeticException if the rounding mode is
4335      *         {@code RoundingMode.UNNECESSARY} and the
4336      *         result is inexact.
4337      */
4338     private static BigDecimal doRound(BigDecimal val, MathContext mc) {
4339         int mcp = mc.precision;
4340         boolean wasDivided = false;
4341         if (mcp > 0) {
4342             BigInteger intVal = val.intVal;
4343             long compactVal = val.intCompact;
4344             int scale = val.scale;
4345             int prec = val.precision();
4346             int mode = mc.roundingMode.oldMode;
4347             int drop;
4348             if (compactVal == INFLATED) {
4349                 drop = prec - mcp;
4350                 while (drop > 0) {
4351                     scale = checkScaleNonZero((long) scale - drop);
4352                     intVal = divideAndRoundByTenPow(intVal, drop, mode);
4353                     wasDivided = true;
4354                     compactVal = compactValFor(intVal);
4355                     if (compactVal != INFLATED) {
4356                         prec = longDigitLength(compactVal);
4357                         break;
4358                     }
4359                     prec = bigDigitLength(intVal);
4360                     drop = prec - mcp;
4361                 }
4362             }
4363             if (compactVal != INFLATED) {
4364                 drop = prec - mcp;  // drop can't be more than 18
4365                 while (drop > 0) {
4366                     scale = checkScaleNonZero((long) scale - drop);
4367                     compactVal = divideAndRound(compactVal, LONG_TEN_POWERS_TABLE[drop], mc.roundingMode.oldMode);
4368                     wasDivided = true;
4369                     prec = longDigitLength(compactVal);
4370                     drop = prec - mcp;
4371                     intVal = null;
4372                 }
4373             }
4374             return wasDivided ? new BigDecimal(intVal,compactVal,scale,prec) : val;
4375         }
4376         return val;
4377     }
4378
4379     /*
4380      * Returns a {@code BigDecimal} created from {@code long} value with
4381      * given scale rounded according to the MathContext settings
4382      */
4383     private static BigDecimal doRound(long compactVal, int scale, MathContext mc) {
4384         int mcp = mc.precision;
4385         if (mcp > 0 && mcp < 19) {
4386             int prec = longDigitLength(compactVal);
4387             int drop = prec - mcp;  // drop can't be more than 18
4388             while (drop > 0) {
4389                 scale = checkScaleNonZero((long) scale - drop);
4390                 compactVal = divideAndRound(compactVal, LONG_TEN_POWERS_TABLE[drop], mc.roundingMode.oldMode);
4391                 prec = longDigitLength(compactVal);
4392                 drop = prec - mcp;
4393             }
4394             return valueOf(compactVal, scale, prec);
4395         }
4396         return valueOf(compactVal, scale);
4397     }
4398
4399     /*
4400      * Returns a {@code BigDecimal} created from {@code BigInteger} value with
4401      * given scale rounded according to the MathContext settings
4402      */
4403     private static BigDecimal doRound(BigInteger intVal, int scale, MathContext mc) {
4404         int mcp = mc.precision;
4405         int prec = 0;
4406         if (mcp > 0) {
4407             long compactVal = compactValFor(intVal);
4408             int mode = mc.roundingMode.oldMode;
4409             int drop;
4410             if (compactVal == INFLATED) {
4411                 prec = bigDigitLength(intVal);
4412                 drop = prec - mcp;
4413                 while (drop > 0) {
4414                     scale = checkScaleNonZero((long) scale - drop);
4415                     intVal = divideAndRoundByTenPow(intVal, drop, mode);
4416                     compactVal = compactValFor(intVal);
4417                     if (compactVal != INFLATED) {
4418                         break;
4419                     }
4420                     prec = bigDigitLength(intVal);
4421                     drop = prec - mcp;
4422                 }
4423             }
4424             if (compactVal != INFLATED) {
4425                 prec = longDigitLength(compactVal);
4426                 drop = prec - mcp;     // drop can't be more than 18
4427                 while (drop > 0) {
4428                     scale = checkScaleNonZero((long) scale - drop);
4429                     compactVal = divideAndRound(compactVal, LONG_TEN_POWERS_TABLE[drop], mc.roundingMode.oldMode);
4430                     prec = longDigitLength(compactVal);
4431                     drop = prec - mcp;
4432                 }
4433                 return valueOf(compactVal,scale,prec);
4434             }
4435         }
4436         return new BigDecimal(intVal,INFLATED,scale,prec);
4437     }
4438
4439     /*
4440      * Divides {@code BigInteger} value by ten power.
4441      */
4442     private static BigInteger divideAndRoundByTenPow(BigInteger intVal, int tenPow, int roundingMode) {
4443         if (tenPow < LONG_TEN_POWERS_TABLE.length)
4444             intVal = divideAndRound(intVal, LONG_TEN_POWERS_TABLE[tenPow], roundingMode);
4445         else
4446             intVal = divideAndRound(intVal, bigTenToThe(tenPow), roundingMode);
4447         return intVal;
4448     }
4449
4450     /**
4451      * Internally used for division operation for division {@code long} by
4452      * {@code long}.
4453      * The returned {@code BigDecimal} object is the quotient whose scale is set
4454      * to the passed in scale. If the remainder is not zero, it will be rounded
4455      * based on the passed in roundingMode. Also, if the remainder is zero and
4456      * the last parameter, i.e. preferredScale is NOT equal to scale, the
4457      * trailing zeros of the result is stripped to match the preferredScale.
4458      */
4459     private static BigDecimal divideAndRound(long ldividend, long ldivisor, int scale, int roundingMode,
4460                                              int preferredScale) {
4461
4462         int qsign; // quotient sign
4463         long q = ldividend / ldivisor; // store quotient in long
4464         if (roundingMode == ROUND_DOWN && scale == preferredScale)
4465             return valueOf(q, scale);
4466         long r = ldividend % ldivisor; // store remainder in long
4467         qsign = ((ldividend < 0) == (ldivisor < 0)) ? 1 : -1;
4468         if (r != 0) {
4469             boolean increment = needIncrement(ldivisor, roundingMode, qsign, q, r);
4470             return valueOf((increment ? q + qsign : q), scale);
4471         } else {
4472             if (preferredScale != scale)
4473                 return createAndStripZerosToMatchScale(q, scale, preferredScale);
4474             else
4475                 return valueOf(q, scale);
4476         }
4477     }
4478
4479     /**
4480      * Divides {@code long} by {@code long} and do rounding based on the
4481      * passed in roundingMode.
4482      */
4483     private static long divideAndRound(long ldividend, long ldivisor, int roundingMode) {
4484         int qsign; // quotient sign
4485         long q = ldividend / ldivisor; // store quotient in long
4486         if (roundingMode == ROUND_DOWN)
4487             return q;
4488         long r = ldividend % ldivisor; // store remainder in long
4489         qsign = ((ldividend < 0) == (ldivisor < 0)) ? 1 : -1;
4490         if (r != 0) {
4491             boolean increment = needIncrement(ldivisor, roundingMode, qsign, q,     r);
4492             return increment ? q + qsign : q;
4493         } else {
4494             return q;
4495         }
4496     }
4497
4498     /**
4499      * Shared logic of need increment computation.
4500      */
4501     private static boolean commonNeedIncrement(int roundingMode, int qsign,
4502                                         int cmpFracHalf, boolean oddQuot) {
4503         switch(roundingMode) {
4504         case ROUND_UNNECESSARY:
4505             throw new ArithmeticException("Rounding necessary");
4506
4507         case ROUND_UP: // Away from zero
4508             return true;
4509
4510         case ROUND_DOWN: // Towards zero
4511             return false;
4512
4513         case ROUND_CEILING: // Towards +infinity
4514             return qsign > 0;
4515
4516         case ROUND_FLOOR: // Towards -infinity
4517             return qsign < 0;
4518
4519         default: // Some kind of half-way rounding
4520             assert roundingMode >= ROUND_HALF_UP &&
4521                 roundingMode <= ROUND_HALF_EVEN: "Unexpected rounding mode" + RoundingMode.valueOf(roundingMode);
4522
4523             if (cmpFracHalf < 0 ) // We're closer to higher digit
4524                 return false;
4525             else if (cmpFracHalf > 0 ) // We're closer to lower digit
4526                 return true;
4527             else { // half-way
4528                 assert cmpFracHalf == 0;
4529
4530                 switch(roundingMode) {
4531                 case ROUND_HALF_DOWN:
4532                     return false;
4533
4534                 case ROUND_HALF_UP:
4535                     return true;
4536
4537                 case ROUND_HALF_EVEN:
4538                     return oddQuot;
4539
4540                 default:
4541                     throw new AssertionError("Unexpected rounding mode" + roundingMode);
4542                 }
4543             }
4544         }
4545     }
4546
4547     /**
4548      * Tests if quotient has to be incremented according the roundingMode
4549      */
4550     private static boolean needIncrement(long ldivisor, int roundingMode,
4551                                          int qsign, long q, long r) {
4552         assert r != 0L;
4553
4554         int cmpFracHalf;
4555         if (r <= HALF_LONG_MIN_VALUE || r > HALF_LONG_MAX_VALUE) {
4556             cmpFracHalf = 1; // 2 * r can't fit into long
4557         } else {
4558             cmpFracHalf = longCompareMagnitude(2 * r, ldivisor);
4559         }
4560
4561         return commonNeedIncrement(roundingMode, qsign, cmpFracHalf, (q & 1L) != 0L);
4562     }
4563
4564     /**
4565      * Divides {@code BigInteger} value by {@code long} value and
4566      * do rounding based on the passed in roundingMode.
4567      */
4568     private static BigInteger divideAndRound(BigInteger bdividend, long ldivisor, int roundingMode) {
4569         // Descend into mutables for faster remainder checks
4570         MutableBigInteger mdividend = new MutableBigInteger(bdividend.mag);
4571         // store quotient
4572         MutableBigInteger mq = new MutableBigInteger();
4573         // store quotient & remainder in long
4574         long r = mdividend.divide(ldivisor, mq);
4575         // record remainder is zero or not
4576         boolean isRemainderZero = (r == 0);
4577         // quotient sign
4578         int qsign = (ldivisor < 0) ? -bdividend.signum : bdividend.signum;
4579         if (!isRemainderZero) {
4580             if(needIncrement(ldivisor, roundingMode, qsign, mq, r)) {
4582             }
4583         }
4584         return mq.toBigInteger(qsign);
4585     }
4586
4587     /**
4588      * Internally used for division operation for division {@code BigInteger}
4589      * by {@code long}.
4590      * The returned {@code BigDecimal} object is the quotient whose scale is set
4591      * to the passed in scale. If the remainder is not zero, it will be rounded
4592      * based on the passed in roundingMode. Also, if the remainder is zero and
4593      * the last parameter, i.e. preferredScale is NOT equal to scale, the
4594      * trailing zeros of the result is stripped to match the preferredScale.
4595      */
4596     private static BigDecimal divideAndRound(BigInteger bdividend,
4597                                              long ldivisor, int scale, int roundingMode, int preferredScale) {
4598         // Descend into mutables for faster remainder checks
4599         MutableBigInteger mdividend = new MutableBigInteger(bdividend.mag);
4600         // store quotient
4601         MutableBigInteger mq = new MutableBigInteger();
4602         // store quotient & remainder in long
4603         long r = mdividend.divide(ldivisor, mq);
4604         // record remainder is zero or not
4605         boolean isRemainderZero = (r == 0);
4606         // quotient sign
4607         int qsign = (ldivisor < 0) ? -bdividend.signum : bdividend.signum;
4608         if (!isRemainderZero) {
4609             if(needIncrement(ldivisor, roundingMode, qsign, mq, r)) {
4611             }
4612             return mq.toBigDecimal(qsign, scale);
4613         } else {
4614             if (preferredScale != scale) {
4615                 long compactVal = mq.toCompactValue(qsign);
4616                 if(compactVal!=INFLATED) {
4617                     return createAndStripZerosToMatchScale(compactVal, scale, preferredScale);
4618                 }
4619                 BigInteger intVal =  mq.toBigInteger(qsign);
4620                 return createAndStripZerosToMatchScale(intVal,scale, preferredScale);
4621             } else {
4622                 return mq.toBigDecimal(qsign, scale);
4623             }
4624         }
4625     }
4626
4627     /**
4628      * Tests if quotient has to be incremented according the roundingMode
4629      */
4630     private static boolean needIncrement(long ldivisor, int roundingMode,
4631                                          int qsign, MutableBigInteger mq, long r) {
4632         assert r != 0L;
4633
4634         int cmpFracHalf;
4635         if (r <= HALF_LONG_MIN_VALUE || r > HALF_LONG_MAX_VALUE) {
4636             cmpFracHalf = 1; // 2 * r can't fit into long
4637         } else {
4638             cmpFracHalf = longCompareMagnitude(2 * r, ldivisor);
4639         }
4640
4641         return commonNeedIncrement(roundingMode, qsign, cmpFracHalf, mq.isOdd());
4642     }
4643
4644     /**
4645      * Divides {@code BigInteger} value by {@code BigInteger} value and
4646      * do rounding based on the passed in roundingMode.
4647      */
4648     private static BigInteger divideAndRound(BigInteger bdividend, BigInteger bdivisor, int roundingMode) {
4649         boolean isRemainderZero; // record remainder is zero or not
4650         int qsign; // quotient sign
4651         // Descend into mutables for faster remainder checks
4652         MutableBigInteger mdividend = new MutableBigInteger(bdividend.mag);
4653         MutableBigInteger mq = new MutableBigInteger();
4654         MutableBigInteger mdivisor = new MutableBigInteger(bdivisor.mag);
4655         MutableBigInteger mr = mdividend.divide(mdivisor, mq);
4656         isRemainderZero = mr.isZero();
4657         qsign = (bdividend.signum != bdivisor.signum) ? -1 : 1;
4658         if (!isRemainderZero) {
4659             if (needIncrement(mdivisor, roundingMode, qsign, mq, mr)) {
4661             }
4662         }
4663         return mq.toBigInteger(qsign);
4664     }
4665
4666     /**
4667      * Internally used for division operation for division {@code BigInteger}
4668      * by {@code BigInteger}.
4669      * The returned {@code BigDecimal} object is the quotient whose scale is set
4670      * to the passed in scale. If the remainder is not zero, it will be rounded
4671      * based on the passed in roundingMode. Also, if the remainder is zero and
4672      * the last parameter, i.e. preferredScale is NOT equal to scale, the
4673      * trailing zeros of the result is stripped to match the preferredScale.
4674      */
4675     private static BigDecimal divideAndRound(BigInteger bdividend, BigInteger bdivisor, int scale, int roundingMode,
4676                                              int preferredScale) {
4677         boolean isRemainderZero; // record remainder is zero or not
4678         int qsign; // quotient sign
4679         // Descend into mutables for faster remainder checks
4680         MutableBigInteger mdividend = new MutableBigInteger(bdividend.mag);
4681         MutableBigInteger mq = new MutableBigInteger();
4682         MutableBigInteger mdivisor = new MutableBigInteger(bdivisor.mag);
4683         MutableBigInteger mr = mdividend.divide(mdivisor, mq);
4684         isRemainderZero = mr.isZero();
4685         qsign = (bdividend.signum != bdivisor.signum) ? -1 : 1;
4686         if (!isRemainderZero) {
4687             if (needIncrement(mdivisor, roundingMode, qsign, mq, mr)) {
4689             }
4690             return mq.toBigDecimal(qsign, scale);
4691         } else {
4692             if (preferredScale != scale) {
4693                 long compactVal = mq.toCompactValue(qsign);
4694                 if (compactVal != INFLATED) {
4695                     return createAndStripZerosToMatchScale(compactVal, scale, preferredScale);
4696                 }
4697                 BigInteger intVal = mq.toBigInteger(qsign);
4698                 return createAndStripZerosToMatchScale(intVal, scale, preferredScale);
4699             } else {
4700                 return mq.toBigDecimal(qsign, scale);
4701             }
4702         }
4703     }
4704
4705     /**
4706      * Tests if quotient has to be incremented according the roundingMode
4707      */
4708     private static boolean needIncrement(MutableBigInteger mdivisor, int roundingMode,
4709                                          int qsign, MutableBigInteger mq, MutableBigInteger mr) {
4710         assert !mr.isZero();
4711         int cmpFracHalf = mr.compareHalf(mdivisor);
4712         return commonNeedIncrement(roundingMode, qsign, cmpFracHalf, mq.isOdd());
4713     }
4714
4715     /**
4716      * Remove insignificant trailing zeros from this
4717      * {@code BigInteger} value until the preferred scale is reached or no
4718      * more zeros can be removed.  If the preferred scale is less than
4719      * Integer.MIN_VALUE, all the trailing zeros will be removed.
4720      *
4721      * @return new {@code BigDecimal} with a scale possibly reduced
4722      * to be closed to the preferred scale.
4723      */
4724     private static BigDecimal createAndStripZerosToMatchScale(BigInteger intVal, int scale, long preferredScale) {
4725         BigInteger qr[]; // quotient-remainder pair
4726         while (intVal.compareMagnitude(BigInteger.TEN) >= 0
4727                && scale > preferredScale) {
4728             if (intVal.testBit(0))
4729                 break; // odd number cannot end in 0
4730             qr = intVal.divideAndRemainder(BigInteger.TEN);
4731             if (qr[1].signum() != 0)
4732                 break; // non-0 remainder
4733             intVal = qr[0];
4734             scale = checkScale(intVal,(long) scale - 1); // could Overflow
4735         }
4736         return valueOf(intVal, scale, 0);
4737     }
4738
4739     /**
4740      * Remove insignificant trailing zeros from this
4741      * {@code long} value until the preferred scale is reached or no
4742      * more zeros can be removed.  If the preferred scale is less than
4743      * Integer.MIN_VALUE, all the trailing zeros will be removed.
4744      *
4745      * @return new {@code BigDecimal} with a scale possibly reduced
4746      * to be closed to the preferred scale.
4747      */
4748     private static BigDecimal createAndStripZerosToMatchScale(long compactVal, int scale, long preferredScale) {
4749         while (Math.abs(compactVal) >= 10L && scale > preferredScale) {
4750             if ((compactVal & 1L) != 0L)
4751                 break; // odd number cannot end in 0
4752             long r = compactVal % 10L;
4753             if (r != 0L)
4754                 break; // non-0 remainder
4755             compactVal /= 10;
4756             scale = checkScale(compactVal, (long) scale - 1); // could Overflow
4757         }
4758         return valueOf(compactVal, scale);
4759     }
4760
4761     private static BigDecimal stripZerosToMatchScale(BigInteger intVal, long intCompact, int scale, int preferredScale) {
4762         if(intCompact!=INFLATED) {
4763             return createAndStripZerosToMatchScale(intCompact, scale, preferredScale);
4764         } else {
4765             return createAndStripZerosToMatchScale(intVal==null ? INFLATED_BIGINT : intVal,
4766                                                    scale, preferredScale);
4767         }
4768     }
4769
4770     /*
4771      * returns INFLATED if oveflow
4772      */
4773     private static long add(long xs, long ys){
4774         long sum = xs + ys;
4775         // See "Hacker's Delight" section 2-12 for explanation of
4776         // the overflow test.
4777         if ( (((sum ^ xs) & (sum ^ ys))) >= 0L) { // not overflowed
4778             return sum;
4779         }
4780         return INFLATED;
4781     }
4782
4783     private static BigDecimal add(long xs, long ys, int scale){
4784         long sum = add(xs, ys);
4785         if (sum!=INFLATED)
4786             return BigDecimal.valueOf(sum, scale);
4787         return new BigDecimal(BigInteger.valueOf(xs).add(ys), scale);
4788     }
4789
4790     private static BigDecimal add(final long xs, int scale1, final long ys, int scale2) {
4791         long sdiff = (long) scale1 - scale2;
4792         if (sdiff == 0) {
4793             return add(xs, ys, scale1);
4794         } else if (sdiff < 0) {
4795             int raise = checkScale(xs,-sdiff);
4796             long scaledX = longMultiplyPowerTen(xs, raise);
4797             if (scaledX != INFLATED) {
4798                 return add(scaledX, ys, scale2);
4799             } else {
4800                 BigInteger bigsum = bigMultiplyPowerTen(xs,raise).add(ys);
4801                 return ((xs^ys)>=0) ? // same sign test
4802                     new BigDecimal(bigsum, INFLATED, scale2, 0)
4803                     : valueOf(bigsum, scale2, 0);
4804             }
4805         } else {
4806             int raise = checkScale(ys,sdiff);
4807             long scaledY = longMultiplyPowerTen(ys, raise);
4808             if (scaledY != INFLATED) {
4809                 return add(xs, scaledY, scale1);
4810             } else {
4811                 BigInteger bigsum = bigMultiplyPowerTen(ys,raise).add(xs);
4812                 return ((xs^ys)>=0) ?
4813                     new BigDecimal(bigsum, INFLATED, scale1, 0)
4814                     : valueOf(bigsum, scale1, 0);
4815             }
4816         }
4817     }
4818
4819     private static BigDecimal add(final long xs, int scale1, BigInteger snd, int scale2) {
4820         int rscale = scale1;
4821         long sdiff = (long)rscale - scale2;
4822         boolean sameSigns =  (Long.signum(xs) == snd.signum);
4823         BigInteger sum;
4824         if (sdiff < 0) {
4825             int raise = checkScale(xs,-sdiff);
4826             rscale = scale2;
4827             long scaledX = longMultiplyPowerTen(xs, raise);
4828             if (scaledX == INFLATED) {
4829                 sum = snd.add(bigMultiplyPowerTen(xs,raise));
4830             } else {
4831                 sum = snd.add(scaledX);
4832             }
4833         } else { //if (sdiff > 0) {
4834             int raise = checkScale(snd,sdiff);
4835             snd = bigMultiplyPowerTen(snd,raise);
4836             sum = snd.add(xs);
4837         }
4838         return (sameSigns) ?
4839             new BigDecimal(sum, INFLATED, rscale, 0) :
4840             valueOf(sum, rscale, 0);
4841     }
4842
4843     private static BigDecimal add(BigInteger fst, int scale1, BigInteger snd, int scale2) {
4844         int rscale = scale1;
4845         long sdiff = (long)rscale - scale2;
4846         if (sdiff != 0) {
4847             if (sdiff < 0) {
4848                 int raise = checkScale(fst,-sdiff);
4849                 rscale = scale2;
4850                 fst = bigMultiplyPowerTen(fst,raise);
4851             } else {
4852                 int raise = checkScale(snd,sdiff);
4853                 snd = bigMultiplyPowerTen(snd,raise);
4854             }
4855         }
4856         BigInteger sum = fst.add(snd);
4857         return (fst.signum == snd.signum) ?
4858                 new BigDecimal(sum, INFLATED, rscale, 0) :
4859                 valueOf(sum, rscale, 0);
4860     }
4861
4862     private static BigInteger bigMultiplyPowerTen(long value, int n) {
4863         if (n <= 0)
4864             return BigInteger.valueOf(value);
4865         return bigTenToThe(n).multiply(value);
4866     }
4867
4868     private static BigInteger bigMultiplyPowerTen(BigInteger value, int n) {
4869         if (n <= 0)
4870             return value;
4871         if(n<LONG_TEN_POWERS_TABLE.length) {
4872                 return value.multiply(LONG_TEN_POWERS_TABLE[n]);
4873         }
4874         return value.multiply(bigTenToThe(n));
4875     }
4876
4877     /**
4878      * Returns a {@code BigDecimal} whose value is {@code (xs /
4879      * ys)}, with rounding according to the context settings.
4880      *
4881      * Fast path - used only when (xscale <= yscale && yscale < 18
4882      *  && mc.presision<18) {
4883      */
4884     private static BigDecimal divideSmallFastPath(final long xs, int xscale,
4885                                                   final long ys, int yscale,
4886                                                   long preferredScale, MathContext mc) {
4887         int mcp = mc.precision;
4888         int roundingMode = mc.roundingMode.oldMode;
4889
4890         assert (xscale <= yscale) && (yscale < 18) && (mcp < 18);
4891         int xraise = yscale - xscale; // xraise >=0
4892         long scaledX = (xraise==0) ? xs :
4893             longMultiplyPowerTen(xs, xraise); // can't overflow here!
4894         BigDecimal quotient;
4895
4896         int cmp = longCompareMagnitude(scaledX, ys);
4897         if(cmp > 0) { // satisfy constraint (b)
4898             yscale -= 1; // [that is, divisor *= 10]
4899             int scl = checkScaleNonZero(preferredScale + yscale - xscale + mcp);
4900             if (checkScaleNonZero((long) mcp + yscale - xscale) > 0) {
4901                 // assert newScale >= xscale
4902                 int raise = checkScaleNonZero((long) mcp + yscale - xscale);
4903                 long scaledXs;
4904                 if ((scaledXs = longMultiplyPowerTen(xs, raise)) == INFLATED) {
4905                     quotient = null;
4906                     if((mcp-1) >=0 && (mcp-1)<LONG_TEN_POWERS_TABLE.length) {
4907                         quotient = multiplyDivideAndRound(LONG_TEN_POWERS_TABLE[mcp-1], scaledX, ys, scl, roundingMode, checkScaleNonZero(preferredScale));
4908                     }
4909                     if(quotient==null) {
4910                         BigInteger rb = bigMultiplyPowerTen(scaledX,mcp-1);
4911                         quotient = divideAndRound(rb, ys,
4912                                                   scl, roundingMode, checkScaleNonZero(preferredScale));
4913                     }
4914                 } else {
4915                     quotient = divideAndRound(scaledXs, ys, scl, roundingMode, checkScaleNonZero(preferredScale));
4916                 }
4917             } else {
4918                 int newScale = checkScaleNonZero((long) xscale - mcp);
4919                 // assert newScale >= yscale
4920                 if (newScale == yscale) { // easy case
4921                     quotient = divideAndRound(xs, ys, scl, roundingMode,checkScaleNonZero(preferredScale));
4922                 } else {
4923                     int raise = checkScaleNonZero((long) newScale - yscale);
4924                     long scaledYs;
4925                     if ((scaledYs = longMultiplyPowerTen(ys, raise)) == INFLATED) {
4926                         BigInteger rb = bigMultiplyPowerTen(ys,raise);
4927                         quotient = divideAndRound(BigInteger.valueOf(xs),
4928                                                   rb, scl, roundingMode,checkScaleNonZero(preferredScale));
4929                     } else {
4930                         quotient = divideAndRound(xs, scaledYs, scl, roundingMode,checkScaleNonZero(preferredScale));
4931                     }
4932                 }
4933             }
4934         } else {
4935             // abs(scaledX) <= abs(ys)
4936             // result is "scaledX * 10^msp / ys"
4937             int scl = checkScaleNonZero(preferredScale + yscale - xscale + mcp);
4938             if(cmp==0) {
4939                 // abs(scaleX)== abs(ys) => result will be scaled 10^mcp + correct sign
4940                 quotient = roundedTenPower(((scaledX < 0) == (ys < 0)) ? 1 : -1, mcp, scl, checkScaleNonZero(preferredScale));
4941             } else {
4942                 // abs(scaledX) < abs(ys)
4943                 long scaledXs;
4944                 if ((scaledXs = longMultiplyPowerTen(scaledX, mcp)) == INFLATED) {
4945                     quotient = null;
4946                     if(mcp<LONG_TEN_POWERS_TABLE.length) {
4947                         quotient = multiplyDivideAndRound(LONG_TEN_POWERS_TABLE[mcp], scaledX, ys, scl, roundingMode, checkScaleNonZero(preferredScale));
4948                     }
4949                     if(quotient==null) {
4950                         BigInteger rb = bigMultiplyPowerTen(scaledX,mcp);
4951                         quotient = divideAndRound(rb, ys,
4952                                                   scl, roundingMode, checkScaleNonZero(preferredScale));
4953                     }
4954                 } else {
4955                     quotient = divideAndRound(scaledXs, ys, scl, roundingMode, checkScaleNonZero(preferredScale));
4956                 }
4957             }
4958         }
4959         // doRound, here, only affects 1000000000 case.
4960         return doRound(quotient,mc);
4961     }
4962
4963     /**
4964      * Returns a {@code BigDecimal} whose value is {@code (xs /
4965      * ys)}, with rounding according to the context settings.
4966      */
4967     private static BigDecimal divide(final long xs, int xscale, final long ys, int yscale, long preferredScale, MathContext mc) {
4968         int mcp = mc.precision;
4969         if(xscale <= yscale && yscale < 18 && mcp<18) {
4970             return divideSmallFastPath(xs, xscale, ys, yscale, preferredScale, mc);
4971         }
4972         if (compareMagnitudeNormalized(xs, xscale, ys, yscale) > 0) {// satisfy constraint (b)
4973             yscale -= 1; // [that is, divisor *= 10]
4974         }
4975         int roundingMode = mc.roundingMode.oldMode;
4976         // In order to find out whether the divide generates the exact result,
4977         // we avoid calling the above divide method. 'quotient' holds the
4978         // return BigDecimal object whose scale will be set to 'scl'.
4979         int scl = checkScaleNonZero(preferredScale + yscale - xscale + mcp);
4980         BigDecimal quotient;
4981         if (checkScaleNonZero((long) mcp + yscale - xscale) > 0) {
4982             int raise = checkScaleNonZero((long) mcp + yscale - xscale);
4983             long scaledXs;
4984             if ((scaledXs = longMultiplyPowerTen(xs, raise)) == INFLATED) {
4985                 BigInteger rb = bigMultiplyPowerTen(xs,raise);
4986                 quotient = divideAndRound(rb, ys, scl, roundingMode, checkScaleNonZero(preferredScale));
4987             } else {
4988                 quotient = divideAndRound(scaledXs, ys, scl, roundingMode, checkScaleNonZero(preferredScale));
4989             }
4990         } else {
4991             int newScale = checkScaleNonZero((long) xscale - mcp);
4992             // assert newScale >= yscale
4993             if (newScale == yscale) { // easy case
4994                 quotient = divideAndRound(xs, ys, scl, roundingMode,checkScaleNonZero(preferredScale));
4995             } else {
4996                 int raise = checkScaleNonZero((long) newScale - yscale);
4997                 long scaledYs;
4998                 if ((scaledYs = longMultiplyPowerTen(ys, raise)) == INFLATED) {
4999                     BigInteger rb = bigMultiplyPowerTen(ys,raise);
5000                     quotient = divideAndRound(BigInteger.valueOf(xs),
5001                                               rb, scl, roundingMode,checkScaleNonZero(preferredScale));
5002                 } else {
5003                     quotient = divideAndRound(xs, scaledYs, scl, roundingMode,checkScaleNonZero(preferredScale));
5004                 }
5005             }
5006         }
5007         // doRound, here, only affects 1000000000 case.
5008         return doRound(quotient,mc);
5009     }
5010
5011     /**
5012      * Returns a {@code BigDecimal} whose value is {@code (xs /
5013      * ys)}, with rounding according to the context settings.
5014      */
5015     private static BigDecimal divide(BigInteger xs, int xscale, long ys, int yscale, long preferredScale, MathContext mc) {
5016         // Normalize dividend & divisor so that both fall into [0.1, 0.999...]
5017         if ((-compareMagnitudeNormalized(ys, yscale, xs, xscale)) > 0) {// satisfy constraint (b)
5018             yscale -= 1; // [that is, divisor *= 10]
5019         }
5020         int mcp = mc.precision;
5021         int roundingMode = mc.roundingMode.oldMode;
5022
5023         // In order to find out whether the divide generates the exact result,
5024         // we avoid calling the above divide method. 'quotient' holds the
5025         // return BigDecimal object whose scale will be set to 'scl'.
5026         BigDecimal quotient;
5027         int scl = checkScaleNonZero(preferredScale + yscale - xscale + mcp);
5028         if (checkScaleNonZero((long) mcp + yscale - xscale) > 0) {
5029             int raise = checkScaleNonZero((long) mcp + yscale - xscale);
5030             BigInteger rb = bigMultiplyPowerTen(xs,raise);
5031             quotient = divideAndRound(rb, ys, scl, roundingMode, checkScaleNonZero(preferredScale));
5032         } else {
5033             int newScale = checkScaleNonZero((long) xscale - mcp);
5034             // assert newScale >= yscale
5035             if (newScale == yscale) { // easy case
5036                 quotient = divideAndRound(xs, ys, scl, roundingMode,checkScaleNonZero(preferredScale));
5037             } else {
5038                 int raise = checkScaleNonZero((long) newScale - yscale);
5039                 long scaledYs;
5040                 if ((scaledYs = longMultiplyPowerTen(ys, raise)) == INFLATED) {
5041                     BigInteger rb = bigMultiplyPowerTen(ys,raise);
5042                     quotient = divideAndRound(xs, rb, scl, roundingMode,checkScaleNonZero(preferredScale));
5043                 } else {
5044                     quotient = divideAndRound(xs, scaledYs, scl, roundingMode,checkScaleNonZero(preferredScale));
5045                 }
5046             }
5047         }
5048         // doRound, here, only affects 1000000000 case.
5049         return doRound(quotient, mc);
5050     }
5051
5052     /**
5053      * Returns a {@code BigDecimal} whose value is {@code (xs /
5054      * ys)}, with rounding according to the context settings.
5055      */
5056     private static BigDecimal divide(long xs, int xscale, BigInteger ys, int yscale, long preferredScale, MathContext mc) {
5057         // Normalize dividend & divisor so that both fall into [0.1, 0.999...]
5058         if (compareMagnitudeNormalized(xs, xscale, ys, yscale) > 0) {// satisfy constraint (b)
5059             yscale -= 1; // [that is, divisor *= 10]
5060         }
5061         int mcp = mc.precision;
5062         int roundingMode = mc.roundingMode.oldMode;
5063
5064         // In order to find out whether the divide generates the exact result,
5065         // we avoid calling the above divide method. 'quotient' holds the
5066         // return BigDecimal object whose scale will be set to 'scl'.
5067         BigDecimal quotient;
5068         int scl = checkScaleNonZero(preferredScale + yscale - xscale + mcp);
5069         if (checkScaleNonZero((long) mcp + yscale - xscale) > 0) {
5070             int raise = checkScaleNonZero((long) mcp + yscale - xscale);
5071             BigInteger rb = bigMultiplyPowerTen(xs,raise);
5072             quotient = divideAndRound(rb, ys, scl, roundingMode, checkScaleNonZero(preferredScale));
5073         } else {
5074             int newScale = checkScaleNonZero((long) xscale - mcp);
5075             int raise = checkScaleNonZero((long) newScale - yscale);
5076             BigInteger rb = bigMultiplyPowerTen(ys,raise);
5077             quotient = divideAndRound(BigInteger.valueOf(xs), rb, scl, roundingMode,checkScaleNonZero(preferredScale));
5078         }
5079         // doRound, here, only affects 1000000000 case.
5080         return doRound(quotient, mc);
5081     }
5082
5083     /**
5084      * Returns a {@code BigDecimal} whose value is {@code (xs /
5085      * ys)}, with rounding according to the context settings.
5086      */
5087     private static BigDecimal divide(BigInteger xs, int xscale, BigInteger ys, int yscale, long preferredScale, MathContext mc) {
5088         // Normalize dividend & divisor so that both fall into [0.1, 0.999...]
5089         if (compareMagnitudeNormalized(xs, xscale, ys, yscale) > 0) {// satisfy constraint (b)
5090             yscale -= 1; // [that is, divisor *= 10]
5091         }
5092         int mcp = mc.precision;
5093         int roundingMode = mc.roundingMode.oldMode;
5094
5095         // In order to find out whether the divide generates the exact result,
5096         // we avoid calling the above divide method. 'quotient' holds the
5097         // return BigDecimal object whose scale will be set to 'scl'.
5098         BigDecimal quotient;
5099         int scl = checkScaleNonZero(preferredScale + yscale - xscale + mcp);
5100         if (checkScaleNonZero((long) mcp + yscale - xscale) > 0) {
5101             int raise = checkScaleNonZero((long) mcp + yscale - xscale);
5102             BigInteger rb = bigMultiplyPowerTen(xs,raise);
5103             quotient = divideAndRound(rb, ys, scl, roundingMode, checkScaleNonZero(preferredScale));
5104         } else {
5105             int newScale = checkScaleNonZero((long) xscale - mcp);
5106             int raise = checkScaleNonZero((long) newScale - yscale);
5107             BigInteger rb = bigMultiplyPowerTen(ys,raise);
5108             quotient = divideAndRound(xs, rb, scl, roundingMode,checkScaleNonZero(preferredScale));
5109         }
5110         // doRound, here, only affects 1000000000 case.
5111         return doRound(quotient, mc);
5112     }
5113
5114     /*
5115      * performs divideAndRound for (dividend0*dividend1, divisor)
5116      * returns null if quotient can't fit into long value;
5117      */
5118     private static BigDecimal multiplyDivideAndRound(long dividend0, long dividend1, long divisor, int scale, int roundingMode,
5119                                                      int preferredScale) {
5120         int qsign = Long.signum(dividend0)*Long.signum(dividend1)*Long.signum(divisor);
5121         dividend0 = Math.abs(dividend0);
5122         dividend1 = Math.abs(dividend1);
5123         divisor = Math.abs(divisor);
5124         // multiply dividend0 * dividend1
5125         long d0_hi = dividend0 >>> 32;
5126         long d0_lo = dividend0 & LONG_MASK;
5127         long d1_hi = dividend1 >>> 32;
5128         long d1_lo = dividend1 & LONG_MASK;
5129         long product = d0_lo * d1_lo;
5130         long d0 = product & LONG_MASK;
5131         long d1 = product >>> 32;
5132         product = d0_hi * d1_lo + d1;
5133         d1 = product & LONG_MASK;
5134         long d2 = product >>> 32;
5135         product = d0_lo * d1_hi + d1;
5136         d1 = product & LONG_MASK;
5137         d2 += product >>> 32;
5138         long d3 = d2>>>32;
5139         d2 &= LONG_MASK;
5140         product = d0_hi*d1_hi + d2;
5141         d2 = product & LONG_MASK;
5142         d3 = ((product>>>32) + d3) & LONG_MASK;
5143         final long dividendHi = make64(d3,d2);
5144         final long dividendLo = make64(d1,d0);
5145         // divide
5146         return divideAndRound128(dividendHi, dividendLo, divisor, qsign, scale, roundingMode, preferredScale);
5147     }
5148
5149     private static final long DIV_NUM_BASE = (1L<<32); // Number base (32 bits).
5150
5151     /*
5152      * divideAndRound 128-bit value by long divisor.
5153      * returns null if quotient can't fit into long value;
5154      * Specialized version of Knuth's division
5155      */
5156     private static BigDecimal divideAndRound128(final long dividendHi, final long dividendLo, long divisor, int sign,
5157                                                 int scale, int roundingMode, int preferredScale) {
5158         if (dividendHi >= divisor) {
5159             return null;
5160         }
5161
5162         final int shift = Long.numberOfLeadingZeros(divisor);
5163         divisor <<= shift;
5164
5165         final long v1 = divisor >>> 32;
5166         final long v0 = divisor & LONG_MASK;
5167
5168         long tmp = dividendLo << shift;
5169         long u1 = tmp >>> 32;
5170         long u0 = tmp & LONG_MASK;
5171
5172         tmp = (dividendHi << shift) | (dividendLo >>> 64 - shift);
5173         long u2 = tmp & LONG_MASK;
5174         long q1, r_tmp;
5175         if (v1 == 1) {
5176             q1 = tmp;
5177             r_tmp = 0;
5178         } else if (tmp >= 0) {
5179             q1 = tmp / v1;
5180             r_tmp = tmp - q1 * v1;
5181         } else {
5182             long[] rq = divRemNegativeLong(tmp, v1);
5183             q1 = rq[1];
5184             r_tmp = rq[0];
5185         }
5186
5187         while(q1 >= DIV_NUM_BASE || unsignedLongCompare(q1*v0, make64(r_tmp, u1))) {
5188             q1--;
5189             r_tmp += v1;
5190             if (r_tmp >= DIV_NUM_BASE)
5191                 break;
5192         }
5193
5194         tmp = mulsub(u2,u1,v1,v0,q1);
5195         u1 = tmp & LONG_MASK;
5196         long q0;
5197         if (v1 == 1) {
5198             q0 = tmp;
5199             r_tmp = 0;
5200         } else if (tmp >= 0) {
5201             q0 = tmp / v1;
5202             r_tmp = tmp - q0 * v1;
5203         } else {
5204             long[] rq = divRemNegativeLong(tmp, v1);
5205             q0 = rq[1];
5206             r_tmp = rq[0];
5207         }
5208
5209         while(q0 >= DIV_NUM_BASE || unsignedLongCompare(q0*v0,make64(r_tmp,u0))) {
5210             q0--;
5211             r_tmp += v1;
5212             if (r_tmp >= DIV_NUM_BASE)
5213                 break;
5214         }
5215
5216         if((int)q1 < 0) {
5217             // result (which is positive and unsigned here)
5218             // can't fit into long due to sign bit is used for value
5219             MutableBigInteger mq = new MutableBigInteger(new int[]{(int)q1, (int)q0});
5220             if (roundingMode == ROUND_DOWN && scale == preferredScale) {
5221                 return mq.toBigDecimal(sign, scale);
5222             }
5223             long r = mulsub(u1, u0, v1, v0, q0) >>> shift;
5224             if (r != 0) {
5225                 if(needIncrement(divisor >>> shift, roundingMode, sign, mq, r)){
5227                 }
5228                 return mq.toBigDecimal(sign, scale);
5229             } else {
5230                 if (preferredScale != scale) {
5231                     BigInteger intVal =  mq.toBigInteger(sign);
5232                     return createAndStripZerosToMatchScale(intVal,scale, preferredScale);
5233                 } else {
5234                     return mq.toBigDecimal(sign, scale);
5235                 }
5236             }
5237         }
5238
5239         long q = make64(q1,q0);
5240         q*=sign;
5241
5242         if (roundingMode == ROUND_DOWN && scale == preferredScale)
5243             return valueOf(q, scale);
5244
5245         long r = mulsub(u1, u0, v1, v0, q0) >>> shift;
5246         if (r != 0) {
5247             boolean increment = needIncrement(divisor >>> shift, roundingMode, sign, q, r);
5248             return valueOf((increment ? q + sign : q), scale);
5249         } else {
5250             if (preferredScale != scale) {
5251                 return createAndStripZerosToMatchScale(q, scale, preferredScale);
5252             } else {
5253                 return valueOf(q, scale);
5254             }
5255         }
5256     }
5257
5258     /*
5259      * calculate divideAndRound for ldividend*10^raise / divisor
5260      * when abs(dividend)==abs(divisor);
5261      */
5262     private static BigDecimal roundedTenPower(int qsign, int raise, int scale, int preferredScale) {
5263         if (scale > preferredScale) {
5264             int diff = scale - preferredScale;
5265             if(diff < raise) {
5266                 return scaledTenPow(raise - diff, qsign, preferredScale);
5267             } else {
5268                 return valueOf(qsign,scale-raise);
5269             }
5270         } else {
5271             return scaledTenPow(raise, qsign, scale);
5272         }
5273     }
5274
5275     static BigDecimal scaledTenPow(int n, int sign, int scale) {
5276         if (n < LONG_TEN_POWERS_TABLE.length)
5277             return valueOf(sign*LONG_TEN_POWERS_TABLE[n],scale);
5278         else {
5279             BigInteger unscaledVal = bigTenToThe(n);
5280             if(sign==-1) {
5281                 unscaledVal = unscaledVal.negate();
5282             }
5283             return new BigDecimal(unscaledVal, INFLATED, scale, n+1);
5284         }
5285     }
5286
5287     /**
5288      * Calculate the quotient and remainder of dividing a negative long by
5289      * another long.
5290      *
5291      * @param n the numerator; must be negative
5292      * @param d the denominator; must not be unity
5293      * @return a two-element {@long} array with the remainder and quotient in
5294      *         the initial and final elements, respectively
5295      */
5296     private static long[] divRemNegativeLong(long n, long d) {
5297         assert n < 0 : "Non-negative numerator " + n;
5298         assert d != 1 : "Unity denominator";
5299
5300         // Approximate the quotient and remainder
5301         long q = (n >>> 1) / (d >>> 1);
5302         long r = n - q * d;
5303
5304         // Correct the approximation
5305         while (r < 0) {
5306             r += d;
5307             q--;
5308         }
5309         while (r >= d) {
5310             r -= d;
5311             q++;
5312         }
5313
5314         // n - q*d == r && 0 <= r < d, hence we're done.
5315         return new long[] {r, q};
5316     }
5317
5318     private static long make64(long hi, long lo) {
5319         return hi<<32 | lo;
5320     }
5321
5322     private static long mulsub(long u1, long u0, final long v1, final long v0, long q0) {
5323         long tmp = u0 - q0*v0;
5324         return make64(u1 + (tmp>>>32) - q0*v1,tmp & LONG_MASK);
5325     }
5326
5327     private static boolean unsignedLongCompare(long one, long two) {
5328         return (one+Long.MIN_VALUE) > (two+Long.MIN_VALUE);
5329     }
5330
5331     private static boolean unsignedLongCompareEq(long one, long two) {
5332         return (one+Long.MIN_VALUE) >= (two+Long.MIN_VALUE);
5333     }
5334
5335
5336     // Compare Normalize dividend & divisor so that both fall into [0.1, 0.999...]
5337     private static int compareMagnitudeNormalized(long xs, int xscale, long ys, int yscale) {
5338         // assert xs!=0 && ys!=0
5339         int sdiff = xscale - yscale;
5340         if (sdiff != 0) {
5341             if (sdiff < 0) {
5342                 xs = longMultiplyPowerTen(xs, -sdiff);
5343             } else { // sdiff > 0
5344                 ys = longMultiplyPowerTen(ys, sdiff);
5345             }
5346         }
5347         if (xs != INFLATED)
5348             return (ys != INFLATED) ? longCompareMagnitude(xs, ys) : -1;
5349         else
5350             return 1;
5351     }
5352
5353     // Compare Normalize dividend & divisor so that both fall into [0.1, 0.999...]
5354     private static int compareMagnitudeNormalized(long xs, int xscale, BigInteger ys, int yscale) {
5355         // assert "ys can't be represented as long"
5356         if (xs == 0)
5357             return -1;
5358         int sdiff = xscale - yscale;
5359         if (sdiff < 0) {
5360             if (longMultiplyPowerTen(xs, -sdiff) == INFLATED ) {
5361                 return bigMultiplyPowerTen(xs, -sdiff).compareMagnitude(ys);
5362             }
5363         }
5364         return -1;
5365     }
5366
5367     // Compare Normalize dividend & divisor so that both fall into [0.1, 0.999...]
5368     private static int compareMagnitudeNormalized(BigInteger xs, int xscale, BigInteger ys, int yscale) {
5369         int sdiff = xscale - yscale;
5370         if (sdiff < 0) {
5371             return bigMultiplyPowerTen(xs, -sdiff).compareMagnitude(ys);
5372         } else { // sdiff >= 0
5373             return xs.compareMagnitude(bigMultiplyPowerTen(ys, sdiff));
5374         }
5375     }
5376
5377     private static long multiply(long x, long y){
5378                 long product = x * y;
5379         long ax = Math.abs(x);
5380         long ay = Math.abs(y);
5381         if (((ax | ay) >>> 31 == 0) || (y == 0) || (product / y == x)){
5382                         return product;
5383                 }
5384         return INFLATED;
5385     }
5386
5387     private static BigDecimal multiply(long x, long y, int scale) {
5388         long product = multiply(x, y);
5389         if(product!=INFLATED) {
5390             return valueOf(product,scale);
5391         }
5392         return new BigDecimal(BigInteger.valueOf(x).multiply(y),INFLATED,scale,0);
5393     }
5394
5395     private static BigDecimal multiply(long x, BigInteger y, int scale) {
5396         if(x==0) {
5397             return zeroValueOf(scale);
5398         }
5399         return new BigDecimal(y.multiply(x),INFLATED,scale,0);
5400     }
5401
5402     private static BigDecimal multiply(BigInteger x, BigInteger y, int scale) {
5403         return new BigDecimal(x.multiply(y),INFLATED,scale,0);
5404     }
5405
5406     /**
5407      * Multiplies two long values and rounds according {@code MathContext}
5408      */
5409     private static BigDecimal multiplyAndRound(long x, long y, int scale, MathContext mc) {
5410         long product = multiply(x, y);
5411         if(product!=INFLATED) {
5412             return doRound(product, scale, mc);
5413         }
5414         // attempt to do it in 128 bits
5415         int rsign = 1;
5416         if(x < 0) {
5417             x = -x;
5418             rsign = -1;
5419         }
5420         if(y < 0) {
5421             y = -y;
5422             rsign *= -1;
5423         }
5424         // multiply dividend0 * dividend1
5425         long m0_hi = x >>> 32;
5426         long m0_lo = x & LONG_MASK;
5427         long m1_hi = y >>> 32;
5428         long m1_lo = y & LONG_MASK;
5429         product = m0_lo * m1_lo;
5430         long m0 = product & LONG_MASK;
5431         long m1 = product >>> 32;
5432         product = m0_hi * m1_lo + m1;
5433         m1 = product & LONG_MASK;
5434         long m2 = product >>> 32;
5435         product = m0_lo * m1_hi + m1;
5436         m1 = product & LONG_MASK;
5437         m2 += product >>> 32;
5438         long m3 = m2>>>32;
5439         m2 &= LONG_MASK;
5440         product = m0_hi*m1_hi + m2;
5441         m2 = product & LONG_MASK;
5442         m3 = ((product>>>32) + m3) & LONG_MASK;
5443         final long mHi = make64(m3,m2);
5444         final long mLo = make64(m1,m0);
5445         BigDecimal res = doRound128(mHi, mLo, rsign, scale, mc);
5446         if(res!=null) {
5447             return res;
5448         }
5449         res = new BigDecimal(BigInteger.valueOf(x).multiply(y*rsign), INFLATED, scale, 0);
5450         return doRound(res,mc);
5451     }
5452
5453     private static BigDecimal multiplyAndRound(long x, BigInteger y, int scale, MathContext mc) {
5454         if(x==0) {
5455             return zeroValueOf(scale);
5456         }
5457         return doRound(y.multiply(x), scale, mc);
5458     }
5459
5460     private static BigDecimal multiplyAndRound(BigInteger x, BigInteger y, int scale, MathContext mc) {
5461         return doRound(x.multiply(y), scale, mc);
5462     }
5463
5464     /**
5465      * rounds 128-bit value according {@code MathContext}
5466      * returns null if result can't be repsented as compact BigDecimal.
5467      */
5468     private static BigDecimal doRound128(long hi, long lo, int sign, int scale, MathContext mc) {
5469         int mcp = mc.precision;
5470         int drop;
5471         BigDecimal res = null;
5472         if(((drop = precision(hi, lo) - mcp) > 0)&&(drop<LONG_TEN_POWERS_TABLE.length)) {
5473             scale = checkScaleNonZero((long)scale - drop);
5474             res = divideAndRound128(hi, lo, LONG_TEN_POWERS_TABLE[drop], sign, scale, mc.roundingMode.oldMode, scale);
5475         }
5476         if(res!=null) {
5477             return doRound(res,mc);
5478         }
5479         return null;
5480     }
5481
5482     private static final long[][] LONGLONG_TEN_POWERS_TABLE = {
5483         {   0L, 0x8AC7230489E80000L },  //10^19
5484         {       0x5L, 0x6bc75e2d63100000L },  //10^20
5485         {       0x36L, 0x35c9adc5dea00000L },  //10^21
5486         {       0x21eL, 0x19e0c9bab2400000L  },  //10^22
5487         {       0x152dL, 0x02c7e14af6800000L  },  //10^23
5488         {       0xd3c2L, 0x1bcecceda1000000L  },  //10^24
5489         {       0x84595L, 0x161401484a000000L  },  //10^25
5490         {       0x52b7d2L, 0xdcc80cd2e4000000L  },  //10^26
5491         {       0x33b2e3cL, 0x9fd0803ce8000000L  },  //10^27
5492         {       0x204fce5eL, 0x3e25026110000000L  },  //10^28
5493         {       0x1431e0faeL, 0x6d7217caa0000000L  },  //10^29
5494         {       0xc9f2c9cd0L, 0x4674edea40000000L  },  //10^30
5495         {       0x7e37be2022L, 0xc0914b2680000000L  },  //10^31
5496         {       0x4ee2d6d415bL, 0x85acef8100000000L  },  //10^32
5497         {       0x314dc6448d93L, 0x38c15b0a00000000L  },  //10^33
5498         {       0x1ed09bead87c0L, 0x378d8e6400000000L  },  //10^34
5499         {       0x13426172c74d82L, 0x2b878fe800000000L  },  //10^35
5500         {       0xc097ce7bc90715L, 0xb34b9f1000000000L  },  //10^36
5501         {       0x785ee10d5da46d9L, 0x00f436a000000000L  },  //10^37
5502         {       0x4b3b4ca85a86c47aL, 0x098a224000000000L  },  //10^38
5503     };
5504
5505     /*
5506      * returns precision of 128-bit value
5507      */
5508     private static int precision(long hi, long lo){
5509         if(hi==0) {
5510             if(lo>=0) {
5511                 return longDigitLength(lo);
5512             }
5513             return (unsignedLongCompareEq(lo, LONGLONG_TEN_POWERS_TABLE[0][1])) ? 20 : 19;
5514             // 0x8AC7230489E80000L  = unsigned 2^19
5515         }
5516         int r = ((128 - Long.numberOfLeadingZeros(hi) + 1) * 1233) >>> 12;
5517         int idx = r-19;
5518         return (idx >= LONGLONG_TEN_POWERS_TABLE.length || longLongCompareMagnitude(hi, lo,
5519                                                                                     LONGLONG_TEN_POWERS_TABLE[idx][0], LONGLONG_TEN_POWERS_TABLE[idx][1])) ? r : r + 1;
5520     }
5521
5522     /*
5523      * returns true if 128 bit number <hi0,lo0> is less than <hi1,lo1>
5524      * hi0 & hi1 should be non-negative
5525      */
5526     private static boolean longLongCompareMagnitude(long hi0, long lo0, long hi1, long lo1) {
5527         if(hi0!=hi1) {
5528             return hi0<hi1;
5529         }
5530         return (lo0+Long.MIN_VALUE) <(lo1+Long.MIN_VALUE);
5531     }
5532
5533     private static BigDecimal divide(long dividend, int dividendScale, long divisor, int divisorScale, int scale, int roundingMode) {
5534         if (checkScale(dividend,(long)scale + divisorScale) > dividendScale) {
5535             int newScale = scale + divisorScale;
5536             int raise = newScale - dividendScale;
5537             if(raise<LONG_TEN_POWERS_TABLE.length) {
5538                 long xs = dividend;
5539                 if ((xs = longMultiplyPowerTen(xs, raise)) != INFLATED) {
5540                     return divideAndRound(xs, divisor, scale, roundingMode, scale);
5541                 }
5542                 BigDecimal q = multiplyDivideAndRound(LONG_TEN_POWERS_TABLE[raise], dividend, divisor, scale, roundingMode, scale);
5543                 if(q!=null) {
5544                     return q;
5545                 }
5546             }
5547             BigInteger scaledDividend = bigMultiplyPowerTen(dividend, raise);
5548             return divideAndRound(scaledDividend, divisor, scale, roundingMode, scale);
5549         } else {
5550             int newScale = checkScale(divisor,(long)dividendScale - scale);
5551             int raise = newScale - divisorScale;
5552             if(raise<LONG_TEN_POWERS_TABLE.length) {
5553                 long ys = divisor;
5554                 if ((ys = longMultiplyPowerTen(ys, raise)) != INFLATED) {
5555                     return divideAndRound(dividend, ys, scale, roundingMode, scale);
5556                 }
5557             }
5558             BigInteger scaledDivisor = bigMultiplyPowerTen(divisor, raise);
5559             return divideAndRound(BigInteger.valueOf(dividend), scaledDivisor, scale, roundingMode, scale);
5560         }
5561     }
5562
5563     private static BigDecimal divide(BigInteger dividend, int dividendScale, long divisor, int divisorScale, int scale, int roundingMode) {
5564         if (checkScale(dividend,(long)scale + divisorScale) > dividendScale) {
5565             int newScale = scale + divisorScale;
5566             int raise = newScale - dividendScale;
5567             BigInteger scaledDividend = bigMultiplyPowerTen(dividend, raise);
5568             return divideAndRound(scaledDividend, divisor, scale, roundingMode, scale);
5569         } else {
5570             int newScale = checkScale(divisor,(long)dividendScale - scale);
5571             int raise = newScale - divisorScale;
5572             if(raise<LONG_TEN_POWERS_TABLE.length) {
5573                 long ys = divisor;
5574                 if ((ys = longMultiplyPowerTen(ys, raise)) != INFLATED) {
5575                     return divideAndRound(dividend, ys, scale, roundingMode, scale);
5576                 }
5577             }
5578             BigInteger scaledDivisor = bigMultiplyPowerTen(divisor, raise);
5579             return divideAndRound(dividend, scaledDivisor, scale, roundingMode, scale);
5580         }
5581     }
5582
5583     private static BigDecimal divide(long dividend, int dividendScale, BigInteger divisor, int divisorScale, int scale, int roundingMode) {
5584         if (checkScale(dividend,(long)scale + divisorScale) > dividendScale) {
5585             int newScale = scale + divisorScale;
5586             int raise = newScale - dividendScale;
5587             BigInteger scaledDividend = bigMultiplyPowerTen(dividend, raise);
5588             return divideAndRound(scaledDividend, divisor, scale, roundingMode, scale);
5589         } else {
5590             int newScale = checkScale(divisor,(long)dividendScale - scale);
5591             int raise = newScale - divisorScale;
5592             BigInteger scaledDivisor = bigMultiplyPowerTen(divisor, raise);
5593             return divideAndRound(BigInteger.valueOf(dividend), scaledDivisor, scale, roundingMode, scale);
5594         }
5595     }
5596
5597     private static BigDecimal divide(BigInteger dividend, int dividendScale, BigInteger divisor, int divisorScale, int scale, int roundingMode) {
5598         if (checkScale(dividend,(long)scale + divisorScale) > dividendScale) {
5599             int newScale = scale + divisorScale;
5600             int raise = newScale - dividendScale;
5601             BigInteger scaledDividend = bigMultiplyPowerTen(dividend, raise);
5602             return divideAndRound(scaledDividend, divisor, scale, roundingMode, scale);
5603         } else {
5604             int newScale = checkScale(divisor,(long)dividendScale - scale);
5605             int raise = newScale - divisorScale;
5606             BigInteger scaledDivisor = bigMultiplyPowerTen(divisor, raise);
5607             return divideAndRound(dividend, scaledDivisor, scale, roundingMode, scale);
5608         }
5609     }
5610
5611 }
```