整数の平方根計算

2016.02.12

はじめに

整数の足し算と引き算だけで整数の平方根を計算するJavaのプログラムの作り方を解説します。

ここで紹介する平方根の計算は、与えられた整数の平方根の整数部を求めるもので小数点以下は切り捨てです。

平方根を求める方法

ここから平方根を求める方法について説明します。

まず、下の表を見てください。

一番左の数値が平方根の解で、真ん中が平方根の解を持つ整数を全て列挙したものです。

そして、その個数を一番右の平方根の解を持つ整数の個数に書いています。

この表から平方根の解が１つ増えると平方根の解を持つ整数の個数が２つ増えることがわかります。

平方根の解	平方根の解を持つ整数	平方根の解を持つ整数の個数
0	0	1
1	1,2,3	3
2	4,5,6,7,8	5
3	9,10,11,12,13,14,15	7
4	16,17,18,19,20,21,22,23,24	9
5	25,26,27,28,29,30,31,32,33,34,35	11

よって、平方根を求めようとする数値から平方根の値を持つ整数の個数の値、3,5,7,9,・・・を順番に引いていき、0以下になった回数が求める平方根の値となります。

具体的な数値で確かめてみましょう。例えば19の場合、1回目の計算 19-3=16、2回目の計算 16-5=9、3回目の計算 9-7=2、4回目の計算 2-9=-7となります。4回目の計算でマイナスになったので平方根は4になります。

以下が、このアルゴリズムを実現したソースコードです。

SqrtInt.java

ダウンロード

public class SqrtInt {
	// 整数型の平方根計算メソッド
	private static int sqrt_intger( int num )
	{
		// 1以下なら元の値を戻す
		if ( 1 >= num ) return num;

		// 平方根の解が1になる整数の数(1と2と3の3個)
		int c = 3;

		// ループ回数(平方根の解)
		int count = 1;

		//　ループ
		while ( true ) {
			num -= c;
			if ( 0 >= num ) break;
			c += 2;
			++ count;
		}
		return count;
	}


	// メイン
	public static void main( String[] args ) {
		int i;

		for ( i = 0; i <= 50; ++ i ) {
			System.out.println( i + "の平方根=" + sqrt_intger( i ) );
		}
	}
}

コンパイルソースコードが「ANSI」の場合

C:\talavax\javasample>javac -encoding sjis SqrtInt.java

コンパイルソースコードが「UTF-8」の場合

C:\talavax\javasample>javac SqrtInt.java

実行

C:\talavax\javasample>java SqrtInt

0から50の平方根を計算した結果（一部省略）

0の平方根=0
1の平方根=1
2の平方根=1
3の平方根=1
4の平方根=2
5の平方根=2
6の平方根=2
7の平方根=2
8の平方根=2
9の平方根=3
10の平方根=3
11の平方根=3
12の平方根=3
13の平方根=3
14の平方根=3
15の平方根=3
16の平方根=4
17の平方根=4
18の平方根=4
　　：
22の平方根=4
23の平方根=4
24の平方根=4
25の平方根=5
26の平方根=5
27の平方根=5
　　：
33の平方根=5
34の平方根=5
35の平方根=5
36の平方根=6
37の平方根=6
38の平方根=6
　　：
46の平方根=6
47の平方根=6
48の平方根=6
49の平方根=7
50の平方根=7

Javaソースコード

ここからは、このソースコードを上から順番に解説していきます。

public class SqrtInt {

クラス名を、SqrtIntとしています。

002
003

	// 整数型の平方根計算メソッド
	private static int sqrt_intger( int num )

整数の平方根を戻すメソッドをsqrt_intgerを作っています。

005
006

		// 1以下なら元の値を戻す
		if ( 1 >= num ) return num;

与えられたnumが0以下の場合、numを返しています。マイナス値の平方根は求められないので元の値numを返しています。このメソッドを呼び出した結果、戻り値がマイナスの場合にエラーとして処理できるようにしています。

008
009

		// 平方根の解が1になる整数の数(1と2と3の3個)
		int c = 3;

平方根が1になる整数の個数を変数cに代入しています。

011
012

		// ループ回数(平方根の解)
		int count = 1;

処理回数を格納した変数countに1を代入しています。

014
015

		//　ループ
		while ( true ) {

while文で無限ループを作っています。

			num -= c;
			if ( 0 >= num ) break;
			c += 2;
			++ count;

numからcを引いた後、numが0以下かどうかをif文で調べ、0以下であればbreak文でwhile文を終了させます。変数numが0より大きい値であれば、cに2を足し、countに1を足します。

	// メイン
	public static void main( String[] args ) {
		int i;

		for ( i = 0; i <= 50; ++ i ) {
			System.out.println( i + "の平方根=" + sqrt_intger( i ) );
		}
	}

0から50までの平方根を表示しています。

この方法は、パソコンでの小数点計算に時間がかかっていた時代に使っていた平方根計算のアルゴリズムの１つで、整数の足し算と引き算だけで平方根の高速計算を実現していました。計算結果の精度は低いので、あまり精度を必要としないプログラムで使われていました。

現在では実数計算は速いのでMath.sqrtメソッドを使ってください。

以上です。