C ++ Ошибка алгоритма длинного целого Карацубы

Question

я получил эту ошибку = Unhandled exception at 0x7A5B1088 (ucrtbased.dll) in algorthmprokect1.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x006B2FF4). occurred

я не знаю, где у меня ошибка, я использую строки, потому что мне нужно получить целые числа из файла, и они имеют 1000 цифр

Обновление: после отладки я понял, что оператор else выполняется бесконечное число раз, но я все еще не нашел решения.

string karatsuba(string X,string Y) {
if (X.length()==1 || (X.length()==2 && ((X.substr(0, 1).compare("-") == 0))))
{
    int buf = stoi(X) * stoi(Y);       //multiply if int has single digit
    return to_string (buf);
}
else
{
    string X1 = X.substr(0, (X.length()/2));                      //divide half to X
    string X2 = X.substr((X.length() / 2), X.length());   

    string Y1 = Y.substr(0, (Y.length() / 2));                // divide half to Y
    string Y2 = Y.substr((Y.length() / 2) , Y.length() );



   string U= karatsuba(X1, X2);
   string V = karatsuba(Y1, Y2);
   string W = karatsuba(to_string(stoi(X1) - stoi(X2)), to_string(stoi(Y1) - stoi(Y2)));
   string Z = to_string(stoi(U) + stoi(V) - stoi(W));
   string P = to_string(pow(10, X.length()) * stoi(U) + pow(10, X.length() / 2) * stoi(Z) + stoi(V));
   return P;
}

}

Answer 1

Этот код не работает должным образом из-за бесконечной рекурсии. Но это не главная проблема.

Основная проблема: это блестящий пример того, как не делать . Вы серьезно недостаточно для выполнения таких задач. Нет смысла пытаться исправить этот код, вы должны просто поместить его в tra sh. Я бы рекомендовал начать с библиотеки GNU MP . Из исходного кода и документации вы можете многое узнать о том, как работать с большими целыми числами и реализовывать алгоритмы с большими целыми числами. Вы также можете попробовать прочитать этот источник .