Aritmética de precisão arbitrária - Arbitrary-precision arithmetic

Na ciência da computação , a aritmética de precisão arbitrária , também chamada de aritmética 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 limitados apenas pela memória disponível do sistema host. Isso contrasta com a aritmética de precisão fixa mais rápida encontrada na maioria dos hardwares de unidade lógica aritmética (ALU), que normalmente oferece entre 8 e 64 bits de precisão.

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

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

Formulários

Uma aplicação comum é a criptografia de chave pública , cujos algoritmos comumente empregam aritmética com inteiros com centenas de dígitos. Outra é em situações em que limites e transbordamentos artificiais 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 calcular constantes matemáticas fundamentais , como π para milhões ou mais 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 por meio de métodos analíticos. Outro exemplo é a renderização de imagens 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 estouro , que é uma limitação inerente da aritmética de precisão fixa. Semelhante ao display de um hodômetro de 5 dígitos que muda de 99999 para 00000, um inteiro de precisão fixa pode exibir um contorno se os números ficarem muito grandes para representar no nível fixo de precisão. Em vez disso, alguns processadores podem lidar com o estouro por saturação , o que significa que, se um resultado não for representável, ele será substituído pelo valor representável mais próximo. (Com a saturação sem sinal de 16 bits, adicionar qualquer valor positivo a 65535 resultaria em 65535.) Alguns processadores podem gerar uma exceção se um resultado aritmético exceder a precisão disponível. Quando necessário, a exceção pode ser detectada e recuperada - por exemplo, a operação pode ser reiniciada no software usando aritmética de precisão arbitrária.

Em muitos casos, a tarefa ou o programador pode garantir que os valores inteiros em um aplicativo específico não crescerão o suficiente para causar um estouro. Essas garantias podem ser baseadas em limites pragmáticos: um programa de frequência escolar pode ter um limite de tarefas de 4.000 alunos. Um programador pode projetar a computação de forma que os resultados intermediários fiquem dentro dos limites de precisão especificados.

Algumas linguagens de programação como Lisp , Python , Perl , Haskell e Ruby usam, ou têm a opção de usar, números de precisão arbitrária para toda a aritmética de inteiros. Embora isso reduza o desempenho, elimina a possibilidade de resultados incorretos (ou exceções) devido ao estouro simples. Também torna possível garantir que os resultados aritméticos serão iguais em todas as máquinas, independentemente do tamanho de palavra de qualquer máquina em particular . 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 vários 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 usando números que cabem inteiramente nos registradores do processador, uma vez que os últimos são geralmente implementados em aritmética de hardware, ao passo que os primeiros devem ser implementados em software. Mesmo se o computador não tiver hardware para certas operações (como divisão inteira ou todas as operações de ponto flutuante) e o software for fornecido, ele usará tamanhos de número intimamente relacionados aos registros de hardware disponíveis: uma ou duas palavras apenas e definitivamente não N palavras. Há exceções, pois certas máquinas de comprimento de palavra variável das décadas de 1950 e 1960, notadamente as séries IBM 1620 , IBM 1401 e Honeywell Liberator , podiam manipular números limitados apenas pelo armazenamento disponível, com um bit extra que delimitava o valor.

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, uma vez que a divisão introduz quase que imediatamente sequências de dígitos que se repetem infinitamente (como 4/7 em decimal ou 1/10 em binário), se essa possibilidade surgir, a representação seria truncada em algum tamanho satisfatório ou os números racionais seriam usado: um grande número inteiro para o numerador e para o denominador . Mas mesmo com o maior divisor comum dividido, 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, 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.

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

Os algoritmos mais simples são para adição e subtração , onde alguém simplesmente adiciona ou subtrai os dígitos em sequência, carregando conforme necessário, o que produz um algoritmo O ( N ) (ver notação grande O ).

A comparação também é muito simples. Compare os dígitos de ordem superior (ou palavras de máquina) até que uma diferença seja encontrada. Não é necessário comparar o resto dos dígitos / palavras. O pior caso é ( N ) , mas geralmente será muito mais rápido. ${\ displaystyle \ Theta}$

