__BIGINT_THIS_FILE_IS( "div.js", "v0.5 beta 9", "2003-12-28" );


//////////////////////////////////////////////////////////////////////////////////////

Bigint.prototype.half = function() {
	var lastIndex = this.table.length - 1;
	var flag = false;
	for( var i = lastIndex; i >= 0; i-- ) {
		if( this.table[i] & 1 ) {
			this.table[i]--;
			this.table[i] >>>= 1;
			if( flag ) this.table[i] += __BIGINT_HALF_UNIT;
			flag = true;
		} else {
			this.table[i] >>>= 1;
			if( flag ) this.table[i] += __BIGINT_HALF_UNIT;
			flag = false;
		}
	}

	if( lastIndex > 0 && this.table[ lastIndex ] === 0 ) this.table.length--;

	return flag; // is Odd ?
}

Bigint.div = function( dividend, divisor ) {
	return ( Bigint.qr( dividend, divisor) )[0];
}

Bigint.qr = function( dividend, divisor ) {
	var bigDividend = Bigint.serio( dividend );
	var bigDivisor = Bigint.serio( divisor );

	if( bigDivisor.isEqualTo(0) ) {
		return Bigint._error( "divmod" , "divisor is 0" );
	}

	var QR = Bigint._qr( bigDividend, bigDivisor );

	if( bigDividend.sign < 0 ) {
		QR[0]._increment( 1 );
		QR[0].sign = QR[0].isZero()? ( 0 ) : ( -1 ) * bigDivisor.sign ;
		QR[1] = Bigint._sub( bigDivisor, QR[1] );
	} else {
		QR[0].sign = QR[0].isZero()? ( 0 ) : bigDivisor.sign ;
	}

	QR[1].sign = QR[1].isZero()? ( 0 ) : ( +1 ) ;

	return QR;
}

Bigint._qr = function( bigDividend, bigDivisor ) {
	var nDivisorLength = bigDivisor.getLength();

	var tableQR;

	if( nDivisorLength < 14 ) {
		tableQR = Bigint._divmod_typeN( bigDividend.toDecimalString(), bigDivisor.toNumber() );
		return [ new Bigint( tableQR[0] ) , new Bigint( tableQR[1] ) ];
	} else if( nDivisorLength === 14 ) {
		tableQR = Bigint._divmod_typeN_v1( bigDividend.toDecimalString(), bigDivisor.toNumber() );
		return [ new Bigint( tableQR[0] ) , new Bigint( tableQR[1] ) ];
	} else if( nDivisorLength <= 294 ) {
		return Bigint._divmod_typeF( bigDividend, bigDivisor );
	} else {
		return Bigint._divmod_typeS( bigDividend, bigDivisor );
	}
}
Bigint.divmod = Bigint.qr;
Bigint._divmod = Bigint._qr;


Bigint._mod = function( bigDividend, bigDivisor ) {
	var nDividendLength = bigDividend.getLength();
	var nDivisorLength = bigDivisor.getLength();

	if( nDividendLength < nDivisorLength ) return bigDividend.copy();

	if( nDivisorLength <= 14 ) {
		var strResult = Bigint._mod_typeN( bigDividend.toDecimalString(), bigDivisor.toNumber() );
		return new Bigint( strResult );
	} else if( bigDivisor.getLength() <= 294 ) { // 294 + GREEDINESS(14) = 308-digit < 2**1024 = 309 digit
		return Bigint._mod_typeF( bigDividend, bigDivisor );
	} else {
		return Bigint._mod_typeS( bigDividend, nDivisor );
	}
}

