1

我该如何解决：2 ^ 200'000在 C 中
我尝试了几种解决方案，例如：

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）。

另请参阅此和此答案。

如果这是一项家庭作业，并且您必须避免使用外部库，请实现您自己的幼稚和低效的 bignum 操作，方法是将例如以 1000000000 为底的大数字表示为 bigdigits 的向量（以 1000000000 为底，即unsigned int-s 小于 1000000000）。但是请注意，bignum 操作的有效算法是一个非常困难的主题（您可以在这方面攻读博士学位）。

使用 Common Lisp（实际上是Linux 上的SBCL(expt 2 200000) ），给出很多数字，以

于 2012-11-26T09:12:16.500 回答
3

您将如何尝试在课堂上用铅笔和纸重复 20 或 100 次来解决这个问题？同样的方法在这里也很完美。我只是建议颠倒数组，这样可以从左到右相乘并以正确的顺序打印最终数字。

于 2012-11-26T09:17:18.277 回答
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 回答
2

你不需要“计算”任何东西。基数 2 是特殊的 - 它是二进制基数 - 以 2^x 的形式出现的 2 的幂可以生成为 1 << x（左移）。您需要设置一个至少可以容纳 200,000 位的位域，例如 unsigned char[25000] 并将最高位设置为 1。然后，您只需将该位域解释为整数。

用十六进制写出这个数字很简单——只需用十六进制写出每个字节。要以十进制打印出来，您可能需要一个 bignum 库:(

于 2012-11-27T11:18:11.577 回答
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 回答
0

为此，您需要某种形式的bignum 库，C 中的任何本机数据类型都无法准确保存该数字。请注意，表示此数字将占用大量内存。

于 2012-11-26T09:12:34.653 回答