算法爲大數非常大的數字（C++）

我想解決Problem 13 @ Project Euler，我正在尋找一個很好的算法來做另外並輸出非常大的數字的答案。首先，我將數字的數字轉換爲矩陣的元素（100 x 50）。這是我想出了算法：算法爲大數非常大的數字（C++）

unsigned long long int sum=0, carry_over=0; 
for(int j=49; j>=0; j--) 
{ 
    for(int i=0; i<100; i++) 
     sum+=num[i][j]; 
    sum+=carry_over; 
    carry_over=sum/10; 
    cout<<sum%10; 
    sum=0; 
} 
cout<<carry_over;

現在，輸出將發生逆轉位，首先是個位數字，在和的第一位結束了。這很容易被人工逆轉。

我想知道這是否是一個很好的算法，考慮到精度和速度。請提出更正以使其更好。

來源

2017-06-25 Truth-seek

更好的方法是使用全範圍的每一個「數字」，因此，例如，如果你有一個64位的計算機，你應該使用'uint64_t'每個數字和存儲全系列各，而不是僅僅爲0〜 10（浪費空間）。 –

爲什麼你開始在每個數字中加上最後一位數字？ [這個問題順便提一下]。 – Peter

@彼得我沒有得到提示。除了最初添加最後一位數字之外，還有什麼其他功能？ –

你的算法已經是最優的。

你的算法有O(m*n)，其中m是在每個數（50）和n的位數是數字（100）的數量的時間複雜度，這是您在輸入有數字量。很容易看出，您必須讀取全部輸入的數字才能輸出正確的答案，因此您必須至少讀取m*n數字，給出的時間複雜度爲O(m*n)只需即可讀取輸入。因此，算法的時間複雜度不能低於此值，因此您的算法是最優的。

如果，不知何故，你已經有輸入數據存儲在RAM（並以適當的格式），你可以考慮一些其他的優化。

代價地址大小：

現代計算機具有32個或64比特的地址的大小，這意味着它們可以在一個操作中做加法在32或64位。 64位是大約18個十進制數字，所以3 64位整數是所有需要來存儲每個整數，因此添加時將複雜性從m=50減少到m=3，使得求和一個數量級更快。

考慮並行處理：

現代計算機可以並行運行多個線程。這個問題的解決方案很容易並行化。如果您的機器能夠同時運行2個線程，則可以使用第一個線程對前50個數字進行求和，並使用第二個線程對第二個50進行求和。在兩個總和完成之後（如果所有事情都是在單個線程上計算的，大約需要一半的時間），只需對兩個子結果進行求和即可。

來源

2017-06-25 07:38:07 Bernard

算法爲大數非常大的數字（C++）

回答

相關問題