Best Tools for JAVA/Best Tools for JAVA.iso/JAVA_ALL/JDBC/JDBC_011/JAVA/LANG/BIGNUM.JAV

Text File | 1996-11-10 | 61.1 KB | 2,222 lines

/*
 * @(#)Bignum.java    1.8 96/11/08
 *
 * Copyright (c) 1996 Sun Microsystems, Inc. All Rights Reserved.
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL purposes and without
 * fee is hereby granted provided that this copyright notice
 * appears in all copies. Please refer to the file "LICENSE"
 * for further important copyright and licensing information.
 *
 * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 *
 * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
 * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
 * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
 * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
 * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
 * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
 * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES").  SUN
 * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
 * HIGH RISK ACTIVITIES.
 */



package java.lang;
import java.util.Random;

/**
 * The Bignum class represents fixed point numbers of practically
 * unlimited precision. The size of each instance depends on the
 * number of digits it represents(its precision). The precision of an
 * instance's fractional part is determined by its scale.
 *
 * <P>The rounding behaviors needed for business and scientific
 * computation often differ. To meet this requirement, the rounding
 * behavior for the class as a whole can be changed.
 *
 * <P>The Bignum class should be used for values that require high
 * precision fixed point or integer computation. Examples of this are
 * money values, security key values and values stored in databases
 * using the high precision SQL NUMERIC or DECIMAL type.
 *
 * <P>Calculations on Bignum objects always return a new Bignum object
 * with the same scale as the Bignum that performed the
 * calculation. Most operations are carried out to one extra decimal
 * place and rounded to the desired scale.
 *
 * <P>Bignum's are immutable and thread-safe.
 *
 * <P>Since Bignum values with 10's of thousands of digits can be
 * represented, the practical limit to their precision is the space
 * and time needed to work with them. The max scale value is max int;
 * the max precision of this implementation is limited only by Java's
 * maximum array size.
 *
 * <P>Bignum objects are composed of three properties: <UL>
 * <LI>Scale: The number of digits to the right of the decimal point.
 * <LI>Sign:  Positive or negative.
 * <LI>Value: In this implementation, a vector of integer digits of radix 2^30.
 * </UL> */
public final class Bignum extends java.lang.Number {

    /**
     * Sets the rounding option for all Bignum's in a program; the
     * default rounding option is ROUND_ABOVE_4.
     *
     * <P>All Bignum computation is done using an extra digit of
     * precision which is truncated prior to returning the result. The
     * rounding option determines how the value of this extra digit
     * affects the returned value. Rounding also applies when the
     * scale of a Bignum is reduced; here, rounding defines how the
     * value of the most significant truncated digit affects the
     * result.
     *
     * <P>If rounding causes the least signifcant digit of a result to
     * be incremented by 1, we say the result has been 'rounded up'. If
     * the least signficant digit of a result is left as is, we say the
     * result has been 'rounded down'.
     *
     * <P>The following rounding options are provided:
     *
     * <DL>
     *  <DT>NO_ROUNDING:        <DD>All results are rounded down regardless
     *                          of the value of the most significant truncated digit.
     *                          For example, 1.999 would round to 1.99.
     *
     *  <DT>ROUND_ABOVE_4:      <DD>If the value of the most significant truncated
     *                          digit is > 4, the result is rounded up; otherwise,
     *                          the result is rounded down. For example, 1.994 would
     *                          round down to 1.99 and 1.995 would round up to 2.00
     *
     *  <DT>ROUND_ABOVE_5:      <DD>If the value of the most significant truncated
     *                          digit is > 5, the result is rounded up; otherwise,
     *                          the result is rounded down. For example, 1.995 would
     *                          round down to 1.99 and 1.996 would round up to 2.00.
     *
     *  <DT>ROUND_ALWAYS :      <DD>If the value of the most significant truncated
     *                          digit is > 0, the result is rounded up; otherwise,
     *                          the result is rounded down. For example, 1.990 would
     *                          round down to 1.99 and 1.991 would round up to 2.00.
     *
     *  <DT>ROUND_STATISTICAL : <DD>If the value of the most significant truncated
     *                          digit is > 5, the result is rounded up.  If the value
     *                          of the most significant truncated digit is < 5, the
     *                          result is rounded down. If the value of the most
     *                          significant truncated digit is = 5, the result is
     *                          rounded down if the remaining least significant digit
     *                          is even; if it's odd the result is rounded up.
     *                          For example, 1.994 would round down to 1.99; 1.996 would
     *                          round up to 2.00; 1.985 would round down to 1.98; and, 1.995
     *                          would round up to 2.00. This option is used to help reduce
     *                          systematic rounding bias. See Bevington and Robinson,
     *                          'Data Reduction and Error Analysis for the Physical Sciences',
     *                          pp. 4, McGraw Hill, Inc., (1992).
     * </DL>
     * @param val The rounding option to use for all Bignum's.
     */

    public static void setRoundingOption(int val) {
        switch(val) {
    case ROUND_STATISTICAL :
        roundingValue = -1;
        break;
    case  NO_ROUNDING :
        roundingValue = 9;
        break;
    case  ROUND_ABOVE_5 :
        roundingValue = 5 ;
        break;
    case  ROUND_ABOVE_4:
        roundingValue= 4;
        break;
    case  ROUND_ALWAYS:
        roundingValue = 0;
        break;
    default:
        if (val < 0 || val > 9)
        throw new IllegalArgumentException("Attempt to set invalid RoundingOption");
        break;
    }
    }

    /**
     * Returns the current rounding option for all Bignum's in this
     * program.
     *
     * @return current rounding option
     */
    public static int getRoundingOption() {
        return(roundingValue);
    }

    /**
     * Creates a Bignum from a string. The string may contain a sign
     * and a decimal point, e.g "-55.12".  Spaces and other
     * non-numeric characters are ignored. Scientific notation, i.e.
     * mantissa with exponent (3E.05) is supported.
     *
     * @param s the string used to initialize the Bignum.
     */

    public Bignum(String s) {
    init(s,-1);
    }

    /**
     * Construct a Bignum given a String and an integer scale.  The
     * scale represents the desired number of places to the right of
     * the decimal point.
     *
     * <P>The String may contain a sign and a decimal point,
     * e.g. "-55.12".  Spaces and other non-numeric characters are
     * ignored. Scientific notation, i.e. mantissa with exponent
     * (3E.05) is supported. The scale must be an integer with value
     * greater than or equal to zero.  If the scale differs from the
     * implicit decimal point given in the String the value is
     * adjusted to the given scale.  This may involve rounding.
     *
     * <P>For example, Bignum("99.995",2) would result in a Bignum
     * with a scale of 2 and a value of "100.00".  If the String
     * contains no decimal point, then the scale is determined solely
     * by the given integer scale. No implicit decimal point is
     * assumed.  For example, the constructor Bignum("123",2) creates
     * a Bignum with a scale of 2 and a value of
     * "123.00".
     *
     * <P><B>Note:</B> Rounding is controlled by the roundingIndex
     * function.
     *
     * @param  s    the string used to initialize the Bignum.
     * @param scale the value greater than or equal to zero
     * representing the desired number of digits to the right of the
     * decimal point.
     */
    public Bignum(String s,int scale) {
    verifyScale(scale);
    init(s,scale);
    }

