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