C / C ++大数计算

我正在尝试在C程序中计算以下数字：

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

2的力量是大到正确处理的方式=>我的印象是我可以使用模数在许多步骤中拆分计算以减小结果大小。 有人有这样做的策略吗？ 还有其他想法吗？

提前完成

马努

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位范围。 对于更大的模量，事情更复杂。