De precisão arbitrária Explicação aritmética

StackOverflow https://stackoverflow.com/questions/1218149

  •  10-07-2019
  •  | 
  •  

Pergunta

Eu estou tentando aprender C e se deparar com a incapacidade de trabalhar com números muito grandes (ou seja, 100 dígitos, 1000 dígitos, etc.). Estou ciente de que existem bibliotecas de fazer isso, mas eu quero tentar implementá-lo eu mesmo.

Eu só quero saber se alguém tem ou pode fornecer um relatório muito detalhado, estúpidos explicação do bignum.

Foi útil?

Solução

É tudo uma questão de armazenamento e algoritmos para números tratar como partes menores adequada. Vamos supor que você tem um compilador em que um int só pode ser de 0 a 99 e você deseja manipular números até 999999 (que só vai se preocupar com números positivos aqui para mantê-lo simples).

Você pode fazer isso dando a cada número três ints e usando as mesmas regras que você (deve ter) aprendeu de volta na escola primária para adição, subtração e as outras operações básicas.

Em uma biblioteca de precisão arbitrária, não há limite fixo sobre o número de tipos de base usados ??para representar os nossos números, apenas o que a memória pode conter.

A adição por exemplo: 123456 + 78: 

12 34 56
      78
-- -- --
12 35 34

Trabalho a partir do final menos significativo:

  • carry inicial = 0.
  • 56 + 78 + 0 transportar = 134 = 34 com um transporte
  • 34 + 00 + 1 de transporte = 35 = 35 0 com transportar
  • 12 + 00 + 0 carry = 12 = 12 com 0 carry

Esta é, de fato, como a adição geralmente funciona no nível de bit dentro de sua CPU.

A subtração é semelhante (usando subtração do tipo base e emprestado em vez de carry), multiplicação pode ser feito com adições repetidas (muito lento) ou produtos cruzados (mais rápido) e divisão é mais complicado, mas pode ser feito mudando e subtração dos números envolvidos (a divisão longa você teria aprendido como uma criança).

Eu realmente escrito bibliotecas para fazer este tipo de coisas usando os poderes máximos de dez que podem ser enquadrados em um número inteiro quando quadrado (para evitar estouro quando a multiplicação de dois ints juntos, como um 16-bit int limitando-se a de 0 a 99 para gerar 9,801 (<32768) quando quadrado, ou 32 bits int utilizando 0 a 9999 para gerar 99980001 (<2147483648)) que facilitou grandemente os algoritmos.

Alguns truques para estar atento.

1 / Ao adicionar ou multiplicar números, pré-alocar o espaço máximo necessário, em seguida reduzir mais tarde, se você achar que é demais. Por exemplo, a adição de dois 100- "dígitos" (onde dígitos é um int) números nunca vai dar-lhe mais de 101 dígitos. Multiplicar um número de 12 dígitos por um número de 3 dígitos nunca vai gerar mais de 15 dígitos (adicionar as contagens dígitos).

2 / Para a velocidade acrescentou, normalize (reduzir o armazenamento necessário para) os números apenas se for absolutamente necessário -. Minha biblioteca tinha isso como uma chamada separada para que o usuário pode escolher entre velocidade e armazenamento preocupações

3 / A adição de um número positivo e negativo é subtracção, e subtraindo um número negativo é o mesmo que a adição positiva equivalente. Você pode economizar um bocado de código por ter o add e métodos subtrair chamar uns aos outros depois de ajustar os sinais.

4 / Evite subtraindo grandes números de pequenos desde que invariavelmente acabam com números como: 

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

Em vez disso, subtrair 10 de 11, então negá-lo: 

11
10-
--
 1 (then negate to get -1).

Aqui estão os comentários (transformados em texto) a partir de uma das bibliotecas que eu tinha que fazer isso para. O código em si é, infelizmente, direitos autorais, mas você pode ser capaz de escolher a informação suficiente para lidar com as quatro operações básicas. Suponha na seguinte que -a e -b representar números negativos e a e b são zero ou números positivos.

Para além , se os sinais são diferentes, o uso subtração da negação: 

-a +  b becomes b - a
 a + -b becomes a - b

Para subtração , se os sinais são diferentes, o uso além da negação: 

 a - -b becomes   a + b
-a -  b becomes -(a + b)

