c++ - 巨大数字的有效指数(我说的是 Googols)

Question

我正在解决一个简单的组合问题，其解是 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)(其中/表示整数除法，% 表示模数)

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

如果有人知道如何解决这个问题，请详细说明(感谢示例代码)。

更新

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

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

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;
}

Answer 1

如@Oli 的回答所述，这不是计算 2^n 的问题，因为它通常只是 1 后跟 0 s 二进制。

但是既然你想以十进制打印出来，这就变成了一个问题，即对于非常大的数字，如何将二进制转换为十进制。

我的回答是这不现实。(我希望这个问题只是出于好奇。)

您提到尝试计算 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 变体的答案。

将大数从二进制转换为十进制是一项艰巨的任务。这里的标准算法是 Divide-and-Conquer conversion 。

我不建议您尝试实现后者 - 因为它远远超出了新手程序员的范围。 (并且还有些数学密集型)