    /**
     * Construct a Bignum from an integer given an integer value and
     * an integer scale.  The scale is set to the value specified. No
     * implicit decimal point is assumed, i.e., if the integer value is
     * "1234" and the scale 2, the resulting Bignum will be "1234.00.
     *
     * @param  x    The int used to initialize the new Bignum.
     * @param scale The desired number of digits after the decimal point.
     */
    public Bignum(int x,int scale) {
    verifyScale(scale);
    if(x < 0) {
        negative = true;
        x *= -1;
        if(x < 0) {
        int[] v = {0,2};
        value = v;
        _setScale(scale);
        return;
        }
    }
    else
        negative = false;
    int digit0 = (int)(x & MASK);
    long carry = (long)x >> SRADIX;
    int digit1 = (int) (carry & MASK);

    if(digit1 > 0) {
        int[] v = {digit0,digit1};
        value = v;
    }
    else {
        int [] v = {digit0};
        value = v;
    }
    _setScale(scale);
    }
    /**
     * Construct a Bignum from an integer given an integer value.
     * The scale is set to zero.
     *
     * @param  x    The long used to initialize the new Bignum.
     */
    public Bignum(int x) {
    this(x,0);
    }
    /**
     * Construct a Bignum from a long integer given a long value and
     * an integer scale.  The scale is set to the value specified. No
     * implicit decimal point is assumed, i.e., if the long value is
     * "1234" and the scale 2, the resulting Bignum will be "1234.00.
     *
     * @param  x    The long value used to initialize the new Bignum.
     * @param scale The desired number of digits after the decimal point.
     */
    public Bignum(long x,int scale) {
    verifyScale(scale);

    if(x < 0) {
        negative = true;
        x *= -1L;
        if(x < 0) {
        int[] v = {0,0,8};
        value = v;
        _setScale(scale);
        return;
        }
    }
    else
        negative = false;
    int digit0 = (int)(x & MASK);
    long carry = x >> SRADIX;
    int digit1 = (int) (carry & MASK);
    carry = carry >> SRADIX;
    int digit2 = (int) (carry & MASK);
    if(digit2 > 0) {
        int[] v= {digit0,digit1,digit2};
        value = v;
    }
    else
        if(digit1 > 0) {
                int[] v = {digit0,digit1};
                value = v;
            }
            else {
                int [] v = {digit0};
        value = v;
        }
    _setScale(scale);
    }
    /**
     * Construct a Bignum from a long integer given a long integer value.
     * The scale is set to zero.
     *
     * @param  x    The long used to initialize the new Bignum.
     */
    public Bignum(long x) {
    this(x,0);
    }

    /**
     * Construct a Bignum from a double given a double value and an
     * integer scale.  The scale is set to the value specified. No
     * implicit decimal point is assumed, i.e., if the double value is
     * "1234" and the scale 2, the resulting Bignum will be "1234.00.
     * If the double value is "1234.5" and the scale 2 the value will
     * be "1234.50".  Rounding may occur during this conversion.
     *
     * @param  x    The double value used to initialize the new Bignum.
     * @param scale The desired number of digits after the decimal point.
     */
    public Bignum(double x, int scale) {
    verifyScale(scale);
    Double d = new Double(x);//I'm going to have to redo this to
    init(d.toString(),scale);// calculate exponent and fraction
    //This is a cheat.
    }

    /**
     * Construct a Bignum from another Bignum.  The
     * scale and value of the new Bignum are copied from the Bignum
     * given in the argument.
     *
     * @param x The Bignum used to initialize the new Bignum.
     */
    public Bignum(Bignum x) {
    scale = x.scale;
    value = new int[x.value.length];
    System.arraycopy(x.value,0,value,0,value.length);
    negative = x.negative;
    }

    /**
     * Given an existing Bignum and an integer scale value, construct
     * a new Bignum with the scale adjusted accordingly.  The
     * scale and value of the new Bignum are copied from
     * the argument Bignum. The scale is then adjusted to the scale
     * given as a parameter. This may result in rounding of the value.
     *
     * @param  x        The Bignum to copy.
     * @param scale An integer representing the desired * scale of the
     * new Bignum.
     */
    public Bignum(Bignum x, int scale) {
    verifyScale(scale);
    this.scale = x.scale;
    value = new int[x.value.length];
    System.arraycopy(x.value,0,value,0,value.length);
    negative = x.negative;
    if (this.scale != scale) {
        _setScale(scale);
    }
    }
    //----------------------Static Factory Methods----------------------------
    /**
     * Return a Bignum created from the given byte array.
     * The array is treated as a string of bits representing an unsigned
     * integer, with the most significant bit at the 0th position.  This
     * function is supplied to simplify and optimize operations in
     * algorithms using large integers, such as hashing calculations.
     *
     * @param byteArray An array of bytes holding the bitstring value of
     *    the desired Bignum.
     * @return A new Bignum whose value is determined by the given byte array.
     */
    public static Bignum createFromByteArray(byte[] byteArray) {
    Bignum    r = new Bignum(0);
    int    numBits = byteArray.length * 8;
    int    numWords = (numBits + (SRADIX - 1)) / SRADIX;

    r.scale = 0;
    r.negative = false;
    r.value = new int [numWords];

    // byteArray[] is big-endian, base256; value[] is little-endian
    // and base 2^SRADIX.  this stuffs bits into value[], LSB first.

    for (int i = byteArray.length - 1, digit = 0; i >= 0; i--) {
        int        bits, bitOffset;

        bits = byteArray [i] & 0x0ff;
        bitOffset = ((byteArray.length - i - 1) * 8) % SRADIX;
        r.value [digit] |= (bits << bitOffset) & MASK;

        bitOffset = SRADIX - bitOffset;
        if (bitOffset <= 8) {
            digit++;
            if (bitOffset < 8)
            r.value [digit] |= (bits >>> bitOffset);
        }
    }//for

    return r;
    }
    /**
     * Returns  a byte array derived from the value of the numeric.
     * The array is considered a string of bits with the most significant bit
     * at the 0th position.This function should be used with great caution.
     * It is supplied to simplify and optimize calculations in algorithms that
     * used hashing calculations, e.g. many security algorithms.
     * @returns A byte array derived from the value of the Bignum
     */
    public  byte[] toByteArray(){
    int i,j;
    i = significantBits();
    if(i <= 0) {
        byte[] b = new byte[1];
        b[0] = 0x00;
    }
    j = i/8;
    if(i%8 >0) j++;

    byte [] outArray = new byte[j];

    int[] r = new int[value.length];
    System.arraycopy(value,0,r,0,value.length);
    for(j=outArray.length - 1;j >= 0; j--) {
        outArray[j] = (byte)(r[0] & 0x000000FF);
        int carry = 0;
        for (i=value.length - 1; i>=0; --i) {
        int val = r[i];
        r[i] = (val>>>8) | carry;
        carry = (int)((val<<(SRADIX-8)) & MASK);
        }
    }
    return outArray;
    }

    /**
     * Return a Bignum created from the given Integer array.
     * The array is considered a string of bits with the least significant bit
     * at the 0th position. This function should be used with great caution.
     * It is supplied to simplify and optimize calculations in algorithms that
     * used hashing calculations, e.g. many security algorithms.
     * @param  intArray    An array of integers holding the desired value of the new Bignum.
     * @return A new Bignum whose value is determined by the given integer array.
     */
    public static Bignum createFromIntegerArray(int [] intArray) {
    int[] t1 = new int[intArray.length + 1];
    for(int i = 0; i < intArray.length;i++){
        t1[i]  = (int)(intArray[i] & MASK);
    }
    Bignum r = new Bignum(t1);
    r.scale = 0;
    r.negative = false;

    return r;
    }
    /**
     * Return a Bignum value created by dividing the argument by
     * 10**scale.  Thus, createFromScaled(504,2) would create the
     * value "5.04". A negative scale throws an IllegalArgumentException.
     *
     * @param  scaled The scaled value as a long.
     * @param  s      The desired scale value
     * @return A new Bignum.
     */
    public static Bignum createFromScaled(long scaled, int s) {
    verifyScale(s);
    Bignum n = new Bignum(scaled);
    if (s != 0)
        n.scale = s;
    return n;
    }

