N次方矩陣乘法.Better方法

我有一個矩陣[2,2] [1,0]。我需要這個2 * 2矩陣的第n個複數。當我使用簡單的乘法時，我可以在O（ n）或O（logn）。 O（LOGN）代碼：N次方矩陣乘法.Better方法

int NUM(int n) 
{ 
    int F[2][2] = {{2,2},{1,0}}; 
    if(n == 0) 
     return 0; 
    power(F, n-1); 
    return F[0][0]; 
} 

/* Optimized version of power() */ 
void power(int F[2][2], int n) 
{ 
    if(n == 0 || n == 1) 
    return; 
    int M[2][2] = {{2,2},{1,0}}; 

power(F, n/2); 
    multiply(F, F); 

if(n%2 != 0) 
    multiply(F, M); 
}

它與n.But的小值相當優良，一旦如果n是10^9或more.int的順序，長整型甚至更長的長整型將無法正常工作所以，我相信這種方法似乎並不是很有幫助。

基本上我的問題是：數字變得非常大，甚至不會長時間的進入int.Then我怎麼處理它。

任何人都可以建議我任何公式或算法來獲得2 * 2矩陣[2,2] [1,0]的n次冪時，n是10^9？

謝謝

來源

2012-07-06 vijay

請說清楚，您是否遇到性能問題（太慢）或溢出問題（數字變得太大，結果變得不正確）？我認爲後者，在這種情況下，這不是算法的錯誤，你需要使用一些bignum庫。 – Thomas 2012-07-06 19:54:18

數字變得相當大，甚至在很長的時間內都不會來。我沒有時間複雜性的問題。 – vijay 2012-07-06 19:56:25

您是否需要一個確切的值，或者只需要模數值很大的值？ – templatetypedef 2012-07-06 19:58:28

這是作業，還是隻是一個練習？如果你有選擇，modulo可能更方便，基本上你可以在每次乘法或乘法後將你的矩陣取模爲M，並且矩陣的單個輸入不會超過（M-1）^ 2，但顯然結果會是模冪運算的一種算法，因此與現在有所不同。

因此，對於無符號長整型，可以使模數達到65535左右，並且無限指數。以某個數字爲模的矩陣的過程很簡單：以每個條目爲模。

請記住，隨着指數增加（週期有多大取決於矩陣和模數的性質），這樣的模冪運算最終會進入一個循環。

的代碼看起來是這樣的（未經測試並沒有特別優雅，非常簡單，只是插入矩陣中的每個乘法後模的）：

/* Raises the matrix to the exponent n, modulo m. */ 
int NUM(int n, int m) 
{ 
    int F[2][2] = {{2,2},{1,0}}; 
    if(n == 0) 
     return 0; 
    power(F, n-1, m); 
    return F[0][0]; 
} 

/* Takes a matrix modulo m. */ 
void modMatrix(int F[2][2], int m) 
{ 
    F[0][0] = F[0][0] % m; 
    F[0][1] = F[0][1] % m; 
    F[1][0] = F[1][0] % m; 
    F[1][1] = F[1][1] % m; 
} 

/* Optimized version of power() - raises a matrix F to the exponent n modulo modulus */ 
void power(int F[2][2], int n, int modulus) 
{ 
    if(n == 0 || n == 1) return; // recursive termination condition 

    int M[2][2] = {{2,2},{1,0}}; // original matrix for multiplication 

power(F, n/2, modulus); // raise the matrix to half the exponent 
modMatrix(multiply(F, F), modulus); // square the matrix to go the rest of the way 

if(n%2 != 0) modMatrix(multiply(F, M), modulus); // if the exponent is odd, multiply one last time 
}

來源

2012-07-06 20:32:34 Thomas

如果可能請包括修改後的代碼。謝謝。 – vijay 2012-07-06 20:36:18

我不確定只給你代碼會對你有多大的用處，但我必須給你自由決定，爲你自己，所以在這裏你去。代碼未經測試，但重要的是您瞭解它。 – Thomas 2012-07-06 20:49:47

對不起，代碼有一個錯誤，現在修復（這就是我得到這麼晚寫代碼......或早...） – Thomas 2012-07-06 21:14:34

因爲它是一個2×2矩陣，一個可行的辦法去是將其展開爲一套 Pauli matrices和一個單位矩陣。然後使用泡利矩陣的性質（正方形是一個單位矩陣等 - 參見鏈接的頁面）來計算第二個冪，這不是一個紙筆練習（見Wiki中的等式（2）上面的鏈接）。

來源

2012-07-07 11:51:47

N次方矩陣乘法.Better方法

回答

相關問題