反饋

Stein算法

Stein算法是一種計算兩個數最大公約數的算法，是針對歐幾里德算法在對大整數進行運算時，需要試商導致增加運算時間的缺陷而提出的改進算法。

中文名: Stein算法
性質: 算法

應用: 計算兩個數最大公約數
針對: 增加運算時間的缺陷

Stein算法歐幾里德算法缺陷

歐幾里德算法是計算兩個數最大公約數的傳統算法，無論從理論還是從實際效率上都是很好的。但是卻有一個致命的缺陷，這個缺陷在素數比較小的時候一般是感覺不到的，只有在大素數時才會顯現出來。

一般實際應用中的整數很少會超過64位（當然已經允許128位了），對於這樣的整數，計算兩個數之間的模是很簡單的。對於字長為32位的平台，計算兩個不超過32位的整數的模，只需要一個指令週期，而計算64位以下的整數模，也不過幾個週期而已。但是對於更大的素數，這樣的計算過程就不得不由用户來設計，為了計算兩個超過64位的整數的模，用户也許不得不採用類似於多位數除法手算過程中的試商法，這個過程不但複雜，而且消耗了很多CPU時間。對於現代密碼算法，要求計算128位以上的素數的情況比比皆是，設計這樣的程序迫切希望能夠拋棄除法和取模。

Stein算法算法步驟

1、設置An=|A|、Bn=|B|、Cn=1和n=1

2、如果An=Bn,那麼An(或Bn)*Cn是最大公約數,算法結束

3、如果An=0，Bn是最大公約數，算法結束

4、如果Bn=0，An是最大公約數，算法結束

5、如果An和Bn都是偶數，則An+1=An/2，Bn+1=Bn/2，Cn+1=Cn*2(注意，乘2只要把整數左移一位即可，除2只要把整數右移一位即可)

6、如果An是偶數，Bn不是偶數，則An+1=An/2，Bn+1=Bn，Cn+1=Cn(很顯然啦，2不是奇數的約數)

7、如果Bn是偶數，An不是偶數，則Bn+1=Bn/2，An+1=An，Cn+1=Cn(很顯然啦，2不是奇數的約數)

8、如果An和Bn都不是偶數，則An+1=|An-Bn|/2，Bn+1=min(An,Bn)，Cn+1=Cn

9、n=n+1，轉2

以前的算法有錯誤，因為cn根本就沒有用到。我編程的時候才發現。現在我已經修正了這個錯誤。

Stein算法兩種算法的對比

歐幾里德算法每次迭代中最惡劣的情況是，a=2b-1，這樣，迭代後，r=b-1。如果a小於2^N，這樣大約需要4N次迭代。而Stein算法，每次迭代後，顯然AN+1BN+1≤ ANBN/2，最大迭代次數也不超過4N次。也就是説，迭代次數幾乎是相等的。但是，需要注意的是，對於大素數，試商法將使每次迭代都更復雜，因此對於大素數，Stein算法將更有優勢。

Stein算法C++ 實現

#define　CHECK(a)　(!(1&(a)))//判斷是否被2整除
#define　CLEAN2(a)　while(CHECK(a))a=a>>=1//移除非公因子的2
#define　BIGERA　if(a<b)(t=a,a=b,b=t)//取較大的數為a
int　gcd(int　a,int　b){
　int　c_2=0,t;
　while((CHECK(a))&&(CHECK(b))){
　a=a>>=1;b=b>>=1;c_2++;
　}
　CLEAN2(a);
　CLEAN2(b);
　BIGERA;
　while(a=((a-b)>>1)){
　CLEAN2(a);
　BIGERA;
　}
　return　b<<c_2;
}
//注意，由於百度百科會刪除空格，以上空格皆為全角空格
//異或交換比中間量賦值慢
//前一版在循環中有重複的判斷，在循環的結尾和絕對值處各判斷了一次ab的大小關係，所以效率受到影響
//經過測試，比其他用遞歸的實現稍快，但是非常有限

Stein算法Php實現

