ユークリッドの互除法:言語問わず

アルゴリズムの勉強をしてるのですが解らないところがあるので教えてください
m < nであれば入れ替えるとあります、確かに入れ替えれば計算が1回分少なくなりますが条件式で入れ替えの作業が3回増えますよね。
人間の頭で計算する場合も入れ替えたほうが有利だとも思います。
でも、この入れ替えの条件式が有ろうがなかろうが答えは結局同じになるような気がするのですが条件式が有る意味はなんですか？

int m = 128, n = 72, d;

if (m < n){
int tmp = m;
m = n;
n = tmp;
}
do{
d = m % n;
m = n;
n = d;
} while (d != 0);

行動規範の内容に同意します

回答6件

ベストアンサー

... 条件式が有る意味はなんですか？...

m > n になるような処理をする理由は、 % の計算回数を減らすためです。

プログラムを少し書き換えてみます。

m, n をコマンドラインで指定できるようにする
m < n なら m と n を swap してから計算をするかを指定できるようにする
% の計算の回数を数えるようにする

$ gcc xx.c
$ ./a.out 129 72 0
のようにして実行します。
(これは m = 120, n = 72, m > n になるような入れ替えはしないで実行します)

swap　をしないと、% の計算回数が１回、多くなってしまいます。

xx.c

c
1#include <stdio.h>
2#include <stdlib.h>
3
4int main(int argc, char** argv) {
5  if (argc != 4) {
6    printf("usage: $ %s m n [0|1]\n", argv[0]);
7    return -1;
8  }
9
10  int m = atoi(argv[1]);
11  int n = atoi(argv[2]);
12  char swap = atoi(argv[3]);
13
14  if (swap != 0) {
15    // gcd(m, n) = gcd(n, m)
16    if (m < n) {
17      int tmp = m;
18      m = n;
19      n = tmp;
20    }
21  }
22
23  // gcd(m, n) = gdc(n, m % n) (m >= n に対して)
24  int count = 0;
25  do {
26    int d = m % n;
27    count++;
28    m = n;
29    n = d;
30  } while (n != 0);
31  printf("count=%d\n", count);
32  printf("%d\n", m);
33  return 0;
34}

