如何以有效的方式計算功率

給定函數使得f（N）= 1^1 * 2^2 * 3^3 ..... N^N。我必須計算f（N）/ f（r）* f（N-r）。我的C代碼在下面給出，但它適用於小的N如5或6如何以有效的方式計算功率

#include<stdio.h> 

unsigned long long power(long x, long y) 
{ 
    unsigned long long temp; 
    if(y == 0) 
     return 1; 
    temp = power(x, y/2); 
    if (y%2 == 0) 
     return temp*temp; 
    else 
     return x*temp*temp; 
} 

int main(){ 
    unsigned long long N,M,Q,r[100001],j; 
    int t,i; 
    scanf("%d",&t); 
    while(t--){ 
     scanf("%llu%llu%llu",&N,&M,&Q); 
     for(i=0;i<Q;i++) 
      scanf("%llu",&r[i]); 
     for(i=0;i<Q;i++){ 
     unsigned long long mult=1; 
      for(j=2;j<=N;j++){ 
       mult=mult*(power(j,j)); 
     } 
      unsigned long long mult1=mult; 
      mult=1; 
      //unsigned long long ans=mult/((power(r[i],r[i]))*(power((N-r[i]),(N-r[i])))); 
      for(j=2;j<=r[i];j++) 
       mult=mult*(power(j,j)); 
      unsigned long long mult2=mult; 
      mult=1; 
      for(j=2;j<=N-r[i];j++) 
       mult=mult*(power(j,j)); 
      unsigned long long mult3=mult; 
      mult=1; 
      unsigned long long ans=mult1/(mult2*mult3); 
      printf("%llu\n",ans%M); 
     } 
    } 
    return 0; 
}

假設中，f（5）= 1^1 * 2^2 * 3^3 * 4^4 * 5^5 = 86400000.如果N非常大N < = 10^5.那麼我怎麼能存儲這麼大的值。任何一個給我一個有效的算法來找到這個值，並將它存儲在任何數組中。感謝您提前。

來源

2014-11-16 user267144

如果你用很長很長的類型，你有-9,223,372,036,854,775,808範圍9,223,372,036,854,775,807。如果你使用花車，你會從3.4E +/- 38（7位數字）中獲得。 http://msdn.microsoft。com/en-us/library/s3f49ktz.aspx – JBaczuk

作爲一個例子，考慮N = 100000和r = 1。然後你有'f（100000）/（f（1）* f（99999））'，它是'100000^100000'。換句話說，答案有500,000個數字。從中可以看出，您需要查找或編寫BigInteger庫。 – user3386109

你不能在等式上做一點代數嗎？ –

對於無符號整數指數，它主要是重複乘法的簡寫（例如x^9是x*x*x*x*x*x*x*x*x）。

要有效計算（減少乘法次數），可以使用臨時計算。例如，對於x*x*x*x*x*x*x*x*x，您可以計算y = x*x並使用y*y*y*y*x代替;並且這是5次乘法而不是8次。也可以執行y = x*x然後z = y*y然後z*z*x將其減至4次乘法。

事實證明，二進制是真棒，使得它非常容易找到所需的乘法的最小數量 - 指數的二進制數字告訴你。

更具體地，（爲無符號整數的指數，忽略溢出）工作的：

result = 1; 
    temp = x; 
    while(exponent != 0) { 
     if((exponent & 1) != 0) { 
      result *= temp; 
     } 
     exponent >>= 1; 
     temp *= temp; 
    } 
    return result;

當然溢出將是一個問題。對於大數字，您需要某種可用於乘法的「大整數」代碼（其中temp和result變量都是「大整數」）。

「大整數」通常只是一個（可變長度）整數數組，其中數組的每個元素表示大數字中的一位數字（例如，「3294位數字的基數4294967296」）。如果你想自己實現，我相信你可以找到乘法和除法的算法;或者如果你沒有合適的C庫。

另一種選擇是使用浮點。我不會推薦這個用於任何超過近似值的東西，因爲在處理大量數據時你會得到精度損失（並且對於「非常大的數字」你仍然會有溢出）。

來源

2014-11-16 12:50:42 Brendan

你可以嘗試：

unsigned long long power(long x, long y) 
{ 
    if(0 == y) return 1; 
    if(1 == y) return x; 

    unsigned long long result = x; 
    for(long i = 2; i < y; i++) 
    { 
     result *= x; 
    } 
    return(result); 
}

來源

2014-11-17 01:56:21 user3629249

你有快速的指數函數：

unsigned long long fastpow(unsigned long long a, int b) 
{ 
    unsigned long long res = 1; 
    while (b) { 
     if (b & 1) res *= a; 
     b >>= 1; 
     a *= a; 
    } 
    return res; 
}

它通常用於加密的環境中，但可以在這裏使用。

正如我在評論中所說的，你試圖寫的函數比事實（N）增長得快，所以你將無法計算出你在問題（10^5）中放置的範圍爲你會得到足夠大的數字，以便它們不容易在任何地方適應。

隨着無符號long long結果，你只能得到：

f(0) -> 1 
f(1) -> 1 
f(2) -> 4 
f(3) -> 108 
f(4) -> 27648 
f(5) -> 86400000 
f(6) -> 4031078400000 
f(7) -> 3319766398771200000 
f(8) -> overflows in 64 bit.

來源

2014-11-17 13:05:44

如何以有效的方式計算功率

回答

相關問題