Como dividir números grandes?

Question

Eu tenho um grande número (inteiro, sem sinal) armazenado em 2 variáveis ​​(como você pode ver, a parte alta e baixa do número):

unsigned long long int high;
unsigned long long int low;

Eu sei como adicionar ou subtrair alguma outra variável desse tipo.

Mas preciso dividir esse tipo de número.Como fazer isso?Eu sei, posso subtrair N vezes, mas, talvez, existam soluções melhores.;-)

Linguagem:C

Answer 1

Sim.Envolverá mudanças, e não recomendo fazer isso em C.Este é um daqueles raros exemplos em que o assembler ainda pode provar seu valor, fazendo com que as coisas funcionem facilmente centenas de vezes mais rápido (e não acho que esteja exagerando).

Não reivindico correção total, mas o seguinte deve ajudá-lo:

(1) Inicialize o resultado para zero.

(2) Desloque o divisor tantos bits quanto possível para a esquerda, sem deixar que ele se torne maior que o dividendo.

(3) Subtraia o divisor deslocado do dividendo e adicione um ao resultado.

(4) Agora desloque o divisor para a direita até que, mais uma vez, seja menor que o dividendo restante, e para cada deslocamento para a direita, o resultado do deslocamento para a esquerda em um bit.Volte para (3) a menos que a condição de parada seja satisfeita.(A condição de parada deve ser algo como "o divisor tornou-se zero", mas não tenho certeza disso.)

É realmente ótimo voltar a alguns problemas REAIS de programação :-)

Answer 2

Você já olhou para alguma biblioteca de grande número, como GNU MP BigNum?

Answer 3

Eu sei, posso subtrair N vezes, mas, talvez, existam soluções melhores.

Subtrair N vezes pode ser lento quando N é grande.

Melhor (ou seja,mais complicado, mas mais rápido) seria deslocar e subtrair, usando o algoritmo que você aprendeu a fazer divisão longa de números decimais no ensino fundamental.

[Também pode haver biblioteca de terceiros e/ou suporte específico do compilador para esses números.]

Answer 4

Hum.Suponho que se você tiver algum espaço em "alto", poderá aumentar tudo um dígito, dividir o alto pelo número e, em seguida, adicionar o restante ao dígito restante superior no baixo e dividir o baixo pelo número e, em seguida, mudar tudo de volta.

Answer 5

Aqui está outra biblioteca fazendo aritmética de 128 bits. GnuCash:Matemática128.

Answer 6

De acordo com meus comentaristas abaixo, minha resposta anterior foi estúpida.

Rapidamente, minha nova resposta seria que quando tentei fazer isso no passado, quase sempre envolvia mudança, porque é a única operação que pode ser aplicada em múltiplas "palavras", por assim dizer, e fazer com que pareça o mesmo. como se fosse uma palavra grande (com a exceção de ter que rastrear bits de transferência).

Existem algumas abordagens diferentes para isso, mas não conheço nenhuma direção geral melhor do que usar turnos, a menos que seu hardware tenha algumas operações especiais.

Answer 7

Você poderia implementar um algoritmo do tipo "BigInt" que faz divisões em matrizes de strings.Crie 1 array de strings para cada par alto e baixo e faça a divisão.Armazene o resultado em outra matriz de strings e converta novamente para um par inteiro alto e baixo.

Como a linguagem é C, o array provavelmente seria um array de caracteres.Considere-o análogo ao "array de strings" que mencionei acima.

Answer 8

Você pode fazer adição e subtração de objetos binários arbitrariamente grandes usando o loop do assembler e as instruções "adicionar/subtrair com transporte (adc/sbb)".Você pode implementar as outras operações usando-os.Nunca investiguei fazer nada além desses dois pessoalmente.

Answer 9

Se o seu processador (ou sua biblioteca C) tiver uma divisão rápida de 64 bits, você poderá dividir a divisão de 128 bits em pedaços (da mesma forma que faria uma divisão de 32 bits em processadores que tivessem divisões de 16 bits).

A propósito, existem vários truques que você pode usar se souber quais serão os valores típicos do dividendo e do divisor.Qual é a origem desses números?Se muitos dos seus casos puderem ser resolvidos rapidamente, pode ser bom que um caso ocasional demore muito tempo.

Além disso, se você puder encontrar casos em que uma resposta aproximada seja correta, isso abrirá a porta para muitas aproximações rápidas.