C ++: Vectorunsigned char

1

I am doing a dynamic numeric class, storing the value of the number in a vector of bytes. I did the functions of addition, subtraction and multiplication in the same way that we learn in school, but this can not be applied in the division. What is the right way to do it?

typedef unsigned char uchar;
typedef unsigned short ushort;
typedef unsigned int uint;
typedef unsigned long ulong;

class Num
{
private:
    vector<uchar> x;
    ...
public:
    ...
    Num(vector<uchar> other)
    {
        if(other.size() > 8) other.resize(8);

        while(!other.empty() && other[other.size() - 1] == 0)
            other.pop_back();

        x = other;
    }

    size_t size() const
    {
        return x.size();
    }
    ...
    friend Num operator+(Num l, const Num& rhs)
    {
        Num r = rhs;
        vector<uchar> res (l.x);
        vector<uchar> mod (1, 0);

        while(r.size() < res.size()) r.x.push_back(0);
        while(r.size() > res.size()) res.push_back(0);

        for(uchar i = 0; i < res.size(); i++)
        {
            mod.push_back((ushort)res[i] + (ushort)r.x[i] > 0xff);
            res[i] += r.x[i];
        }

        Num nmod = mod;
        if(nmod.size() > 0) return (Num(res) + nmod);
        return Num(res);
    }
    friend Num operator-(Num l, const Num& rhs)
    {
        Num r = rhs;
        vector<uchar> res (l.x);
        vector<uchar> mod (1, 0);

        while(r.size() < res.size()) r.x.push_back(0);
        while(r.size() > res.size()) res.push_back(0);

        for(uchar i = 0; i < res.size(); i++)
        {
            mod.push_back(res[i] < r.x[i]);
            res[i] -= r.x[i];
        }

        Num nmod = mod;
        if(nmod.size() > 0) return (Num(res) - nmod);
        return Num(res);
    }

    Num& operator+=(const Num& r)
    {
        Num res = *this + r;
        *this = res;
        return *this;
    }
    Num& operator-=(const Num& r)
    {
        Num res = *this - r;
        *this = res;
        return *this;
    }

    friend Num operator*(Num l, const Num& rhs)
    {
        Num r = rhs;
        Num res;

        for(uchar i = 0; i < r.size(); i++)
        {
            vector<uchar> temp(i, 0);
            vector<uchar> mod(i + 1, 0);

            for(uchar j = 0; j < l.size(); j++)
            {
                ushort v = l.x[j] * r.x[i];
                temp.push_back(v % 256);
                mod.push_back(v / 256);
            }

            res += Num(temp) + Num(mod);
        }
        return res;
    }
    ...
};

The operations I did are the same as the ones that you learn in school, considering each% of the vector% as if it were a 256-based numeric.

    
asked by anonymous 25.07.2017 / 22:42

1 answer

1

You can implement algorithms learned in school. But in your case you want to make an adaptation where you work with each uchar of the vector being a 256 base number, correct? In addition, you must define the type of division that will be made. Let's assume it's a Euclidean division of positive numbers.

The following image will guide you. It gives as an example the division of two numbers, a dividend with six figures (it is recommended that the largest magnitude is not zero) divided by a divisor of four (the largest magnitude simply can not be zero). The image only shows the positions of the digits operated to make it clear how to perform the operations in terms of steps.

The image does not display sample figures because this depends on the basis on which it works and the explanation will be given regardless of the basis. The point is that the logic is independent of the numeric base, so it is valid for binary, octal, decimal, hexadecimal, base 256, etc., so only the houses of each digit and the constraints are considered (for example, from 0 to 7 and whatever exceeds those limits generates carry).

Thealgorithmconsistsofrepeatedlyfindingacorrectdigitfromthequotient,fromthelargesttothesmallestdigits,andupdatingatemporarynumberuntilthequotientiscomplete,thenthefinaltemporarynumberistheremainder.Eachrepetitionisperformedconsideringthepairingofdigits.

Atfirst,thetemporarynumberisequaltothedividend.Witheachrepetition,oneworkswiththedigitsofgreatermagnitudeofthetemporaryone.Theamountoftemporarydigitsworkedinthefirstcycleisthesamenumberofdigitsofthedivisor(intheexample,onlythefourmostadvanceddigitsareworked),andthenextdigitsaplusdigitfromthetemporarytoworkonthem.Theserepetitionsoccuruntiltherearenomorenumeralsleftinthetemporarynumbertoincludeattheendofthecycle,whichisthereforethelast.

Thisworkconsistsof:(1)investigatewhichisthelargestdigit(onthebaseused)whoseproductofitwiththedivisorislessthanorequaltotheworkingportionofthetemporarynumber;(2)setthequotientfiguretothatnumber;(3)setthosetemporarydigitsbysubtractingthemwiththeproductthatwascalculatedin(1).

Therefore,aprocedureisrequiredthatcompareswhetheronenumberislessthanorequaltoanother(forstep(1)),anotherthatcalculatesmultiplication(forstep(1)),andyetanotherthatcalculatessubtraction(forstep(3)).Itislogicalthatusingthecomparatorandtheproductinprocedure(1),thisprogrammedthepartinsteadofcalculatingitinline,searchingforthecorrectfigureisanappropriatemeasure.Thereareseveralwaystofindthismaximum,it'suptoyou.InitsplaceIwouldworkinbinarybutreflectedinbase256aswell.

Callingthetemporary"Tmp1" would use another temporary "Tmp2" (for power values of 2) and a further "Tmp3" (for product "Tmp2 * Divider").

(a) Assign, by hour, "QuotientType = 0";

(b) Repeatedly work with "Tmp2 = 128", then "Tmp2 = 64", "Tmp = 32", thereafter until the last "Tmp2 = 1" (note that you can calculate shifting bits to gain performance ):

(b.1) Calculate "Tmp3 = Tmp2 * Divider" (you can calculate by shifting bits;

(b.2) If "Tmp3

26.07.2017 / 02:29