Bigint.mod = function( dividend, modulus ) {
	var bigDividend = Bigint.serio( dividend );
	var bigDivisor = Bigint.serio( modulus );

	if( bigDivisor.isZero() || bigDivisor.sign < 0 ) {
		return Bigint._error( "mod" , "modulus is not positive: " + modulus );
	} else if( bigDivisor.isEqualTo( 1 ) ) {
		return new Bigint( 0 );
	} else if( bigDivisor.isEqualTo( 2 ) ) {
		return new Bigint( bigDividend.table[0] & 1 );
	}

	var bigResult = Bigint._mod( bigDividend, bigDivisor );

	if( bigDividend.sign < 0 ) bigResult = Bigint._sub( bigDivisor, bigResult );

	bigResult.sign = (bigResult.isZero())? (0) : (+1);
	return bigResult;
}

///////////////////////////////////////////////////////////////////////////////
//
//	type N
//
///////////////////////////////////////////////////////////////////////////////

Bigint._qr_typeN = function( strDividend, nDivisor ) {
	// nDivisor can be 14-digit or less
	// However, _divmod_typeN_v1 is faster for 14-digit
	// This function is fast for small nDivisor.

	var strDividendHead = strDividend.substr( 0 , 15 );
	var pos = 15;
	var strQuotient = "";
	var q, r, nDigitsToEat, strRemainderTail;

	while( true ) {
		r = strDividendHead % nDivisor;
		q = ( strDividendHead - r ) / nDivisor;
		strDividendHead = ( r )? r + "" : "" ;

		if( strQuotient === "" ) {
			strQuotient = q + "";
		} else {
			strQuotient += Bigint._padding[ strRemainderTail.length ]( q );
		}

		if( pos >= strDividend.length ) break;

		nDigitsToEat = 15 - strDividendHead.length;
		strRemainderTail = strDividend.substr( pos, nDigitsToEat );
		strDividendHead += strRemainderTail;
		pos += nDigitsToEat;
	}

	if( strQuotient === "" ) strQuotient = "0";
	if( strDividendHead === "" ) strDividendHead = "0";

	return [ strQuotient, strDividendHead ];
}

Bigint._divmod_typeN = Bigint._qr_typeN;

Bigint._mod_typeN = function( strDividend, nDivisor ) {
	// nDivisor should be 14-digit or less
	var strDividendHead = strDividend.substr( 0 , 15 );
	var pos = 15;
	while( true ) {
		var r = strDividendHead % nDivisor;
		if( pos >= strDividend.length ) return r;
		strDividendHead = ( r )? r + "" : "";
		var nDigitsToEat = 15 - strDividendHead.length;
		strDividendHead += strDividend.substr( pos, nDigitsToEat );
		pos += nDigitsToEat;
	}
}

Bigint._isDivisible_typeN = function( strDividend, nDivisor ) {
	var strDividendHead = strDividend.substr( 0 , 15 );
	var pos = 15; 
	while( true ) {
		var r = strDividendHead % nDivisor;
		if( pos >= strDividend.length ) return ( ( strDividendHead % nDivisor === 0) );
		strDividendHead = ( r )? r + "" : "";
		var nDigitsToEat = 15 - strDividendHead.length;
		strDividendHead += strDividend.substr( pos, nDigitsToEat );
		pos += nDigitsToEat;
	}
}

Bigint._divmod_typeN_v1 = function( bigDividend, nDivisor ) {
	var strDividend = bigDividend.toDecimalString();
	var nDivisorLength = ( nDivisor + "" ).length;

	var strDividendHead = strDividend.substr( 0 , nDivisorLength );
	var strQuotient = "";

	for( var pos = nDivisorLength - 1; pos < strDividend.length; pos++ ) {
		if( strDividendHead / nDivisor < 1 ) {
			if( strQuotient !== "" ) strQuotient += "0";

			if( pos === strDividend.length - 1 ) break;

			strDividendHead +=  strDividend.charAt( pos + 1 );
			continue;
		}

		var q = Math.floor( strDividendHead / nDivisor );
		strQuotient += q;
		var strRemainderHead = strDividendHead % nDivisor + "";
		if( strRemainderHead === "0" ) strRemainderHead = "";

		strDividendHead = strRemainderHead + strDividend.charAt( pos+1 );
	}
	
	if( strQuotient === "" ) strQuotient = "0";
	if( strDividendHead === "" ) strDividendHead = "0";
	
	return [ strQuotient, strDividendHead-0 ];
}

