算法为大数非常大的数字（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++）

回答

相关问题