floatingdecimal.java

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

	0,
	3,
	5,
	7,
	10,
	12,
	14,
	17,
	19,
	21,
	24,
	26,
	28,
	31,
	33,
	35,
	38,
	40,
	42,
	45,
	47,
	49,
	52,
	54,
	56,
	59,
	61,
    };

    private static final char infinity[] = { 'I', 'n', 'f', 'i', 'n', 'i', 't', 'y' };
    private static final char notANumber[] = { 'N', 'a', 'N' };
    private static final char zero[] = { '0', '0', '0', '0', '0', '0', '0', '0' };
}

/*
 * A really, really simple bigint package
 * tailored to the needs of floating base conversion.
 */
class FDBigInt {
    int	nWords; // number of words used
    int data[]; // value: data[0] is least significant

    private static boolean debugging = false;

    public static void setDebugging( boolean d ) { debugging = d; }

    public FDBigInt( int v ){
	nWords = 1;
	data = new int[1];
	data[0] = v;
    }

    public FDBigInt( long v ){
	data = new int[2];
	data[0] = (int)v;
	data[1] = (int)(v>>>32);
	nWords = (data[1]==0) ? 1 : 2;
    }

    public FDBigInt( FDBigInt other ){
	data = new int[nWords = other.nWords];
	System.arraycopy( other.data, 0, data, 0, nWords );
    }

    private FDBigInt( int [] d, int n ){
	data = d;
	nWords = n;
    }

    /*
     * Left shift by c bits.
     * Shifts this in place.
     */
    public void
    lshiftMe( int c )throws IllegalArgumentException {
	if ( c <= 0 ){
	    if ( c == 0 )
		return; // silly.
	    else
		throw new IllegalArgumentException("negative shift count");
	}
	int wordcount = c>>5;
	int bitcount  = c & 0x1f;
	int anticount = 32-bitcount;
	int t[] = data;
	int s[] = data;
	if ( nWords+wordcount+1 > t.length ){
	    // reallocate.
	    t = new int[ nWords+wordcount+1 ];
	}
	int target = nWords+wordcount;
	int src    = nWords-1;
	if ( bitcount == 0 ){
	    // special hack, since an anticount of 32 won't go!
	    System.arraycopy( s, 0, t, wordcount, nWords );
	    target = wordcount-1;
	} else {
	    t[target--] = s[src]>>>anticount;
	    while ( src >= 1 ){
		t[target--] = (s[src]<<bitcount) | (s[--src]>>>anticount);
	    }
	    t[target--] = s[src]<<bitcount;
	}
	while( target >= 0 ){
	    t[target--] = 0;
	}
	data = t;
	nWords += wordcount + 1;
	// may have constructed high-order word of 0.
	// if so, trim it
	while ( nWords > 1 && data[nWords-1] == 0 )
	    nWords--;
    }

    /*
     * normalize this number by shifting until
     * the MSB of the number is at 0x08000000.
     * This is in preparation for quoRemIteration, below.
     * The idea is that, to make division easier, we want the
     * divisor to be "normalized" -- usually this means shifting
     * the MSB into the high words sign bit. But because we know that
     * the quotient will be 0 < q < 10, we would like to arrange that
     * the dividend not span up into another word of precision.
     * (This needs to be explained more clearly!)
     */
    public int
    normalizeMe() throws IllegalArgumentException {
	int src;
	int wordcount = 0;
	int bitcount  = 0;
	int v = 0;
	for ( src= nWords-1 ; src >= 0 && (v=data[src]) == 0 ; src--){
	    wordcount += 1;
	}
	if ( src < 0 ){
	    // oops. Value is zero. Cannot normalize it!
	    throw new IllegalArgumentException("zero value");
	}
	/*
	 * In most cases, we assume that wordcount is zero. This only
	 * makes sense, as we try not to maintain any high-order
	 * words full of zeros. In fact, if there are zeros, we will
	 * simply SHORTEN our number at this point. Watch closely...
	 */
	nWords -= wordcount;
	/*
	 * Compute how far left we have to shift v s.t. its highest-
	 * order bit is in the right place. Then call lshiftMe to
	 * do the work.
	 */
	if ( (v & 0xf0000000) != 0 ){
	    // will have to shift up into the next word.
	    // too bad.
	    for( bitcount = 32 ; (v & 0xf0000000) != 0 ; bitcount-- )
		v >>>= 1;
	} else {
	    while ( v <= 0x000fffff ){
		// hack: byte-at-a-time shifting
		v <<= 8;
		bitcount += 8;
	    }
	    while ( v <= 0x07ffffff ){
		v <<= 1;
		bitcount += 1;
	    }
	}
	if ( bitcount != 0 )
	    lshiftMe( bitcount );
	return bitcount;
    }

