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