Aritmética de precisão arbitrária

A aritmética de precisão arbitrária, também conhecida como "bignum" ou simplesmente "aritmética longa" é um conjunto de estruturas de dados e algoritmos que permite processar números muito maiores do que os que podem ser usados ​​nos tipos de dados padrão. Aqui estão vários tipos de aritmética de precisão arbitrária.

Aritmética clássica de inteiros longos

A idéia principal é que o número seja armazenado como uma array de seus "dígitos" em alguma base. As bases usadas com mais frequências são decimais, potências decimais ($10^4$ or $10^9$) e binárias.

As operações nos números desta forma são realizadas usando algoritmos "da escola" de adição, subtração, multiplicação e divisão. Também é possível usar algoritmos de multiplicação rápida: transformada rápida de Fourier e algoritmo de Karatsuba.

Aqui descrevemos a aritmética longa apenas para números inteiros não negativos. Para estender os algoritmos para lidar com números inteiros negativos, é necessário introduzir e manter condições extras(booleans) de "número negativo" ou usar outras modificações nos algoritmos.

Estrutura de dados

Armazenaremos números como um vector<int>, no qual cada elemento é um único "dígito" do número.

typedef vector<int> lnum;

Para melhorar o desempenho, usaremos $10^9$ como base, para que cada "dígito" do número longo contenha 9 dígitos decimais de uma só vez.

const int base = 1000*1000*1000;

Os dígitos serão armazenados na ordem do menos ao mais significativo. odas as operações serão implementadas para que, após cada uma delas, o resultado não tenha zeros à esquerda. Todas as operações que podem resultar em um número com zeros à esquerda devem ser seguidas por um código que os remova. Observe que nesta representação existem duas notações válidas para o número zero: e vetor vazio e um vetor com um único dígito zero.

Saída

Imprimir o número inteiro longo é a operação mais fácil. Primeiro, imprimimos o último elemento do vetor (ou 0, se o vetor estiver vazio), seguido pelo restante dos elementos preenchidos com zeros à esquerda, se necessário, para que tenham exatamente 9 dígitos.

printf ("%d", a.empty() ? 0 : a.back());
for (int i=(int)a.size()-2; i>=0; --i)
    printf ("%09d", a[i]);

Observe que é colocado o tipo "(int)" em a.size() para evitar um "unsigned integer underflow" se o vetor conter menos de 2 elementos.

Entrada

Para ler um número inteiro longo, leia sua notação em uma string e então em "dígitos" com atoi:

for (int i=(int)s.length(); i>0; i-=9)
    if (i < 9)
        a.push_back (atoi (s.substr (0, i).c_str()));
    else
        a.push_back (atoi (s.substr (i-9, 9).c_str()));

Se usarmos uma array de char em vez de uma de string, o código será ainda mais curto:

for (int i=(int)strlen(s); i>0; i-=9) {
    s[i] = 0;
    a.push_back (atoi (i>=9 ? s+i-9 : s));
}

Se a entrada puder conter zeros à esquerda, eles poderão ser removidos da seguinte maneira:

while (a.size() > 1 && a.back() == 0)
    a.pop_back();

Adição

Incremente o número inteiro longo $a$ por $b$ e armazene o resultado em $a$:

int carry = 0;
for (size_t i=0; i<max(a.size(),b.size()) || carry; ++i) {
    if (i == a.size())
        a.push_back (0);
    a[i] += carry + (i < b.size() ? b[i] : 0);
    carry = a[i] >= base;
    if (carry)  a[i] -= base;
}

Subtração

Reduza o número inteiro longo $a$ por $b$ ($a \ge b$) e armazene em $a$:

