Na ciência da computação, a aritmética de precisão arbitrária, também chamada de aritmética de bignum, aritmética de precisão múltipla ou, às vezes, aritmética de precisão infinita, indica que os cálculos são realizados em números cujos dígitos de precisão são potencialmente limitados apenas pela memória disponível do sistema hospedeiro. Isso contrasta com a aritmética de precisão fixa, mais rápida, encontrada na maioria dos hardwares de Unidade lógica e aritmética (ULA), que normalmente oferece entre 8 e 64 bits de precisão.

Várias linguagens de programação modernas têm suporte integrado para bignums, e outras possuem bibliotecas disponíveis para matemática de inteiros e ponto flutuante com precisão arbitrária. Em vez de armazenar valores como um número fixo de bits relacionado ao tamanho do registrador do processador, essas implementações normalmente usam arrays de comprimento variável de dígitos.

A precisão arbitrária é usada em aplicações onde a velocidade da aritmética não é um fator limitante, ou onde são necessários resultados precisos com números muito grandes. Ela não deve ser confundida com a computação simbólica fornecida por muitos sistemas de computação algébrica, que representam números por expressões como e, portanto, podem representar qualquer número computável com precisão infinita.

Aplicações

Uma aplicação comum é a Criptografia de chave pública, cujos algoritmos comumente empregam aritmética com inteiros que possuem centenas de dígitos. Outra é em situações onde limites artificiais e erros de transbordo seriam inadequados. Também é útil para verificar os resultados de cálculos de precisão fixa e para determinar valores ótimos ou quase ótimos para coeficientes necessários em fórmulas, por exemplo, o que aparece na Integração gaussiana.

A aritmética de precisão arbitrária também é usada para computar constantes matemáticas fundamentais, como π, com milhões ou mais de dígitos e para analisar as propriedades das cadeias de dígitos ou, mais geralmente, para investigar o comportamento preciso de funções como a Função zeta de Riemann, onde certas questões são difíceis de explorar através de métodos analíticos. Outro exemplo é na renderização de imagens de fractais com uma ampliação extremamente alta, como as encontradas no Conjunto de Mandelbrot.

A aritmética de precisão arbitrária também pode ser usada para evitar o transbordo (overflow), que é uma limitação inerente da aritmética de precisão fixa. Semelhante ao visor do odômetro de um automóvel que pode mudar de 99999 para 00000, um inteiro de precisão fixa pode apresentar efeito de rotação (wraparound) se os números crescerem muito para serem representados no nível fixo de precisão. Alguns processadores podem, em vez disso, lidar com o transbordo por aritmética de saturação, o que significa que se um resultado for irrepresentável, ele será substituído pelo valor representável mais próximo. (Com saturação não sinalizada de 16 bits, adicionar qualquer quantidade positiva a 65535 resultaria em 65535.) Alguns processadores podem gerar uma exceção se um resultado aritmético exceder a precisão disponível. Onde necessário, a exceção pode ser capturada e recuperada — por exemplo, a operação poderia ser reiniciada em software usando aritmética de precisão arbitrária.

Em muitos casos, a tarefa ou o programador pode guarantee que os valores inteiros em uma aplicação específica não crescerão o suficiente para causar um transbordo. Tais garantias podem ser baseadas em limites pragmáticos: um programa de frequência escolar pode ter um limite de tarefa de 4.000 alunos. Um programador pode projetar o cálculo de modo que os resultados intermediários permaneçam dentro dos limites de precisão especificados.

Algumas linguagens de programação, como Lisp, Python, Perl, Haskell, Ruby e Raku, usam, ou têm a opção de usar, números de precisão arbitrária para toda a aritmética de inteiros. Isso permite que os inteiros cresçam para qualquer tamanho limitado apenas pela memória disponível do sistema. Embora isso reduza o desempenho, elimina a preocupação com resultados incorretos (ou exceções) devido a um transbordo simples. Também torna possível quase garantir que os resultados aritméticos serão os mesmos em todas as máquinas, independentemente do tamanho da palavra de qualquer máquina específica. O uso exclusivo de números de precisão arbitrária em uma linguagem de programação também simplifica a linguagem, porque um número é um número e não há necessidade de múltiplos tipos para representar diferentes níveis de precisão.

Problemas de implementação

A aritmética de precisão arbitrária é consideravelmente mais lenta do que a aritmética que usa números que cabem inteiramente dentro dos registradores do processador, já que esta última geralmente é implementada em hardware, enquanto a primeira deve ser implementada em software. Mesmo que o computador careça de hardware para certas operações (como divisão de inteiros ou todas as operações de ponto flutuante) e o software seja fornecido em seu lugar, ele usará tamanhos de números intimamente relacionados aos registradores de hardware disponíveis: apenas uma ou duas palavras. Existem exceções, já que certas máquinas de comprimento de palavra variável das décadas de 1950 e 1960, notadamente o IBM 1620, IBM 1401 e a série Honeywell 200, podiam manipular números limitados apenas pelo armazenamento disponível, com um bit extra que delimitava o valor.

Estrutura de dados Os números podem ser armazenados em um formato de ponto fixo ou em um formato de ponto flutuante como um significando multiplicado por um expoente arbitrário. No entanto, como a divisão introduz quase imediatamente sequências de dígitos que se repetem infinitamente (como em decimal ou em binário), caso essa possibilidade surja, a representação seria truncada em algum tamanho satisfatório ou então seriam usados números racionais: um grande inteiro para o numerador e outro para o denominador. Mas mesmo com o máximo divisor comum simplificado, a aritmética com números racionais pode se tornar complicada muito rapidamente: , e se for adicionado em seguida, o resultado será .