    /**
     * Return a Bignum created from the given string and radix.
     * Decimal places are ignored and the scale is set to zero.
     * The string may contain a sign.
     * @param  s    A string containing the intended value of the Bignum.
     * @param  radix    The base of the string representation.
     * @return A new Bignum whose value is given by the string argument.
     */
    public static Bignum createFromRadixString(String s, int radix) {
    Bignum r = new Bignum(0);
    r.scale = 0;
    r.negative = false;
    r.value = new int[s.length()/(radix/2) + 1];

    int[] t1;
    //char maxChar = Character.forDigit(radix - 1,radix);
    int a;
    char c;
    boolean gotFirstDigit = false;
    for (int i = 0;i < s.length() ;i++ ) {
        c = s.charAt(i);
        a = Character.digit(c,radix);
        if(a >= 0){
        gotFirstDigit = true;
        t1 = mulAndAdd(r.value,radix,a);
        if(t1 != null)
            r.value = t1;
        continue;
        }
        if (c == '-' && !gotFirstDigit) {
        r.negative = true;
        continue;
        }
    }//for
    return r;
    }
    /**
     *Random number generator
     *Returns a random number using randomSeed as a seed and with a number of bits of up to bitSize.
     *@param bitSize The position of the most significant bit in the random number
     *@param randomSeed a Random number used as the seed for the random number generated
     *@return a new Bignum of maximium size bitSize
     */
    public static Bignum random(int bits, Random randomSeed){
    int ni = (bits-1)/SRADIX + 1;
    int i;
    bits = bits % SRADIX;
    int[] rs = new int[ni];
    for (i=0; i<ni; ++i) {
        int r = (int) (randomSeed.nextInt() & MASK);
        rs[i] = r;
    }
    rs[ni-1] &= (1<<bits)-1;
    Bignum rslt = new Bignum(rs);
    rslt.dropLeadingZeroes();
    return rslt;
    }


    /**
     * The following methods convert the Bignum value to an
     * appropriate Java built-in type.  Note that these conversions
     * may result in a loss of precision.
     *
     */

    /**
     * Convert the Bignum value an int.
     * This conversion may result in a loss of precision.  Digits
     * after the decimal point are dropped.
     *
     * @return An int value representation of the Bignum.
     */
    public int intValue() {
    return ((int)longValue());
    }

    /**
     * Convert the Bignum value to a long.
     * This conversion may result in a loss of precision.  Digits
     * after the decimal point are dropped.
     *
     * @return A long value representation of the Bignum.
     */
    public long longValue() {
    Bignum temp = new Bignum(this);
    temp._setScale(0);
    long lv = 0;
    int i = temp.value.length < 3 ? temp.value.length - 1: 2;

    for(;i >= 0;i--){
        lv = (lv << SRADIX) + temp.value[i];
    }
    return temp.negative? -lv : lv;
    }

    /**
     * Convert the Bignum value to a float.
     * This conversion may result in a loss of precision.
     *
     * @return A float value representation of the Bignum.
     */
    public float floatValue() {
    return ((float) doubleValue());
    }

    /**
     * Convert the Bignum value to a double.
     * This conversion may result in a loss of precision.
     *
     * @return A double value representation of the Bignum.
     */
    public  double doubleValue() {
    Bignum temp = new Bignum(this);
    temp._setScale(0);
    double d=0.0;
    int m = value.length - 1;
    m = m > 4? m - 4 : 0;
    for(int i=value.length - 1;i>=m;i--) {
        d = d * MASK + (double) value[i];
    }
    if(m > 0)
        d = d * Math.pow(SRADIX,m);
    temp = this.subtract(temp);

    if (scale != 0) {
        double  s = 1;
        s = Math.pow(10,scale);
        d = d/s;
    }
    return negative? -d : d;
    }


    /**
     * Convert the Bignum value to a String.
     * Negative numbers are represented by a leading "-". No sign is
     * added for positive numbers.
     *
     * @return A String representation of the Bignum.
     */
    public  String toString() {
    if(value == null)
        return "null";
    int l = value.length * 10 + 2;

    if(l < scale)
        l = scale + 2;

    char[] x = new char[l];
    int xi=x.length - 1;
    int dp = xi - scale;
    if(scale == 0)
        dp = -9999;
    int[] temp = new int[value.length];
    System.arraycopy(value,0,temp,0,temp.length);
    for (int i=temp.length - 1; i >= 0;) {
        if(temp[i] == 0){
        i--;
        continue;
        }
        int rem = div0(temp,temp,10);
        x[xi--] = Character.forDigit(rem,10);
        if(xi == dp) xi--;
    }
    if(xi == x.length - 1) //was value all zeroes?
        x[xi--] = '0';
    if(dp > 0){
        while(xi > dp)
        x[xi--] = '0';
        x[dp] = '.';
    }
    String ms = negative ? "-":"";
    ms += (new String(x,xi,x.length - xi)).trim();
    return ms;
    }

    /**
     * Returns a String representation of the Bignum in the given radix.
     * In this version scaling is ignored for any radix other than 10.
     * @param radix    the base of the number to be returned
     * @return a String representation of the Bignum in the given radix
     */
    public String toString(int radix) {
    if(radix == 10)
        return toString();

    if(value == null)
        return "null";

    StringBuffer sb = new StringBuffer();
    int[] temp = new int[value.length];
    int len = 0;
    System.arraycopy(value,0,temp,0,temp.length);
    for (int i=temp.length - 1; i >= 0;) {
        if(temp[i] == 0){
        i--;
        continue;
        }
        int rem = div0(temp,temp,radix);
        sb.insert(0,Character.forDigit(rem,radix));
        len++;
    }
    if(len==0)
        sb.insert(0,'0');
    String ms = negative ? "-":"";
    ms += (sb.toString()).trim();
    return ms;

    }


    /**
     * Return the number of digits to the right of the decimal point.
     *
     *
     * @return An integer value representing the number of decimal
     * places to the right of the decimal point.
     */
    public int getScale() {
    return (scale);
    }


    //-----------------------------Arithmetic Operations------------------
    /**
     * Returns the arithmetic sum of the Bignum and the argument.
     * The scale of the sum is determined by this object not by the
     * argument. The calculation is performed using a
     * scale equal to the greater scale of the two operands. Rounding is
     * applied to the result.
     *
     * @param  n  The Bignum to add.
     * @return The sum as a Bignum.
     */
    public Bignum add(Bignum n) {
        Bignum result= new Bignum(this);
    Bignum x;
    if(scale != n.scale){
        x = new Bignum(n);
        x._setScale(scale);
    }
    else
        x = n;
        //signs match
        if (result.negative == x.negative) {
            result.value = add0(result.value,x.value);
            return (result);
        }
        //result is positive
        if (!result.negative) {
            int cmp = result.compareAbs(x);
            if (cmp < 0) { //abs value of result is less
        result.value = sub0(x.value,result.value);
        result.negative = x.negative;
        return (result);
            } else {
        if (cmp > 0) { //abs value of result is greater
            result.value = sub0(result.value,x.value);
            return (result);
        } else { //abs values are equal
            result.zero();
            return (result);

        }
            }
        }

        //result is negative
        int cmp = result.compareAbs(x);
        if (cmp < 0) { //abs value of result is less
            result.value = sub0(x.value,result.value);
            result.negative = x.negative;
            return (result);
        } else {
            if (cmp > 0) { //abs value of result is greater
        result.value = sub0(result.value,x.value);

        return (result);
            }
        }
        //abs values  are equal
        result.zero();
        return (result);
    }

    /**
     * Returns the arithmetic difference between the Bignum and the
     * argument.  The scale of the difference is determined by this object
     * not by the argument. The calculation is performed using a
     * scale equal to the greater scale of the two operands. Rounding is
     * applied to the result.
     *
     * @param  n The Bignum to subtract.
     * @return The difference as a Bignum.
     */
    public Bignum subtract(Bignum n) {
    Bignum result = new Bignum(this);
    Bignum x;
    if(result.scale != n.scale) {
        if(result.scale > n.scale) {
            x = new Bignum(n);
            x._setScale(result.scale);
        }
        else {
            x = n;
            result._setScale(x.scale);
        }
    }
    else
        x = n;

    if (result.negative == false && x.negative == false) {
        switch(result.compareAbs(x)) {
        case 0:
        result.zero();
        break;
        case 1:
        result.value = sub0(result.value,x.value);
        break;
        default:
        result.value = sub0(x.value,result.value);
        result.negative = true;
        }
        if(result.scale != this.scale)
            result._setScale(this.scale);
        return (result);
    }

    if (result.negative == false && x.negative == true) {
        result.value = add0(result.value,x.value);
    }
    else if (result.negative == true && x.negative == false) {
        result.value = add0(result.value,x.value);
    }
    else {
        switch(result.compareAbs(x)) {
        case 0:
        result.zero();
        break;
        case 1:
        result.value = sub0(result.value,x.value);
        result.negative = true;
        break;
        default:
        result.value = sub0(x.value,result.value);
        result.negative = false;
        }
    }
    if(result.scale != this.scale)
        result._setScale(this.scale);

    return (result);
    }

