C/C++大量計算

Question

我試圖計算在C程序下面的編號：

result = (3 * pow(2,500000000) - 2) % 1000000000 

2的冪是方式大，以妥善處理=>我的印象我可以使用模以多個步驟拆分計算以減小結果大小。有人有這樣做的策略嗎？任何其他想法？

Thanx提前

馬努

Answer 1

最簡單的方法是通過反覆平方通過在每個步驟中的模量減少求冪。

unsigned long long mod_pow(unsigned long long base, unsigned long long exponent, unsigned long long modulus) 
{ 
    if (exponent == 0) return 1; 
    unsigned long long aux = 1; 
    while(exponent > 1) { 
     if (exponent % 2 != 0) { 
      aux *= base; 
      aux %= modulus; 
     } 
     base *= base; 
     base %= modulus; 
     exponent /= 2; 
    } 
    return (base*aux) % modulus; 
} 

然後可以用它來計算

result = (3*mod_pow(2,500000000,1000000000) - 2) % 1000000000; 

該函數假定該模數的平方不超過64位的範圍。對於更大的模量，事情更復雜。