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