C / C ++大量的计算 [英] C/C++ Large number calculation

问题描述

我试图计算在C程序下面的编号：

I'm trying to compute the following number in a C program :

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

2的幂的方式是到大得到妥善处理=>我的IM pression下我可以用模，以减少结果的大小在许多步骤拆分计算。是否有人有这样做的策略？任何其他的想法？

The power of 2 is way to large to be handled properly => I'm under the impression I could split the calculation in many steps using the modulo to reduce the result size. Does someone has a strategy for doing so ? Any other idea ?

感谢名单提前

马努

推荐答案

最简单的方法是通过反复平方在每一步的模数降低。幂

The simplest method is exponentiation by repeated squaring reducing by the modulus in each step.

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;
}

然后，您可以用它来计算

You can then use that to compute

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

该函数中假设模数的平方不超过64位的范围。对于较大的弹性模量，事情比较复杂。

The function supposes that the square of the modulus does not exceed the 64-bit range. For larger moduli, things are more complicated.

这篇关于C / C ++大量的计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！