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 π·sin(2) 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

1 3

{\displaystyle {\sqrt {\frac {1}{3}}}}

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 ⁠4/7⁠ em decimal ou ⁠1/10⁠ 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: ⁠1/99⁠ − ⁠1/100⁠ = ⁠1/9900⁠, e se ⁠1/101⁠ for adicionado em seguida, o resultado será ⁠10001/999900⁠. 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

N

{\displaystyle N}

dígitos sejam empregados, os algoritmos foram projetados para minimizar a complexidade assintótica para grandes

N

{\displaystyle N}

. 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

O ( N )

{\displaystyle O(N)}

(veja notação grande-

O

{\displaystyle O}

). 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 é

Θ ( N )

{\displaystyle \Theta (N)}

, 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

Θ (

N

2

)

{\displaystyle \Theta (N^{2})}

, mas algoritmos de multiplicação que alcançam complexidade

O ( N log ⁡ ( N ) log ⁡ ( log ⁡ ( N ) ) )

{\displaystyle O(N\log(N)\log(\log(N)))}

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

N

{\displaystyle N}

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, 1 × 2, 1 × 2 × 3, 1 × 2 × 3 × 4,...: 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] := 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 d 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 não é, por si só, limitado a um único dígito. Isso tem a consequência de que o método falhará para n > 3200 ou algo do tipo. Em uma implementação mais geral, n 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. Há também a questão de imprimir o resultado na base dez, para consideração humana. Como a base já é dez, o resultado poderia ser mostrado simplesmente imprimindo os dígitos sucessivos do array digit, mas eles apareceriam com o dígito de ordem mais alta por último (de modo que 123 apareceria como "321"). Todo o array poderia ser impresso em ordem inversa, mas isso apresentaria o número com zeros à esquerda ("00000...000123"), o que pode não ser apreciado, por isso esta implementação constrói a representação em uma variável de texto preenchida com espaços e depois a imprime. Os primeiros resultados (com espaçamento a cada cinco dígitos e anotações adicionadas aqui) são:

Esta implementação poderia fazer um uso mais eficaz da aritmética integrada do computador. Uma evolução simples seria usar a base 100 (com as mudanças correspondentes no processo de tradução para a saída) ou, com variáveis de computador suficientemente largas (como inteiros de 32 bits), poderíamos usar bases maiores, como 10000. Trabalhar em uma base de potência de 2 mais próxima das operações de inteiros integradas do computador oferece vantagens, embora a conversão para uma base decimal para a saída se torne mais difícil. Em computadores modernos típicos, adições e multiplicações levam um tempo constante independente dos valores dos operandos (desde que os operandos caiam em palavras de máquina únicas), portanto, há grandes ganhos em compactar o máximo possível de um bignumber em cada elemento do array de dígitos. O computador também pode oferecer recursos para dividir um product em um dígito e um transporte sem exigir as duas operações de mod e div como no exemplo, e quase todas as unidades aritméticas fornecem um sinalizador de transporte (carry flag) que pode ser explorado na adição e subtração de precisão múltipla. Este tipo de detalhe é o forte dos programadores de linguagem de máquina, e uma rotina de bignumber em linguagem assembly adequada pode rodar mais rápido do que o resultado da compilação de uma linguagem de alto nível, que não fornece acesso direto a tais recursos, mas sim mapeia as instruções de alto nível para o seu modelo da máquina alvo usando um compilador otimizador.

História O primeiro computador comercial da IBM, o IBM 702 (a máquina de válvulas de vácuo) de meados da década de 1950, implementava a aritmética de inteiros inteiramente em hardware em cadeias de dígitos de qualquer comprimento de 1 a 511 dígitos. A primeira implementação generalizada em software de aritmética de precisão arbitrária foi provavelmente a do Maclisp. Mais tarde, por volta de 1980, os sistemas operacionais VAX/VMS e VM/CMS ofereceram recursos de bignum como uma coleção de funções de cadeia de caracteres em um caso e nas linguagens EXEC 2 e REXX no outro. Uma implementação generalizada antiga estava disponível através do IBM 1620 de 1959–1970. O 1620 era uma máquina de dígitos decimals que usava transistores discretos, mas possuía hardware (que usava tabelas de busca) para realizar aritmética de inteiros em cadeias de dígitos de um comprimento que poderia ir de dois até qualquer quantidade de memória disponível. Para a aritmética de ponto flutuante, a mantissa era restrita a cem dígitos ou menos, e o expoente era restrito a apenas dois dígitos. A maior memória fornecida oferecia 60 000 dígitos, no entanto, os compiladores Fortran para o 1620 se fixavam em tamanhos padrão como 10, embora isso pudesse ser especificado em um cartão de controle se o padrão não fosse satisfatório.

Bibliotecas de software A aritmética de precisão arbitrária na maioria dos softwares de computador é implementada chamando uma biblioteca externa que fornece tipos de dados e sub-rotinas para armazenar números com a precisão solicitada e realizar computações. Diferentes bibliotecas têm diferentes maneiras de representar números de precisão arbitrária; algumas bibliotecas trabalham apenas com números inteiros, outras armazenam números de ponto flutuante em uma variedade de bases (potências decimais ou binárias). Em vez de representar um número como um único valor, algumas armazenam números como um par numerador-denominador (racionais) e algumas podem representar totalmente números computáveis, embora apenas até algum limite de armazenamento. Fundamentalmente, as máquinas de Turing não podem representar todos os números reais, já que a cardinalidade de

R

{\displaystyle \mathbb {R} }

excede a cardinalidade de

Z

{\displaystyle \mathbb {Z} }

.

Veja também Algoritmo de Karatsuba Algoritmo de Schönhage–Strassen Multiplicação de Toom-Cook

Referências

Leitura adicional Knuth, Donald (2008). Seminumerical Algorithms. Col: The Art of Computer Programming. 2 3rd ed. [S.l.]: Addison-Wesley. ISBN 978-0-201-89684-8 , Section 4.3.1: The Classical Algorithms Derick Wood (1984). Paradigms and Programming with Pascal. [S.l.]: Computer Science Press. ISBN 0-914894-45-5 Richard Crandall, Carl Pomerance (2005). Prime Numbers. [S.l.]: Springer-Verlag. ISBN 9780387252827 , Chapter 9: Fast Algorithms for Large-Integer Arithmetic

Ligações externas Rosetta Code task Arbitrary-precision integers Estudos de caso no estilo em que mais de 95 linguagens de programação computam o valor de 5**4**3**2 usando aritmética de precisão arbitrária.