对于巨大数字的有效指数(我说的是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) (其中/表示整数除法,%表示模数)

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

如果有人知道如何解决这个问题,请详细说明(示例代码表示赞赏).

UPDATE

感谢大家的帮助!很明显,这个问题意味着以一种现实的方式解决,但我确实设法胜过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;
}

Answer 1

正如@ Oli的回答所提到的,这不是一个计算问题,2^n因为这只是一个二进制1的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可以得到Squaring的Exponentiation变体的答案.

对于大数字,从二进制转换为十进制是一项更难的任务.这里的标准算法是Divide-and-Conquer转换.

我不建议你尝试实现后者 - 因为它远远超出了启动程序员的范围.(也有点数学密集)