Eu estou tentando encontrar um algoritmo eficiente em Java para encontrar a parte decimal de repetição de dois números inteiros a
e b
onde a/b
.
por exemplo. 5/7 = 0,714258 714258 ....
Atualmente, só conheço o método de divisão longa.
algorithms
math
Jun Hao
fonte
fonte
Respostas:
Acredito que existem duas abordagens gerais aqui, você pode essencialmente "força bruta" procurar a sequência mais longa de repetição ou pode resolvê-la como um problema da teoria dos números.
Já faz muito tempo que não encontrei esse problema, mas um caso especial (1 / n) é o problema nº 26 no Projeto Euler, portanto, você poderá encontrar mais informações pesquisando soluções eficientes para esse nome específico. Uma pesquisa nos leva ao site de Eli Bendersky, onde ele explica sua solução . Aqui está um pouco da teoria da página Decimal Expansions da Mathworld :
Minha teoria dos números está um pouco enferrujada no momento, então o melhor que posso fazer é levá-lo nessa direção.
fonte
Deixe
n < d
, e você está tentando descobrir a parte que se repeten/d
. Letp
Ser o número de dígitos na parte de repetição: entãon/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...)
. A parte entre colchetes é uma série geométrica, igual a1/(10^p - 1)
.Então
n / d = R / (10^p - 1)
. Reorganize para obterR = n * (10^p - 1) / d
. Para encontrar R, faça um loopp
de 1 ao infinito e pare assim que ele sed
dividir uniformementen * (10^p - 1)
.Aqui está uma implementação em Python:
(
k
controla o comprimento da sequência repetida, para que você possa distinguir entre 1/9 e 1/99, por exemplo)Observe que essa implementação (ironicamente) faz um loop para sempre se a expansão decimal for finita, mas termina se for infinita! Você pode verificar esse caso, porém, porque
n/d
só terá uma representação decimal finita se todos os fatores primosd
que não são 2 ou 5 também estiverem presentesn
.fonte
0.123123... = 123/999
0.714258714258... = 714258/999999 (=5/7)
etc.Divisão longa? : /
Transforme o resultado em uma sequência e aplique esse algoritmo a ela. Use BigDecimal se sua sequência não for longa o suficiente com tipos comuns.
fonte