1

Estou fazendo uma classe numérica dinâmica, armazenando o valor do número em um vetor de bytes. Fiz as funções de soma, subtração e multiplicação do mesmo jeito que se aprende na escola, porém isso não pode ser aplicado na divisão. Qual a maneira certa de fazer?

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;
    }
    ...
};

As operações que fiz são iguais as que se aprende na escola considerando cada uchar do vetor como se fosse um algarismo com base 256.

1 Resposta 1

1

Pode sim implementar algoritmos aprendidos na escola. Mas no seu caso você quer fazer uma adaptação onde se trabalha com cada uchar do vetor sendo um algarismo de base 256, correto? Além disso, deve-se definir o tipo de divisão que será feita. Vamos assumir que é divisão euclidiana de números positivos.

A imagem a seguir servirá de guia. Ela apresenta como exemplo a divisão de dois números, um dividendo com seis algarismos (recomenda-se que o de maior magnitude não seja zero) dividido por um divisor de quatro (o de maior magnitude simplesmente não pode ser zero). A imagem apenas apresenta as posições dos algarismos operados para ficar mais claro como se realizam as operações em termos de etapas.

A imagem não apresenta algarismos de exemplo porque isso depende da base em que se trabalha e a explicação será dada independentemente da base. A questão é que a lógica independe da base numérica, portanto vale para sistema binário, octal, decimal, hexadecimal, base 256, etc, assim se atentando apenas às casas de cada dígito e às restrições (por exemplo, em base octal os dígitos vão de 0 a 7 e o que exceder desses limites gera carry).

Casas de algarismos em processo de divisão euclidiana. O algoritmo consiste em repetidamente encontrar um dígito correto do quociente, dos dígitos de maior magnitude aos de menor, e atualizar um número temporário até que o quociente esteja completo, quando então o número temporário final é o resto. Cada repetição é realizada considerando o emparelhamento de algarismos.

No início, o número temporário é igual ao dividendo. A cada repetição, trabalha-se com os dígitos de maior magnitude do temporário. A quantidade de dígitos do temporário trabalhados no primeiro ciclo é o mesmo número de dígitos do divisor (no exemplo, apenas os quatro algarismos mais avançados são trabalhados) e nos seguintes libera-se mais um algarismo do temporário para trabalhar neles. Essas repetições ocorrem até não sobrar mais algarismos no número temporário para incluir ao final do ciclo, sendo este portanto o último.

Esse trabalho consiste em: (1) investigar qual é o maior algarismo (na base utilizada) cujo produto dele com o divisor é menor ou igual ao trecho trabalhado do número temporário; (2) setar o algarismo do quociente com esse número; (3) setar aqueles algarismos temporários com a subtração deles com o produto que foi calculado em (1).

Portanto é necessário um procedimento que compara se um número é menor ou igual a outro (para o passo (1)), outro que calcula multiplicação (para o passo (1)) e outro ainda que calcula subtração (para o passo (3)). É lógico que utilizar o comparador e o produto no procedimento (1), este programado a parte ao invés de calculá-lo inline, na busca do algarismo correto é uma medida adequada. Há várias formas de encontrar esse máximo, fica a sua escolha. No seu lugar eu trabalharia em binário mas refletido em base 256, assim.

Chamando o temporário de "Tmp1", usaria outro temporário "Tmp2" (para valores de potência de 2) e mais um "Tmp3" (para produto "Tmp2*Divisor").

(a) Atribuir, por hora, "DígitoDoQuociente=0";

(b) Repetidamente trabalhar com "Tmp2=128", depois "Tmp2=64", "Tmp=32", daí em diante até o último "Tmp2=1" (repare que dá para calcular deslocando bits para ganhar desempenho):

(b.1) Calcular "Tmp3=Tmp2*Divisor" (dá para calcular deslocando bits;

(b.2) Se "Tmp3<=Tmp1", calcular "DígitoDoQuociente=DígitoDoeQuociente+Tmp2";

(b.3) Se "Tmp3<=Tmp1", calcular "Tmp1 = Tmp1-Tmp3".

5
  • Como o resto pode ser negativo? 26/07/2017 às 1:16
  • De qualquer forma, a divisão será inteira euclidiana, pois essa classe não possui assinatura e nem algarismos decimais (ponto flutuante) 26/07/2017 às 1:25
  • A divisão inteira na computação é diferente da divisão inteira na matemática. Se, por exemplo, você escreve em C++ a expressão constante ((-99)%(15)), o valor da expressão será -9 quando na verdade o resto da divisão euclidiana retorna 6 (15-9). É porque ((99)%(15)) é 9, aí se o dividendo (no caso 99) trocar de sinal, na computação o resto (no caso 9) troca de sinal também.
    – RHER WOLF
    26/07/2017 às 7:07
  • Qual método você recomenda para o passo (1)? Sou novo nisso, só consigo pensar em usar um for ou um while, mas eu vou ter com isso 256^8-1 repetições no pior caso (0xFFFFFFFFFFFFFFFF / 1) 26/07/2017 às 12:40
  • Vou complementar no final da minha resposta.
    – RHER WOLF
    26/07/2017 às 19:15

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .