如何计算大数n的2^n次方？

Question

我正在尝试编写一个程序，接受一个数字n作为输入，并输出2的n次方的结果。问题是，n可能非常大（高达100,000）。我需要计算非常大数字的pow(2,n);。

我认为解决方法是将这些数字存储在数组中，因为没有内置的数字类型可以保存如此大的值。

这些数字是以十进制格式（基数10）表示的。

我使用的是C语言，而不是C ++，因此无法使用STL向量和其他C ++容器。我也不能使用外部库，例如GMP。我需要在纯C中手动实现算法。

- DarkAtom

---

最不重要的数字存储在第一个数组条目（索引0）还是最后一个数组条目中？有一个输入n = ...和预期结果数组的示例将会很有帮助。 - Socowi

乘法的方法？我们在学校学的那种——逐位相乘，进位等。 - Eugene Sh.

步骤1：编写一个函数，用于乘以值的2个字符串十进制表示。步骤2 使用平方取幂算法。 - chux - Reinstate Monica

创建一个“大字符串表”，其中从2^0到2^100,000的每个值都表示为查找中的字符串。运行时间恒定，不需要大数库，只需要大量RAM :) 如果使用另一种能够很好处理此类操作的语言生成大字符串表，则可获得额外积分。 - Michael Dorgan

从一开始就了解的有用信息可能是，2^n需要ceil(n * log10(2))个十进制数字（n-100000为30103）。 - Clifford

Answer 1

问题不在于计算2的高次方，而在于将这个数字转换为十进制表示：

• 让我们用无符号32位整数数组来表示大数。
• 计算2ⁿ只需要设置一个比特位。
• 转换为二进制可以通过将该数字反复除以1000000000来完成，每次产生9个数字。

以下是一个简单但快速的实现：

#include <stdint.h>
#include <stdio.h>

void print_2_pow_n(int n) {
    int i, j, blen = n / 32 + 1, dlen = n / 29 + 1;
    uint32_t bin[blen], dec[dlen];
    uint64_t num;

    for (i = 0; i < blen; i++)
        bin[i] = 0;
    bin[n / 32] = (uint32_t)1 << (n % 32);

    for (j = 0; blen > 0; ) {
        for (num = 0, i = blen; i-- > 0;) {
            num = (num << 32) | bin[i];
            bin[i] = num / 1000000000;
            num = num % 1000000000;
        }
        dec[j++] = (uint32_t)num;
        while (blen > 0 && bin[blen - 1] == 0)
            blen--;
    }
    printf("2^%d = %u", n, dec[--j]);
    while (j-- > 0)
        printf("%09u", dec[j]);
    printf("\n");
}

int main() {
    int i;
    for (i = 0; i <= 100; i += 5)
        print_2_pow_n(i);
    print_2_pow_n(1000);
    print_2_pow_n(10000);
    print_2_pow_n(100000);
    return 0;
}

输出：

2^0 = 1
2^5 = 32
2^10 = 1024
2^15 = 32768
2^20 = 1048576
2^25 = 33554432
2^30 = 1073741824
2^35 = 34359738368
2^40 = 1099511627776
2^45 = 35184372088832
2^50 = 1125899906842624
2^55 = 36028797018963968
2^60 = 1152921504606846976
2^65 = 36893488147419103232
2^70 = 1180591620717411303424
2^75 = 37778931862957161709568
2^80 = 1208925819614629174706176
2^85 = 38685626227668133590597632
2^90 = 1237940039285380274899124224
2^95 = 39614081257132168796771975168
2^100 = 1267650600228229401496703205376
2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
2^10000 = 1995063116880758384883742<...>91511681774304792596709376
2^100000 = 9990020930143845079440327<...>97025155304734389883109376

2¹⁰⁰⁰⁰⁰有30103位数字，这正是floor(100000 * log10(2))。 在我的老笔记本电脑上执行需要33毫秒。

- chqrlie

---

我喜欢你的 while (j --> 0) 循环。 - Stef

@stef：著名的dowto运算符是迭代数组以递减索引值的最佳解决方案，它还适用于无符号类型 :) - chqrlie

@stef：我喜欢这个问题，尤其是那个形象生动的 x slides to 0。 - chqrlie

Answer 2

创建一个位数组并设置第n位，然后按照位数组是小端数的方式除以10，倒序打印余数，即可得到2的n次幂的十进制表示。

