Эффективное возведение в степень для ОГРОМНЫХ чисел (я говорю о гуголах)

Я нахожусь в процессе решения простой комбинированной задачи, решение которой равно 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;
}