Também tratamento especial para assegurar que estamos subtraindo um pequeno número de grandes: 

small - big becomes -(big - small)

Multiplicação usa matemática de nível de entrada da seguinte forma: 

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

A maneira pela qual isto é conseguido envolve extracção de cada um dos algarismos de 32 um de cada vez (para trás), em seguida, utilizando suplemento para calcular um valor para ser adicionado àresultar (inicialmente zero).

operações

ShiftLeft e ShiftRight são usados ??para rapidamente multiplicar ou dividir um LongInt pelo valor envoltório (10 para a matemática "real"). No exemplo acima, podemos adicionar 475 a zero 2 vezes (o último dígito de 32) para obter 950 (resultado = 0 + 950 = 950).

Em seguida, deixou turno 475 para obter 4750 e deslocamento para a direita 32 para obter 3. Adicionar 4750 a zero 3 vezes para obter 14250 em seguida, adicione a resultar de 950 para obter 15200.

desvio à esquerda 4750 para obter 47500, deslocamento para a direita 3 para obter 0. Uma vez que o direito deslocado 32 agora é zero, estamos acabados e, de fato 475 x 32 é igual a 15200.

Divisão também é complicado, mas com base em aritmética cedo (o método "gazinta" para "vai para"). Considere o seguinte divisão longa para 12345 / 27: 

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

Portanto 12345 / 27 é 457 com 6 restante. Verifique: 

  457 x 27 + 6
= 12339    + 6
= 12345

Esta é implementado usando uma variável draw-down (inicialmente zero) para derrubar os segmentos de 12345 um de cada vez até que seja maior ou igual a 27.

Em seguida, basta subtrair 27 a partir de que até chegarmos abaixo. 27 - o número de subtrações é o segmento adicionado à linha superior

Quando não há mais segmentos para trazer para baixo, temos o nosso resultado.

Tenha em mente estes são algoritmos bastante básico. Há muito melhores maneiras de fazer aritmética complexa se os seus números vão ser particularmente grande. Você pode olhar para algo como GNU Precision múltipla Aritmética Biblioteca -. É substancialmente melhor e mais rápido do que as minhas próprias bibliotecas

Ele tem o misfeature bastante infeliz em que ele vai simplesmente sair se ele é executado fora de memória (uma falha bastante fatal para uma biblioteca de uso geral, na minha opinião), mas, se você pode olhar passado que, é muito bom no que ele faz.

Se você não pode usá-lo para o licenciamento razões (ou porque você não quer que seu aplicativo simplesmente sair sem motivo aparente), você poderia pelo menos ter os algoritmos de lá para integrar em seu próprio código.

Eu também descobri que os bods mais em MPIR (um fork do GMP) são mais passíveis de discussões sobre possíveis mudanças - eles parecem um bando mais favorável ao desenvolvedor

.

Outras dicas

Enquanto re-inventar a roda é extremamente bom para a sua edificação pessoal e aprendizagem, é também uma tarefa extremamente grande. Eu não quero dissuadi-lo como seu um exercício importante e que eu fiz eu mesmo, mas você deve estar ciente que existem questões sutis e complexas no trabalho que o endereço pacotes maiores.

Por exemplo, multiplicação. Ingenuamente, você pode pensar do método 'estudante', ou seja, escrever o número um sobre o outro, em seguida, fazer a longo multiplicação como você aprendeu na escola. exemplo: 

      123
    x  34
    -----
      492
+    3690
---------
     4182

, mas este método é extremamente lenta (O (n ^ 2), sendo n o número de dígitos). Em vez disso, pacotes bignum modernos utilizam quer uma transformada discreta de Fourier ou uma transformada numérico para transformar este em uma junta essencialmente (n ln (n)) operação.

E este é apenas para números inteiros. Quando você entrar em funções mais complicadas em algum tipo de representação real do número (log, sqrt, exp, etc.) as coisas ficam ainda mais complicadas.

Se você gostaria de alguma fundamentação teórica, eu recomendo a leitura do primeiro capítulo do livro de Yap, "Problemas Fundamentais da Algorithmic Algebra" . Como já mencionado, a biblioteca gmp bignum é uma excelente biblioteca. Para números reais, eu usei mpfr e gostei.

Não reinvente a roda: ele pode vir a ser quadrado!

Use uma biblioteca de terceiros, tais como GNU MP , que é testada e comprovada.