///////////////////////////////////////////////////////////////////////////////
//
//	type F
//
///////////////////////////////////////////////////////////////////////////////

Bigint._mod_typeF = function( bigDividend, bigDivisor ) { // v3
	var strDividend = bigDividend.toDecimalString();
	var strDivisor = bigDivisor.toDecimalString();

	if( strDividend.length < strDivisor.length ) return ( bigDivisor );

	var GREEDINESS = 14; // 15 might be slightly better for middle-sized bigDivisor ( like 10^20 ~ 10^40 )

	var strDividendHead = strDividend.substr( 0 , strDivisor.length + GREEDINESS );
	var pos = strDivisor.length + GREEDINESS;

	for( var dummy=0; dummy < 30; dummy++ ) { // Dividend is 294-digit at most: 21 ~ 25 loops should be enough if you eat 13 ~ 14-digit per loop
		if( pos >= strDividend.length && Bigint.strcmp( strDividendHead , strDivisor ) < 0 ) {
			 return ( new Bigint( strDividendHead ) );
		}

		// Because of floating-point arithmetic, q may be inaccurate (sometimes error=1, rarely error=2)
		// If q is too small, strRemainderHead will be > strDivisor, but no problem in going on.
		// If q is too big, we should correct q later.
		var fQuotient = strDividendHead / strDivisor;
		var q = Math.floor( fQuotient );

		 //	This trick does work for Miller-Rabin test
		 //	 where you'd get bigDivident congruent to -1 modulo bigDivisor.
		 //	Without this, you are likely to get 'correction=1' (see below) many times, which will affect the speed.
		 // This trick does not affect the spped because usually it is unlikely to have fractional < 0.00001
 		var fractional = fQuotient - q;
		if( fractional < 0.00001 && q > 1 ) {
			 q--;
		}

		var bigQuotient = new Bigint( q );
		var bigProduct = Bigint._mul( bigDivisor, bigQuotient );
		var strProduct = bigProduct.toDecimalString();
		var strRemainderHead = Bigint._strsub( strDividendHead , strProduct );

		var correction = 0;

		// If strProduct is bigger and cannot be subtracted from strDividendHead,
		// _strsub returns void 0 (This doesn't happen too often)
		while( strRemainderHead === void 0 ) {
			correction++;

			// Let q be q-1, then strProduct will be this:
			strProduct = Bigint._strsub( strProduct, strDivisor );

			// Probably now we can subtract strProduct from strDividendHead
			strRemainderHead = Bigint._strsub( strDividendHead , strProduct );
			
			if( correction > 10 ) {
				return Bigint._error( "_mod_typeF",	"failed to auto-correct: " + bigDividend + " / " + bigDivisor );
			}
		}

		if( strRemainderHead === "0" ) strRemainderHead = "";

		var nDigitsToEat = ( strDivisor.length + GREEDINESS ) - strRemainderHead.length;
		strDividendHead = strRemainderHead + strDividend.substr( pos , nDigitsToEat );
		pos += nDigitsToEat;
	}

	return Bigint._error("_mod_typeF", "too many loops for " + bigDividend + " / " + bigDivisor );
}

