Блог

Иногда я получаю ошибку двойного свободного или поврежденного умножения при вызове 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 amp;amp; 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 124981979384285271237499877628063356640550971704683349 10

output:61570875311836896177160171483803585754449032097881406485428574047240260231941510408967012466051516880250861675778266507307838302815858408

Что верно, но ввод: 73 773 2 * Ошибка в `./ a.out’: двойное освобождение или повреждение (out): 0x00000000007bbe20 * и т.д.

Моей проблемой была эта строка:

 for (int j = i; j >= 0; j--) {
  

(встроенный цикл for в методе schoolSubtraction.)
необходимая замена заключалась в следующем:

 for (int j = i; j > 0; j--) {
  

Мне все еще интересно узнать, как из-за этой ошибки числа стали отрицательными. Конечно, это остановило бы доступ за пределы в случае, если бы они были, но как это изменение помешало числам, переданным методу, иметь V1 меньше, чем V2?