    /**
     * Returns the arithmetic product of the object Bignum and the
     * argument.  The scale of the product is determined by this object
     * not by the argument.
     *
     * @param  x The multiplier as a Bignum.
     * @return The product as a Bignum.
     */
    public Bignum multiply(Bignum x) {

    Bignum prod = new Bignum(this); //product
    Bignum m; //multiplicand
    Bignum mx; //multiplier

    prod.scale += x.scale;
    prod.negative = (negative == x.negative? false: true);

    if (value.length > x.value.length) {
        //use the smallest number as the multiplier
        m = this;
        mx = x;
    } else {
        m = x;
        mx = this;
    }
    if(mx.value.length == 1)
        prod.value = mul0(m.value,mx.value[0]);//use the faster single digit multiply
    else
        prod.value = mul0(m.value,mx.value);

    if(prod.scale != scale)
        prod._setScale(scale);
    prod.dropLeadingZeroes();
    return (prod);
    }

    /**
     * Returns the arithmetic quotient calculated by dividing the
     * Bignum by the argument.  The scale of the quotient is
     * determined by this object not by the argument.
     *
     * @param  x The divisor as a Bignum.
     * @return The quotient as a Bignum.
     */

    public Bignum divide(Bignum x) {
    if (x.compareAbs(Bignum.ZERO) == 0) {
        throw new ArithmeticException("Division by zero");
    }

    Bignum dividend = new Bignum(this);
    Bignum divisor = new Bignum(x);

    dividend.dropLeadingZeroes();
    divisor.dropLeadingZeroes();
    //scaling for decimal places
    if(roundingValue < 9 || (divisor.scale > dividend.scale)) {
        int scaleFactor = divisor.scale + 1;
        dividend.scale++;
        int m1 = 9; //this is approx log10 of BASE
        int m4 = 1000000000;
        int x1 = scaleFactor;
        for(;x1 >= m1;x1 -= m1 )
        dividend.value = mul0(dividend.value,m4);
        if(x1 > 0 )
        dividend.value = mul0(dividend.value,pow(10,x1));
    }

    //----------------------------------------------------------------
    Bignum quot = new Bignum(new int[(dividend.value.length - divisor.value.length) + 1]);
    quot.negative = divisor.negative ? !dividend.negative : dividend.negative;
    quot.scale = dividend.scale;
    if(divisor.value.length == 1){
        //if divisor is only 1 digit use quick division
        //remainder can only be an int
        div0(quot.value,dividend.value,divisor.value[0]);
        quot._setScale(scale);
        return quot;
    }
    //Next normalize the dividend and divisor, i.e. divisor[leftmostDigit] >= BASE/2
    //
    int vLeftmostDigit = divisor.value[divisor.value.length - 1];
    if(vLeftmostDigit >= (BASE)/2){
            int[] tvalue = new int[dividend.value.length + 1];
            System.arraycopy(dividend.value, 0, tvalue, 0, dividend.value.length);
            tvalue[tvalue.length - 1] = 0;
            dividend.value = tvalue;
            div (dividend, divisor, quot);
        } else {
            int[] tvalue = new int[dividend.value.length + 1];
            System.arraycopy(dividend.value,0,tvalue,0,dividend.value.length);
            int d = (BASE)/(vLeftmostDigit + 1);
            dividend.value = mul0(tvalue,d);
            divisor.value = mul0(divisor.value,d);
            div (dividend, divisor, quot);
        }
    quot._setScale(scale);
    return quot;
    }
    /**
     * Returns an array of two Bignum objects. The first element in
     * the array holds the quotient value resulting from the arithmetic
     * division of this Bignum object by the argument. The second element
     * in the array holds the remainder.
     *
     * @param  x The divisor as a Bignum.
     * @return An array of two Bignum objects containing the quotient and
     * remainder of the division.
     */

    public Bignum[] integerDivide(Bignum x) {
    if (x.compareAbs(Bignum.ZERO) == 0) {
        throw new ArithmeticException("Division by zero");
    }

    Bignum dividend = new Bignum(this);
    Bignum divisor = new Bignum(x);
    Bignum quot = _intDivide(divisor,dividend,scale);

    Bignum[] r = {quot,dividend};
    return r;
    }


    /* Private helper function for performing integer division
     * and remainder arithmetic.
     * the remainder is returned in dividend
     */
    static private Bignum  _intDivide(Bignum divisor,Bignum dividend, int scale){


    dividend.dropLeadingZeroes();
    divisor.dropLeadingZeroes();


    //scaling for decimal places
    if(divisor.scale > dividend.scale) {
        int scaleFactor = divisor.scale;// + 1;
        //dividend.scale++;
        int m1 = 9; //this is approx log10 of BASE
        int m4 = 1000000000;
        int x1 = scaleFactor;
        for(;x1 >= m1;x1 -= m1 )
        dividend.value = mul0(dividend.value,m4);
        if(x1 > 0 )
        dividend.value = mul0(dividend.value,pow(10,x1));
    }

    //--------------------------------------------------------------------
    if(dividend.lessThan(divisor)){
        return new Bignum(0,0);
    }
    Bignum quot = new Bignum(new int[(dividend.value.length - divisor.value.length) + 1]);
    quot.negative = divisor.negative ? !dividend.negative : dividend.negative;
    if(dividend.scale >= divisor.scale)
        quot.scale = dividend.scale - divisor.scale;
    else
        quot.scale = 0;

    //if divisor is only 1 digit use quick division
    if(divisor.value.length == 1){
        //remainder can only be an int
        int rem = div0(quot.value,dividend.value,divisor.value[0]);
        dividend.zero();
        dividend.value[0] = (int) (rem & MASK);
        long carry = (long)rem >> SRADIX;
        int digit1 = (int) (carry & MASK);
        if (digit1 > 0) {
        if(dividend.value.length < 2 ) {
            int[] newval = {dividend.value[0],digit1};
            dividend.value = newval;
        }
        else
            dividend.value[1] = digit1;
        }
        if(quot.scale > 0)
        return truncate(quot);
        else
        return quot;
    }
    //Next normalize the dividend and divisor, i.e. divisor[leftmostDigit] >= BASE/2
    //
    int vLeftmostDigit = divisor.value[divisor.value.length - 1];

    if(vLeftmostDigit >= (BASE)/2){
            int[] tvalue = new int[dividend.value.length + 1];
            System.arraycopy(dividend.value, 0, tvalue, 0, dividend.value.length);
            tvalue[tvalue.length - 1] = 0;
            dividend.value = tvalue;
            div (dividend, divisor, quot);
        } else {
            int[] tvalue = new int[dividend.value.length + 1];
            System.arraycopy(dividend.value,0,tvalue,0,dividend.value.length);
            int d = (BASE)/(vLeftmostDigit + 1);
            dividend.value = mul0(tvalue,d);
            divisor.value = mul0(divisor.value,d);
            div (dividend, divisor, quot);
            div0(dividend.value,dividend.value,d);
        }

    //quot._setScale(scale);

    if(quot.scale > 0) {
        quot = truncate(quot);

        }

    return quot;

    }
    /**
     * Returns the arithmentic remainder calculated by dividing this
     * Bignum object by the argument.  No rounding is performed.
     *
     * @param  x The divisor as a Bignum.
     * @return The remainder as a Bignum.
     */
    public Bignum remainder(Bignum x) {
    if (x.compareAbs(Bignum.ZERO) == 0) {
        throw new ArithmeticException("Division by zero");
    }

    if(this.lessThan(x))
        return new Bignum(this);

       Bignum dividend = new Bignum(this);
       Bignum divisor = new Bignum(x);
    _intDivide(divisor,dividend,scale);
    return dividend;
    }




