c++ - c ++で3 ^ 9999を計算して出力する方法は?

Question

私が見つけたように、3^9999 のような演算を C++ で動作させる方法を誰かが説明できますか?数値が長すぎると問題が発生します。解決する方法があると聞いたことがあります。(外部ライブラリを提案しないでください)

Answer 1

問題を3つの問題に分割します。

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

ライブラリに依存しないソリューションを求めているため、難しい方法で実行する必要があります。

2 つの数字の配列を乗算する関数を作成します。これには約 4771 桁が必要ですlog10(3)*9999。2 つの配列をすべてゼロと 3 で初期化し、最初の配列を 2 番目の配列で 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");
}