下面的快速程序可以实现这个功能，并且它给出的结果与bc命令相同，所以我想它是有效的。打印程序可能需要进行一些调整。

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

uint_least32_t div32(size_t N, uint_least32_t Z[/*N*/], uint_least32_t X[/*N*/], uint_least32_t Y)
{
    uint_least64_t carry; size_t i;
    for(carry=0, i = N-1; i!=-1; i--)
        carry = (carry << 32) + X[i], Z[i] = carry/Y, carry %= Y;
    return carry;
}

void pr10(uint_least32_t *X, size_t N)
{
    /*very quick and dirty; based on recursion*/
    uint_least32_t rem=0;
    if(!X[N?N-1:0]) return;
    rem = div32(N,X,X,10);
    while(N && !X[N-1]) N--;
    pr10(X,N);
    putchar(rem+'0');
}
int main(int C, char **V)
{
    uint_least32_t exp = atoi(V[1]);
    size_t nrcells = exp/32+1;
    uint_least32_t *pow  = calloc(sizeof(uint_least32_t),nrcells);
    if(!pow) return perror(0),1;
    else pow[exp/32] = UINT32_C(1)<<(exp%32);
    pr10(pow,nrcells);

}

示例运行：

$ ./a.out 100
1267650600228229401496703205376

- PSkocik

---

这对于exp < 80'000非常有效，但是对于exp >= 80'000没有输出。有任何想法为什么？ - Socowi

@Socowi 可能是由于打印例程中的递归引起了堆栈溢出。 - Petr Skocik

@Socowi，我在那里犯了一个偏移一错误。现在应该可以工作了。 - Petr Skocik

Answer 3

步骤一：决定如何表示大数

已经有相关的库可以帮助实现。广泛使用的选项是GNU多精度整数库。（但根据您的编辑，这不是一个选项。您仍然可以浏览一下它们，以了解它们是如何做的，但这并非必要）。

如果你想自己开发，我不建议存储十进制数字。如果这样做，每次在元素上进行算术运算时都需要转换成二进制表示法。最好像链表一样存储uint32_t，再加上一个符号位。当您要读取和写入时，可以进行十进制转换，但是请在二进制中进行数学计算。

步骤二：实现指数

在此假设使用链表的大数实现；您可以根据需要调整算法。

如果只计算2的幂，那很容易。它是由N个0后面跟着1组成的。因此，如果每个块存储M个比特，并且要表示2^N，则只需有floor(N/M)个全0块，并在最高位块中存储1 << (N%M)。

如果您想要以有效的方式对任意底数进行指数运算，则应使用平方取幂。其背后的想法是：如果您想要计算3^20，那么不需要将3*3*3*...*3相乘。而是计算3^2=3*3。然后3^4=3^2*3^2. 3^8 = 3^4 * 3^4. 3^16 = 3^8 * 3^8。在进行过程中存储每个中间结果。当达到再次平方会得到比目标值更大的数字时，停止平方并从已有的部分组装最终结果。在此例子中，3^20 = 3^16 * 3^4。

该方法仅需要5步即可计算出最终结果，而不是20步；由于时间与指数成对数关系，因此指数越大，速度增益就会更加明显。甚至计算3^100000只需要21次乘法。

我不知道任何聪明的方法来进行乘法；你可能只能按照基本的长乘法算法，在块的级别上执行一些操作：我们之前使用uint32_t而不是uint64_t，是为了可以将操作数转换为更大的类型并进行乘法运算，而不会因为溢出而丢失进位位。

将二进制转换为十进制以打印

首先，找到比您的数字小的最大10倍数。
我把这个做法高效地留给读者作为练习，但是您可以通过幂的平方进行指数计算，然后减去各种存储的中间值，以比反复除以10更快地达到实际值。

或者您可以通过反复乘以10来找到该数字；无论如何，接下来的部分都将是线性的。

但是，无论您如何获得它，您都有一个q，使得q = k * 10, 10 * q > n, q <= n，您只需逐个十进制数字循环即可：

for (; q; q /= 10) {
   int digit = n / q; //truncated down to floor(n/q)
   printf("%d", digit);
   n -= digit * q;
}

