Divisão de números grandes
-
05-07-2019 - |
Pergunta
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?
Solução
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.
Outras dicas
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.
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?).
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.
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/