ロコリンの雑記

アニメ大好きニートのロコリンのブログ。2015年卒(修士)の社会人。学生時代(2010年)から続けてるブログなのでエントリによっては学生ブログと社会人ブログになっています。時系列から察して。
 
 
このブログについて
ブログ内検索
カテゴリ
プロフィール

ロコリン

Author:ロコリン
2018年5月だけニート(6月から会社員)。2015年3月まで大学院生でした。
趣味:アニメ/Twitter/ゲーム/ニコ動
今(2015年2月更新):プリキュア/プリパラ/アイカツ/ごちうさ/艦これ

外部リンク
Twitter

スポンサーサイト 

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

直角 3 角形の各辺の長さの比が自然数の組 (ピタゴラス数) を探す 

2010年12月25日

レポートの図を描いているときに、 3 角形を描いて思い出したことなのですが、
直角 3 角形の各辺の長さの比が自然数のものってなんかいいですよね。
例えば 3:4:5 とか。
それを探すプログラムを暇潰しに作りました。


目次

1. 単純な総当たり法

前提として、直角 3 角形の底辺 \(x\) 、高さ \(y\) 、斜辺 \(r\) のとき、常に次の等式が成り立ちます。 (3 平方の定理、ピタゴラスの定理)

\[x^{2}+y^{2}=r^{2}\]

1.1 C++ による実装 (sankakuInt.cpp)

作ったプログラムのソースコードを貼ります (C++) (ただし better C)。

/**
 * 直角 3 角形の各辺の比が自然数であるものを答えるプログラム ver. 1.00
 * rexpit blog
 * 2010/12/25
 *
 * 使い方
 * コンパイルしてそのまま実行すればおk。
 * コマンドライン引数を指定することで調べる範囲を変えたり、互いに素でないものを表示しなくしたりできる。
 *
 * オプション
 *  [数]
 *   1 ~ [数] までの範囲で調べる。
 *  -c
 *   互いに素でないものを表示しない。
 *  -g
 *   最大公約数 (GCD) を表示する。
 **/

#include <cmath>
#include <iostream>
#include <cstdlib>

/** function gcd(a, b)
 * a と b の最大公約数を求める。
 *
 * 引数:
 *  a, b : 最大公約数を求めたい2数
 *
 * 戻り値:
 *  a, b の最大公約数
 **/
template <typename T>
T gcd(T a, T b) {
	T r;

	while (b != 0){
		r = a % b;
		a = b;
		b = r;
	}

	return a;
}

int main(const int argc, const char *argv[]) {
	unsigned int maxBottom;
	bool flagCoprimeOnly = false;	/* 互いに素でないと出さない */
	bool flagViewGcd = false;	/* 最大公約数を表示する */

	/* [▼ここから▼] コマンドライン引数を解析 */
	try {
		const unsigned int maxBottomLim = (1u << (sizeof(unsigned int) << 2)) - 1;
		unsigned int countArgNumber = 0;	/* 引数が数字から始まるものをカウント */
		maxBottom = (maxBottomLim >> 8) + 1;
		for (int i = 0; i < argc; ++i) {
			if (argv[i][0] == '-') {
				for (int j = 1; argv[i][j] != '\0'; ++j) {
					switch (argv[i][j]) {
						case 'c':
							flagCoprimeOnly = true;
							break;
						case 'g':
							flagViewGcd = true;
							break;
						default:
							throw "The command line arguments are not correct.";
					}
				}
			} else if (argv[i][0] >= '0' && argv[i][0] <= '9') {
				if (countArgNumber >= 1) {
					throw "The command line arguments are not correct.";
				}
				++countArgNumber;
				maxBottom = strtoul(argv[i], NULL, 10);
				if (maxBottom > maxBottomLim) {
					throw "Too big value.";
				}
			}
		}
	} catch (const char *e) {
		std::cerr << e << std::endl;
		return 1;
	}
	/* [▲ここまで▲] コマンドライン引数を解析 */

	/* [▼ここから▼] メイン */
	std::cout << "x\ty\tr" << std::flush;
	if (flagViewGcd) { std::cout << "\tgcd" << std::flush; }
	std::cout << std::endl;
	for (unsigned int y = 1; y <= maxBottom; ++y) {
		for (unsigned int x = 1; x <= y; ++x) {
			const unsigned int r2 = x * x + y * y;
			unsigned int r;
			for (r = (unsigned int)sqrt((double)r2); r * r < r2; ++r);

			if (r * r != r2) { continue; }
			const unsigned int gcdNum = gcd(x, y);
			if (flagCoprimeOnly && gcdNum != 1) { continue; }
			std::cout << x << '\t' << y << '\t' << r << std::flush;
			if (flagViewGcd) {
				std::cout << '\t' << gcdNum << std::flush;
			}
			std::cout << std::endl;
		}
	}
	/* [▲ここまで▲] メイン */
	return 0;
}

