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