sqrt method

bool sqrt(MPData x, MPData a)

Implementation

bool sqrt( MPData x, MPData a ){
	a = clone( a );

	_setLen( x, 0 );
	if( a.val(0) < 0 ){ return true; }
	int la = getLen( a );
	if( la == 0 ){ return false; }
	if( la == 1 ){
		_setLen( x, 1 );
		x.set( 1, ClipMath.sqrt( a.val(1).toDouble() ).toInt() );
		return false;
	}
	if( la == 2 ){
		_setLen( x, 1 );
		x.set( 1, ClipMath.sqrt( (a.val(2) * element + a.val(1)).toDouble() ).toInt() );
		return false;
	}

	int l = (la + 1) ~/ 2;
	MPData b = MPData();
	b.set( l + 1, 0 ); // 配列の確保
	_fill( 0, x, 1, l );
	_fill( 0, b, 1, l );
	_setLen( x, l );
	_setLen( b, l );

	// 最上位桁の平方数を求める
	int i = (l - 1) * 2 + 1;
	int aa = a.val(i);
	if( ClipMath.imod( la, 2 ) == 0 ){
		aa += a.val(i + 1) * element;
	}
	x.set( l, ClipMath.sqrt( aa.toDouble() ).toInt() );

	// 初回のaとbが求まる
	b.set( l, x.val(l) + x.val(l) );
	if( b.val(l) >= element ){
		b.sub( l, element );
		b.set( l + 1, 1 );
		_setLen( b, l + 1 );
	}
	MPData w = MPData();
	mul( w, x, x );
	sub( a, a, w );
	l--;

	MPData q = MPData();
	MPData r = MPData();
	while( true ){
		div( q, a, b, r ); // 仮値Q
		if( l > 1 ){
			_fill( 0, q, 1, l - 1 );
		}
		if( getLen( q ) > l ){
			q.set( l, element - 1 );
			_setLen( q, l );
		}
		while( true ){
			add( r, b, q );
			mul( w, r, q );
			if( cmp( w, a ) <= 0 ){
				break;
			}
			q.dec(l); // 仮値Qを下げる
		}
		x.set( l, q.val(l) );
		if( l == 1 ){
			break;
		}

		// 次のaとbが求まる
		add( b, r, q );
		sub( a, a, w );
		l--;
	}
	return false;
}