    /*
     * Multiply a FDBigInt by an int.
     * Result is a new FDBigInt.
     */
    public FDBigInt
    mult( int iv ) {
	long v = iv;
	int r[];
	long p;

	// guess adequate size of r.
	r = new int[ ( v * ((long)data[nWords-1]&0xffffffffL) > 0xfffffffL ) ? nWords+1 : nWords ];
	p = 0L;
	for( int i=0; i < nWords; i++ ) {
	    p += v * ((long)data[i]&0xffffffffL);
	    r[i] = (int)p;
	    p >>>= 32;
	}
	if ( p == 0L){
	    return new FDBigInt( r, nWords );
	} else {
	    r[nWords] = (int)p;
	    return new FDBigInt( r, nWords+1 );
	}
    }

    /*
     * Multiply a FDBigInt by another FDBigInt.
     * Result is a new FDBigInt.
     */
    public FDBigInt
    mult( FDBigInt other ){
	// crudely guess adequate size for r
	int r[] = new int[ nWords + other.nWords ];
	int i;
	// I think I am promised zeros...

	for( i = 0; i < this.nWords; i++ ){
	    long v = (long)this.data[i] & 0xffffffffL; // UNSIGNED CONVERSION
	    long p = 0L;
	    int j;
	    for( j = 0; j < other.nWords; j++ ){
		p += ((long)r[i+j]&0xffffffffL) + v*((long)other.data[j]&0xffffffffL); // UNSIGNED CONVERSIONS ALL 'ROUND.
		r[i+j] = (int)p;
		p >>>= 32;
	    }
	    r[i+j] = (int)p;
	}
	// compute how much of r we actually needed for all that.
	for ( i = r.length-1; i> 0; i--)
	    if ( r[i] != 0 )
		break;
	return new FDBigInt( r, i+1 );
    }

    /*
     * Add one FDBigInt to another. Return a FDBigInt
     */
    public FDBigInt
    add( FDBigInt other ){
	int i;
	int a[], b[];
	int n, m;
	long c = 0L;
	// arrange such that a.nWords >= b.nWords;
	// n = a.nWords, m = b.nWords
	if ( this.nWords >= other.nWords ){
	    a = this.data;
	    n = this.nWords;
	    b = other.data;
	    m = other.nWords;
	} else {
	    a = other.data;
	    n = other.nWords;
	    b = this.data;
	    m = this.nWords;
	}
	int r[] = new int[ n ];
	for ( i = 0; i < n; i++ ){
	    c += (long)a[i] & 0xffffffffL;
	    if ( i < m ){
		c += (long)b[i] & 0xffffffffL;
	    }
	    r[i] = (int) c;
	    c >>= 32; // signed shift.
	}
	if ( c != 0L ){
	    // oops -- carry out -- need longer result.
	    int s[] = new int[ r.length+1 ];
	    System.arraycopy( r, 0, s, 0, r.length );
	    s[i++] = (int)c;
	    return new FDBigInt( s, i );
	}
	return new FDBigInt( r, i );
    }

    /*
     * Subtract one FDBigInt from another. Return a FDBigInt
     * Assert that the result is positive.
     */
    public FDBigInt
    sub( FDBigInt other ){
	int r[] = new int[ this.nWords ];
	int i;
	int n = this.nWords;
	int m = other.nWords;
	int nzeros = 0;
	long c = 0L;
	for ( i = 0; i < n; i++ ){
	    c += (long)this.data[i] & 0xffffffffL;
	    if ( i < m ){
		c -= (long)other.data[i] & 0xffffffffL;
	    }
	    if ( ( r[i] = (int) c ) == 0 )
		nzeros++;
	    else
		nzeros = 0;
	    c >>= 32; // signed shift.
	}
	if ( c != 0L )
	    throw new RuntimeException("Assertion botch: borrow out of subtract");
	while ( i < m )
	    if ( other.data[i++] != 0 )
		throw new RuntimeException("Assertion botch: negative result of subtract");
	return new FDBigInt( r, n-nzeros );
    }

