Иногда я получаю ошибку двойного освобождения или повреждения, когда вызывается schoolSubtraction, если первое число меньше второго (что-то из контекста невозможно) (p1- (p0 + p2)). SchoolAddition проверено и работает для всех тестовые случаи для добавления цифр в вектор. Предположение в schoolSubtraction, что оба числа равны по длине, всегда верно из-за вызовов обработчика нуля для векторов.
Я попытался отследить и не могу найти, где произошла ошибка
std::vector<int> handleVecZero(std::vector<int> V1, int L) {
std::reverse(V1.begin(), V1.end());
for (int i = 0; i < L; i++) {
V1.push_back(0);
}
std::reverse(V1.begin(), V1.end());
return V1;
}
std::vector<int> schoolSubtraction(std::vector<int> V1, std::vector<int> V2, int B) {
//V1-V2 and assumed same length vecs
std::cout << V1.size() << " - " << V2.size() << std::endl;
for (size_t i = 0; i < V1.size(); i++) {
std::cout << V1[i] << ", ";
}
std::cout << std::endl;
for (size_t i = 0; i < V2.size(); i++) {
std::cout << V2[i] << ", ";
}
std::cout << std::endl;
std::vector<int> ans;
for (size_t i = 0; i < V1.size(); i++) {
std::cout << V1[i] << " take " << V2[i] << std::endl;
if ((V1[i]-V2[i])<0) {
ans.push_back((V1[i]+B-V2[i]));
for (int j = i; j >= 0; j--) {
// std::cout << "yet" <<std::endl;
if ((ans[j-1]>0)) {
// std::cout << "taken from " << i-j << " which was " << ans[i-j] << std::endl;
ans[j-1]-=1;
break;
} else {
ans[j-1]=B-1;
}
}
} else {
ans.push_back(V1[i]-V2[i]);
}
}
return ans;
}
std::vector<int> karatsubaMultiplication(std::vector<int> V1, std::vector<int> V2, size_t ZeroTrack, int B) {
std::vector<int> res;
V1 = handleVecZero(V1, std::max(V1.size(),V2.size())-V1.size());
V2 = handleVecZero(V2, std::max(V1.size(),V2.size())-V2.size());
std::vector<int> p0, p1, p2, p, V1U, V1L, V2U, V2L;
if (V1.size() < 3 && V2.size() < 3) {
int round = 0;
for (int i = V2.size()-1; i >= 0; i--) {
std::vector<int> ans;
for (int j = V1.size()-1; j >= 0; j--) {
(ZeroTrack >= ans.size()) {
ans.push_back((V1[j]*V2[i]+round)%B);
} else {
ans[ZeroTrack] += ((V1[j]*V2[i]+round)%B);
std::cerr << " - " << (V1[j]*V2[i]+round)/B << " - ";
if (ans[ZeroTrack]>=B) {
ans[ZeroTrack]-=B;
ans[ZeroTrack+1]+=1;
}
}
round = (V1[j]*V2[i]+round)/B;
ZeroTrack+=1;
}
ans.push_back(round);
std::reverse(ans.begin(), ans.end());
for (int p = 0; p < 1-i; p++) {
ans.push_back(0);
}
res = handleVecZero(res, std::max(res.size(),ans.size())-res.size());
res = schoolAddition(res,ans,B);
round = 0;
if (ZeroTrack > 1) {
ZeroTrack -=1;
} else {
ZeroTrack = 1;
}
}
return res;
} else {
for (size_t i = 0; i < V1.size(); i++) {
if (i < V1.size()/2) {
V1U.push_back(V1[i]);
} else {
V1L.push_back(V1[i]);
}
}
for (size_t i = 0; i < V2.size(); i++) {
if (i < V2.size()/2) {
V2U.push_back(V2[i]);
} else {
V2L.push_back(V2[i]);
}
}
V1L = handleVecZero(V1L, std::max(V1L.size(),V1U.size())-V1L.size());
V1U = handleVecZero(V1U, std::max(V1L.size(),V1U.size())-V1U.size());
V2L = handleVecZero(V2L, std::max(V2L.size(),V2U.size())-V2L.size());
V2U = handleVecZero(V2U, std::max(V2L.size(),V2U.size())-V2U.size());
std::vector<int> del1 = schoolAddition(V1L, V1U, B);
std::vector<int> del2 = schoolAddition(V2L, V2U, B);
p0 = karatsubaMultiplication(V1L, V2L, ZeroTrack, B);
p2 = karatsubaMultiplication(V1U, V2U, ZeroTrack, B);
V1L = handleVecZero(V1L, std::max(V1L.size(),V1U.size())-V1L.size());
V1U = handleVecZero(V1U, std::max(V1L.size(),V1U.size())-V1U.size());
V2L = handleVecZero(V2L, std::max(V2L.size(),V2U.size())-V2L.size());
V2U = handleVecZero(V2U, std::max(V2L.size(),V2U.size())-V2U.size());
p1 = karatsubaMultiplication(schoolAddition(V1L, V1U, B),schoolAddition(V2L, V2U, B), 0, B);
// Necessary Transforms
std::vector<int> b;
size_t maxZeroHandle=0;
maxZeroHandle = std::max(p1.size(),p2.size());
maxZeroHandle = std::max(maxZeroHandle, p0.size());
p0 = handleVecZero(p0,maxZeroHandle-p0.size());
p1 = handleVecZero(p1,maxZeroHandle-p1.size());
p2 = handleVecZero(p2,maxZeroHandle-p2.size());
std::vector<int> z = schoolAddition(p2,p0,B);
p1=handleVecZero(p1,z.size()-p1.size());
b = schoolSubtraction(p1,z,B);
for (size_t i = 0; i < 2*V2L.size(); i++) {
p2.push_back(0);
}
for (size_t i = 0; i < (V2L.size()); i++) {
b.push_back(0);
}
b = handleVecZero(b,p2.size()-b.size());
p0 = handleVecZero(p0,p2.size()-p0.size());
p = schoolAddition(p2,b,B);
p = schoolAddition(p,p0,B);
for (size_t q = 0; q < p.size(); q++) {
if (p[0]==0) {
p.erase(p.begin());
} else {
break;
}
}
}
return p;
}
Ввод (в виде числа 1, номер 2, база): 492638023618775948882302343403408655761920113817048519624315622726245389531264254792 1249819793842852712374998776280633566405504971 10066833 10 10 100668
Выход: 61570875311836896177160171483803585754449032097881406485428574047240260231941510408967012466051516880250861675778266507307838302815858408
Что правильно
но вход: 73 773 2 * Ошибка в `./a.out ': двойное освобождение или повреждение (out): 0x00000000007bbe20 * и т. д.