Bigint._qr_typeF = function( bigDividend, bigDivisor ) { // v3
	var strDividend = bigDividend.toDecimalString();
	var strDivisor = bigDivisor.toDecimalString();

	if( strDividend.length < strDivisor.length ) return ( bigDivisor );

	var GREEDINESS = 14;

	var strDividendHead = strDividend.substr( 0 , strDivisor.length + GREEDINESS );
	var pos = strDivisor.length + GREEDINESS;

	var strResultQ = "";

	for( var dummy=0; dummy < 30; dummy++ ) { // Dividend is 294-digit at most: 21 ~ 25 loops should be enough if you eat 13 ~ 14-digit per loop
		if( pos >= strDividend.length && Bigint.strcmp( strDividendHead , strDivisor ) < 0 ) {
			 // if( strResultQ === "" ) strResultQ = "0";
			 // if( strDividendHead === "" ) strDividendHead = "0";
			 return [ new Bigint( strResultQ ), new Bigint( strDividendHead ) ];
		}

		var fQuotient = strDividendHead / strDivisor;
		var q = Math.floor( fQuotient );

		var bigQuotient = new Bigint( q );
		var bigProduct = Bigint._mul( bigDivisor, bigQuotient );
		var strProduct = bigProduct.toDecimalString();
		var strRemainderHead = Bigint._strsub( strDividendHead , strProduct );

		var correction = 0;
		var flag = false;
		while( strRemainderHead === void 0 ) {
_debug(dummy,"- for "+q);
			flag = true;
			correction++;
			bigQuotient._decrement();
			strProduct = Bigint._strsub( strProduct, strDivisor );
			strRemainderHead = Bigint._strsub( strDividendHead , strProduct );
			
			if( correction > 10 ) {
				return Bigint._error( "_qr_typeF", "negative auto-correction failed: " + bigDividend + " / " + bigDivisor );
			}
		}

		while( Bigint.strcmp( strRemainderHead, strDivisor ) >= 0 ) {
_debug(dummy,"+");
			if( flag ) {
				return Bigint._error( "_qr_typeF", "R is strange after negative auto-correction: " + bigDividend + " / " + bigDivisor );
			}
			
			correction++;
			bigQuotient._increment();
			strRemainderHead = Bigint._strsub( strRemainderHead , strDivisor );
			
			if( correction > 10 ) {
				return Bigint._error( "_qr_typeF", "positive auto-correction failed: " + bigDividend + " / " + bigDivisor );
			}
		}

		strResultQ += bigQuotient.toDecimalString();

		if( strRemainderHead === "0" ) strRemainderHead = "";

		var r_length = strRemainderHead.length;

		var nDigitsToEat = ( strDivisor.length + GREEDINESS ) - r_length;
		strDividendHead = strRemainderHead + strDividend.substr( pos , nDigitsToEat );
		pos += nDigitsToEat;
		var tmppos = r_length + 1;
		while( Bigint.strcmp( strDividendHead.substr( 0, tmppos ), strDivisor ) < 0 && tmppos < strDividendHead.length ) {
			strResultQ += "0";
			tmppos++;
		}
		
	}

	return Bigint._error("_qr_typeF", "too many loops for " + bigDividend + " / " + bigDivisor );
}

Bigint._divmod_typeF = Bigint._qr_typeF;


///////////////////////////////////////////////////////////////////////////////
//
//	type S ( Divisor : 295-digit or more )
//
///////////////////////////////////////////////////////////////////////////////

