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的权力是大到可以正确处理=我的印象是，我可以拆分计算在许多步骤使用模数减小结果大小。有人有这样做的策略吗？任何其他想法？

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 ?

Thanx提前

Manu

推荐答案

最简单的方法是通过重复平方减去每步中的模数的乘幂。

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

您可以使用它来计算

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屋！