O tamanho dos números de precisão arbitrária é limitado na prática pelo armazenamento total disponível e pelo tempo de computação.

Operações Inúmeros algoritmos foram desenvolvidos para realizar eficientemente operações aritméticas em números armazenados com precisão arbitrária. Em particular, supondo que dígitos sejam empregados, os algoritmos foram projetados para minimizar a complexidade assintótica para grandes .

Os algoritmos mais simples são para adição e subtração, onde simplesmente se adiciona ou subtrai os dígitos em sequência, propagando o transporte conforme necessário, o que resulta em um algoritmo (veja notação grande-).

A comparação também é muito simples. Compare os dígitos de ordem superior (ou palavras de máquina) até encontrar uma diferença. Comparar o resto dos dígitos/palavras não é necessário. O pior caso é , mas pode terminar muito mais rápido com operandos de magnitude semelhante.

Para a multiplicação, os algoritmos mais diretos usados para multiplicar números à mão (como ensinado na escola primária) requerem operações , mas algoritmos de multiplicação que alcançam complexidade foram desenvolvidos, como o Algoritmo de Schönhage–Strassen, baseado em transformadas rápidas de Fourier, e também existem algoritmos com complexidade ligeiramente pior, mas com desempenho no mundo real às vezes superior para menores. A multiplicação de Karatsuba é um desses algoritmos.

Para divisão, veja Algoritmo de divisão.

Para uma lista de algoritmos junto com estimativas de complexidade, veja Complexidade computacional de operações matemáticas.

Precisão predefinida Em algumas linguagens como REXX e ooRexx, a precisão de todos os cálculos deve ser definida antes de realizar um cálculo. Outras linguagens, como Python e Ruby, estendem a precisão automaticamente para evitar transbordo.

Exemplo O cálculo de fatoriais pode facilmente produzir números muito grandes. Isso não é um problema para o seu uso em muitas fórmulas (como Série de Taylor) porque eles aparecem junto com outros termos, de modo que — com atenção cuidadosa à ordem de avaliação — os valores dos cálculos intermediários não causam problemas. Se forem desejados valores aproximados de números fatoriais, a Aproximação de Stirling fornece bons resultados usando aritmética de ponto flutuante. O maior valor representável para uma variável inteira de tamanho fixo pode ser excedido mesmo para argumentos relativamente pequenos, conforme mostrado na tabela abaixo. Até mesmo os números de ponto flutuante logo ficam fora de alcance, por isso pode ajudar reformular os cálculos em termos do logaritmo do número.

Mas se forem desejados valores exatos para grandes fatoriais, então é necessário um software especial, como no pseudocódigo a seguir, que implementa o algoritmo clássico para calcular 1, , , ,...: os números fatoriais sucessivos.

constants: Limit = 1000 % Dígitos suficientes. Base = 10 % A base da aritmética simulada. FactorialLimit = 365 % Número alvo para resolver, 365! tdigit: Array[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"]

variables: digit: Array[1:Limit] of 0..9 % O número grande. carry, d: Integer % Assistentes durante a multiplicação. last: Integer % Índice para os dígitos do número grande. text: Array[1:Limit] of character % Rascunho para a saída.

digit[*] := 0 % Limpa todo o array. last := 1 % O número grande começa como um único dígito, digit := 1 % seu único dígito é 1.

for n := 1 to FactorialLimit: % Avança produzindo 1!, 2!, 3!, 4!, etc.

carry := 0 % Inicia uma multiplicação por n. for i := 1 to last: % Passa por cada dígito. d := digit[i] * n + carry % Multiplica um único dígito. digit[i] := d mod Base % Mantém o dígito de ordem inferior do resultado. carry := d div Base % Transporta para o próximo dígito.

while carry > 0: % Armazena o transporte restante no número grande. if last >= Limit: error("transbordo") last := last + 1 % Mais um dígito. digit[last] := carry mod Base carry := carry div Base % Remove o último dígito do transporte.

text[*] := " " % Agora prepara a saída. for i := 1 to last: % Traduz de binário para texto. text[Limit - i + 1] := tdigit[digit[i]] % Invertendo a ordem. print text[Limit - last + 1:Limit], " = ", n, "!"

Com o exemplo em vista, vários detalhes podem ser discutidos. O mais importante é a escolha da representação do número grande. Neste caso, apenas valores inteiros são necessários para os dígitos, portanto, um array of inteiros de largura fixa é adequado. É conveniente que os elementos sucessivos do array representem potências mais altas da base.

A segunda decisão mais importante é a escolha da base da aritmética, aqui dez. Existem muitas considerações. A variável de rascunho deve ser capaz de conter o resultado de uma multiplicação de um único dígito mais o transporte da multiplicação do dígito anterior. Na base dez, um inteiro de dezesseis bits é certamente adequado, pois permite até 32767. No entanto, este exemplo trapaceia, no sentido de que o valor de não é, por si só, limitado a um único dígito. Isso tem a consequência de que o método falhará para ou algo do tipo. Em uma implementação mais geral, também usaria uma representação de múltiplos dígitos. Uma segunda consequência do atalho é que, após a conclusão da multiplicação de múltiplos dígitos, o último valor de carry pode precisar ser transportado para múltiplos dígitos de ordem superior, não apenas um.