c++ - 如何在 C++ 中计算和打印 3^9999？

Question

有人可以解释如何让像 3^9999 这样的操作在 c++ 中工作，正如我发现的那样，如果数字太长会导致问题。我听说有办法解决它。（请不要建议任何外部库）

Answer 1

把你的问题分成三个问题。

1）首先解决如何将很长的整数相乘。

2）9999变成二进制10011100001111。有 14 位。设置了 8 位。设置位（从末尾开始）意味着9999 = 1 + 2 + 4 + 8 + 256 + 512 + 1024 + 8192. 这些因素通常是有用的，因为3^2 = 3^1 * 3^1等等n^(2^m) = n^(2^(m-1)) * n^(2^(m-1))。您可以从 开始计算循环中的因子3^1 = 3，即进行 13 次乘法运算。

3)3^9999 = 3^1 * 3^2 * 3^4 * 3^8 * 3^256 * 3^512 * 3^1024 * 3^8192通过将因子乘以结果来计算。这使得 7 更多的乘法。

要计算 3^9999，您需要 20 个非常长的整数乘法。

Answer 2

由于您要求提供不依赖于库的解决方案，因此您将不得不以艰难的方式去做。

创建一个将两个数字数组相乘的函数。为此，您需要大约log10(3)*9999数字，或 4771。用全零和 3 初始化两个数组，然后将第一个数组乘以第二个数组 9998 次。

Answer 3

希望您不是在寻找优化...

int N = 9998;
int M = 5000;
int arr [M];

for ( int j = 0 ; j < M ; ++j )
        arr[j]=0;

arr[M-1] = 3;


for ( int i = 0 ; i < N ; ++i ) {

        for ( int j = 0 ; j < M ; ++j )
                arr[j] = arr[j]*3;

        for ( int j = M-1 ; j > 0 ; --j ) {
                arr[j-1] = arr[j-1] + arr[j]/10;
                arr[j] = arr[j]% 10;
        }
}


for ( int j = 0 ; j < M ; ++j )
        std::cout << arr[j];

Answer 4

关于我如何让它变得更丑以便他的教授不会接受的任何想法？=]

#include <stdio.h>
#include <string.h>
int main()
{
    unsigned char ds[9999];
    unsigned char c;
    ds[0] = 3;
    bzero(ds+1, 9998);
    for(int p = 2; p <= 9999; p++)
    {
        c = 0;
        for(int d=0; d<p/2+1; d++)
        {
            ds[d] = ds[d] * 3 + c;
            c = ds[d] / 10;
            ds[d] = ds[d] % 10;
        }
    }
    int d = 9998;
    for(; d>=0; d--)
        if(ds[d] != 0)
            break;
    for(; d>=0; d--)
        printf("%d", ds[d]);
    printf("\n");
}