C++: Vector division<unsigned char>

Question

I’m making a dynamic numeric class, storing the value of the number in a vector of bytes. I did the functions of summation, subtraction and multiplication in the same way that we learn in school, but this cannot be applied in the division. What’s 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’ve done are the same as what you learn in school considering each uchar vector as if it were a digit based on 256.

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 base digit 256, correct? In addition, one must define the type of division that will be made. Let’s assume it’s Euclidean division of positive numbers.

The following image will serve as a guide. It presents as an example the division of two numbers, a dividend with six digits (it is recommended that the highest magnitude is not zero) divided by a divisor of four (the highest magnitude simply cannot be zero). The image only shows the positions of the digits operated to clarify how the operations are performed in terms of steps.

The image does not display example digits because it depends on the basis on which it is worked and the explanation will be given independently of the base. The question is that the logic is independent of the numerical base, therefore it is valid for binary system, octal, decimal, hexadecimal, base 256, etc., thus considering only the boxes of each digit and the restrictions (for example, on an octal basis the digits range from 0 to 7 and what exceeds these limits generates carry).

The algorithm consists of repeatedly finding a correct quotient digit, from the highest magnitude digits to the lowest, and updating a temporary number until the quotient is complete, when then the final temporary number is the rest. Each repetition is performed considering the pairing of digits.

At the beginning, the temporary number is equal to the dividend. At each repetition, we work with the digits of greater magnitude of the temporary. The number of temporary digits worked in the first cycle is the same number of digits as the divisor (in the example, only the four most advanced digits are worked) and in the following one digit is released from the temporary digit to work on them. These repetitions occur until there are no more digits left in the temporary number to include at the end of the cycle, this being the last.

This work consists of: (1) investigate which is the largest digit (on the base used) whose product with the splitter is less than or equal to the worked portion of the temporary number; (2) specify the number of the quotient with that number; (3) specify those temporary digits by subtracting them with the product which has been calculated in (1).

Therefore it is necessary a procedure that compares whether one number is less than or equal to another (for step (1)), another that calculates multiplication (for step (1)) and another that calculates subtraction (for step (3)). It is logical that using the comparator and the product in the procedure (1), this programmed the part instead of calculating it inline, in the search of the correct digit is an appropriate measure. There are several ways to find this maximum, gets your choice. In its place I would work in binary but reflected in base 256, so.

Calling the temporary "Tmp1", it would use another temporary "Tmp2" (for power values of 2) and another "Tmp3" (for product "Tmp2*Divisor").

(a) Assign, per hour, "Digit = 0";

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

(b.1) Calculate "Tmp3=Tmp2*Divisor" (can be calculated by moving bits;

(b.2) If "Tmp3<=Tmp1", calculate "Digit quotient=Digit quotient+Tmp2";

(b.3) If "Tmp3<=Tmp1", calculate "Tmp1 = Tmp1-Tmp3".