Para a multiplicação , os algoritmos mais simples usados ​​para multiplicar números à mão (como ensinado na escola primária) requerem operações ( N ² ) , mas os algoritmos de multiplicação que alcançam a complexidade O ( N  log ( N ) log (log ( N ))) foram desenvolvido, como o algoritmo Schönhage-Strassen , baseado em transformadas rápidas de Fourier , e também existem algoritmos com complexidade um pouco pior, mas às vezes com desempenho do mundo real superior para N menores . A multiplicação de Karatsuba é um desses algoritmos. ${\ displaystyle \ Theta}$

Para divisão , consulte algoritmo de divisão .

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

Para obter exemplos em montagem x86 , consulte links externos .

Precisão predefinida

Em alguns idiomas, como REXX , a precisão de todos os cálculos deve ser definida antes de fazer um cálculo. Outras linguagens, como Python e Ruby , estendem a precisão automaticamente para evitar estouro.

Exemplo

O cálculo de fatoriais pode facilmente produzir números muito grandes. Isso não é um problema para seu uso em muitas fórmulas (como a série de Taylor ) porque aparecem junto com outros termos, de modo que - dada a atenção cuidadosa à ordem de avaliação - os valores de cálculo intermediários não são problemáticos. Se valores aproximados de números fatoriais são desejados, a aproximação de Stirling dá 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. Mesmo os números de ponto flutuante são logo ultrapassados, então pode ajudar a reformular os cálculos em termos do logaritmo do número.

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

