floatingdecimal.java

来自「《移动Agent技术》一书的所有章节源代码。」· Java 代码 · 共 1,376 行 · 第 1/3 页

	 *	M      = (1/2^nSignificantBits) * 2^nTinyBits * 10^max( 0, -decExp )
	 * i.e. M is (1/2) of the ULP of d, scaled like B.
	 * When we iterate through dividing B/S and picking off the
	 * quotient bits, we will know when to stop when the remainder
	 * is <= M.
	 *
	 * We keep track of powers of 2 and powers of 5.
	 */

	/*
	 * Estimate decimal exponent. (If it is small-ish,
	 * we could double-check.)
	 *
	 * First, scale the mantissa bits such that 1 <= d2 < 2.
	 * We are then going to estimate
	 *	    log10(d2) ~=~  (d2-1.5)/1.5 + log(1.5) 
	 * and so we can estimate 
	 *      log10(d) ~=~ log10(d2) + binExp * log10(2)
	 * take the floor and call it decExp.
	 * FIXME -- use more precise constants here. It costs no more.
	 */
	double d2 = Double.longBitsToDouble( 
	    expOne | ( fractBits &~ fractHOB ) );
	decExp = (int)Math.floor(
	    (d2-1.5D)*0.289529654D + 0.176091259 + (double)binExp * 0.301029995663981 );
	int B2, B5; // powers of 2 and powers of 5, respectively, in B
	int S2, S5; // powers of 2 and powers of 5, respectively, in S
	int M2, M5; // powers of 2 and powers of 5, respectively, in M
	int Bbits; // binary digits needed to represent B, approx.
	int tenSbits; // binary digits needed to represent 10*S, approx.
	FDBigInt Sval, Bval, Mval;

	B5 = Math.max( 0, -decExp );
	B2 = B5 + nTinyBits + binExp;

	S5 = Math.max( 0, decExp );
	S2 = S5 + nTinyBits;

	M5 = B5;
	M2 = B2 - nSignificantBits;

	/*
	 * the long integer fractBits contains the (nFractBits) interesting
	 * bits from the mantissa of d ( hidden 1 added if necessary) followed
	 * by (expShift+1-nFractBits) zeros. In the interest of compactness,
	 * I will shift out those zeros before turning fractBits into a
	 * FDBigInt. The resulting whole number will be 
	 * 	d * 2^(nFractBits-1-binExp).
	 */
	fractBits >>>= (expShift+1-nFractBits);
	B2 -= nFractBits-1;
	int common2factor = Math.min( B2, S2 );
	B2 -= common2factor;
	S2 -= common2factor;
	M2 -= common2factor;

	/*
	 * HACK!! For exact powers of two, the next smallest number
	 * is only half as far away as we think (because the meaning of
	 * ULP changes at power-of-two bounds) for this reason, we
	 * hack M2. Hope this works.
	 */
	if ( nFractBits == 1 )
	    M2 -= 1;

	if ( M2 < 0 ){
	    // oops. 
	    // since we cannot scale M down far enough,
	    // we must scale the other values up.
	    B2 -= M2;
	    S2 -= M2;
	    M2 =  0;
	}
	/*
	 * Construct, Scale, iterate.
	 * Some day, we'll write a stopping test that takes
	 * account of the assymetry of the spacing of floating-point
	 * numbers below perfect powers of 2
	 * 26 Sept 96 is not that day.
	 * So we use a symmetric test.
	 */
	char digits[] = this.digits = new char[18];
	int  ndigit = 0;
	boolean low, high;
	long lowDigitDifference;
	int  q;

	/*
	 * Detect the special cases where all the numbers we are about
	 * to compute will fit in int or long integers.
	 * In these cases, we will avoid doing FDBigInt arithmetic.
	 * We use the same algorithms, except that we "normalize"
	 * our FDBigInts before iterating. This is to make division easier,
	 * as it makes our fist guess (quotient of high-order words)
	 * more accurate!
	 *
	 * Some day, we'll write a stopping test that takes
	 * account of the assymetry of the spacing of floating-point
	 * numbers below perfect powers of 2
	 * 26 Sept 96 is not that day.
	 * So we use a symmetric test.
	 */
	Bbits = nFractBits + B2 + (( B5 < n5bits.length )? n5bits[B5] : ( B5*3 ));
	tenSbits = S2+1 + (( (S5+1) < n5bits.length )? n5bits[(S5+1)] : ( (S5+1)*3 ));
	if ( Bbits < 64 && tenSbits < 64){
	    if ( Bbits < 32 && tenSbits < 32){
		// wa-hoo! They're all ints!
		int b = ((int)fractBits * small5pow[B5] ) << B2;
		int s = small5pow[S5] << S2;
		int m = small5pow[M5] << M2;
		int tens = s * 10;
		/*
		 * Unroll the first iteration. If our decExp estimate
		 * was too high, our first quotient will be zero. In this
		 * case, we discard it and decrement decExp.
		 */
		ndigit = 0;
		q = (int) ( b / s );
		b = 10 * ( b % s );
		m *= 10;
		low  = (b <  m );
		high = (b+m > tens );
		if ( q >= 10 ){
		    // bummer, dude
		    throw new RuntimeException( "Assertion botch: excessivly large digit "+q);
		} else if ( (q == 0) && ! high ){
		    // oops. Usually ignore leading zero.
		    decExp--;
		} else {
		    digits[ndigit++] = (char)('0' + q);
		}
		/*
		 * HACK! Java spec sez that we always have at least
		 * one digit after the . in either F- or E-form output.
		 * Thus we will need more than one digit if we're using
		 * E-form
		 */
		if ( decExp <= -3 || decExp >= 8 ){
		    high = low = false;
		}
		while( ! low && ! high ){
		    q = (int) ( b / s );
		    b = 10 * ( b % s );
		    m *= 10;
		    if ( q >= 10 ){
			// bummer, dude
			throw new RuntimeException( "Assertion botch: excessivly large digit "+q);
		    }
		    if ( m > 0L ){
			low  = (b <  m );
			high = (b+m > tens );
		    } else {
			// hack -- m might overflow!
			// in this case, it is certainly > b,
			// which won't
			// and b+m > tens, too, since that has overflowed
			// either!
			low = true;
			high = true;
		    }
		    digits[ndigit++] = (char)('0' + q);
		}
		lowDigitDifference = (b<<1) - tens;
	    } else {
		// still good! they're all longs!
		long b = (fractBits * long5pow[B5] ) << B2;
		long s = long5pow[S5] << S2;
		long m = long5pow[M5] << M2;
		long tens = s * 10L;
		/*
		 * Unroll the first iteration. If our decExp estimate
		 * was too high, our first quotient will be zero. In this
		 * case, we discard it and decrement decExp.
		 */
		ndigit = 0;
		q = (int) ( b / s );
		b = 10L * ( b % s );
		m *= 10L;
		low  = (b <  m );
		high = (b+m > tens );
		if ( q >= 10 ){
		    // bummer, dude
		    throw new RuntimeException( "Assertion botch: excessivly large digit "+q);
		} else if ( (q == 0) && ! high ){
		    // oops. Usually ignore leading zero.
		    decExp--;
		} else {
		    digits[ndigit++] = (char)('0' + q);
		}
		/*
		 * HACK! Java spec sez that we always have at least
		 * one digit after the . in either F- or E-form output.
		 * Thus we will need more than one digit if we're using
		 * E-form
		 */
		if ( decExp <= -3 || decExp >= 8 ){
		    high = low = false;
		}
		while( ! low && ! high ){
		    q = (int) ( b / s );
		    b = 10 * ( b % s );
		    m *= 10;
		    if ( q >= 10 ){
			// bummer, dude
			throw new RuntimeException( "Assertion botch: excessivly large digit "+q);
		    }
		    if ( m > 0L ){
			low  = (b <  m );
			high = (b+m > tens );
		    } else {
			// hack -- m might overflow!
			// in this case, it is certainly > b,
			// which won't
			// and b+m > tens, too, since that has overflowed
			// either!
			low = true;
			high = true;
		    }
		    digits[ndigit++] = (char)('0' + q);
		}
		lowDigitDifference = (b<<1) - tens;
	    }
	} else {
	    FDBigInt tenSval;
	    int  shiftBias;

	    /*
	     * We really must do FDBigInt arithmetic.
	     * Fist, construct our FDBigInt initial values.
	     */
	    Bval = new FDBigInt( fractBits  );
	    if ( B5 != 0 ){
		if ( B5 < small5pow.length ){
		    Bval = Bval.mult( small5pow[B5] );
		} else {
		    Bval = Bval.mult( big5pow( B5 ) );
		}
	    }
	    if ( B2 != 0 ){
		Bval.lshiftMe( B2 );
	    }
	    Sval = new FDBigInt( big5pow( S5 ) );
	    if ( S2 != 0 ){
		Sval.lshiftMe( S2 );
	    }
	    Mval = new FDBigInt( big5pow( M5 ) );
	    if ( M2 != 0 ){
		Mval.lshiftMe( M2 );
	    }


	    // normalize so that division works better
	    Bval.lshiftMe( shiftBias = Sval.normalizeMe() );
	    Mval.lshiftMe( shiftBias );
	    tenSval = Sval.mult( 10 );
	    /*
	     * Unroll the first iteration. If our decExp estimate
	     * was too high, our first quotient will be zero. In this
	     * case, we discard it and decrement decExp.
	     */
	    ndigit = 0;
	    q = Bval.quoRemIteration( Sval );
	    Mval = Mval.mult( 10 );
	    low  = (Bval.cmp( Mval ) < 0);
	    high = (Bval.add( Mval ).cmp( tenSval ) > 0 );
	    if ( q >= 10 ){
		// bummer, dude
		throw new RuntimeException( "Assertion botch: excessivly large digit "+q);
	    } else if ( (q == 0) && ! high ){
		// oops. Usually ignore leading zero.
		decExp--;
	    } else {
		digits[ndigit++] = (char)('0' + q);
	    }
	    /*
	     * HACK! Java spec sez that we always have at least
	     * one digit after the . in either F- or E-form output.
	     * Thus we will need more than one digit if we're using
	     * E-form
	     */
	    if ( decExp <= -3 || decExp >= 8 ){
		high = low = false;
	    }
	    while( ! low && ! high ){
		q = Bval.quoRemIteration( Sval );
		Mval = Mval.mult( 10 );
		if ( q >= 10 ){
		    // bummer, dude
		    throw new RuntimeException( "Assertion botch: excessivly large digit "+q);
		}
		low  = (Bval.cmp( Mval ) < 0);
		high = (Bval.add( Mval ).cmp( tenSval ) > 0 );
		digits[ndigit++] = (char)('0' + q);
	    }
	    if ( high && low ){
		Bval.lshiftMe(1);
		lowDigitDifference = Bval.cmp(tenSval);
	    } else
		lowDigitDifference = 0L; // this here only for flow analysis!
	}
	this.decExponent = decExp+1;
	this.digits = digits;
	this.nDigits = ndigit;
	/*
	 * Last digit gets rounded based on stopping condition.
	 */
	if ( high ){
	    if ( low ){
		if ( lowDigitDifference == 0L ){
		    // it's a tie!
		    // choose based on which digits we like.
		    if ( (digits[nDigits-1]&1) != 0 ) roundup();
		} else if ( lowDigitDifference > 0 ){
		    roundup();
		}
	    } else {
		roundup();
	    }
	}
    }

    public String
    toString(){
	// most brain-dead version
	StringBuffer result = new StringBuffer( nDigits+8 );
	if ( isNegative ){ result.append( '-' ); }
	if ( isExceptional ){
	    result.append( digits, 0, nDigits );
	} else {
	    result.append( "0.");
	    result.append( digits, 0, nDigits );
	    result.append('e');
	    result.append( decExponent );
	}
	return new String(result);
    }

    public String
    toJavaFormatString(){
	char result[] = new char[ nDigits + 10 ];
	int  i = 0;
	if ( isNegative ){ result[0] = '-'; i = 1; }
	if ( isExceptional ){
	    System.arraycopy( digits, 0, result, i, nDigits );
	    i += nDigits;
	} else {
	    if ( decExponent > 0 && decExponent < 8 ){
		// print digits.digits.
		int charLength = Math.min( nDigits, decExponent );
		System.arraycopy( digits, 0, result, i, charLength );
		i += charLength;
		if ( charLength < decExponent ){
		    charLength = decExponent-charLength;
		    System.arraycopy( zero, 0, result, i, charLength );
		    i += charLength;
		    result[i++] = '.';
		    result[i++] = '0';
		} else {
		    result[i++] = '.';
		    if ( charLength < nDigits ){
			int t = nDigits - charLength;
			System.arraycopy( digits, charLength, result, i, t );
			i += t;
		    } else{
			result[i++] = '0';
		    }
		}
	    } else if ( decExponent <=0 && decExponent > -3 ){
		result[i++] = '0';
		result[i++] = '.';
		if ( decExponent != 0 ){
		    System.arraycopy( zero, 0, result, i, -decExponent );
		    i -= decExponent;
		}
		System.arraycopy( digits, 0, result, i, nDigits );
		i += nDigits;
	    } else {
		result[i++] = digits[0];
		result[i++] = '.';
		if ( nDigits > 1 ){
		    System.arraycopy( digits, 1, result, i, nDigits-1 );
		    i += nDigits-1;
		} else {
		    result[i++] = '0';
		}
		result[i++] = 'E';
		int e;
		if ( decExponent <= 0 ){
		    result[i++] = '-';
		    e = -decExponent+1;
		} else {
		    e = decExponent-1;
		}
		// decExponent has 1, 2, or 3, digits
		if ( e <= 9 ) {
		    result[i++] = (char)( e+'0' );
		} else if ( e <= 99 ){
		    result[i++] = (char)( e/10 +'0' );
		    result[i++] = (char)( e%10 + '0' );
		} else {
		    result[i++] = (char)(e/100+'0');
		    e %= 100;
		    result[i++] = (char)(e/10+'0');
		    result[i++] = (char)( e%10 + '0' );
		}
	    }
	}
	return new String(result, 0, i);
    }

    private static final int small5pow[] = {
	1,
	5,
	5*5,
	5*5*5,
	5*5*5*5,
	5*5*5*5*5,
	5*5*5*5*5*5,
	5*5*5*5*5*5*5,
	5*5*5*5*5*5*5*5,
	5*5*5*5*5*5*5*5*5,
	5*5*5*5*5*5*5*5*5*5,
	5*5*5*5*5*5*5*5*5*5*5,
	5*5*5*5*5*5*5*5*5*5*5*5,
	5*5*5*5*5*5*5*5*5*5*5*5*5
    };

    private static final long long5pow[] = {
	1L,
	5L,
	5L*5,
	5L*5*5,
	5L*5*5*5,
	5L*5*5*5*5,
	5L*5*5*5*5*5,
	5L*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
	5L*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5,
    };

    // approximately ceil( log2( long5pow[i] ) )
    private static final int n5bits[] = {