Bigint._mod_typeS = function( bigDividend, bigDivisor ) {
	var strDividend = bigDividend.toDecimalString();
	var strDivisor = bigDivisor.toDecimalString();

	var DIVISOR_HEAD_LENGTH = 16;
	var strDivisorHead = strDivisor.substr( 0 , DIVISOR_HEAD_LENGTH );

	if( strDividend.length < strDivisor.length ) return ( bigDivisor );

	var GREEDINESS = 14;
		// Can't be 15. Unlike _mod_typeF, fQuotient is triple-lossy (denominator, numerator & float ).
		// High GREEDINESS would produce such a big error that couldn't be auto-corrected.

	var DIMINISHED_DIVIDEND_HEAD_LENGTH = DIVISOR_HEAD_LENGTH + GREEDINESS;
	var strDividendHead = strDividend.substr( 0 ,  strDivisor.length + GREEDINESS );
	var pos = strDivisor.length + GREEDINESS;
	var cuteness = pos - strDividendHead.length; // always 0 unless strDividend is so short that pos > its length
	var strDividendHeadDiminished = strDividendHead.substr( 0, DIMINISHED_DIVIDEND_HEAD_LENGTH - cuteness );

	for( var dummy=0; dummy < 1000; dummy++ ) {

//_debug(strDividendHead + " / " + strDivisor + " = " + strDividendHead/strDivisor);
//_debug("strDividendHead.length",strDividendHead.length)
//_debug("strDivisor.length",strDivisor.length)
		if( pos >= strDividend.length && Bigint.strcmp( strDividendHead , strDivisor ) < 0 ) {
			 return ( new Bigint( strDividendHead ) );
		}

		var fQuotient = strDividendHeadDiminished / strDivisorHead;
//_debug("strDividendHeadDiminished.length",strDividendHeadDiminished.length)
//_debug("strDivisorHead.length",strDivisorHead.length)
		var q = Math.floor( fQuotient );
/*
 		var fractional = fQuotient - q;
		if( fractional < 0.00001 && q > 1 ) {
			 q--;
		}
*/
		var bigQuotient = new Bigint( q );
		var bigProduct = Bigint._mul( bigDivisor, bigQuotient );
		var strProduct = bigProduct.toDecimalString();
		var strRemainderHead = Bigint._strsub( strDividendHead , strProduct );

		var correction = 0;

		while( strRemainderHead === void 0 ) {
			correction++;
//			_debug( "correction = " + correction + ": fQuotient = " + fQuotient );
			strProduct = Bigint._strsub( strProduct, strDivisor );
			strRemainderHead = Bigint._strsub( strDividendHead , strProduct );
			
			if( correction > 10 ) {
				return Bigint._error("_mod_typeS", "failed to auto-correct: " + bigDividend + " / " + bigDivisor);
			}
		}

		if( strRemainderHead === "0" ) strRemainderHead = "";

		var nDigitsToEat = strDivisor.length + GREEDINESS - strRemainderHead.length;
		strDividendHead = strRemainderHead + strDividend.substr( pos , nDigitsToEat );
		pos += nDigitsToEat;
		cuteness = strDivisor.length + GREEDINESS - strDividendHead.length;
		strDividendHeadDiminished = strDividendHead.substr( 0 , DIMINISHED_DIVIDEND_HEAD_LENGTH - cuteness );
	}

	return Bigint._error("_mod_typeS: too many loops for " + bigDividend + " / " + bigDivisor );

}