Você faz isso basicamente da mesma maneira que você faz com lápis e papel ...

  • O número é para ser representada num tampão (matriz) capaz de assumir um tamanho arbitrário (o que significa que utilizando malloc e realloc) conforme necessário
  • você implementar aritmética básica, tanto quanto possível usando estruturas de linguagem suportada, e lidar com carrega e movendo o ponto de raiz manualmente
  • areas textos de análise numéricos para encontrar argumentos eficientes para lidar por função mais complexa
  • você só implementar, tanto quanto você precisa.

Normalmente você vai usar como unidade básica de computação

  • bytes contendo com 0-99 ou 0-255
  • palavras de 16 bits bônus contendo murchar 0-9999 ou 0--65.536
  • palavras de 32 bits contendo ...
  • ...

como ditado pela sua arquitetura.

A escolha da base binária ou decimal depende de você deseja para a máxima eficiência de espaço, a legibilidade humana, ea presença ou ausência de Binary Coded Decimal (BCD) apoio de matemática em seu chip.

Você pode fazê-lo com alto nível escolar de matemática. Embora algoritmos mais avançados são usados ??em realidade. Assim, por exemplo, para adicionar dois números de 1024 bytes: 

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}

resultado terá de ser maior por one place em caso de adição de cuidar de valores máximos. Olhada nisso: 

9
   +
9
----
18

TTMath é uma grande biblioteca se você quiser aprender. Ele é construído usando C ++. O exemplo acima era uma bobagem, mas isso é como adição e subtração é feito em geral!

Uma boa referência sobre o assunto é Computacional complexidade das operações matemáticas . Diz-lhe quanto espaço é necessário para cada operação que deseja implementar. Por exemplo, se você tem dois números N-digit, então você precisa 2N digits para armazenar o resultado da multiplicação.

As Mitch Dito isto, é, de longe, não é uma tarefa fácil de implementar! Eu recomendo que você dê uma olhada TTMath se você sabe C ++.

Uma das referências finais (IMHO) é de Knuth TAOCP Volume II. Ele explica muitos algoritmos para representar números e operações aritméticas sobre essas representações. 

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}

Assumindo que você deseja escrever um grande código inteiro mesmo, isso pode ser surpreendentemente simples, você fala como alguém que fez isso recentemente Aqui estão alguns dos truques que eu usei (embora em MATLAB.):

  • Eu armazenado cada dígito decimal indivíduo como um número de dois. Isso faz com que simples muitas operações, especialmente de saída. Enquanto isso não ocupam mais espaço de armazenamento do que você poderia desejar, a memória é barato aqui, e isso faz a multiplicação muito eficiente se você pode convolve um par de vetores de forma eficiente. Alternativamente, você pode armazenar vários dígitos decimais em um duplo, mas cuidado, então, que a convolução para fazer a multiplicação pode causar problemas numéricos em números muito grandes.

  • loja um sinal mordeu separadamente.

  • A adição de dois números é principalmente uma questão de adicionar os dígitos, em seguida, verificar se há um carry em cada etapa.

  • A multiplicação de um par de números é o melhor feito como convolução seguido por um passo de transporte, pelo menos, se você tem um código de convolução rápida na torneira.

  • Mesmo quando você armazenar os números como uma seqüência de dígitos decimais individuais, (ops também mod / REM) divisão pode ser feito para ganhar aproximadamente 13 dígitos decimais em um momento no resultado. Isso é muito mais eficiente do que uma divisão que funciona em apenas 1 dígito decimal de uma vez.

  • Para calcular uma potência inteira de um inteiro, calcular a representação binária do expoente. Em seguida, o uso repetido operações para calcular os poderes quadratura conforme necessário.

  • Muitas operações (factoring, testes de primalidade, etc.) beneficiarão de uma operação powermod. Ou seja, quando você calcular mod (a ^ p, N), reduzir o mod resultado N em cada etapa da exponenciação onde p tem sido expressa em uma forma binária. Não calcular a ^ p primeiro, e depois tentar reduzi-lo mod n.

Aqui está uma simples (ingênuo) exemplo que eu fiz em PHP.

Eu implementei "Adicionar" e "Multiply" e usou isso para um exemplo expoente.

http://adevsoft.com/simple-php -arbitrary de precisão-integer-big-num-example /

Código snip 

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top