最小公約数(ユークリッドアルゴリズム&&steinアルゴリズム)

2734 ワード

最小公約数を求めて、最も考えやすいのはユークリッドアルゴリズムで、このアルゴリズムも比較的に理解しやすくて、効率もとても良いです.転がり相殺法とも呼ばれる.
任意の2つの数a,b(a>b),d=gcd(a,b),bがゼロでなければgcd(a,b)=gcd(b,a%b)
証明:r=a%b、すなわちkが存在し、a=b*k+rとなると、r=a-b*kとなる.明らかにr>=0、r%d=((a%d)-(b*k)%d)%dは、a%d=b%d=0であるため、r%d=0である.
したがってgcd(a,b)を求めることはgcd(b,a%b)を求めることに移行することができ、これは再帰過程であり、それはいつ再帰が終わるのか、考えてみれば、a,bはゼロではなく、bがゼロである場合を再帰の終了(もちろん他の終了条件でもよい)とすることができ、これは最大公約数を求める方法で他の終了条件である.これが最大公約数を求める方法です.
ユークリッド再帰版:

int gcd(int a,int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

非再帰版:

int gcd(int a,int b)//euclid
{
    int r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

Steinアルゴリズム
ユークリッドアルゴリズムは2つの数の最大公約数を計算する伝統的なアルゴリズムであり,理論的にも効率的にも優れている.しかし、彼には致命的な欠陥があり、この欠陥は大きな素数の時にしか現れない.
ハードウェアプラットフォームは、一般的に整数が最大64ビットであり、このような整数に対して、2つの数の間のモジュールを計算するのは簡単である.ワード長が32ビットのプラットフォームでは、32ビットを超えない2つの整数を計算するモードは、1つの命令周期しか必要ありませんが、64ビット以下の整数モードを計算するのは、いくつかの周期にすぎません.しかし、より大きな素数に対しては、このような計算プロセスはユーザーによって設計されなければならず、64ビットを超える2つの整数のモジュールを計算するために、ユーザーは複数の数除算手算プロセスに類似した試商法を採用しなければならないかもしれない.このプロセスは複雑であるだけでなく、多くのCPU時間を消費している.現代の暗号アルゴリズムでは,128ビット以上の素数の計算が要求される場合が多く,このようなプログラムの設計は除算と型取りを捨てることを切に望んでいる.
SteinアルゴリズムはJ.Steinによって1961年に提案され,この方法も2つの数を計算する最大公約数である.ユークリッドアルゴリズムとは異なり,Steinアルゴリズムは整数のシフトと加減法のみであり,これはプログラム設計者にとって福音である.
Steinアルゴリズムの正しさを説明するためには、まず以下の結論に注意しなければならない.
gcd(a,a)=a,すなわち1つの数と彼自身の公約数はそれ自身である.
gcd(ka,kb)=kgcd(a,b)、すなわち最大公約数演算と倍乗演算を交換することができ、特に、k=2の場合、2つの偶数の最大公約数が必ず2で除けることを説明する.
kがbを除去できない場合、gcd(ka,b)=gcd(a,b)、すなわち、約2つの数のうちの1つだけを含む因子は最大公約数に影響しない.特に、k=2の場合、偶数と奇数の最大公約数を計算する場合、偶数を2で割ってもよい.
アルゴリズムの手順:
1、A=0の場合、Bは最大公約数であり、アルゴリズムは終了する
2、B=0の場合、Aは最大公約数であり、アルゴリズムは終了する
3、A 1=A、B 1=B、C 1=1を設定する
4、AnとBnが共に偶数である場合、An+1=An/2、Bn+1=Bn/2、Cn+1=Cn*2(注意、2を乗じて整数を左に1桁だけシフトすればよく、2を除いて整数を右に1桁シフトすればよい)
5、Anが偶数、Bnが偶数でない場合、An+1=An/2、Bn+1=Bn、Cn+1=Cn(明らかに、2は奇数の約数ではない)
6、Bnが偶数で、Anが偶数でない場合、Bn+1=Bn/2、An+1=An、Cn+1=Cn(明らかに、2は奇数の約数ではない)
7、AnとBnが共に偶数でない場合、An+1=|An-Bn|/2、Bn+1=min(An,Bn)、Cn+1=Cn
8、nプラス1、回転1
よく理解しましょう.実現も簡単で、効率も員アルゴリズムより悪くありません.
実装コードは次のとおりです.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
int stein(int a,int b)
{
    if(a==0) return b;
    if(b==0) return a;
    if(a%2==0 && b%2==0) return 2*stein(a>>1,b>>1);
    else if(a%2==0)   return stein(a>>1,b);
    else if(b%2==0)   return stein(a,b>>1);
    else return stein(abs(a-b),min(a,b));
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d
",stein(a,b));
}

【アルゴリズム】システムとファイル操作

図の遍歴アルゴリズム-馬遍歴盤