Bigint._qr_typeS = function( bigDividend, bigDivisor ) {
	var strDividend = bigDividend.toDecimalString();
	var strDivisor = bigDivisor.toDecimalString();

	var DIVISOR_HEAD_LENGTH = 16;
	var strDivisorHead = strDivisor.substr( 0 , DIVISOR_HEAD_LENGTH );

	if( strDividend.length < strDivisor.length ) return ( bigDivisor );

	var GREEDINESS = 14;

	var DIMINISHED_DIVIDEND_HEAD_LENGTH = DIVISOR_HEAD_LENGTH + GREEDINESS;
	var strDividendHead = strDividend.substr( 0 ,  strDivisor.length + GREEDINESS );
	var pos = strDivisor.length + GREEDINESS;
	var cuteness = pos - strDividendHead.length; // always 0 unless strDividend is so short that pos > its length
	var strDividendHeadDiminished = strDividendHead.substr( 0, DIMINISHED_DIVIDEND_HEAD_LENGTH - cuteness );

	var strResultQ = "";

	for( var dummy=0; dummy < 1000; dummy++ ) {

//_debug(strDividendHead + " / " + strDivisor + " = " + strDividendHead/strDivisor);
//_debug("strDividendHead.length",strDividendHead.length)
//_debug("strDivisor.length",strDivisor.length)
		if( pos >= strDividend.length && Bigint.strcmp( strDividendHead , strDivisor ) < 0 ) {
			 return [ new Bigint( strResultQ ) , new Bigint( strDividendHead ) ];
		}

		var fQuotient = strDividendHeadDiminished / strDivisorHead;
//_debug("strDividendHeadDiminished.length",strDividendHeadDiminished.length)
//_debug("strDivisorHead.length",strDivisorHead.length)
		var q = Math.floor( fQuotient );
		var bigQuotient = new Bigint( q );
		var bigProduct = Bigint._mul( bigDivisor, bigQuotient );
		var strProduct = bigProduct.toDecimalString();
		var strRemainderHead = Bigint._strsub( strDividendHead , strProduct );

		var correction = 0;

		var flag = false;
		while( strRemainderHead === void 0 ) {
_debug(dummy,"- for " + q);
			flag = true;
			correction++;
			bigQuotient._decrement();
			strProduct = Bigint._strsub( strProduct, strDivisor );
			strRemainderHead = Bigint._strsub( strDividendHead , strProduct );
			
			if( correction > 10 ) {
				return Bigint._error( "_qr_typeS", "negative auto-correction failed: " + bigDividend + " / " + bigDivisor );
			}
		}

		while( Bigint.strcmp( strRemainderHead, strDivisor ) >= 0 ) {
_debug(dummy,"+");

			if( flag ) {
				return Bigint._error( "_qr_typeS", "R is strange after negative auto-correction: " + bigDividend + " / " + bigDivisor );
			}
			
			correction++;
			bigQuotient._increment();
			strRemainderHead = Bigint._strsub( strRemainderHead , strDivisor );
			
			if( correction > 10 ) {
				return Bigint._error( "_qr_typeS", "positive auto-correction failed: " + bigDividend + " / " + bigDivisor );
			}
		}

		strResultQ += bigQuotient.toDecimalString();
		if( strRemainderHead === "0" ) strRemainderHead = "";

		var r_length = strRemainderHead.length;

		var nDigitsToEat = ( strDivisor.length + GREEDINESS ) - r_length;
		strDividendHead = strRemainderHead + strDividend.substr( pos , nDigitsToEat );
		pos += nDigitsToEat;
		var tmppos = r_length + 1;
		while( Bigint.strcmp( strDividendHead.substr( 0, tmppos ), strDivisor ) < 0 && tmppos < strDividendHead.length ) {
			strResultQ += "0";
			tmppos++;
		}

		cuteness = strDivisor.length + GREEDINESS - strDividendHead.length;
		strDividendHeadDiminished = strDividendHead.substr( 0 , DIMINISHED_DIVIDEND_HEAD_LENGTH - cuteness );
	}

	return Bigint._error("_qr_typeS: too many loops for " + bigDividend + " / " + bigDivisor );

}

Bigint._divmod_typeS = Bigint._qr_typeS;



///////////////////////////////////////////////////////////////////////////////
//
//	Obsolete 
//
///////////////////////////////////////////////////////////////////////////////


