// 整数演算で平方根を求める
// 小数第１位を四捨五入した値である

int isqrt(int x)
{
int s,t,u;
	if (x==0) return(0); // sqr(0)は0
	if (x<0) return(-1); // 負数の平方根は求められない

	s=1;
	t=x;
	while (s<t) {
		s<<=1; // *=2
		t>>=1; // /=2
	}
	s=(t+s)>>1;

	do {
		t=s;
		s=(x/s+s)>>1;
	} while (s<t);

	u=t+1;
	return((x-t*t)<(u*u-x)? t:u); // ここは四捨五入判定処理
}

#if 0
#include <math.h>

void main()
{
int i;
	for (i=0;i<=10;i++) {
		printf("sqr(%d)=%d/%f\n",i,isqrt(i),sqrt((double)i));
	}
}
#endif