可能有更有效的方法在文献中，但我不熟悉。但只要我们写输出时仅需要执行低效部分，这就不是一个大问题；无论算法如何，这都很慢。我的意思是，打印所有 100,000 个数字可能需要一两毫秒。当我们显示数字供人类消费时，这并不重要，但如果我们必须等待一毫秒作为循环中的计算的一部分，它会累积起来并变得非常低效。这就是为什么我们从不以十进制表示形式存储数字的原因：通过内部以二进制表示，我们在输入和输出时只需执行低效部分，而其中的所有内容都很快。

- Ray

---

这并没有解决所提出的问题。没有一种直接的方式可以用十进制形式表示结果。 - Eugene Sh.

@EugeneSh。我原以为这超出了问题的范围，但我已经添加了一个快速说明如何做到这一点。 - Ray

好的，为了我正确理解最后一部分：q是小于巨大数字的最大10的次幂，n是您输入的数字（0 <= n <= 100k）？ - DarkAtom

@Ray 但是我的数字在内存中以二进制形式存储在链表中，就像你说的那样，而不是以十进制形式存储在变量中。 - DarkAtom

@DarkAtom 变量不以十进制形式存储数字。"2048"、"0x800"和"1000 0000 0000"只是表示数字2048的不同字符串方式。当我说2048时，我指的是数字，而不是任何特定的表示。在计算机中，将使用二进制表示。在这里的注释中，我使用的是十进制版本。 - Ray

Answer 4

这是一个相当幼稚和低效的解决方案。按要求，数字用十进制数字数组表示。我们通过重复将数字2与其自身相加来计算指数2ⁿ： 从e := 2开始，重复执行e := e + e n次。

为了得出digits数组长度的上限，我们使用以下方法：

• 在基数b下，数字x的表示形式有⌈log_b(x)⌉位数字。
• 比较任何数字x的二进制和十进制表示之间的数字位数，如果忽略舍入(⌈⌉)，它们只会相差一个常数因子。
  log₂(x) / log₁₀(x) = 1 / log₁₀(2) = 3.3219... > 3
• 2ⁿ具有log₂(2ⁿ) = n个二进制位。
• 因此，2ⁿ大约有n/3个十进制数字。由于舍入问题，我们在此基础上再加上+1。

void print(int digits[], int length) {
    for (int i = length - 1; i >= 0; --i)
        printf("%d", digits[i]);
    printf("\n");
}
void times2(int digits[], int length) {
    int carry = 0;
    for (int i = 0; i < length; ++i) {
        int d = 2 * digits[i] + carry;
        digits[i] = d % 10;
        carry = d / 10;
    }
}
int lengthOfPow2(int exponent) {
    return exponent / 3 + 1;
}
// works only for epxonents > 0
void pow2(int digits[], int length, int exponent) {
    memset(digits, 0, sizeof(int) * length);
    digits[0] = 2;
    for (int i = 1; i < exponent; ++i)
        times2(digits, length);
}
int main() {
    int n = 100000;
    int length = lengthOfPow2(n);
    int digits[length];
    pow2(digits, length, n);
    print(digits, length);
    return 0;
}

On unix-like systems you can check correctness for a fixed n using

diff \
  <(compiledProgram | sed 's/^0*//' | tr -d '\n') \
  <(bc <<< '2^100000' | tr -d '\n\\')

As already pointed out, this solution is not very efficient. Compiled with clang -O2 computing 2^100'000 took 8 seconds on an Intel i5-4570 (3,2GHz).

The next step to speed this up would be to repeatedly cube your number instead of repeatedly multiplying by 2. Even with a naive implementation of the cube step this should be faster than the implementation presented in this answer.

If you need to be even more efficient you can implement the cube step using something like Karatsuba's algorithm or even fast fourier transformation (FFT). With the cubing approach and FFT you can compute 2ⁿ in around O(n·log(n)) (there may be an additional log(log(n)) factor due to rounding issues in FFT).

- Socowi

Answer 5

我无法以对数复杂度（平方取幂）找到解决方案，但我成功编写了一个朴素的实现，时间复杂度为O（noOfDigits*pow），其中2^n中的noOfDigits将为n*log10(2)+1;

我只使用https://www.mathsisfun.com/calculator-precision.html的前几位数字检查了答案，看起来是正确的。

