C++ Karatsuba long integer algorithm error

0

i got this error = Unhandled exception at 0x7A5B1088 (ucrtbased.dll) in algorthmprokect1.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x006B2FF4). occurred

i don't know where i have a mistake i am using strings because i need to get integers from file and they has 1000 digits

Update:After Debugging i realized that else statement runs infinite number of times but i still didn't found the solution.

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

}

c++
algorithm
asked on Stack Overflow Apr 5, 2020 by Tlamir • edited Apr 5, 2020 by Tlamir

1 Answer

0

This code is not working properly because of the infinite recursion. But this is not the main problem of it.

The main problem is: it's a brilliant example of how not to do. You are severe underqualified to do such tasks. There is no point in attempts to fix this code, you must simply put it into trash. I would recommend to start with the GNU MP library. You can learn much from the source code and documentation there how to work with big integers and implement big integer algorithms. You may also try to read this source.

answered on Stack Overflow Apr 5, 2020 by Sergey Strukov

User contributions licensed under CC BY-SA 3.0