3

我正在解决一个简单的组合问题，其解决方案是 2^(n-1)。

唯一的问题是 1 <= n <= 2^31 -1（有符号 32 位整数的最大值）

我尝试使用 Java 的 BigInteger 类，但它对于 2^31/10^4 及更大的数字会超时，所以这显然行不通。

此外，我仅限于使用 Java 或 C++ 的内置类。

知道我需要速度，我选择用 C++ 构建一个对字符串进行算术运算的类。

现在，当我进行乘法运算时，我的程序的乘法类似于我们在纸上进行乘法以提高效率（而不是重复添加字符串）。

但即使这样，我也不能将 2 自身乘以 2^31 - 1 次，它只是不够有效。

因此，我开始阅读有关该问题的文本，并得出了...的解决方案

2^n = 2^(n/2) * 2^(n/2) * 2^(n%2)（其中 / 表示整数除法，% 表示模数）

这意味着我可以求解对数乘法的幂运算。但对我来说，我无法绕过如何将此方法应用于我的代码？如何选择下限以及跟踪最终乘法所需的各种数字的最有效方法是什么？

如果有人对如何解决此问题有任何了解，请详细说明（示例代码表示赞赏）。

更新

感谢大家的帮助！显然，这个问题应该以一种现实的方式来解决，但我确实设法java.math.BigInteger用只执行 ceil(log2(n)) 迭代的幂函数来超越。

如果有人对我生成的代码感兴趣，这里是......

using namespace std;

bool m_greater_or_equal (string & a, string & b){ //is a greater than or equal to b?
    if (a.length()!=b.length()){
        return a.length()>b.length();
    }
    for (int i = 0;i<a.length();i++){
        if (a[i]!=b[i]){
            return a[i]>b[i];
        }
    }
    return true;
}

string add (string& a, string& b){
    if (!m_greater_or_equal(a,b)) return add(b,a);
    string x = string(a.rbegin(),a.rend());
    string y = string(b.rbegin(),b.rend());
    string result = "";
for (int i = 0;i<x.length()-y.length()+1;i++){
    y.push_back('0');
}

int carry = 0;
for (int i =0;i<x.length();i++){
    char c = x[i]+y[i]+carry-'0'-'0';
    carry = c/10;
    c%=10;
    result.push_back(c+'0');
}
if (carry==1) result.push_back('1');
return string(result.rbegin(),result.rend());

}

string multiply (string&a, string&b){
    string row = b, tmp;
    string result = "0";

    for (int i = a.length()-1;i>=0;i--){

        for (int j= 0;j<(a[i]-'0');j++){
            tmp = add(result,row);
            result = tmp;
        }
        row.push_back('0');
    }
    return result;
}

int counter = 0;

string m_pow (string&a, int exp){
    counter++;
    if(exp==1){
        return a;
    }
    if (exp==0){
        return "1";
    }
    string p = m_pow(a,exp/2);
    string res;
    if (exp%2==0){
        res = "1";  //a^exp%2 is a^0 = 1
    } else {
        res = a;   //a^exp%2 is a^1 = a
    }
    string x = multiply(p,p);
    return multiply(x,res);
    //return multiply(multiply(p,p),res); Doesn't work because multiply(p,p) is not const

}

int main(){


    string x ="2";

    cout<<m_pow(x,5000)<<endl<<endl;
    cout<<counter<<endl;

    return 0;
}
4

3 回答 3

6

正如@Oli 的回答所提到的，这不是计算问题，2^n因为这只是二进制中的 a1后跟0s 。

但是由于您想以十进制打印它们，这就变成了如何将非常大的数字从二进制转换为十进制的问题。

我对此的回答是，这不现实。（我希望这个问题只是出于好奇。）

您提到尝试以2^(2^31 - 1)十进制计算和打印出来。该数字长 646,456,993 位。

  • Java BigInteger做不到。它适用于小数字并使用O(n^2)算法。
  • 正如评论中提到的，C++ 中没有内置的 BigNum 库。
  • 甚至Mathematica也无法处理： General::ovfl : Overflow occurred in computation.
  • 您最好的选择是使用GMP库。

如果您只是有兴趣查看部分答案：

2^(2^31 - 1) = 2^2147483647 = 

880806525841981676603746574895920 ... 7925005662562914027527972323328

(total: 646,456,993 digits)

这是使用闭源库完成的，在 Core i7 2600K @ 4.4 GHz 上花费了大约 37 秒和 3.2 GB 内存，其中包括将所有 6.46 亿位数字写入大型文本文件所需的时间。
（记事本打开文件所需的时间比计算它所需的时间长。）

现在要回答您在一般情况下如何实际计算这种幂的问题，@dasblinkenlight 有答案，它是Exponentiation by Squaring 的变体。

将大数从二进制转换为十进制是一项艰巨的任务。这里的标准算法是分治转换。

我不建议你尝试实现后者——因为它远远超出了初学者的范围。（而且也有点数学密集型）

于 2012-01-07T18:52:57.640 回答
4

你根本不需要做任何乘法。2^(n-1) 只是1 << (n-1)，即 1 后跟(n-1)零（二进制）。

于 2012-01-07T17:48:51.187 回答
3

在您的代码中应用此方法的最简单方法是以最直接的方式应用它 - 递归。它适用于任何 number a，不仅适用于2，因此我编写了将a其作为参数的代码以使其更有趣：

MyBigInt pow(MyBigInt a, int p) {
    if (!p) return MyBigInt.One;
    MyBigInt halfPower = pow(a, p/2);
    MyBigInt res = (p%2 == 0) ? MyBigInt.One : a;
    return res * halfPower * halfPower;
}
于 2012-01-07T17:50:16.367 回答