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