gcd 練習 2007/09/17

package gmc;

import java.math.BigInteger;

public class Test {

public static void main(String[] args) {

for (int i = 0; i < 10; i++) {
int m = (int) (Math.random() * 1000000);
int n = (int) (Math.random() * 1000000);

System.out.printf("%d: m=%d n=%d %s %n", i, m, n,
(gcd(m, n) == gcd_o(m, n)));

// System.out.println(gcd(m, n));
// System.out.println(gcd_r(m, n));
// System.out.println(gcd_o(m, n));

}
}

/**
* n,mに対して剰余の演算を行うことができる<br>
*
* 1. 入力をm,nとする。 <br>
* 2. nが0なら、mを出力してアルゴリズムを終了する。<br>
* 3. nがmを割り切るなら、nを出力してアルゴリズムを終了する。 <br>
* 4. そうでないなら、mをnで割った余りを新たにmとし、更にmとnを取り替えて3に戻る。<br>
*
*/
static int gcd(int m, int n) {
int state = 1;
while (true) {

switch (state) {

case 1:
if (m < n) {
int tmp = m;
m = n;
n = tmp;
}
case 2:
if (n == 0)
return m;
case 3:
int r = m % n;
if (r == 0)
return n;
m = n;
n = r;
state = 3;
}
}
}

static int gcd_r(int m, int n) {
if (m < n)
return gcd(n, m);
if (n == 0)
return m;
int r = m % n;
if (r == 0)
return n;
return gcd(n, r);
}

static public int gcd_o(int m, int n) {
return gcd(BigInteger.valueOf(m), BigInteger.valueOf(n)).intValue();
}

static public BigInteger gcd(BigInteger l, BigInteger r) {
return l.gcd(r);
}

}