大量数字的有效指数（我在说谷歌） [英] Efficient Exponentiation For HUGE Numbers (I'm Talking Googols)

问题描述

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

I am in the midst of solving a simple combination problem whose solution is 2^(n-1).

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

The only problem is 1 <= n <= 2^31 -1 (max value for signed 32 bit integer)

我尝试使用Java的BigInteger类，但它超时2 ^ 31/10 ^ 4

I tried using Java's BigInteger class but It times out for numbers 2^31/10^4 and greater, so that clearly doesn't work out.

此外，我只能使用Java或C ++的内置类。

Furthermore, I am limited to using only built-in classes for Java or C++.

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

Knowing I require speed, I chose to build a class in C++ which does arithmetic on strings.

现在，我的程序的倍数类似于我们在纸上乘以效率（而不是重复添加字符串）。

Now, when I do multiplication, my program multiplies similarly to how we multiply on paper for efficiency (as opposed to repeatedly adding the strings).

但是即使有了，我不能乘2

But even with that in place, I can't multiply 2 by itself 2^31 - 1 times, it is just not efficient enough.

所以我开始阅读有关问题的文本，我来到...的解决方案...

So I started reading texts on the problem and I came to the solution of...

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

2^n = 2^(n/2) * 2^(n/2) * 2^(n%2) (where / denotes integer division and % denotes modulus)

这意味着我可以用对数乘法求解求幂。但对我来说，我不能得到如何应用这种方法我的代码？我如何选择一个下界，什么是最有效的方式来跟踪我需要的最后乘法的各种数字？

This means I can solve exponentiation in a logarithmic number of multiplications. But to me, I can't get around how to apply this method to my code? How do I choose a lower bound and what is the most efficient way to keep track of the various numbers that I need for my final multiplication?

如果任何人有任何知识如何解决这个问题，请详细说明（示例代码非常感谢）。

If anyone has any knowledge on how to solve this problem, please elaborate (example code is appreciated).

UPDATE

感谢大家的帮助！显然，这个问题是以现实的方式解决的，但是我试图用一个只执行ceil（log2（n））的幂函数优于 java.math.BigInteger ）迭代。

Thanks to everyone for all your help! Clearly this problem is meant to be solved in a realistic way, but I did manage to outperform java.math.BigInteger with a power function that only performs ceil(log2(n)) iterations.

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

If anyone is interested in the code I've produced, here it is...

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

推荐答案

应用此最简单的方法方法在你的代码是应用它最直接的方式 - 递归。它适用于任何数字 a ，不仅对于 2 ，所以我写的代码，

The easiest way to apply this method in your code is to apply it the most direct way - recursively. It works for any number a, not only for 2, so I wrote code that takes a as a parameter to make it more interesting:

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

这篇关于大量数字的有效指数（我在说谷歌）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！