首页 > 解决方案 > 我收到双重免费或损坏错误 Karatsuba Multiplication (base <=10)

问题描述

如果第一个数字小于第二个数字(上下文暗示不可能(p1-(p0 + p2)))调用schoolSubtraction时,有时会出现双重释放或损坏错误。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;
}

input (in form of number 1, number 2, base): 492638023618775948882302343403408655761920113817048519624315622726245389531264254792 124981979384285271237499877628063356640550971704683349 10

输出:615708753118368961771601714838035857544490320978814064854285740472402602319415104089670124660515168802508616757783026507385788266507385888

这是正确的,但输入:73 773 2 * `./a.out' 中的错误:双重释放或损坏(输出):0x00000000007bbe20 *等。

标签: ubuntuc++98double-free

解决方案


我的问题是这一行:

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

(schoolSubtraction 方法中嵌入的 for 循环。)需要的替换是这样的:

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

我仍然有兴趣知道这个错误是如何导致数字为负数的。当然,如果它们是,它会停止越界访问,但是这种更改如何阻止传递给方法的数字使 V1 低于 V2?


推荐阅读