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