Bigint._divmod_typeF_old = function( bigDividend, bigDivisor ) {
	var strDividend = bigDividend.toDecimalString();
	var strDivisor = bigDivisor.toDecimalString();

	if( !bigDivisor.multipliedBy ) {
		_debug("setMultiplicationTable...");
		bigDivisor.setMultiplicationTable();
	}

	var strDividendHead = strDividend.substr( 0 , strDivisor.length );

	var strQuotient = "";

	for( var pos = strDivisor.length - 1; pos < strDividend.length; pos++ ) {

		var q;

		var compare = Bigint.strcmp( strDividendHead, strDivisor );

		if( compare < 0 ) {
			if( strQuotient !== "" ) strQuotient += "0";

			if( pos === strDividend.length - 1 ) break;

			strDividendHead += strDividend.charAt( pos + 1 );
			continue;
		} else if( compare <= 1 ) {
			q = 1;
		} else {
			var fQuotient = strDividendHead / strDivisor;
			q = Math.floor( fQuotient );
			var decimal = fQuotient - q;

			if( q === 10 ) {
				q = 9;
			} else if( q > 1 && decimal < 0.000000000001 ) {
				if( Bigint.strcmp( strDividendHead, bigDivisor.multipliedBy[ q ] ) < 0 ) q--;
			} else if( q < 9 && decimal > 0.999999999999 ) {
				if( Bigint.strcmp( strDividendHead, bigDivisor.multipliedBy[ q+1 ] ) >= 0 ) q++;
			}
		}

		strQuotient += ( q + "" );

		var strRemainderHead = Bigint._strsub( strDividendHead , bigDivisor.multipliedBy[ q ] );
		if( strRemainderHead === "0" ) strRemainderHead = "";
		strDividendHead = strRemainderHead + strDividend.charAt( pos + 1 );
	}
	
	if( strQuotient === "" ) strQuotient = "0";
	if( strDividendHead === "" ) strDividendHead = "0";

	return [ ( new Bigint ( strQuotient ) ), ( new Bigint( strDividendHead ) ) ];
}


Bigint._divmod_typeS_old = function( bigDividend, bigDivisor ) {
	var strDividend = bigDividend.toDecimalString();
	var strDivisor = bigDivisor.toDecimalString();

	var strDividendHead = strDividend.substr( 0 , strDivisor.length );
	var strQuotient = "";
	if( bigDivisor.multipliedBy === void 0 ) {
		_debug("setMultiplicationTable...");
		
		bigDivisor.setMultiplicationTable();
	}
	
	if( bigDivisor.turningPoint === void 0 ) {
		bigDivisor.turningPoint = false;
		for( var i=2; i<=9; i++ ) {
			if( bigDivisor.multipliedBy[i].length > strDivisor.length ) {
				bigDivisor.turningPoint = i;
				break;
			}
		}
	}
	for( var pos = strDivisor.length - 1; pos < strDividend.length; pos++ ) {

		var flagAskew = ( strDividendHead.length > strDivisor.length )? true : false ;
		var q;
		var compare = Bigint.strcmp( strDividendHead, strDivisor );

		if( compare < 0 ) {
			if( strQuotient !== "" ) strQuotient += "0";
			if( pos === strDividend.length - 1 ) break;
			strDividendHead += strDividend.charAt( pos + 1 );
			continue;
		} else if( compare <= 1 ) {
			q = 1;
		} else {
			var min, max;
			if( flagAskew ) {
				min = bigDivisor.turningPoint;
				max = 9;
			} else {
				min = 1;
				max = (bigDivisor.turningPoint)? bigDivisor.turningPoint - 1 : 9;
			}

			for( q = min; q <= max; q++ ) {
				var compare = Bigint.strcmp( strDividendHead, bigDivisor.multipliedBy[ q ] );
				
				if( compare < 0 ) {
					q--;
					break;
				} else if( compare === 0 ) {
					break;
				} else {
					if( q === max ) break;
				}
			}
		}

		strQuotient += ( q + "" );

		var strRemainderHead = Bigint._strsub( strDividendHead , bigDivisor.multipliedBy[ q ] );
		if( strRemainderHead === "0" ) strRemainderHead = "";
		strDividendHead = strRemainderHead + strDividend.charAt( pos + 1 );
	}
	
	if( strQuotient === "" ) strQuotient = "0";
	if( strDividendHead === "" ) strDividendHead = "0";
	return [ ( new Bigint ( strQuotient ) ), ( new Bigint( strDividendHead ) ) ];
}

