アルゴリズム-最大公約数

最大公約数は古典的な数学問題であり、この問題には4つの共通の解法、質因数分解法、短除法があるが、比較的よく使われているのは転がり相除法であり、アルゴリズムはヨーロッパの著作「幾何学の元」から出ており、もう1つは「九章算術」から出た更相減損法であり、一般的に実現されるときは転がり相除法によって実現される.基本的な論理は,aとbの最大公約数をf(a,b)として表し,a>=b>0とすると仮定する.今k=a/b、m=a%bを取ると、a=k*b+mとなり、m=a-k*bに変形する.xおよびyはf(a,b)によって除去され、mはf(a,b)によっても除去され、f(a,b)=f(b,a%b)である.
ループ値
上記の論理に基づいて、2つの数字a,bを定義し、まずmod=a%bの余剰数を定義し、それからbをaに割り当て、modをbに割り当て、ループを飛び出してaを返すのが最大公約数であり、コードは以下の通りである.

-(NSInteger)maxDivisor:(NSInteger)a secondNumber:(NSInteger)b{
    if (a<b) {
        a=a+b;
        b=a-b;
        a=a-b;
    }
    while (b!=0) {
        NSInteger  mod=a%b;
        a=b;
        b=mod;
    }
    return a;
}

転々とした相殺再帰版
サイクルの理解から、再帰的に実現することができます.

-(NSInteger)maxmodRecursive:(NSInteger)a secondNumber:(NSInteger)b{
    if (a<b) {
        a=a+b;
        b=a-b;
        a=a-b;
    }
    if (b==0) {
        return a;
    }else{
        return [self maxmodRecursive:b secondNumber:a%b];
    }
}

転々とした変形
転がり相除法は大整数に対して最大公約数を求め、転がり相除法の効率にボトルネックが現れ、大整数にとって型取り演算(除法に用いる)のオーバーヘッドは非常に高価であり、これはユークリッドアルゴリズムの限界であり、実際にはユークリッドの転がり相除法を参考に最適化することができる.1つの数学的知識は,2つの数の最大公約数が比較小数と2つの数の差の間の公約数に等しいことを認識する必要がある.「-」演算、すなわちf(a,b)=f(a−b,b)とすることができる.

-(NSInteger)maxRecursive:(NSInteger)a secondNumber:(NSInteger)b{
    if (a<b) {
        a=a+b;
        b=a-b;
        a=a-b;
    }
    if (b==0) {
        return a;
    }else{
        return [self maxRecursive:b secondNumber:a-b];
    }
}

大数演算問題は,aとbの差が大きいとアルゴリズムの反復回数が高すぎてアルゴリズムの効率が低くなり,a=1000,b=1と他の最適化を考慮しなければならないという形式で解決された.
シフト演算
上記の方法は大きな整数と反復の問題に対してよく解決できず、シフト演算によって以上の問題をよく解決することができます.
(1)b=k*b 1の場合、a=k*a 1.f(a,b)=k*f(a 1,b 1)
(2)a=p*a 2の場合、pは素数であり、b%p!=0でf(a,b)=f(p*a 2,b)=f(a 2,b)
そこで私たちは次の解決策を得ました.
p=2、
a,bがいずれも偶数であれば、f(a,b)=2*f(a/2,b/2)=2*f(a>>1,b>>1);
aが偶数であれば、bは奇数であり、f(a,b)=f(a/2,b)=f(a>>1,b);
aが奇数であれば、bは偶数であり、f(a,b)=f(a,b/2)=f(a,b>>1);
aとbが共に奇数であれば、f(a,b)=f(b,a−b)である.このときa−bは必ず偶数であり,次は必ず2で除算され,アルゴリズムの時間的複雑度はO(log 2(max(a,b))である.

-(NSInteger)maxLogic:(NSInteger)a secondNumber:(NSInteger)b{
    if (a<b) {
        a=a+b;
        b=a-b;
        a=a-b;
    }
    if (b==0) {
        return a;
    }else{
        //a   
        if ((a&1)==0) {
            //b   
            if ((b&1)==0) {
                return [self maxLogic:a>>1 secondNumber:b>>1]<<1;
            }else{//b   
                return [self maxLogic:a>>1 secondNumber:b];
            }
        }else{//a   
            //b   
            if ((b&1)==0) {
                return [self maxLogic:a secondNumber:b>>1];
            }else{//b   
                return [self maxLogic:b secondNumber:a-b];
            }
        }
    }
    return 0;
}

シフト演算と減算により,大整数除算を避け,アルゴリズムの効率を向上させ,常に検討する必要があるものもある.