    /**
     * Square root
     * Returns the square root of this Bignum.
     * @return the square root of this Bignum.
     */
    public Bignum sqrt() {

    // Uses a Newtonian convergence algorithm.
        Bignum g = new Bignum(this,scale + 1);
        Bignum temp = new Bignum(0);
        div0(g.value,g.value,2);
        Bignum eps = createFromScaled(5,g.scale);
        Bignum diff = (g.multiply(g)).subtract(this);
        while(diff.compareAbs(eps) > 0){
            temp.value = mul0(g.value,2);
            temp.scale = g.scale;
            temp.negative = g.negative;

            temp = diff.divide(temp);
            g = g.subtract(temp);
            temp = g.multiply(g);

            diff = temp.subtract(this);
        }
        return g;
    }

    /**
     * Returns a new Bignum whose value is calculated by
     * raising this Bignum to the power of the given exponent.
     * @param e An integer value cotaining the exponent to be used.
     * @return this Bignum raised to the power given by the exponent argument.
     */

    public Bignum pow(int e) {
    //A binary power algorithm is used.
    if(e==0) return new Bignum(1.0,scale);
    Bignum ans = new Bignum(this);
    int[] t = {1};
    while(e > 1) {
        if((e & 0x0001)==0x0001){
        t = mul0(t, ans.value);
        }
        ans.value = mul0(ans.value,ans.value);
        e >>=1;
    }
    ans.value = mul0(ans.value,t);
    ans.dropLeadingZeroes();
    return ans;
    }

    /**
     * Returns true if the arithmetic value of the Bignum equals the
     * argument.
     *
     * @param  obj The object to compare.
     * @return The boolean result of the comparison.
     */
    public  boolean equals(Object obj) {
        Bignum x = (Bignum) obj;
        if (compare(x) == 0) {
            return (true);
        }
        return (false);
    }

    /**
     * Returns true if the arithmetic value of the Bignum is less
     * than the argument.
     *
     * @param  x The object to compare.
     * @return The boolean result of the comparison.
     */
    public boolean lessThan(Bignum x) {
    if (compare(x) == -1) {
        return (true);
    }
    return (false);
    }

    /**
     * Returns true if the arithmetic value of the Bignum is less
     * than or equals the argument.
     *
     * @param  x The object to compare.
     * @return The boolean result of the comparison.
     */
    public  boolean lessThanOrEquals(Bignum x) {
    if (compare(x) != 1) {
        return (true);
    }
    return (false);
    }

    /**
     * Returns true if the arithmetic value of the Bignum is greater
     * than the argument.
     *
     * @param  x The object to compare.
     * @return The boolean result of the comparison.
     */
    public  boolean greaterThan(Bignum x) {
    if (compare(x) == 1) {
        return (true);
    }
    return (false);
    }

    /**
     * Returns true if the arithmetic value of the Bignum is greater
     * than or equals the argument.
     *
     * @param  x The object to compare.
     * @return The boolean result of the comparison.
     */
    public  boolean greaterThanOrEquals(Bignum x) {
    if (compare(x) != -1) {
        return (true);
    }
    return (false);
    }

    /**
     * Returns an integer hashcode for the Bignum.
     *
     * @return The hashcode as an integer.
     */
    public int hashCode() {
        int hash = 0;
        for(int i = 0; i < value.length; i++) {
            try {
                hash += value[i];
            }catch(Exception ex){
                hash = 0;
            }

        }
        return hash;
    }

    /**
     * Returns a Bignum copied from the current object with the scale
     * set as specified by the argument.  Note that changing the scale
     * to a smaller value may result in rounding.
     *
     * @param  scale the character to be converted
     * @return A Bignum with the adjusted scale.
     * @see Bignum#setRoundingOption
     */
    public Bignum setScale(int scale) {
        verifyScale(scale);
        Bignum x = new Bignum(this,scale);
        return (x);
    }
    //------------------------------Bit Operations------------------------
    /**
     *Returns the number of significant bits in the Bignum.
     *@return an integer containing the number of the most significant bit
     * of this Bignum.
     */
    public int significantBits() {
    int i;
    for(i = value.length - 1; i >= 0 && value[i] == 0;--i);
    if(i < 0)
        return 0;
    int val = value[i];
    int l = i;
    i = 0;
    while(val !=0){
        val >>>=1;
        ++i;
    }

    l = l  * SRADIX;
    return l + i;
    }
    /**
     * Returns a new Bignum whose value is calculated by shifting this
     * Bignum to the left by the number of bits given in shiftBits
     *
     * @param shiftBits the number of bits to shift.
     * @return A new Bignum whose value is this Bignum / 2^shiftBits
     */
    public  Bignum shiftRight(int shiftBits){
    if(shiftBits < 0)
        throw new IllegalArgumentException("Number of bits to shift may not be negative");

    int nw = shiftBits / SRADIX;
    shiftBits %= SRADIX;
    int[] r = new int[value.length - nw];
    System.arraycopy(value,nw,r,0,value.length - nw);
    int i;
    int carry = 0;
    for (i=r.length - 1; i>=0; --i) {
        int val = r[i];
        r[i] = (val>>>shiftBits) | carry;
        carry = (int)((val<<(SRADIX-shiftBits)) & MASK);
    }
    Bignum result = new Bignum(r);
    result.dropLeadingZeroes();
    return result;

    }
    /**
     *  Returns a new Bignum calculated by shifting this Bignum to the
     *  left by the number of bits given in shiftBits.
     *
     *  @param shiftBits The number of bits to shift
     *  @return A new Bignum whose value is this Bignum * 2^shiftBits
     */
    public Bignum shiftLeft(int shiftBits){
    if(shiftBits < 0)
        throw new IllegalArgumentException("Number of bits to shift may not be negative");
    int nw = shiftBits / SRADIX;
    shiftBits %= SRADIX;
    int[] r = new int[value.length + nw + 1];

    System.arraycopy(value, 0, r, nw, value.length);

    int i;
    int carry = 0;
    for (i=0; i< r.length - 1; ++i) {
        int val = r[i];
        r[i] = (int)((val<<shiftBits) | carry & MASK);
        carry = val >>>(SRADIX - shiftBits);
    }
    if(carry != 0)
        r[r.length -1] = carry;

    Bignum result = new Bignum(r);
    result.dropLeadingZeroes();
    return result;
    }

    //------------------------------Modular Arithmetic----------------------
    /**
     * Returns the modular multiplicative inverse of this Bignum
     * @param mod the modulus to be used
     * @return the modular multiplicative inverse of this Bignum using "mod" as
     * the modulus
     */
    public Bignum modInverse(Bignum mod) {
    Bignum i = new Bignum(mod);
    Bignum h = new Bignum(this);
    Bignum v = new Bignum(ZERO);
    Bignum d = new Bignum(1);
    while(h.greaterThan(ZERO)) {
        Bignum tt[] = i.integerDivide(h);
        Bignum t = tt[0];
        Bignum x = h;
        h = i.subtract(t.multiply(x));
        i = x;
        x = d;
        d = v.subtract(t.multiply(x));
        v = x;

    }
    if(!v.negative)
        return v.remainder(mod);
    Bignum m = (v.remainder(mod)).multiply(mod);
    return(v.subtract(m));


    }

    /**
     * Modular exponentiation. Calculates a new Bignum
     * @param exponent the exponent to be used
     * @param mod the modulus to be used
     * @return a new Bignum whose values is this^exponent mod "mod".
     */

    public Bignum modExp (Bignum exponent, Bignum mod){
    int ipr = exponent.significantBits() - 1;
    int ibit = 1 << (ipr % SRADIX);
    ipr = ipr / SRADIX;
    int[] t = new int[value.length  + 1];
    Bignum rslt = new Bignum(ONE);
    while (ipr >= 0) {

        rslt.value  = mul0(rslt.value,rslt.value,t);
        if(rslt.value != t)
        t = rslt.value;
        rslt = rslt.remainder(mod);
        if ((exponent.value[ipr] & ibit) != 0) {
                for(int i = 0; i < t.length;i++) t[i] = 0;
        rslt.value = mul0(rslt.value,this.value,t);
        if(rslt.value != t)
            t = rslt.value;
        rslt = rslt.remainder(mod);
        }
        ibit >>>= 1;
        if (ibit==0) {
        --ipr;
        ibit = 1<<(SRADIX-1);
        }
        for(int i = 0; i < t.length;i++) t[i] = 0;
    }
    return rslt;
    }
    //----------------------Prime Number Testing----------------------------
    private static int[] smallPrimes = new int[51];

