[PHP] 最大公約数を計算する関数 (gmp_gcd)

PHPGMP関数, 最大公約数, 約数

以前に最大公約数を求める関数を作成しました。

しかし!なんと! GMP関数に最大公約数を計算する関数が既にありました。

無知でした。

参考までに以下の投稿になります。

ということで、自分で作った関数と、この関数を比較してみます。

まずは「gmp_gcd」について確認。

gmp_gcd関数

説明

パラメーターに2つの数字を指定してそれらの最大公約数を計算します。

パラメーター

a

b

a,bともにPHP 5.5 以前での GMP 数リソース、PHP 5.6 以降での GMP オブジェクト、あるいは数値に変換可能な数値形式の文字列です。要するに数字ですね。

返り値

a と b の両方を割り切ることができる正の数を GMP 数で返します。

$c = gmp_gcd("18", "24");

これだけでOkです。

では、自作の関数と処理速度を比較

自作関数との処理速度比較

ではmicrotime関数を使って処理時間を計測してみましょう。

//約数を調べる関数
function divisor($num) {
$limit = sqrt($num);
for($i=1;$i<=$limit;$i++) {
if($num%$i == 0) {
$j[] = $i;
$k = $num/$i;
if ($i!=$k) {
$j[] = $k;
}
}
}
sort($j);
return $j;
}

//調べる2つの値
$a = 15;
$b = 180:

$mt1 = microtime(true); //計測開始

//a,bそれぞれの約数を配列に格納
$c = divisor($a);
$d = divisor($b);

//公約数をチェック
$e = array_intersect($c, $d);

//最大公約数をチェック
$f = end($e);

$mt2 = microtime(true); //自作関数の処理終了およびgmp_gcd関数の処理開始

$g = gmp_gcd("{$a}", "{$b}");

$mt3 = microtime(true); //gmp_gcd関数の処理終了

$r1 = $mt2 - $mt1; //自作関数の処理時間
$r2 = $mt3 - $mt2; //gmp_gcd関数の処理時間

//処理時間を見やすく小数点以下8桁に
echo "自作関数の処理時間 - " .sprintf('%0.8f',$r1);
echo "gmp_gcd関数の処理時間 - " .sprintf('%0.8f',$r2);

結果は… gmp_gcd関数の圧勝です。

$a = 15 $b = 180 で検証した結果は以下のようにばらつきがあり、たまに自作関数のほうが早かったりもしました。


自作関数
gmp_gcd関数
1回目
0.000172140.00009394
2回目0.000216010.00004196
3回目0.00013304 0.00009704
4回目0.00015116 0.00003386
5回目0.00008392 0.00009918
6回目0.00013804 0.00002408
7回目0.00012803 0.00002885
8回目0.00009513 0.00003695
9回目0.00009108 0.00011206

しかし、検証する数字を大きくするとその差が顕著になりました。

$a = 78547964 $b = 614558



自作関数
gmp_gcd関数
1回目
0.00449896 0.00027299
2回目 0.00217199 0.00016904
3回目 0.00582504 0.00005984
4回目 0.00339293 0.00006700
5回目 0.00297999 0.00006795
6回目 0.00305319 0.00006890
7回目 0.00318217 0.00004101
8回目 0.00259995 0.00011706
9回目 0.00229311 0.00002503

でも、自作関数だと約数も出せるし… ということでサンプルページも引き続き自作関数でやります。