function _str_to_biggerTable( strBigNumber ) {
	var tableSize = Math.ceil( strBigNumber.length / __BIGINT_BIGGER_POWER );

	var biggerTable = new Array( tableSize );

	var length_0 = strBigNumber.length % __BIGINT_BIGGER_POWER;
	if( length_0 === 0 ) length_0 = __BIGINT_BIGGER_POWER;
	biggerTable[ tableSize-1 ] = strBigNumber.substr( 0, length_0 ) - 0;

	var pos = length_0;
	var tmpstr;

	for( var i=tableSize-2; i >= 0; i-- ) {
		tmpstr = strBigNumber.substr( pos , __BIGINT_BIGGER_POWER );
		pos += __BIGINT_BIGGER_POWER;
		biggerTable[i] = tmpstr - 0;
	}
	
	return biggerTable;
}

function _bigger_to_big( biggerTable ) {
	biggerTable.reverse();
	return ( new Bigint( biggerTable.join("") ) );
}

/*
Bigint.prototype.half_v1 = function () {
	var resultTable = new Array();
	var flag = 0;
	for( var i=this.table.length-1; i>=0; i-- ) {
		var tmpstr = this.table[ i ] + "";
		var lastDigit = tmpstr.charAt( tmpstr.length - 1 );

		if( flag === 1 ) this.table[ i ] += __BIGINT_BIG_UNIT;

		if( lastDigit % 2 === 1 ) {
			resultTable[i] = ( this.table[i] - 1 ) / 2;
			flag = 1;
		} else {
			resultTable[i] = this.table[i] / 2;
			flag = 0;
		}
	}

	if( resultTable[ resultTable.length-1 ] === 0 ) resultTable.length--;

	this.table = resultTable;
}
*/


Bigint._mod_typeS_v1 = function( bigDividend, bigDivisor ) {
	var strDividend = bigDividend.toDecimalString();
	var strDivisor = bigDivisor.toDecimalString();
	
	if( strDividend.length < strDivisor.length ) return bigDivisor;
	
	var strDividendHead = strDividend.substr( 0 , strDivisor.length );
	if( bigDivisor.multipliedBy === void 0 ) {
		_debug("setMultiplicationTable...");
		bigDivisor.setMultiplicationTable();
	}
	if( bigDivisor.turningPoint === void 0 ) {
		bigDivisor.turningPoint = false;
		for( var i=2; i<=9; i++ ) {
			if( bigDivisor.multipliedBy[i].length > strDivisor.length ) {
				bigDivisor.turningPoint = i;
				break;
			}
		}
	}
	for( var pos = strDivisor.length - 1; pos < strDividend.length; pos++ ) {
		var flagAskew = ( strDividendHead.length > strDivisor.length )? true : false ;
		var q;
		var compare = Bigint.strcmp( strDividendHead, strDivisor );
		if( compare < 0 ) {
			if( pos === strDividend.length - 1 ) break;
			strDividendHead += strDividend.charAt( pos + 1 );
			continue;
		} else if( compare <= 1 ) {
			q = 1;
		} else {
			var min, max;
			if( flagAskew ) {
				min = bigDivisor.turningPoint;
				max = 9;
			} else {
				min = 1;
				max = (bigDivisor.turningPoint)? bigDivisor.turningPoint - 1 : 9;
			}

			for( q = min; q <= max; q++ ) {
				var compare = Bigint.strcmp( strDividendHead, bigDivisor.multipliedBy[ q ] );
				
				if( compare < 0 ) {
					q--;
					break;
				} else if( compare === 0 ) {
					break;
				} else {
					if( q === max ) break;
				}
			}
		}

		var strRemainderHead = Bigint._strsub( strDividendHead , bigDivisor.multipliedBy[ q ] );
		if( strRemainderHead === "0" ) strRemainderHead = "";
		strDividendHead = strRemainderHead + strDividend.charAt( pos + 1 );
	}
	
	if( strDividendHead === "" ) strDividendHead = "0";
	return ( new Bigint( strDividendHead ) );
}