    static {
        smallPrimes[0] = 2;
        smallPrimes[1] = 3;
        smallPrimes[2] = 5;
        smallPrimes[3] = 7;
        smallPrimes[4] = 11;
        smallPrimes[5] = 13;
        smallPrimes[6] = 17;
        smallPrimes[7] = 19;
        smallPrimes[8] = 23;
        smallPrimes[9] = 29;
        smallPrimes[10] =31;
        smallPrimes[11] =37;
        smallPrimes[12] =41;
        smallPrimes[13] =43;
        smallPrimes[14] =47;
        smallPrimes[15] =53;
        smallPrimes[16] =59;
        smallPrimes[17] =61;
        smallPrimes[18] =67;
        smallPrimes[19] =71;
        smallPrimes[20] =73;
        smallPrimes[21] =79;
        smallPrimes[22] =83;
        smallPrimes[23] =89;
        smallPrimes[24] =97;
        smallPrimes[25] =101;
        smallPrimes[26] =103;
        smallPrimes[27] =107;
        smallPrimes[28] =109;
        smallPrimes[29] =113;
        smallPrimes[30] =127;
        smallPrimes[31] =131;
        smallPrimes[32] =137;
        smallPrimes[33] =139;
        smallPrimes[34] =149;
        smallPrimes[35] =151;
        smallPrimes[36] =157;
        smallPrimes[37] =163;
        smallPrimes[38] =167;
        smallPrimes[39] =173;
        smallPrimes[40] =179;
        smallPrimes[41] =181;
        smallPrimes[42] =191;
        smallPrimes[43] =193;
        smallPrimes[44] =197;
        smallPrimes[45] =199;
        smallPrimes[46] =211;
        smallPrimes[47] =223;
        smallPrimes[48] =227;
        smallPrimes[49] =229;
        smallPrimes[50] =233;
    }

    /**
     * This method tests for primality, first by attempting to divide
     * by a few small primes, then by using the Rabin probabilistic
     * primality test 50 times.  The probability of failing this test
     * is less than 1 / (4^n).
     *
     * @return a boolean, true if this Bignum is probably prime, false
     * otherwise.
     */
    public boolean isProbablePrime() {
    Bignum n1, n2;
       // test to see if this is divisible by a small prime.
       if((value[0] & 0x00000001) != 0x00000001) //make sure its odd
           return equals( TWO);
    for (int i = 1; i < 11 ; i++) {
        int prime = smallPrimes[i];
        if (quickMod(prime) == 0)
        if(value[0] != prime)
            return false;
    }
    // use a probabilistic test on this
    return isProbablePrime0(50);
    }
    private  int quickMod(int d) {
        int rem = 0;
        int i = value.length;
    while (i-- > 0) {
        long temp = (long) (((value[i]) <<32) | rem);
        rem = (int)(temp % d);
    }
    if(negative && rem !=0)
        rem = d - rem;
    return rem;

    }

    private boolean isProbablePrime0(int n) {
    Bignum wm1 = subtract(ONE);
    //calculate a = largest power of 2 that divides wm1
    int a = 0;
    int l = 0;
    for(int i = 0;i < wm1.value.length && wm1.value[i] == 0;l++,i++);
    int val = wm1.value[l];
    while((val & 1) ==0) {
            a++;
        val >>>= 1;
        }
    a = l * SRADIX + a;
    if(a == 0 ) //wm1 is odd so w must be even
        return false;

    int j;
    Bignum m = wm1.shiftRight(a);

    Bignum  z = new Bignum(3);
    //System.out.println(m.toString(16));

    z = z.modExp(m,this);
    //System.out.println(z.toString(16));
    if (z.equals(ONE) || z.equals(wm1))
        return true;
        for (j=1; j<a; j++)
        {
        z = z.multiply(z);
        z = z.remainder(this);
        if (z.equals(wm1))
            return true;
        if (z.equals(ONE))
            return false;
        }

    int s = wm1.significantBits();

    for(int i = 0; i < n; i++) {
            //System.out.println("Round: " + i);
        Bignum b = random(s,new Random());
        if(b.greaterThan(wm1))
        b = b.remainder(wm1);
        z = b.modExp(m, this);
        if(z.equals(ONE) || z.equals(wm1))
        continue;
        for(j=1;j<a;j++){
        z = z.modExp(TWO,this);
        if(z.equals(wm1))
            break;
        if(z.equals(ONE))
            return false;
        }
        if(j == a)
        return false;

    }

    return true;
    }
    //---------------------------Miscellaneous Operations------------------
    // public constants
    public final static  int   ROUND_STATISTICAL    = -1;
    public final static  int   NO_ROUNDING   = 9;
    public final static  int   ROUND_ABOVE_5 = 5 ;
    public final static  int   ROUND_ABOVE_4 = 4;
    public final static  int   ROUND_ALWAYS  = 0;

    //-----------------------------Implementation---------------------------
    /**
     * The maximum scale supported.
     *
     */
    private static final int MAXSCALE = 0x3fffffff;          //Maximum scale.



    private int value[];
    private int scale;
    private boolean negative;
    //----------------------------------------------------------------------
    /**
     * The roundingValue is a digit between -1 and 9 that determines
     * rounding behavior.
     */
    private static int roundingValue = 4;

    /**
     * To avoid problems with negative carries,etc, we user a base 2^30;
     */
    static final int SRADIX = 30;
    private static final int BASE = 1<<SRADIX;

    // Useful masks
    private static final long MASK = 0x3fffffffL;

    public static final Bignum ZERO = new Bignum("0,0");
    public static final Bignum ONE  = new Bignum(1,0);
    public static final Bignum TWO = new Bignum(2,0);

    //----------------------------------------------------------------------

    /**
     * Throws IllegalArgument exception is the scale is negative or
     * greater then MAXSCALE (0x3fffffffL).
     *
     */
    static private void verifyScale(int scale) {

       if (scale < 0) {
           throw new IllegalArgumentException("Scale is negative");
       }
       if (scale > MAXSCALE) {
           throw new IllegalArgumentException("Scale greater than maximum scale");
       }
    }

    /**
     * Compare the value of this Bignum to the value of the argument.
     * Returns 1 if this is greater than the argument,
     *        -1 if this is less than the argument,
     *         0 if this is equal to the argument.
     * @param  B  A Bignum to compare.
     * @return      1 if this > B,0 if this = B,-1 if this < B.
     */
    public int compare(Bignum B) {
    if (negative == false && B.negative == false) {
        return (compareAbs(B));
    }
    if (negative == true && B.negative == false) {
        return (-1);
    }
    if (negative == false && B.negative == true) {
        return (1);
    }
    int r = compareAbs(B);
    if (r != 0) {
        r *= -1;
    }
    return (r);
    }

    /**
     * Private function used for arithmetic comparisons.  Performs an
     * absolute comparison.
     *
     * @param  A A Bignum to compare.
     * @return 1 if this > A,0 if this = A,-1 if this < A.
     */
    private int compareAbs(Bignum A) {
    Bignum B;
    if(A.scale == scale)
        B = A;
    else
        B = new Bignum(A,scale);

    //look for the first significant digit
    int sigA,sigB;
    for (sigB = B.value.length  - 1;sigB > 0 && B.value[sigB] == 0 ; sigB-- );
    sigB++;
    for (sigA = value.length - 1 ;sigA > 0 && value[sigA] == 0 ; sigA--);
    sigA++;
    if (sigA > sigB)
        return (1);
    if (sigB > sigA)
        return (-1);
    if (sigA == 0 && sigB == 0)
        return (0);
    while (--sigA >= 0 )  {
        if (value[sigA] > B.value[sigA]) {
        return (1);
        }
        if (value[sigA] < B.value[sigA]) {
        return (-1);
        }
    }
    return (0);
    }

