div method

bool div(MPData q, MPData a, MPData b, [ MPData? r, ])

Implementation

bool div( MPData q, MPData a, MPData b, [MPData? r] ){
	a = clone( a );
	b = clone( b );

	r ??= MPData();

	int k = 1;
	if( a.val(0) < 0 && b.val(0) >= 0 ){ k = -1; }
	if( b.val(0) < 0 && a.val(0) >= 0 ){ k = -1; }
	int l = (a.val(0) < 0) ? -1 : 1;

	a.set( 0, getLen( a ) );
	b.set( 0, getLen( b ) );
	q.set( 0, 0 ); r.set( 0, 0 );

	int lq, lr;
	int K;
	int Q;	// 仮商

	if( b.val(0) == 0 || (b.val(0) == 1 && b.val(1) == 0) ){ return true ; }
	if( a.val(0) == 0 || (a.val(0) == 1 && a.val(1) == 0) ){ return false; }

	if( a.val(0) < b.val(0) ){
		_copy( a, 0, r, 0, a.val(0) + 1 );
		lr = r.val(0); r.set( 0, 0 ); _setLen( r, lr * l );
		return false;
	}

	if( b.val(0) == 1 ){
		int rr = 0;
		int c = _div1( q, a, b.val(1) );
		if( c > 0 ){
			r.set( rr++, 1 );
			r.set( rr, c );
		} else {
			r.set( rr, 0 );
		}
		lq = q.val(0); q.set( 0, 0 ); _setLen( q, lq * k );
		lr = r.val(0); r.set( 0, 0 ); _setLen( r, lr * l );
		return false;
	}

	// 正規化
	if( (K = element ~/ (b.val(b.val(0)) + 1)) > 1 ){
		_mul1( a, clone( a ), K );
		_mul1( b, clone( b ), K );
	}

	q.set( 0, a.val(0) - b.val(0) + 1 );
	for( int i = q.val(0); i > 0; i-- ){ q.set( i, 0 ); }
	int n = b.val(0);
	int m;
	int aa, bb, rr;
	while( (m = a.val(0)) >= n ){
		// 仮商Qを求める
		if( a.val(a.val(0)) >= b.val(b.val(0)) ){
			aa = a.val(0);
			for( bb = b.val(0); bb > 0; aa--, bb-- ){
				if( a.val(aa) != b.val(bb) ){ break; }
			}
			if( bb == 0 ){
				a.sub( 0, b.val(0) );
				q.inc(m - n + 1);
				continue;
			} else if( a.val(aa) > b.val(bb) ){
				_sub1( a, b, m - n, bb );
				q.inc(m - n + 1);
				continue;
			}
			Q = element - 1;
		} else {
			Q = (element * a.val(a.val(0)) + a.val( a.val(0) - 1 )) ~/ b.val(b.val(0));
		}
		if( m == n ){ break; }

		while( true ){
			if( Q == 1 ){
				// a=a-b
				b.set( b.val(0) + 1, 0 );
				_sub1( a, b, a.val(0) - b.val(0) - 1, b.val(0) );
				break;
			}

			// a=a-仮商(Q)*bを求める
			_mul1( r, b, Q );
			aa = a.val(0);
			for( rr = r.val(0); rr > 0; aa--, rr-- ){
				if( a.val(aa) != r.val(rr) ){ break; }
			}
			if( rr == 0 ){
				a.sub( 0, r.val(0) );
				break;
			} else if( a.val(aa) > r.val(rr) ){
				_sub1( a, r, a.val(0) - r.val(0), rr );
				break;
			} else {
				Q--;
			}
		}
		q.set( m - n, Q );
	}
	if( q.val(q.val(0)) == 0 ){ q.dec(0); }

	if( K > 1 ){
		// 逆正規化
		_div1( r, a, K );
	} else {
		_copy( a, 0, r, 0, a.val(0) + 1 );
	}

	lq = q.val(0); q.set( 0, 0 ); _setLen( q, lq * k );
	lr = r.val(0); r.set( 0, 0 ); _setLen( r, lr * l );
	return false;
}