ちょっと必要になって、最大公約数について調べたところ…
数が2個の場合は検索ですぐに出てくるんですが
3個以上の数、になるとあまり見かけないなーということで
試しに作ってみました。
(結果の証明は省きます)
(おさらいを兼ねて)数が2個の場合
最大公約数
ユークリッドの互除法を用いるのが有名みたいですね～。
- 2数の剰余が0になったら、『割られる数』＝『最大公約数』・・・①
- そうでなければ2数を『割る数』と『2数の剰余』として①を再度計算
ということらしいので、以下のような処理が多いかと思います。
function gcd($a, $b) {
if ($b === 0)
return $a;
return gcd($b, $a % $b);
}
echo gcd(1071, 1029); // 21
最小公倍数
最小公倍数を見ると、2数に限っては
- 『最小公倍数』と『最大公約数』を掛け合わせると、2数の積になる
という性質があるみたいですね～。
つまるところ、『2数の積』を『最大公約数』で割ったものが『最小公倍数』
ということなので、gcd関数を流用して以下のような感じに。
function gcd($a, $b) {
if ($b === 0)
return $a;
return gcd($b, $a % $b);
}
function lcm($a, $b) {
return $a * $b / gcd($a, $b);
}
echo lcm(1071, 1029); // 52479
数が3個以上の場合は？
本題はこっち。
まず調べる数が不定なので、引数を配列に変更してみます。
次にアルゴリズム部分ですが、数が増えたとは言っても
変数a,b,cについて
- 『aとbとcの最大公約数』 ＝ 『aとbの最大公約数』と『c』 の最大公約数
- 『aとbとcの最小公倍数』 ＝ 『aとbの最小公倍数』と『c』 の最小公倍数
という関係になるので、やはり再帰にすれば問題はなさそうです。
というわけで
クラスにしたりなんだりを経て、できあがったものがこちらです！
(キュー〇ー3分クッキングのテーマに乗せて)
※gitに移しました
法則に沿っているだけなので、コードの実装の詳細は省きますが
テクニックっぽいものとしては以下です。
必要に応じて参照渡しで
// 値渡し
ini_set('memory_limit', '1024M');
echo MathAppend::gcd(array_fill(0,6500,1)); // Fatal error: Allowed memory size of 1073741824 bytes exhausted...
// 参照渡し
ini_set('memory_limit', '16M');
echo MathAppend::gcd(array_fill(0,13000,1)); // 1
使用メモリを1/64にして、更に要素数を倍にしても余裕で処理できる！ すごい！
calcGCD/calcLCMの中で、配列長を変更しているため
値渡しだとその都度新しい配列が生成されてしまうので
特に要素数が多い場合、参照渡しにしないと厳しいです。
getGCD/getLCMの方も参照渡しを試してはみたのですが、
処理時間が増加するという結果になったのでお蔵入りに。
配列からの値の取り出し方
2数を取得する際、indexを0と1でベタ書きできるので
コード中のarray_popの部分は、最初array_shiftで作ってました。
が、
$a = array();
for ($i=1;$i<=6500;$i++) {
$a[] = $i;
}
// array_shift
$s = microtime(true);
MathAppend::gcd($a);
echo (microtime(true) - $s); // 2.04~2.05secくらい
// array_pop
$s = microtime(true);
MathAppend::gcd($a);
echo (microtime(true) - $s); // 1.94~1.95secくらい
と、処理時間にそれなりの差が出るようなのでarray_popに変更しました。
array_shiftが『全要素が前詰めされる』のに対して
array_popだと『最後の1要素がなくなる』だけですしね！
まとめ
更にメモリ消費を抑えたり、処理時間を減らしたりなどのコード面の課題や
実はもっと単純なアルゴリズムがあるかも！ などの数学面の課題もありますが～
数学アルゴリズムをコードに落とすのって意外と楽しいです。
みんなもアルゴリズム使ってね！