    /**
     * Private function used to initialize a Bignum using a string.
     * The radix is assumed to be 10
     * @param  s    A string containing the intended value of the Bignum.
     * @param  scale    The number of digits to the right of the decimal point.
     *                  Should be -1 if the scale is to be determined by the contents
     *                  of the argument string s.
     */
    private void init(String s, int iscale) {
    boolean scaleGiven = true;
    scale = 0;
    int mantVal = 0;
    if (iscale < 0) {
        scaleGiven = false;
    }
    int inScale = 0; //Scale computed from decimal point in s


    negative = false;         //Default to positive
    if (scaleGiven) {
        value = new int[(s.length() + iscale)/3 + 1];
    } else {
        value = new int[s.length()/5 + 1];
    }
    int[] t1 = new int[1];
    t1[0] = 10;
    //int [] t1;
    boolean mant = false;
    boolean gotFirstDigit = false;
    boolean gotFirstExpDigit = false;

    for (int i = 0;i < s.length() ;i++ ) {
        char c = s.charAt(i);
        if (c >= '0' && c <= '9') {
        if (inScale != 0) {
            if(!mant)
            inScale++;
        }
        int a = Character.digit(c,10);
        if(mant ) {
            mantVal = mantVal * 10 + a;
            gotFirstExpDigit = true;
        }
        else {
            t1 = mulAndAdd(value,10,a);
            if(t1 != null)
            value = t1;
            gotFirstDigit = true;
        }
        continue;
        }
        if (c == '-') {
        if(mant ){
            if(!gotFirstExpDigit)
                mantVal = -mantVal;
        }
        else{
            if(!gotFirstDigit)
                negative = true;
        }
        continue;
        }
        if (c == '.' && inScale == 0) {
        inScale = 1;
        }
        if (c== 'E' || c =='e')
        mant = true;
    }//for
    if(mant) {
        if(inScale != 0)
        scale = inScale - 1;
        else
        scale = 0;
        if(mantVal < 0) {
        mantVal *= -1;
        divide((new Bignum(10,0)).pow(mantVal));
        }
        else
        value = mul0(value,(new Bignum(10,0)).pow(mantVal).value);
        if(scaleGiven)
        _setScale(iscale);
        return;

    }
    if (inScale != 0) {
        //did we find a decimal point in the string
        inScale--;
        scale = inScale;
        //if so, use it
        if (scaleGiven) {
        if (scale != iscale)    {
            //the number of decimal places in string exceeds request
            _setScale(iscale);
        }

        }
    } else {
        // there was no decimal point in the string
        scale = 0;
        if (scaleGiven) {
        _setScale(iscale);
        }
    }
    }

    /**
     * Set the value of the Bignum to zeroes.  The precision and
     * scale are retained.
     */
    private void zero() {
        negative = false;
        for (int i = 0; i < value.length; i++) {
            value[i] = 0;
        }
    }

    /**
     * Remove leading zeroes from the value of the Bignum. Zeroes to
     * the right of the decimal point are retained.
     *
     * <P>The precision is changed accordingly. One zero is retained
     * if all digits are zero and the scale is zero.
     */
    private void dropLeadingZeroes() {
    int i;
    for(i = value.length -1;i >= 0 && value[i] == 0;i--);
    if(i < 0) i = 0;
    if(++i >= value.length ) return;
    int[] nval = new int[i];
    System.arraycopy(value,0,nval,0,i);
    value = nval;
    }
    /**
     *Returns a new Bignum whose value equals the
     *integer part of the input argument. The fractional part, if any,
     *is dropped.
     *@param Bignum The input value to truncate
     *@returns A new Bignum equal to the integer value of the argument
     */
    public static Bignum truncate(Bignum in) {
    if(in.scale == 0)
        return new Bignum(in);
        int scaleFactor = in.scale  - 1;
        int[] tval = new int[1];
        tval[0] = 0;

    int m1 = 9; //
    int m4 = 1000000000;
    int x = scaleFactor;
    for(;x >= m1;x -= m1 )
        tval = mul0(tval,m4);
    if(x > 0 )
        tval = mul0(tval,pow(10,x));
    tval = add0(in.value,tval);
    x = scaleFactor + 1;
    for(;x >= m1;x -= m1)
        div0(tval,tval,m4);

    if(x > 0)
        div0(tval,tval,pow(10,x));
    Bignum out = new Bignum(tval);
    out.scale = 0;
    out.negative = in.negative;
    return out;

    }

    /**
     * Set the number of the digits to the right of the decimal point.
     * The precision and value of the Bignum will be adjusted
     * accordingly.  Note that changing the scale to a smaller value
     * may result in rounding the value.
     *
     * @param  scale the character to be converted
     * @see Bignum#setRoundingOption
     */
    private void _setScale(int iscale) {
        verifyScale(iscale);
        if (iscale == scale) {
            return;
        }
        if(iscale > scale){
        for(int i = iscale - scale;i > 0;--i)
        value = mul0(value,10);
            scale = iscale;
            return;
        }
        int tempRoundingValue = roundingValue;
        //to round to the nearest even, first truncate.
        //Later, check to see if it the result of the truncation
        //is odd. If it is add 1;
        if(roundingValue == ROUND_STATISTICAL)
            tempRoundingValue = 9;
        //iscale < scale
        int scaleFactor = (scale - iscale) - 1;
        int[] tval = new int[1];
        tval[0] = 9 - tempRoundingValue;

    int m1 = 9; //this is approx log10 of BASE
    int m4 = 1000000000;
    int x = scaleFactor;
    for(;x >= m1;x -= m1 )
        tval = mul0(tval,m4);
    if(x > 0 )
        tval = mul0(tval,pow(10,x));
    value = add0(value,tval);
    x = scaleFactor + 1;
    for(;x >= m1;x -= m1)
        div0(value,value,m4);

    if(x > 0)
        div0(value,value,pow(10,x));
    if(roundingValue == ROUND_STATISTICAL) {
        //Check for an odd result
        if((value[0] & 0x00000001) == 0x00000001)
            value[0] += 1; //and add 1 it was odd

    }
    scale = iscale;
    }
    //---------------------------------------------------------------------
    /**
     * Algorithmic multiplication of two positive integers represented as
     * 32-bit integers. Knuth Algorithm M.
     *
     * u is required to be longer or equal to v.
     *
     */
    private static int[] mul0(int[] u, int[] v) {
    int n = u.length - 1;
    int m = v.length - 1;
    long k = 0;

    int[] w = new int[u.length + v.length];
    for (int j = 0; j <= n; j++) {
        k = 0;
        int q = j;
        for (int i = 0; i <= m; i++) {
            //
            long uv = u[j];
            long t = uv * v[i] + w[q] + k;
            w[(q++)] = (int)(t & MASK);
            k = t >> SRADIX;
        }
        for(;k != 0;) {
            long uv = w[q] + k ;
            w[q++] = (int) (uv & MASK);
            k = uv >> SRADIX;
        }
        //

    }
    if(w[w.length -1] != 0)
        return w;

    int ul = w.length - 1;
    for(;ul > 0 && w[ul] == 0;ul--);
    ul++;
    int[] w1 = new int[ul];
    System.arraycopy(w,0,w1,0,w1.length);
        return w1;
    }

    private static int[] mul0(int[] u, int v) {
    int n = u.length - 1;
    long k = 0;
    long x = v & MASK;
    int[] w = new int[u.length];
    if (x != 0) {
        for (int i = 0; i <= n; i++) {
            long uv = (u[i] & MASK) * x + k;
            w[i] = (int)(uv & MASK);
            k = uv >> SRADIX;
        }
        if(k != 0){
            int[] ww = new int[w.length + 1];
            System.arraycopy(w,0,ww,0,w.length);
            ww[ww.length - 1] = (int) k;
            w = ww;
        }
    }
    return w;
    }