int carry = 0;
for (size_t i=0; i<b.size() || carry; ++i) {
    a[i] -= carry + (i < b.size() ? b[i] : 0);
    carry = a[i] < 0;
    if (carry)  a[i] += base;
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();

Observe que, após executar a subtração, removemos os zeros à esquerda para manter a premissa de que nossos números inteiros longos não possuem zeros à esquerda.

Multiplicação por número inteiro curto

Multiplique o número inteiro longo $a$ pelo número inteiro curto $b$ ($b < base$) e armazene em $a$:

int carry = 0;
for (size_t i=0; i<a.size() || carry; ++i) {
    if (i == a.size())
        a.push_back (0);
    long long cur = carry + a[i] * 1ll * b;
    a[i] = int (cur % base);
    carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();

Otimização adicional: Se o tempo de execução for extremamente importante, você pode tentar substituir duas divisões por uma encontrando apenas o resultado inteiro da divisão (a variável carry) e usá-lo para encontrar o módulo usando a multiplicação. Isso geralmente torna o código mais rápido, embora não drasticamente.

Multiplicação por número inteiro longo

Multiplique números inteiros longos $a$ e $b$ armazenando em $c$:

lnum c (a.size()+b.size());
for (size_t i=0; i<a.size(); ++i)
    for (int j=0, carry=0; j<(int)b.size() || carry; ++j) {
        long long cur = c[i+j] + a[i] * 1ll * (j < (int)b.size() ? b[j] : 0) + carry;
        c[i+j] = int (cur % base);
        carry = int (cur / base);
    }
while (c.size() > 1 && c.back() == 0)
    c.pop_back();

Divisão por número inteiro curto

Divida o inteiro longo $a$ pelo inteiro curto $b$ ($b < base$), armazene o resultado inteiro em $a$ e o resto no carry:

int carry = 0;
for (int i=(int)a.size()-1; i>=0; --i) {
    long long cur = a[i] + carry * 1ll * base;
    a[i] = int (cur / b);
    carry = int (cur % b);
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();

Aritmética inteira longa para Fatoração

A idéia é armazenar o número inteiro como sua fatoração, ou seja, as potências dos primos que o dividem.

Essa abordagem é muito fácil de implementar e permite a multiplicação e a divisão facilmente (assintoticamente mais rápidas que o método clássico), mas não a adição ou subtração. Também é muito eficiente em termos de memória em comparação com a abordagem clássica.

Este método é frequentemente usado para cálculos módulo um número não-primo M; neste caso, um número é armazenado como potências dos divisores de M que dividem o número, mais o resto módulo M.

Aritmética inteira longa em módulos primos (Algoritmo de Garner)

A idéia é escolher um conjunto de números primos (normalmente eles são pequenos o suficiente para caber no tipo de dados padrão) e armazenar um número inteiro como um vetor de restos da divisão do número inteiro por cada um desses números primos.

O teorema do resto chinês afirma que essa representação é suficiente para restaurar exclusivamente qualquer número de 0 ao produto desses primos. O algoritmo de Garner permite restaurar o número dessa representação para um número inteiro normal.

Este método permite economizar memória em comparação com a abordagem clássica (embora a economia não seja tão dramática quanto na representação de fatoração). Além disso, permite realizar rápida adição, subtração e multiplicação no tempo proporcional ao número de números primos usados ​​como módulos (consulte o artigo teorema chinês do resto para implementação).

A desvantagem é que converter o número inteiro de volta à forma normal é bastante trabalhoso e requer a implementação da aritmética clássica de precisão arbitrária com multiplicação. Além disso, este método não suporta divisão.

Aritmética fracionária de precisão arbitrária

As frações ocorrem em competições de programação com bem menos frequência do que números inteiros, e a aritmética longa é muito mais difícil de implementar para frações, portanto, as competições de programação apresentam apenas um pequeno subconjunto da aritmética longa fracionária.

Aritmética em frações irredutíveis

Um número é representado como uma fração irredutível $\frac{a}{b}$, onde $a$ e $b$ são inteiros. Todas as operações em frações podem ser representadas como operações em numeradores e denominadores inteiros dessas frações. Geralmente, isso requer o uso de aritmética clássica de precisão arbitrária para armazenar numerador e denominador, porém um tipo de dados inteiro de 64 bits é suficiente para as operações.

Armazenando floats como um tipo separado

Às vezes, um problema requer o manuseio de números muito pequenos ou muito grandes, sem permitir overflow ou underflow. O tipo de dados interno usa de 8 a 10 bytes e permite valores do expoente no intervalo $ [- 308; 308] $, que às vezes pode ser insuficiente.

A abordagem é muito simples: uma variável inteira separada é usada para armazenar o valor do expoente e, após cada operação, o número de ponto flutuante é normalizado, ou seja, retornado ao intervalo $[0.1; 1)$ ajustando o expoente de acordo.

Quando dois desses números são multiplicados ou divididos, seus expoentes devem ser adicionados ou subtraídos, respectivamente. Quando números são adicionados ou subtraídos, eles devem ser levados ao expoente comum primeiro multiplicando um deles por 10, elevado à potência igual à diferença dos valores do expoente. O método gira em torno do expoente e as mudanças feitas no número.

Como nota final, a base do expoente não precisa ser igual a 10. Com base na representação interna dos números de ponto flutuante, faz mais sentido usar 2 como base do expoente.

Problemas