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