Constant Limit = 1000;            % Sufficient digits.
Constant Base = 10;               % The base of the simulated arithmetic.
Constant FactorialLimit = 365;    % Target number to solve, 365!
Array digit[1:Limit] of integer;  % The big number.
Integer carry,d;                  % Assistants during multiplication.
Integer last,i;                   % Indices to the big number's digits.
Array text[1:Limit] of character; % Scratchpad for the output.
Constant tdigit[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"];
BEGIN
 digit:=0;                        % Clear the whole array.
 digit[1]:=1;                     % The big number starts with 1,
 last:=1;                         % Its highest-order digit is number 1.
 for n:=1 to FactorialLimit do    % Step through producing 1!, 2!, 3!, 4!, etc. 
  carry:=0;                       % Start a multiply by n.
  for i:=1 to last do             % Step along every digit.
   d:=digit[i]*n + carry;         % The classic multiply.
   digit[i]:=d mod Base;          % The low-order digit of the result.
   carry:=d div Base;             % The carry to the next digit.
  next i;
  while carry > 0                 % Store the carry in the big number.            
   if last >= Limit then croak("Overflow!");  % If possible!
   last:=last + 1;                % One more digit.
   digit[last]:=carry mod Base;   % Placed.
   carry:=carry div Base;         % The carry reduced.
  Wend                            % With n > Base, maybe > 1 digit extra.
  text:=" ";                      % Now prepare the output.
  for i:=1 to last do             % Translate from binary to text.
   text[Limit - i + 1]:=tdigit[digit[i]];  % Reversing the order.
  next i;                         % Arabic numerals put the low order last.
  Print text," = ",n,"!";         % Print the result!
 next n;                          % On to the next factorial up.
END;

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

A segunda decisão mais importante está na escolha da base da aritmética, aqui dez. Existem muitas considerações. A variável d do scratchpad 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 número inteiro de dezesseis bits é certamente adequado, pois permite até 32767. No entanto, este exemplo engana, pois o valor de n não está limitado a um único dígito. Isso tem como consequência que o método falhará para n > 3200 ou mais. Em uma implementação mais geral, n também usaria uma representação de vários dígitos. Uma segunda consequência do atalho é que após a multiplicação de vários dígitos ter sido concluída, o último valor de transporte pode precisar ser transportado para vários dígitos de ordem superior, não apenas um.

Há também a questão de imprimir o resultado em base dez, para consideração humana. Como a base já é de dez, o resultado poderia ser mostrado simplesmente imprimindo os dígitos sucessivos de matriz dígitos , mas que eles iriam aparecer com o dígito mais alta ordem último (de modo a que 123 seria apresentado como "321"). A matriz inteira pode ser impressa em ordem reversa, mas isso apresentaria o número com zeros à esquerda ("00000 ... 000123") que pode não ser apreciado, portanto, esta implementação constrói a representação em uma variável de texto preenchida com espaço e, em seguida, imprime naquela. Os primeiros resultados (com espaçamento a cada quinto dígito e anotação adicionada aqui) são:

Essa implementação poderia fazer um uso mais eficaz da aritmética embutida do computador. Um escalonamento simples seria usar a base 100 (com alterações correspondentes no processo de tradução para saída) ou, com variáveis ​​de computador suficientemente amplas (como inteiros de 32 bits), poderíamos usar bases maiores, como 10.000. Trabalhar em uma base de potência de 2 mais perto das operações inteiras integradas do computador oferece vantagens, embora a conversão para uma base decimal para 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 (contanto que os operandos caibam em palavras de máquina única), portanto, há grandes ganhos em empacotar o maior número possível em cada elemento do matriz de dígitos. O computador também pode oferecer recursos para dividir um produto em um dígito e transportar 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 que pode ser explorado em adição e subtração de precisão múltipla. Esse tipo de detalhe é o grão de programadores de código de máquina, e uma rotina de bignumber de linguagem assembly adequada pode ser executada muito mais rápido do que o resultado da compilação de uma linguagem de alto nível, que não fornece acesso a tais recursos.

Para uma multiplicação de um dígito, as variáveis ​​de trabalho devem ser capazes de conter o valor (base-1) ² + transporte, onde o valor máximo do transporte é (base-1). Da mesma forma, as variáveis ​​usadas para indexar a matriz de dígitos são elas próprias limitadas em largura. Uma maneira simples de estender os índices seria lidar com os dígitos do bignumber em blocos de algum tamanho conveniente de modo que o endereçamento seria via (bloco i , dígito j ) onde i e j seriam números inteiros pequenos, ou, um poderia escalar para empregando técnicas de bignumber para as variáveis ​​de indexação. Em última análise, a capacidade de armazenamento da máquina e o tempo de execução impõem limites ao tamanho do problema.

História

O primeiro computador de negócios da IBM , o IBM 702 (uma máquina de tubo a vácuo ) de meados da década de 1950, implementou a aritmética de inteiros inteiramente em hardware em cadeias de dígitos de qualquer comprimento de 1 a 511 dígitos. A implementação mais antiga de software de aritmética de precisão arbitrária foi provavelmente a do Maclisp . Posteriormente, por volta de 1980, os sistemas operacionais VAX / VMS e VM / CMS ofereceram recursos de bignum como uma coleção de funções de string em um caso e nas linguagens EXEC 2 e REXX no outro.

Uma implementação inicial generalizada estava disponível por meio do IBM 1620 de 1959–1970. O 1620 era uma máquina de dígitos decimais que usava transistores discretos, mas tinha hardware (que usava tabelas de pesquisa ) para realizar aritmética de inteiros em cadeias de dígitos de comprimento que poderia ser de dois a qualquer memória disponível. Para aritmética de ponto flutuante, a mantissa foi restrita a cem dígitos ou menos, e o expoente foi restrito a apenas dois dígitos. A maior memória fornecida ofereceu 60.000 dígitos, no entanto, os compiladores Fortran para o 1620 se estabeleceram em tamanhos fixos como 10, embora 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 cálculos.

Bibliotecas diferentes têm maneiras diferentes de representar números de precisão arbitrária, algumas bibliotecas funcionam apenas com números inteiros, outras armazenam números de ponto flutuante em uma variedade de bases (poderes decimais ou binários). Em vez de representar um número como valor único, alguns armazenam números como um par numerador / denominador ( racionais ) e alguns podem representar números totalmente computáveis , embora apenas até algum limite de armazenamento. Fundamentalmente, as máquinas de Turing não podem representar todos os números reais , pois a cardinalidade de ℝ excede a cardinalidade de ℤ .

Veja também

• Algoritmo Karatsuba
• Multiplicação de Toom-Cook
• Algoritmo Schönhage-Strassen
• Algoritmo de Fürer
• Aritmética de precisão mista

Referências

• Knuth, Donald (2008). Algoritmos Seminuméricos . The Art of Computer Programming . 2 (3ª ed.). Addison-Wesley. ISBN 978-0-201-89684-8{{citações inconsistentes}}CS1 maint: postscript ( link ), Seção 4.3.1: Os algoritmos clássicos

links externos

• O Capítulo 9.3 de The Art of Assembly de Randall Hyde discute a aritmética de multiprecisão, com exemplos em montagem x86 .
• Tarefa do Rosetta Code Inteiros de precisão arbitrária Estudos de caso no estilo em que mais de 95 linguagens de programação calculam o valor de 5 ** 4 ** 3 ** 2 usando aritmética de precisão arbitrária.