大型數學運算C++

Question

我想在C++中進行大型數學運算。

long long h= 4294967295; 
long long d=7910266469; 
long long n=10021211227; 
long long result; 

我需要的計算是這樣的：

h^d mod n

result=pow(h,d) % n; 

我不知道哪種類型的using.Please幫我選擇型數字.. 感謝

Answer 1

看this wikipedia article。 有一個很不錯的例子有以下內存效率的僞代碼：

function modular_pow(base, exponent, modulus) 
    if modulus = 1 then return 0 
    c := 1 
    for e_prime = 1 to exponent 
     c := (c * base) mod modulus 
    return c 

甚至還有beeing內存效率和使用更少的操作的例子。我認爲應該可以從中獲取C++代碼。

如果您使用此方法，您的解決方案的long long應該沒問題。

---

未經測試，但一個簡單的1：從上面的僞代碼1 ...翻譯

long long result = 1; 
int i; 
for(i=0; i<d;i++){ 
    result = (result * h) % n; 
}