ほんとうに swap することが有効なのかを実験してみます。
(m = 1.. 1000, n = 1...1000 の組に対して最小公約数を求める処理を行い、その処理時間を計測してみました。
1.. 20000 で、swap なし約 41 秒
1.. 20000 で、swap あり約 39 秒
40 秒に対して 2 秒の差つまり 5 % ほどですが、
swa0 の手間をかけて % 計算の回数を減らした方が処理時間が短くなりました。
(5 % の差は消費税 8 % と比較して考えれば、それなりに大きな差であることが感じられるとおもいます)

xx1.c

c
1#include <stdio.h>
2#include <stdlib.h>
3
4int main(int argc, char** argv) {
5  int num = atoi(argv[1]);
6  int swap = atoi(argv[2]);
7  long count = 0;
8
9  for(int m0 = 1; m0 <= num; m0++) {
10    for(int n0 = 1; n0 <= num; n0++) {
11      int m = m0;
12      int n = n0;
13      if (swap != 0) {
14        if (m < n) {
15          int tmp = m;
16          m = n;
17          n = tmp;
18        }
19      }
20
21      do {
22        count++;
23        int d = m % n;
24        m = n;
25        n = d;
26      } while (n != 0);
27      // printf("gcd(%d, %d)=%d\n", m0, n0, m);
28
29    }
30  }
31  printf("count=%ld\n", count);
32  return 0;
33}

さらに参考として再帰をつかった版も書いてみました。
do .. until でループさせるよりも、
gcd(m, n) = gcd(n, m % n)
をより素直にプログラムコードにしたことになります。

xxr.c

c
1#include <stdio.h>
2#include <stdlib.h>
3
4int count = 0;
5
6int gcd(int m, int n) {
7  if (m < n) {
8    int t = m;
9    m = n;
10    n = t;
11  }
12
13  if (n == 0) {
14    return m;
15  }
16  count++;
17  return gcd(n, m % n);
18}
19
20int main(int argc, char** argv) {
21  int m = atoi(argv[1]);
22  int n = atoi(argv[2]);
23
24  count = 0;
25  printf("%d\n", gcd(m, n));
26  printf("count=%d\n", count);
27  return 0;
28}

投稿2018/03/18 08:02

編集2018/03/18 13:19

katoy

総合スコア22324

退会済みユーザー

2018/03/18 12:58

わざわざ検証までしていただきありがとうございました。いままで何も考えずに剰余算をやってました、恥ずかしい話ですが初心者には思いもよらないような事がいっぱいありますね。勉強になりました。ありがとうございました。

katoy

2018/03/18 13:33

数学とコンピュータプログラムの溝については、　　http://www.neowing.co.jp/product/NEOBK-1812179 　　その数式、プログラムできますか? をよむとよいです。ユークリッドの互除法をプログラムコードにすることについても述べられています。

行動規範の内容に同意します

アルゴリズムのことはわかりませんが、
そこで入れ替えないと結果は変わってきますが、それはいいんでしょうか？

d=m%n; で、n>m だとd==m になってしまいますねー

ああ、結局あとの処理で入れ替わるので最終的な結果は同じということですか。

なら、最初に入れ替えることで、後のループが１回少なくできるってことですね。
単純なデータ移動より、演算するほうがはるかに実行時間がかかりますから

投稿2018/03/18 00:17

編集2018/03/18 00:30

y_waiwai

総合スコア87774

y_waiwai

2018/03/18 00:28

ああ、結局あとの処理で入れ替わるので最終的な結果は同じということですか。なら、最初に入れ替えることで、後のループが１回少なくできるってことですね。単純なデータ移動より、演算するほうがはるかに実行時間がかかりますから

退会済みユーザー

2018/03/18 12:52

解答有りあがとうございました。勉強になりました。

行動規範の内容に同意します

1回のループで%演算以外に入れ替えを行い、かつ、0であるかの確認を行っています。条件文を入れなかった場合にかかる処理はループ1回ですが、演算は一つではありません。なので、比較するのは次の処理です。

比較演算(大小) + 条件ジャンプ(if) + 代入3回(入れ替え)
剰余演算 + 代入3回(剰余算結果等の代入) + 比較演算(0かどうか) + 条件ジャンプ(while)

最適化やCPUに命令があるかどうかによって比較演算や条件ジャンプの処理が異なると言えば異なるのですが、ifとwhile、大小と0一致がおなじコストだった場合、純粋に剰余演算分の処理が増えていることになります。モダンCPU命令のクロックサイクル数 - Qiitaによると、現在のx86/x64でも整数の剰余演算は他に比べてかなりコストが高い処理のようです。

ただ、この考察には半分の確率で条件分岐自体が不要であることも考慮する必要があります。つまり、大小の入れ替えが不要だった場合は

比較演算(大小) + 条件ジャンプ(if)

分が丸々損であると言うことです。ですが、期待値で行くと半分になりますので、

(コスト(比較演算) + コスト(条件ジャンプ)) / 2 <=> コスト(剰余演算)

上の符号がどちらになるかと言うことをシビアに検討しないと、わからないと思います。あとは、言語や環境、CPUによりますので、実測するしかないでしょう。

投稿2018/03/18 03:37

raccy

総合スコア21735

catsforepaw

2018/03/18 04:57

> 比較演算(大小) + 条件ジャンプ(if) > 分が丸々損であると言うことです。比較自体は加減算と同程度(単純な代入命令とも同程度)なので、命令数が1個増えたところでほとんど無視できるレベルかと思います。条件分岐に関しては、質問にあるコードのif文程度なら、おそらくフラグ判定付きの代入命令に置き換わるでしょう。フラグ判定付きといえども所詮代入命令なので、それが2,3個増えたところで、その後のループにおける条件分岐と除算に比べれば、やはり無視できる程度のコストだと思います。とは言いつつも、それはC/C++に関する考察なので、言語が違えばそれが当てはまらない場合もあるでしょうね。特にインタープリタ方式の言語ではだいぶ事情が変わってくると思います。

退会済みユーザー

2018/03/18 12:55

解答ありがとうございました。演算をそこまでシビアに考えるというのも奥が深いですね。勉強になりました。

行動規範の内容に同意します