ソースコードの色塗りは手作業でやりました。
こういうのはソフトに任せるべきなんでしょうが、まあいいでしょう。
ソースコードを彩色するいいソフトがあったら紹介してください。

あと、 HTML 中にソースコードを書くとき、普通の人は注意すると思いますが、次の文字列置換をしてください。
特に、 & の置換は最初に行ってください。

手順 検索文字列 置換文字列
1 & &amp;
2 < &lt;
3 > &gt;
4 " &quot;

1.2 JavaScript による実装 (ショボ版)

この程度のプログラムなら、 JavaScript に移植して Web ページ上で実装することができると思います。



インタプリタ言語なだけあって C++ で実装したものと比べるとだいぶ遅いです (2010年現在) 。
文字列の出力が最大のボトルネックになっているみたいです。もっといい出力方法はないでしょうか。
C++ をコンパイルできる方 (でこのプログラムを使いたい方) は C++ 版のソースをコンパイルしてみてください。
コンパイルした方がすごく速いです。

1.3 追記

2010年12月26日追記

どうやら、この自然数の組は「ピタゴラス数」と呼ばれているそうです。
そして、それを求める公式のようなものがあるそうです。

\[(m^{2}-n^{2})^{2}+(2mn)^{2} = (m^{2}+n^{2})^{2}\]
\(m\), \(n\) は自然数です。 (\(m\in\mathbb{N}, n\in\mathbb{N}\))

知らなかった...
「ユークリッドの互除法」 (最大公約数を求めるアルゴリズム) を初めて知ったときのような驚きです。
工学部は微積には力を注いでいますが、整数論はほとんどやりません。
でも情報セキュリティ分野では整数論が重要になりますから、あながち無縁でもないと思うのです。
ということで、春休みになったら数論のページでも見て独学してみますか。

2. きれいに整列する総当たり法

2010年12月30日追記

27日は一日中レポートを書いて、28日は一日中ゲームをして、29日は買い物に行ったのですが、
今日、またこのプログラムを作ってみました。
作品集(日本画)と風景写真』の「ピタゴラス数(2) ~さんすう・数学のお勉強~」を参考にしました。
並び順が前回と違います。

2.1 C++ による実装 (pythanum.cpp)

/**
 * ピタゴラス数を答えるプログラム ver. 1.11
 * rexpit blog
 * 2012/ 2/11 v1.11 もうちょっと C++ っぽくした (リファクタリング)
 * 2010/12/30 v1.10 完成
 *
 * 使い方
 * コンパイルしてそのまま実行すればおk。
 * コマンドライン引数を指定することで調べる範囲を変えたり、互いに素でないものを表示しなくしたりできる。
 *
 * オプション
 *  [数]
 *   1 ~ [数] までの範囲で調べる。
 *  -i
 *   入力された数を含む組のみを表示する。
 *  -c
 *   互いに素でないものも表示する。
 *  -g
 *   最大公約数 (GCD) を表示する。
 *  -t
 *   直角三角形の正接 (tanθ) を表示する。
 **/

#include <iostream>
#include <cstdlib>

/** function gcd(a, b)
 * a と b の最大公約数を求める。
 *
 * 引数:
 *  a, b : 最大公約数を求めたい2数
 *
 * 戻り値:
 *  a, b の最大公約数
 **/
template <typename T>
T gcd(T a, T b) {
	T r;

	while (b != 0){
		r = a % b;
		a = b;
		b = r;
	}

	return a;
}

/** class Pythanum
 * ピタゴラス数を表示する。
 **/
class Pythanum {
private:
	int maxBottom;
	bool flagInputOnly;	// 入力された数のみ表示する
	bool flagCoprimeOnly;	// 互いに素でないと出さない
	bool flagViewGcd;	// 最大公約数を表示する
	bool flagViewTan;	// 正接を表示する

public:
	Pythanum();	// コンストラクタで初期設定
	void setOptions(const int argc, const char *argv[]) throw(char *);	// コマンドライン引数で設定
	void operator()(void) const;	// 関数オブジェクトで計算・表示
};

Pythanum::Pythanum() :	// コンストラクタ初期化子による初期設定
	maxBottom(20),
	flagInputOnly(false),
	flagCoprimeOnly(true),
	flagViewGcd(false),
	flagViewTan(false)
{}