#include <stdio.h>
#include <math.h>
//MAX is no of digits in 2^1000000
#define MAX 30103
int a[MAX];
int n;
void ipow(int base, int exp,int maxdigits)
{
    a[0]=1;
    for (;exp>0;exp--){
            int b=0;
            for(int i=0;i<maxdigits;i++){
                a[i]*=base;
                a[i]+=b;
                b=a[i]/10;
                a[i]%=10;
            }
    }
}
int main()
{
    int base=2;
    int pow=100000;
    n=log10(2)*pow+1;
    printf("Digits=%d\n",n);
    ipow(base,pow,n);
    for(int i=n-1;i>=0;i--){
        printf("%d",a[i]);
    }
    return 0;
}

我也写了一个幂运算的代码，但是乘法函数没有进行优化。这个实现似乎比上面的实现更快。

#define MAX 30103
int a[MAX];
int b[MAX];
int z[MAX];
//stores product in x[]; mul of large arrays implemented in n^2 complexity
//n and m are no of digits in x[] and y[]
//returns no of digits in product
int mul(int x[],int y[],int n,int m){
    for(int i=0;i<n+m;i++)
        z[i]=0;
    for(int j=0;j<m;j++){
        int c=0;
        for(int i=0;i<n+m;i++){
            z[i+j]+=x[i]*y[j];
            z[i+j]+=c;
            c=z[i+j]/10;
            z[i+j]%=10;
        }
    }
    for(int i=0;i<n+m;i++){
            x[i]=z[i];
    }
    if(x[n+m-1]==0)
        return n+m-1;
    return n+m;
}
//stores answer in x[]
int ipow(int base, int exp)
{
    int n=1,m=0;
    for(int i=0;base>0;i++){
        b[i]=base%10;
        base/=10;
        m++;
    }
    a[0]=1;
    for (;;)
    {
        if (exp & 1)
            n=mul(a,b,n,m);
        exp >>= 1;
        if (!exp)
            break;
        m=mul(b,b,m,m);
    }
}
int main()
{
    int base=2;
    int pow=100000;
    n=log10(2)*pow+1;
    printf("Digits=%d\n",n);
    ipow(base,pow);
    printf("\n");
    for(int i=n-1;i>=0;i--){
        printf("%d",a[i]);
    }
    return 0;
}

- Sandeep Polamuri

---

很好的贡献。而且足够复杂，如果学生不理解就交上去，他们将得到零分。 - Michael Dorgan

计算2的100000次方需要26秒的执行时间。 - Sandeep Polamuri

把结果放进一个字符串表中，然后使用它。瞬间运行 :) - Michael Dorgan

@SandeepPolamuri，你对测量时间的评论可能有点误导人。是的，只使用clang -lm编译，我也得到了30秒的结果，但使用clang -O2只需要7秒。顺便说一下，我自动比较了pow=100'000的结果，所有数字都是正确的。 - Socowi

刚刚意识到 Java BigInteger 可以在 1 秒内完成相同的操作。 - Sandeep Polamuri

现在使用gcc -O2编译器，我的更新代码只需要3秒就能执行。直到现在我才知道这些编译器参数的存在。 - Sandeep Polamuri

Answer 6

由于最初的问题陈述没有指定输出基数，所以这里提供一个玩笑实现：

#include <stdio.h>

void print_2_pow_n(int n) {
    printf("2^%d = 0x%d%.*d\n", n, 1 << (n % 4), n / 4, 0);
}

int main() {
    int i;
    for (i = 0; i < 16; i++)
        print_2_pow_n(i);
    print_2_pow_n(100);
    print_2_pow_n(100000);
    return 0;
}

输出：

2^0 = 0x1
2^1 = 0x2
2^2 = 0x4
2^3 = 0x8
2^4 = 0x10
2^5 = 0x20
2^6 = 0x40
2^7 = 0x80
2^8 = 0x100
2^9 = 0x200
2^10 = 0x400
2^11 = 0x800
2^12 = 0x1000
2^13 = 0x2000
2^14 = 0x4000
2^15 = 0x8000
2^100 = 0x10000000000000000000000000
2^100000 = 0x10...<0 repeated 24998 times>...0

- chqrlie

---

二的幂次方，二的幂次方基数。这太作弊了！:D - Petr Skocik

O(n)解决方案，所以UV。注意：100,000可能超过*printf()的环境限制（c18 § 7.21.6.1 15），该限制至少为4095，因此会“破坏”printf()。 - chux - Reinstate Monica

@chux：确实是对printf实现质量的压力测试。在基于苹果BSD的Libc的OS/X上和在带有GNU libc的Linux上都能按预期工作。其他系统可能不太稳定 :) - chqrlie