Я нахожусь в процессе решения простой задачи комбинации, решение которой 2 ^ (n-1).
Единственная проблема - 1 <= n <= 2 ^ 31 -1 (максимальное значение для 32-разрядного целого числа со знаком) </p>
Я пытался использовать класс 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;
}