最大公約数の二つのアルゴリズムを求めます.
4159 ワード
ユークリッドアルゴリズム-転々相除法
ユークリッドアルゴリズムは2つの数の最大公約数を計算する従来のアルゴリズムであり、理論からも実際の効率からも優れています.しかし、致命的な欠陥があります.この欠陥は素数が小さい時には普通は感じられません.大きな素数の時にしか現れません.一般的に、実際に適用される整数は64ビットを超えることは少ない(もちろん、現在は128ビットが許可されている).このような整数に対して、2つの数の間のモードを計算するのは簡単である.字の長さが32ビットのプラットフォームに対して、32ビットを超えない二つの整数の型を計算するには、一つの命令周期だけが必要で、64ビット以下の整数モデルを計算するのも、幾つかの周期にすぎない.しかし、より大きな素数については、このような計算プロセスは、ユーザによって設計されなければならない.64ビットを超える2つの整数のモデルを計算するために、ユーザは、マルチビットの除算手と同様の試行商法を採用しなければならないかもしれない.このプロセスは複雑であるだけでなく、多くのCPU時間を消費する.現代暗号アルゴリズムに対しては、128ビット以上の素数を計算することが求められています.このようなプログラムを設計するには、除法と型取りを捨てることが切望されます.
欠陥を補ったSteeinアルゴリズム
アルゴリズムの思想:(娘を摘み取る)
J.Steein 1961年に提案されたSteeinアルゴリズムによって、この欠陥がよく解決されました.Steinアルゴリズムは整数のシフトと減算しかありません.Steinアルゴリズムの正確性を説明するために、まず以下の結論に注意しなければなりません.gcd(k a,k b)=k gcd(a,b)は、最大公約数演算と倍乗演算が交換できます.特に、k＝2の場合、2つの偶数の最大公約数は必ず2で割り切れるという説明がなされている.kとbが素数であるとき、gcd(k a,b)＝gcd(a,b)、つまり約2つの数のうちの1つだけが含まれている因子は最大公約数に影響しない.特に、k＝2の場合、偶数と奇数の最大公約数を計算する場合には、まず偶数を2で割っても良い.
ユークリッドアルゴリズムは毎回の反復の中で最も悪い場合は、a=2 b-1であり、このように反復後、r=b-1である.aが2^Nより小さい場合、これは約4 N反復が必要である.Steinアルゴリズムは、反復のたびにAN+1 BN+1≦ANBN/2であり、最大反復回数も4 Nを超えないことが明らかになっている.つまり、反復回数はほぼ同じです.しかしながら、大素数に対しては、試行商法は反復のたびにより複雑になり、したがって大素数に対してはSteinアルゴリズムがより有利になることに留意されたい.
long long Euclid(long long a, long long b)
{
return b == 0 ? a : Euclid(b, a % b);
}ユークリッドアルゴリズムは2つの数の最大公約数を計算する従来のアルゴリズムであり、理論からも実際の効率からも優れています.しかし、致命的な欠陥があります.この欠陥は素数が小さい時には普通は感じられません.大きな素数の時にしか現れません.一般的に、実際に適用される整数は64ビットを超えることは少ない(もちろん、現在は128ビットが許可されている).このような整数に対して、2つの数の間のモードを計算するのは簡単である.字の長さが32ビットのプラットフォームに対して、32ビットを超えない二つの整数の型を計算するには、一つの命令周期だけが必要で、64ビット以下の整数モデルを計算するのも、幾つかの周期にすぎない.しかし、より大きな素数については、このような計算プロセスは、ユーザによって設計されなければならない.64ビットを超える2つの整数のモデルを計算するために、ユーザは、マルチビットの除算手と同様の試行商法を採用しなければならないかもしれない.このプロセスは複雑であるだけでなく、多くのCPU時間を消費する.現代暗号アルゴリズムに対しては、128ビット以上の素数を計算することが求められています.このようなプログラムを設計するには、除法と型取りを捨てることが切望されます.
欠陥を補ったSteeinアルゴリズム
アルゴリズムの思想:(娘を摘み取る)
J.Steein 1961年に提案されたSteeinアルゴリズムによって、この欠陥がよく解決されました.Steinアルゴリズムは整数のシフトと減算しかありません.Steinアルゴリズムの正確性を説明するために、まず以下の結論に注意しなければなりません.gcd(k a,k b)=k gcd(a,b)は、最大公約数演算と倍乗演算が交換できます.特に、k＝2の場合、2つの偶数の最大公約数は必ず2で割り切れるという説明がなされている.kとbが素数であるとき、gcd(k a,b)＝gcd(a,b)、つまり約2つの数のうちの1つだけが含まれている因子は最大公約数に影響しない.特に、k＝2の場合、偶数と奇数の最大公約数を計算する場合には、まず偶数を2で割っても良い.
long long Stein(long long a, long long b) //0 <= b < a
{
long long r = 0;
while(b > 0)
{
if((a % 2 == 0) && (b % 2 == 0))
{
a = a >> 1;
b = b >> 1;
r = r + 1;
}
else if((a % 2 == 0) && (b % 2 == 1))
{
a = a >> 1;
}
else if((a % 2 == 1) && (b % 2 == 0))
{
b = b >> 1;
}
else if((a % 2 == 1) && (b % 2 == 1))
{
a = (a - b) >> 1;
}
if(a < b) swap(a, b);
}
return a << r;
}
ユークリッドアルゴリズムは毎回の反復の中で最も悪い場合は、a=2 b-1であり、このように反復後、r=b-1である.aが2^Nより小さい場合、これは約4 N反復が必要である.Steinアルゴリズムは、反復のたびにAN+1 BN+1≦ANBN/2であり、最大反復回数も4 Nを超えないことが明らかになっている.つまり、反復回数はほぼ同じです.しかしながら、大素数に対しては、試行商法は反復のたびにより複雑になり、したがって大素数に対してはSteinアルゴリズムがより有利になることに留意されたい.