Divisão de números grandes

Question

Eu preciso de algum algoritmo de divisão que pode lidar com grandes números inteiros (128 bits). Eu já perguntei como fazê-lo através de operadores bit movediças. No entanto, minha implementação atual parece pedir uma melhor abordagem

Basicamente, eu armazenar números como dois long long unsigned int de no formato

A * 2 ^ 64 + B com B < 2 ^ 64.

Este número é divisível por 24 e quero dividi-lo por 24.

Minha abordagem atual é transformá-lo como

A * 2 ^ 64 + B     A             B
--------------  = ---- * 2^64 + ----
      24           24            24

           A               A mod 24                    B         B mod 24
= floor( ---- ) * 2^64 +  ---------- * 2^64 + floor( ---- ) +   ----------
           24               24.0                      24           24.0

No entanto, este é buggy.

(Note que piso é A / 24 e que mod é A % 24. As divisões normais são armazenados em long double, os inteiros são armazenados em long long unsigned int.

Desde 24 é igual a 11000 em binário, o segundo summand não deve mudar algo na faixa da quarta summand uma vez que é deslocada 64 bits para a esquerda.

Então, se A * 2 ^ 64 + B é divisível por 24, e B não é, ele mostra facilmente que erros desde que retorna algum número não-integral.

O que é o erro na minha implementação?

Answer 1

A maneira mais fácil que eu posso pensar de fazer isso é tratar os números de 128 bits como quatro números de 32 bits:

A_B_C_D = A*2^96 + B*2^64 + C*2^32 + D

E, em seguida, fazer uma longa divisão por 24:

E = A/24 (with remainder Q)
F = Q_B/24 (with remainder R)
G = R_C/24 (with remainder S)
H = S_D/24 (with remainder T)

Onde meios X_Y X*2^32 + Y. Então a resposta é E_F_G_H com T restante. A qualquer momento você só precisa de divisão de números de 64 bits, por isso deve ser factível com apenas operações inteiras.

Answer 2

isso poderia ser resolvido com a multiplicação inversa? A primeira coisa a notar é que 24 == 8 * 3 assim o resultado de

a / 24 == (a >> 3) / 3

Let x = (a >> 3) então o resultado da divisão é 8 * (x / 3). Agora ele continua a encontrar o valor de x / 3.

estados aritmética modular que existe um número n tal que n * 3 == 1 (mod 2^128). Isto dá:

x / 3 = (x * n) / (n * 3) = x * n

Ela continua a encontrar o n constante. Há uma explicação sobre como fazer isso em wikipedia . Você também vai ter que implementar a funcionalidade de multiplicar para números de 128 bits.

Espero que isso ajude.

/A.B.

Answer 3

Você não deveria estar usando long double para as suas "divisões normais", mas inteiros lá também. long double não tem algarismos significativos suficientes para obter a resposta certa (e mesmo assim a questão toda é fazer isso com operações inteiras, correto?).

Answer 4

Uma vez que 24 é igual a 11000 em binário, o segundo summand não deve mudar algo na faixa da quarta summand uma vez que é deslocada 64 bits para a esquerda.

A sua fórmula é escrito em números reais. (Um mod 24) / 24 pode ter um número arbitrário de casas decimais (1/24 é por exemplo 0,041666666 ...) e pode, portanto, interferir com o quarto termo na sua decomposição, mesmo uma vez multiplicada por 2 ^ 64.

A propriedade que Y * 2 ^ 64 não interfere com os elementos binários de peso inferior em uma adição só funciona quando Y é um número inteiro.

Answer 5

Do not.

Vai pegar uma biblioteca para fazer essas coisas -. Você vai ser incrivelmente grato que você escolheu ao depurar erros estranhos

Snippets.org tinha uma biblioteca C / C ++ BigInt nele site um tempo atrás, o Google também virou-se o seguinte: http://mattmccutchen.net/bigint/