Steinアルゴリズムは最大公約数を求めます

最大公約数を求めるアルゴリズムといえば、多くの人が転々と相殺法、すなわちユークリッドアルゴリズムを思い出し、アルゴリズム思想は以下の通りである.
2つの整数a,bを与えて、aとbの最大公約数を求め、dがaとbの公約数であれば、aもbとa%bの公約数であり、逆にaがbとa%bの公約数であれば、bもaとbの公約数であり、この考えを利用して、アルゴリズムは以下のように実現される.

int gcd(int a, int b) {
    int t, r;
    if(a < b){
        t = a;
        a = b;
        b = t;
    }
    while(b != 0) {
        r = b;
        b = a % b;
        a = r;
    }
    return a;

}

このアルゴリズムは,マシンワード長タイプの整数に対しては比較的効率的であるが,大きな整数(bigint)タイプを扱う場合には除算演算が必要となり,さらにいくつかのワード長を前に処理するとCPU時間が浪費され,Steinアルゴリズムではシフトと減算で処理され,除算演算がないため,最大公約数を求める場合には比較的効率的である.Steinアルゴリズムの原理は以下の通りである.
1.aとbが偶数であれば、公約数2を記録し、2を除いた(すなわち、右シフト1ビット).
2.いずれかの数が偶数であれば、偶数は2を除きます.この場合、2はこの2つの数の公約数ではないからです.
3.両方が奇数であれば、a=|a−b|,b=min(a,b)であり、dがaとbの公約数であれば、dもa−bとmin(a,b)の公約数であるからである.
以上の原理に基づいて、再帰アルゴリズムは以下のように実現される.

int sgcd(a, b) {
    int t;
    if(a < b){
        t = a;
        a = b;
        b = t;
    }
    if(b == 0) return a;
    if(a % 2 == 0 && b % 2 == 0){
       return 2 * sgcd(a / 2, b / 2);
    } else if(a % 2 == 0 && b % 2 != 0){
        return sgcd(a / 2, b);
    } else if(a % 2 != 0 && b % 2 == 0){
        return sgcd(a, b / 2);
    } else {
        return sgcd(a-b, b);
    }
}

参照先:
http://www.cnblogs.com/drizzlecrj/archive/2007/09/14/892340.html
http://blog.henix.info/blog/stein-gcd-algorithm.html