ゆるゆるプログラミング

・整数の平方根計算

整数の足し算と引き算だけで整数平方根を計算するJavaのプログラムを解説します。ここで紹介する平方根の計算は、与えられた整数平方根整数部を求めるもので小数点以下は切り捨てです。

ここから平方根を求める方法について説明します。まず、下の表を見てください。一番左の数値が平方根の解で、真ん中が平方根の解を持つ整数を全て列挙したものです。そして、その個数を一番右の平方根の解を持つ整数の個数に書いています。この表から平方根の解が1つ増えると平方根の解を持つ整数の個数が2つ増えることがわかります。

平方根の解 平方根の解を持つ整数 平方根の解を持つ整数の個数
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 ← クリックしてダウンロードページに移動
001:    public class SqrtInt {
002:    	// 整数型の平方根計算メソッド
003:    	private static int sqrt_intger( int num )
004:    	{
005:    		// 1以下なら元の値を戻す
006:    		if ( 1 >= num ) return num;
007:    
008:    		// 平方根の解が1になる整数の数(1と2と3の3個)
009:    		int c = 3;
010:    
011:    		// ループ回数(平方根の解)
012:    		int count = 1;
013:    
014:    		// ループ
015:    		while ( true ) {
016:    			num -= c;
017:    			if ( 0 >= num ) break;
018:    			c += 2;
019:    			++ count;
020:    		}
021:    		return count;
022:    	}
023:    
024:    
025:    	// メイン
026:    	public static void main( String[] args ) {
027:    		int i;
028:    
029:    		for ( i = 0; i <= 50; ++ i ) {
030:    			System.out.println( i + "の平方根=" + sqrt_intger( i ) );
031:    		}
032:    	}
033:    }

SqrtIntを実行

C:\talavax\javasample>java SqrtInt

0から200の平方根を計算した結果を表示します。(一部抜粋)

SqrtInt.javaの出力結果

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

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

001:    public class SqrtInt {

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

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

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

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

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

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

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

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

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

014:    		// ループ
015:    		while ( true ) {

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

016:    			num -= c;
017:    			if ( 0 >= num ) break;
018:    			c += 2;
019:    			++ count;

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

025:    	// メイン
026:    	public static void main( String[] args ) {
027:    		int i;
028:    
029:    		for ( i = 0; i <= 50; ++ i ) {
030:    			System.out.println( i + "の平方根=" + sqrt_intger( i ) );
031:    		}
032:    	}

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

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

■■関連コンテンツ

平方根 Math.sqrtの使い方について解説
繰り返し処理に使用するwhile文について解説-画像

while文

繰り返し処理に使用するwhile文について解説

条件による処理の分岐に使用するif文について解説-画像

if文

条件による処理の分岐に使用するif文について解説

■新着情報

2020.09.03 お札とコインの数 必要なお札と硬貨の枚数?
2020.08.27 ポーカーの役判定 ポーカーの役を判定
2020.08.25 ゾロ目の出る確率 サイコロの目のでる確率は?
2020.08.24 文字列配列をint配列に変換 String[]→int[]
2020.08.24 文字列配列をdouble配列に変換 String[]→double[]
2020.08.19 キーボード入力値を配列に格納 キーボード入力→配列
2020.08.19 キーボード入力値をリストに格納 キーボード入力→リスト
2020.08.19 キーボード入力 ScannerクラスとSystem.inを使用

■広告

フィギュア予約最大25%OFF+ポイント5%還元!ホビーサーチ

~約8,000名の受講生と80社以上の導入実績~ 企業向けプログラミング研修ならCodeCamp

日本最大級ショッピングサイト!お買い物なら楽天市場

 

 

 

 

 

 

 

 

 

Topへ