function steincore($a,$b) {
    if ($a == 0) {return $b;}
    if ($b == 0) {return $a;}
    while (($a & 1) == 0) {
        $a=$a>>1;
    }
    if ($a<$b) {
        $b=($b-$a)>>1;
        return steincore($b,$a);
    }
    else {
        $a=($a-$b)>>1;
        return steincore($a,$b);
    } 
}
function stein($a,$b) {
    $c=0;
    while ((($a & 1)==0)&&(( $b & 1 )==0)) {
        $a=$a>>1;
        $b=$b>>1;
        $c=$c+1;
    }
    if (($a & 1) == 0) {
        $a=$a>>1;
        return steincore($a,$b)<<$c;
    }
    else {
        return steincore($b,$a)<<$c;
    }
}

//通過改善流程省去了低效的a，b交換，同時用while循環代替了過多的遞歸，以節約空間和時間。
//迭代過程化為子過程以減少不必要的判斷
//子過程中只有減法運算後的值可能為偶數所以只需要對$a判斷是否為偶數

Stein算法javascript實現

function stein(a,b) {
    if (a==0) {return b;}
    if (b==0) {return a;}
    var c=0;
    while (((a & 1)==0)&&(( b & 1 )==0)) {
        a=a>>1;
        b=b>>1;
        c=c+1;
    }
    while ((a & 1)==0) {
        a=a>>1;
    }
    while ((b & 1)==0) {
        b=b>>1;
    }
    if (a<b) {
        b=(b-a)>>1;
        var r=stein(b,a)<<c;
        return r;
    }
    else {
        a=(a-b)>>1;
        var r=stein(a,b)<<c;
        return r;
    }
}


//基於php版修改而成

Stein算法優化的C實現

^[1]

int gcdcore(int a,int b) {
    if (a==0) return b;
    if (b==0) return a;
    while ((a & 0x1)==0) {
        a=a>>1;
    }
    if (a<b) {
        b=(b-a)>>1;
        return gcdcore(b,a);
    }
    else {
        a=(a-b)>>1;
        return gcdcore(a,b);
    }
}
int gcd(int a,int b) {
    int c=0;
    while (((a & 0x1)==0)&&(( b & 0x1 )==0)) {
        a=a>>1;
        b=b>>1;
        c++;
    }
    if ((a & 0x1) == 0) {
        a=a>>1;
        return gcdcore(a,b)<<c;
    }
    else {
        return gcdcore(b,a)<<c;
    }
}

Stein算法Ruby實現

def steincore(a,b)
        a === 0 ? (return b) :
        b === 0 ? (return a) :
        a=a>>1 while ((a&1)===0)
        a<b ? (return steincore((b-a)>>1,a)) : (return steincore((a-b)>>1,b))
end
def GCD(a,b)
        c=0
        a,b,c=a>>1,b>>1,c+1 while ((a & 1 === 0)&&( b & 1 === 0))
        ((a & 1)===0) ? (a=steincore(a,b)) : (a=steincore(b,a))
        return (a << c)
end

Stein算法Pascal實現

function stein(a,b :longint):longint;

Begin

if a ＜b then

begin

a:=a xor b;

b:=a xor b;

a:=a xor b;

end;

if b = 0 then exit(a);

If (a and 1 = 0) and (b and 1 = 0) then exit(stein(a shr 1,b shr 1) shl 1);

If (a and 1 = 0) then exit(stein(a shr 1,b));

If (b and 1 = 0) then exit(stein(a,b shr 1));

exit(stein((a+b)shr 1,(a-b)shr 1));

End;

參考資料

1. 優化stein算法．百度空間[引用日期2013-11-09]

詞條統計

瀏覽次數：次
編輯次數：32次歷史版本
最近更新： thereforenay （2024-01-23）

1 歐幾里德算法缺陷
2 算法步驟
3 兩種算法的對比
4 C++ 實現
5 Php實現
6 javascript實現
7 優化的C實現
8 Ruby實現
9 Pascal實現