1

どうすれば解決できますか: 2 ^ 200'000C
で次のようないくつかの解決策を試しました:

unsigned long long int variable = 1;
int i = 0;
 for(i = 0; i < 200000; i++) {
        variable *= 2;
 }
 printf("%llu", variable);

私は結果を得ました：0

私も疲れました：

variable = 1 << 200000;

そして、私は同じ結果を得ました

そしてあまりにも：

pow(2, 200000);

そして、私は結果を得ました：inf

私は結果が本当に大きな数になることを知っています!

4

6 に答える 6

6

bignumsを使用する必要があります。それらを提供する優れた C ライブラリはGMPlib (またはGmp ) です。

this & this answerも参照してください。

それが宿題であり、外部ライブラリを避ける必要がある場合は、独自のナイーブで非効率な bignum 操作を実装してください。たとえば、基数 1000000000 の大きな数値を bigdigits のベクトルとして表します (基数 1000000000、つまりunsigned int1000000000 未満の -s)。ただし、bignum 操作の効率的なアルゴリズムは非常に難しいテーマであることに注意してください (これで博士号を取得できます)。

Common Lisp (実際には Linux ではSBCL(expt 2 200000) ) を使用すると、多くの数字が表示され、末尾が

于 2012-11-26T09:12:16.500 に答える
3

If you can't use an external bignum library, then you have to implement your own.

Start by defining what your big number will look like in memory. For example, for rational numbers (which are the most awesome) a number might be represented as "a/b*(2**e)"; and you might have a variable sized array of unsigned bytes to represent a denominator, a variable length array of unsigned bytes to represent a divisor, a variable length array of unsigned bytes to represent an exponent, and some flags (e.g. denominator sign and exponent sign).

The next step is to write code to do primitive operations on pieces of your big number. For example, code to add variable length arrays together, code to shift a variable length array left/right, code to multiply 2 variable length arrays, etc.

The next step would be to implement normal operations using your primitive operations. For example (for the rational numbers), "bigNumber << 44" is actually "a/b*(2**e) << 44", and you'd just add 44 to "e".

The next step is to convert your number into your format using those normal operations you implemented. For example, you might create a big number that has the value 1 (denominator=1, divisor=1, exponent=0) and then shift it left by 200000 (denominator=1, divisor=1, exponent=0+200000).

Of course then you need some way of converting your big number into a string so it can be displayed. This requires actual division (rather than "multiply by inverse") which gets tricky.

Please note that for your purposes you only actually need a "0 bit" significand and an 18-bit exponent to store the number (in a format designed specifically for that number). If you don't need to display the resulting number in decimal, then it becomes very easy.

For example, to display it in hex you could do:

char hexDigitTable[16] = "0123456789ABCDEF";

// My big number with a 0-bit significand and 18-bit exponent!
uint32_t exponent = 20000;     

printBigNumber(uint32_t exponent) {
    int digit;

    if(exponent > 4) {
        // Note: "number / 16" is the same as "number >> 4" which is
        //       the same as "exponent - 4".
        printBigNumber(exponent - 4);
    }
    digit = 1 << (exponent & 3);
    printf("%c", hexDigitTable[digit]);
}

See how easy it is if you're lazy? :-)

于 2012-11-26T09:44:07.917 に答える
3

教室で鉛筆と紙を使って 20 回または 100 回の繰り返しでこの問題をどのように解決しようとしますか? ここでも同じアプローチが完璧です。配列を逆にすることをお勧めします。これにより、左から右に乗算し、最終的な数値を正しい順序で出力できます。

于 2012-11-26T09:17:18.277 に答える
2

「計算」する必要はありません。基数 2 は特殊で、2 進基数であり、2 のべき乗は 2^x の形式で、1 << x (左シフト) として生成できます。unsigned char[25000] など、少なくとも 200,000 ビットを保持できるビットフィールドを設定し、最上位ビットを 1 に設定する必要があります。その後、このビットフィールドを整数として解釈するだけで済みます。

この数値を 16 進数で書き出すのは簡単です。すべてのバイトを 16 進数で書き出すだけです。10進数で出力するには、おそらくbignumライブラリが必要です:(

于 2012-11-27T11:18:11.577 に答える
0

これには何らかの形式のbignum ライブラリが必要です。C のネイティブ データ型は、この数値を正確に保持できません。この数値を表すには、かなりの量のメモリが必要になることに注意してください。

于 2012-11-26T09:12:34.653 に答える
0

2 ^ 200000 は組み込みデータ型をはるかに超えています。

手動で乗算をシミュレートするには、べき乗を配列で表す必要があります。

たとえば、配列 { 0,1,2,3,4,5,6,7,8,9 } を使用して 9,876,543,210 を格納できます。

次に、分割統治アルゴリズムを使用して、計算の複雑さを軽減する必要があります。

計算するには

a ^ b

計算する必要があります

t = a ^ (b/2)

最初。次に、t を使用して計算します。

a ^ b = t * t * a ^ ( b % 2 )
于 2012-11-27T10:57:25.903 に答える