2016.02.12

整数の平方根計算

はじめに

整数足し算引き算だけで整数平方根を計算する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
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
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ソースコード

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

001
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文無限ループを作っています。

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

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

025
026
027
028
029
030
031
032
	// メイン
	public static void main( String[] args ) {
		int i;

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

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

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

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

以上です。

関連コンテンツ

平方根の意味と、Math.sqrtメソッドの使い方をソースコードを使って詳しく解説しています。

2020.03.23

数学に関係するJavaのメソッドやソースコードなどを紹介しています。

2022.10.25

変数やクラスに格納されている値をコンソール出力する方法は?

2020.03.23

メソッドの定義方法を詳しく解説しています。Javaのサンプルソースコードを使った説明もあります。

2020.03.23

メソッドを抜けるときに使用するreturn文について説明しています。

2020.03.20

処理を繰り返すために使用するwhile文について解説しています。

2016.01.26

条件式を判断して処理を分岐する方法を詳しく説明しています。

2023.03.20

基本的な計算である足し算(加法)/引き算(減法)/掛け算(乗法)/割り算(除法)を行うプログラム作成。

2020.03.23

画像フォーマット形式・色・大きさ・傾きなどの変更、特定の図形(文字・記号など)を見つけたり、取り出したりする画像処理について詳しく解説。

2015.11.29

Javaの学習に役立つソースコードを多数紹介しています。是非、ご覧ください。

2022.09.10

Javaを使った簡単な応用プログラム(生年月日から年齢を計算プログラムなど)を紹介しています。

2022.07.07

プログラミング、ITに関する用語をまとめています。

2022.10.17

繰り返し処理の作り方を解説しています。

2016.03.02

繰り返し処理(ループ)から強制的に抜けかたについて解説しています。

2017.07.14

プログラムの最初に実行されるメソッドは?

2022.12.13

プログラミングで使う変数って何?

2020.03.23

Javaのプログラムを書いてみませんか?プログラムの書き方をくわしく説明しています。

2020.03.23

「Javaソースコード」から実行可能な「オブジェクトコード」に変換する方法をくわしく説明しています。

2020.03.23

Javaのプログラムを作ってみませんか?プログラミングに必要なものの用意から実行までを説明しています。

2020.03.23

Swingパッケージを使ってグラフィック表示を行う方法を解説しています。

2020.03.23

繰り返し処理を使ったJavaのソースコードサンプルを紹介しています。

2020.03.23

配列を使うJavaソースコードを多数紹介しています。

2021.05.18

三角形、台形、円などいろいろな図形の面積を計算するプログラムを紹介しています。詳しくは、記事をご覧ください。

2021.05.18

StringクラスとStringBuilderクラスを利用したプログラミングの仕方を紹介しています。

2016.12.16

日本で使われてきた伝統文様「和柄」について解説しています。

2022.07.27

プログラミング言語とは?種類や特徴について説明しています。

2022.08.03

自然数と整数って何が違う?

2020.03.23

アルゴリズムって何?

2022.12.29

Javaプログラムの構成について解説しています。詳しくは、こちらをご覧ください。

2020.03.23

for文で変数名iがよく使われる理由について説明しています。興味のある方は是非。

2022.08.29

コンピューター(computer)の意味を説明しています。

2022.07.22

「ゆるゆるプログラム」のコンテンツを紹介しています。興味のある方はこの記事をご覧ください。

2020.03.23

広告