void Pythanum::setOptions(const int argc, const char *argv[]) throw(char *) {
	const int maxBottomLim = (1u << ((sizeof(int) << 2) - 1)) - 1;
	int countArgNumber = 0;	// 引数が数字から始まるものをカウント
	for (int i = 0; i < argc; ++i) {
		if (argv[i][0] == '-') {
			for (int j = 1; argv[i][j] != '\0'; ++j) {
				switch (argv[i][j]) {
					case 'c':
						flagCoprimeOnly = false;
						break;
					case 'g':
						flagViewGcd = true;
						break;
					case 'i':
						flagInputOnly = true;
						break;
					case 't':
						flagViewTan = true;
						break;
					default:
						throw "The command line arguments are not correct.";
				}
			}
		} else if (argv[i][0] >= '0' && argv[i][0] <= '9') {
			if (countArgNumber >= 1) {
				throw "The command line arguments are not correct.";
			}
			++countArgNumber;
			maxBottom = atoi(argv[i]);
			if (maxBottom > maxBottomLim) {
				throw "Too big value.";
			}
		}
	}
}

void Pythanum::operator()(void) const {
	std::cout << "x\ty\tr" << std::flush;
	if (flagViewGcd) { std::cout << "\tgcd" << std::flush; }
	if (flagViewTan) { std::cout << "\ttan" << std::flush; }
	std::cout << std::endl;
	for (int x0 = 1; x0 <= maxBottom; ++x0) {
		if ((x0 & 3) == 2) { continue; }	// x0 が偶数で 4 の倍数でないとき飛ばす。
		for (int m0 = x0; m0 > 0; m0 -= 2) {
			// m, n を定める
			if (x0 % m0 != 0) { continue; }	// m0 が約数でないときスルー
			int x = x0;	// 計算するので余計に変数を用意しとく
			const int n = x0 / m0;
			const int m = ((x0 & 3) == 0) ? m0 >> 1 : m0;	// x が 4 の倍数のとき m0 を 2 で割る
			if (m >= n) { continue; }	// m >= n のときスルー

			// y を定める
			int y = n * n - m * m;
			if ((x & 1) == 1) { y >>= 1; }
			if (x > y) { continue; }	// y が x 未満のときスルー
			int gcdNum = gcd(x, y);
			if (gcdNum != 1) { continue; }	// x と y が互いに素でないときスルー

			// r を定める
			int r = m * m + n * n;
			if ((x & 1) == 1) { r >>= 1; }

			// 表示
			const int y0 = y, r0 = r, gcdNum0 = gcdNum;
			for (; x <= maxBottom; x += x0, y += y0, r += r0, gcdNum += gcdNum0) {
				if (flagInputOnly && x != maxBottom && y != maxBottom && r != maxBottom) { continue; }	// オプションで入力した数以外いらないときスルー
				if (flagCoprimeOnly && gcdNum != 1) { break; }	// オプションで互いに素以外いらないときスルー
				std::cout << x << '\t' << y << '\t' << r << std::flush;
				if (flagViewGcd) {
					std::cout << '\t' << gcdNum << std::flush;
				}
				if (flagViewTan) {
					std::cout << '\t' << ((double)y / (double)x) << std::flush;
				}
				std::cout << std::endl;
			}
		}
	}
}

int main(const int argc, const char *argv[]) {	
	try {
		Pythanum pythanum;
		pythanum.setOptions(argc, argv);	// コマンドライン引数を解析
		pythanum();	// メイン
	} catch (const char *e) {
		std::cerr << e << std::endl;
		return 1;
	} catch (...) {
		std::cerr << "\(^o^)/オワタ" << std::endl;
		return 1;
	}
	return 0;
}

2.2 JavaScript による実装 (完全版)

これの JavaScript 版も載せます。



やっぱり JavaScript そのものが遅いのではなく、文字列の出力だけが遅いということがわかりました。
このプログラムのオプションは、表示するものを絞り込むものなのです。
計算回数はほとんど変わりません。
にもかかわらず、表示する行数が少ない方が高速です。
よって、ボトルネックは文字列の出力であることが明らかとなりました。

スポンサーサイト
コメント
はてなダイアリーならソースコードを色分けできますよ。
詳細は上のURLに記事にしました。

C++以外でもHTML/CSS,Java,Python,RUbyなどかなり対応してるっぽい。
Re: はてなダイアリーなら
> おたっくすさん
アドバイスありがとうございます。

ブログを2つ持つのもいいかもしれませんね。
ソースコードはあっちで、雑記 (日記) はこっちでという感じに使い分けられそうです。
はてなで作るときは、しっかり計画を立てて、まとまったブログを作りたいと思います。














 管理者にだけ表示を許可する

トラックバック
 
http://rexpit.blog29.fc2.com/tb.php/38-90ac3340
最新記事
最新コメント
FC2カウンタ
欲しい
最近買ったもの
Amazon 検索
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。