    /*
     * Compare FDBigInt with another FDBigInt. Return an integer
     * >0: this > other
     *  0: this == other
     * <0: this < other
     */
    public int
    cmp( FDBigInt other ){
        int i;
	if ( this.nWords > other.nWords ){
	    // if any of my high-order words is non-zero,
	    // then the answer is evident
	    int j = other.nWords-1;
	    for ( i = this.nWords-1; i > j ; i-- )
		if ( this.data[i] != 0 ) return 1;
	}else if ( this.nWords < other.nWords ){
	    // if any of other's high-order words is non-zero,
	    // then the answer is evident
	    int j = this.nWords-1;
	    for ( i = other.nWords-1; i > j ; i-- )
		if ( other.data[i] != 0 ) return -1;
	} else{
	    i = this.nWords-1;
	}
	for ( ; i > 0 ; i-- )
	    if ( this.data[i] != other.data[i] )
		break;
	// careful! want unsigned compare!
	// use brute force here.
	int a = this.data[i];
	int b = other.data[i];
	if ( a < 0 ){
	    // a is really big, unsigned
	    if ( b < 0 ){
		return a-b; // both big, negative
	    } else {
		return 1; // b not big, answer is obvious;
	    }
	} else {
	    // a is not really big
	    if ( b < 0 ) {
		// but b is really big
		return -1;
	    } else {
		return a - b;
	    }
	}
    }

    /*
     * Compute
     * q = (int)( this / S )
     * this = 10 * ( this mod S )
     * Return q.
     * This is the iteration step of digit development for output.
     * We assume that S has been normalized, as above, and that
     * "this" has been lshift'ed accordingly.
     * Also assume, of course, that the result, q, can be expressed
     * as an integer, 0 <= q < 10.
     */
    public int
    quoRemIteration( FDBigInt S )throws IllegalArgumentException {
	// ensure that this and S have the same number of
	// digits. If S is properly normalized and q < 10 then
	// this must be so.
	if ( nWords != S.nWords ){
	    throw new IllegalArgumentException("disparate values");
	}
	// estimate q the obvious way. We will usually be
	// right. If not, then we're only off by a little and
	// will re-add.
	int n = nWords-1;
	long q = ((long)data[n]&0xffffffffL) / (long)S.data[n];
	long diff = 0L;
	for ( int i = 0; i <= n ; i++ ){
	    diff += ((long)data[i]&0xffffffffL) -  q*((long)S.data[i]&0xffffffffL);
	    data[i] = (int)diff;
	    diff >>= 32; // N.B. SIGNED shift.
	}
	if ( diff != 0L ) {
	    // damn, damn, damn. q is too big.
	    // add S back in until this turns +. This should
	    // not be very many times!
	    long sum = 0L;
	    while ( sum ==  0L ){
		sum = 0L;
		for ( int i = 0; i <= n; i++ ){
		    sum += ((long)data[i]&0xffffffffL) +  ((long)S.data[i]&0xffffffffL);
		    data[i] = (int) sum;
		    sum >>= 32; // Signed or unsigned, answer is 0 or 1
		}
		/*
		 * Originally the following line read
		 * "if ( sum !=0 && sum != -1 )"
		 * but that would be wrong, because of the 
		 * treatment of the two values as entirely unsigned,
		 * it would be impossible for a carry-out to be interpreted
		 * as -1 -- it would have to be a single-bit carry-out, or
		 * +1.
		 */
		if ( sum !=0 && sum != 1 )
		    throw new RuntimeException("Assertion botch: "+sum+" carry out of division correction");
		q -= 1;
	    }
	}
	// finally, we can multiply this by 10.
	// it cannot overflow, right, as the high-order word has
	// at least 4 high-order zeros!
	long p = 0L;
	for ( int i = 0; i <= n; i++ ){
	    p += 10*((long)data[i]&0xffffffffL);
	    data[i] = (int)p;
	    p >>= 32; // SIGNED shift.
	}
	if ( p != 0L )
	    throw new RuntimeException("Assertion botch: carry out of *10");

	return (int)q;
    }

    public long
    longValue(){
	// if this can be represented as a long,
	// return the value
	int i;
	for ( i = this.nWords-1; i > 1 ; i-- ){
	    if ( data[i] != 0 ){
		throw new RuntimeException("Assertion botch: value too big");
	    }
	}
	switch(i){
	case 1:
	    if ( data[1] < 0 )
		throw new RuntimeException("Assertion botch: value too big");
	    return ((long)(data[1]) << 32) | ((long)data[0]&0xffffffffL);
	case 0:
	    return ((long)data[0]&0xffffffffL);
	default:
	    throw new RuntimeException("Assertion botch: longValue confused");
	}
    }

    public String
    toString() {
	StringBuffer r = new StringBuffer(30);
	r.append('[');
	int i = Math.min( nWords-1, data.length-1) ;
	if ( nWords > data.length ){
	    r.append( "("+data.length+"<"+nWords+"!)" );
	}
	for( ; i> 0 ; i-- ){
	    r.append( Integer.toHexString( data[i] ) );
	    r.append( (char) ' ' );
	}
	r.append( Integer.toHexString( data[0] ) );
	r.append( (char) ']' );
	return new String( r );
    }
}