python~gcd~最大公約数

初めに

こんにちは、keymaleです。久しぶりの更新です。googleに言われてads.txtを入れたら、閲覧数と広告費が増えたので一定の効果がある、というかgoogleはこれを評価してるんだなと思って少しやる気が出てきたので書きます。

最大公約数、プログラミングではよくgcd(greatest common divisor)と略されますね。atcoderを始めたのですが、よくgcdに関する問題が出るので、関数としてまとめておこうと思った次第です。再帰関数で作るものと、非再帰関数のものを紹介し、最後に速さを比較したいと思います。

gcd 再帰関数

再帰関数で記述する場合は以下のようになります。

ユークリッドの互除法を使って、ひたすら割り切れなくなるまで繰り返します。繰り返しを再帰で表現しています。再帰なので往復のループ分時間がかかるかもしれません。

gcd 非再帰関数

非再帰関数で記述する場合は以下のようになります。

再帰関数同様ユークリッドの互除法でひたすら割ってます。非再帰のほうがループ回数が少ないので、実行時間が短いことが予想されます。

実行時間比較

今回は、再帰関数、非再帰関数、mathモジュールからimportしたgcdで比較します。比較用のコードは以下になります。

gcdの引数を1~1000までをそれぞれ変えて、1000000回計算して、その時の時間を図りました。結果は以下の通りです。

  • 再帰関数gcd  1.93 sec
  • 非再帰関数gcd 1.22 sec
  • math.gcd 0.48 sec

再帰関数より、非再帰関数で記述したほうが早いことがわかります。また、pythonで関数を書くとループ数と割り算の処理が律速して遅くなります。mathモジュールはC言語で記述されているため圧倒的に高速です。pythonでコンテストに出る際はmathモジュールを使いましょう。
c++とかはこの記事を参考にgcdの関数をチートシートとして持っておくといいでしょうか。今回はこの辺で終わりにします。