    //------------------------------------------------------------------------
    /**
     *  Quick add of two Bignum array values
     *
     */
    private static int[] add0(int[] u, int[] v) {

    int j=0;
    int ul = u.length - 1;
    for(;ul > 0 && u[ul] == 0;ul--);

    int vl = v.length - 1;
    for(;vl > 0 && v[vl] == 0;vl--);

    ul++;vl++;

    if(ul < vl){
        int[] temp = u;
        u = v;
        v = temp;
        int temp2 = ul;
        ul = vl;
        vl = temp2;
    }
    int[] w = new int[ul + 1];

    long carry = 0;
    long temp;

    for (j = 0; j < vl ; ++j) {
        temp = u[j] + v[j] + carry;
        carry = temp >> SRADIX;
        w[j] = (int) (temp & MASK);
    }
    for (; carry != 0 && j < ul; ++j) {
        temp = u[j] + carry;
        w[j] =  (int)(temp & MASK);
        carry = temp >> SRADIX;
    }
    if(carry == 0 && j < ul) {
        for(;j < ul;++j) w[j] = u[j];
    }
    else{
        w[j] = (int) (carry & MASK);
    }
    return w;
    }
    //-------------------------------------------------------------------
    /**
     * Internal routine to quickly add an integer value to a Bignum value.
     *
     */
    private static int[] add0(int[] u, int v) {
    int j=0;
    int ul = u.length - 1;
    for(;ul > 0 && u[ul] == 0;ul--);

    int[] w = new int[ul++ + 1];
    long carry = 0;

    long temp = ((long)u[j] & MASK) + ((long)v & MASK);
    carry = temp >> SRADIX;
    w[j] = (int)(temp & MASK);
    for (++j; carry != 0 && j < ul; ++j) {
        temp = u[j] + carry;
        w[j] = (int)  (temp & MASK);
        carry = temp >> SRADIX;
    }
    if(carry == 0 && j < ul) {
        for(;j < ul;++j) {w[j] = u[j];}
    }
    return w;
    }
    //---------------------------------------------------------------------
    /*
     * Subtraction of two positive integers represented as 32-bit
     * integers. See Knuth Algorithm S.
     *
     * This operation is not commutative, and u must be longer or equal
     * in length to v.
     *
     * See add0 for details on representation and implementation.
     */
    private static int[] sub0(int[] u, int[] v) {

    boolean borrow = false;

    int ul = u.length - 1;
    for(;ul > 0 && u[ul] == 0;ul--);

    int vl = v.length - 1;
    for(;vl > 0 && v[vl] == 0;vl--);

    int[] w = new int[ul + 1];
    int wj;
    int j = 0;
    for (; j <= vl;) {
        wj = u[j] - v[j] + (borrow?-1:0);
        w[j++] = (int)(wj & MASK);
        borrow = wj < 0;
    }
    if(borrow)
        {
            for (; j <=  ul; ) {
                w[j] = (u[j] - (borrow?1:0));
                if(w[j++] >= 0) break;
            }
        }
    for(;j <= ul;j++)
        w[j] = u[j];
    return w;
    }

    //-----------------------------------------------------------------
    private static int div0(int[] quotient,int[] dividend,int divisor){
    long carry = 0;
    for(int i = dividend.length - 1;i >= 0;--i){
        long x = (dividend[i] & MASK) + (carry << SRADIX);
        quotient[i] = (int) (x/((long)divisor & MASK));
        carry = x % (long)divisor;
    }
    return (int)carry;
    }


    private static void div(Bignum dvdnd, Bignum div, Bignum quot) {
       int divlen = div.value.length - 1;

       int d1 = div.value[divlen];    //divisor must be at least 2 digits
       int d2 = div.value[divlen - 1];
       int[] dndVal = dvdnd.value;
       int[] divVal = div.value;
       int qx = quot.value.length - 1;
       long q;
       for (int j = dvdnd.value.length - 1; j>divlen; j--) {
           int dd0  = dndVal[j];
           int dd1 = dndVal[j-1];
           int dd2 = dndVal[j-2];
        long temp1 = (((long)dd0)<<SRADIX) + (long)dd1;
           if (dd0 == d1) {
           q = (BASE)-1;
           } else {
           q = temp1 / (long) d1;
           }
           for (;;) {
           long  p1 = d2 * q;
        long  p2 = temp1 - (d1 * q);
        p2= (p2<<SRADIX) + dd2;
        if(p1 > p2)
               q--;
        else
               break;
           }
        if(q == 0){
                   quot.value[qx--] = 0;
        continue;
        }
           int k = j-divlen-1;
           long carry = 0;
           for (int dk = 0; dk <= divlen; dk++) {
           long x1 = divVal[dk] * q + carry;
           int x2 = dndVal[k] - (int)(x1 & MASK);
           if (x2<0) {
               dndVal[k++] = x2 + (BASE);
               carry = (x1>>SRADIX) + 1;
           } else {
               dndVal[k++] = x2;
               carry = (x1>>SRADIX);
           }//elseif
           }//for
           if (carry != 0){
           int temp = dndVal[k] - (int)carry;
           if(temp >= 0)
               dndVal[k] = temp;
           else{
               dndVal[k] = temp + (BASE);
               //the guess was too big! back it off by 1
               carry = 0;
               k = j - divlen -1;
            q--;
               for (int dk = 0; dk <= divlen; dk++) {
               long nv = divVal[dk] + dndVal[k] + carry;
               dndVal[k++] = (int)(nv & MASK);
               carry = nv>>SRADIX;
               }//for
               if (carry == 1)
               dndVal[k] =(int) ((dndVal[k]+1) & MASK);
           }//else
           }//if
           quot.value[qx--] = (int)q;

    }//for

    }
    /**
     * Private power integer function used in division
     * and scaling.
     * @arg b the integer base value.
     * @arg e the exponent to be used
     *@return an integer value calculated as b^e;
     */
    private static int pow(int b,int e){
    if(e == 0) return 1;
    if(e == 1) return b;
    int ans = b;
    int temp = 1;
    while(e != 1){
        if((e & 0x0001)==0x0001)
               temp *= ans;
        ans *= ans;
        e >>=1;
    }
    return ans * temp;
    }
    /**
     *Private routine that multiplies the val by integer m
     * and adds the integer a.
     *@Returns a new array, if a new one had to be allocated,
     *otherwise, returns null;
     */
    private static int[] mulAndAdd(int val[],int m, int a){
    int n = val.length - 1;
    long k = a & MASK;
    long x = m & MASK;
    int[] w = val;
    if (x!= 0) {
        for (int i = 0; i <= n; i++) {
            long uv = (val[i] & MASK) * x + k;
            w[i] = (int)(uv & MASK);
            k = uv >> SRADIX;
        }
        if(k != 0){
            int[] ww = new int[w.length + 1];
            System.arraycopy(w,0,ww,0,w.length);
            ww[ww.length - 1] = (int) (k & MASK);
            w = ww;
        }
    }
    return w==val?null:w;
    }

    /**
     * Private constructor that creates a Bignum from an
     * array of integers. This is used internally to optimize
     * certain operations.
     * @param valueArray an array of integers that are presumed to hold the
     * value of the new Bignum.
     */
    private Bignum(int[] valueArray){
    value = valueArray;
    negative = false;
    }


    //---------------------------------------------------------------------
    /**
     * Algorithmic multiplication of two positive integers represented as
     * 32-bit integers. Knuth Algorithm M.
     *
     * u is required to be longer or equal to v.
     *
     */
    private static int[] mul0(int[] u, int[] v, int[] x) {
    int[] w = x;
       int n = u.length - 1;
       while(u[n] == 0) n--;
       int m = v.length - 1;
       while(v[m] == 0) m--;
       if(m < 0 || n < 0) {
           if(w == null) w = new int[1];
           w[0] = 0;
           return w;
       }
       long k = 0,uv,t;
       int q =0, maxpos = 0;
    if (w == null || w.length < (n + m + 3))
           w = new int[n + m + 3];
       for (int j = 0; j <= n; j++) {
           k = 0;
           q = j;
           for (int i = 0; i <= m; i++) {
           //
           uv = u[j];
           t = uv * v[i] + w[q] + k;
           w[(q++)] = (int)(t & MASK);
           k = t >> SRADIX;
           }
           for(;k != 0;) {
           uv = w[q] + k ;
           w[q++] = (int) (uv & MASK);
           k = uv >> SRADIX;
           }
           if(q > maxpos)
               maxpos = q;
           //

       }
    return w;

    }


}//Bignum